一种大规模稀疏中国邮递员问题快速求解方法

1

作者 唐继州 何丽莉 白洪涛 《吉林大学学报（理学版）》 CAS 北大核心 2024年第2期311-319,共9页

针对现有中国邮递员问题求解方法在大规模稀疏路网图上求解效率的瓶颈,提出一种在可接受时间范围内求得可行解的基于蚁群优化的快速求解方法.该方法针对Euler回路求解的奇偶点图上作业法的第二阶段,采用蚁群算法进行求解,同时根据大规... 针对现有中国邮递员问题求解方法在大规模稀疏路网图上求解效率的瓶颈,提出一种在可接受时间范围内求得可行解的基于蚁群优化的快速求解方法.该方法针对Euler回路求解的奇偶点图上作业法的第二阶段,采用蚁群算法进行求解,同时根据大规模稀疏路网图的特性基于密度峰值聚类算法对方法进行改进:首先在蚁群算法求解前对大规模稀疏路网图进行聚类分割;其次根据邻近节点覆盖率对分割后的节点群进行合并;最后通过改变部分节点所属聚类使各节点群内部节点个数均为偶数.实验结果表明:在奇偶点图上作业法所能支持的节点规模下,该方法可求得与确定性算法相同的最优解,并在运算时间上达到约10倍的效率优化;且该方法在大规模稀疏路网图下可有效提高计算效率,并在可控时间范围内得到优化的可行解,针对5000个节点规模的路网图最快可在60 s内完成求解. 展开更多

关键词 中国邮递员问题 蚁群优化 密度峰值聚类 EULER图

下载PDF 职称材料

基于一种新的边权编码方案的中国邮递员问题的DNA计算模型 被引量：7

2

作者 韩爱丽 朱大铭 《计算机研究与发展》 EI CSCD 北大核心 2007年第6期1053-1062,共10页

权编码方法是DNA计算中一个重要且有挑战性的问题.设计了一种新的用于表示赋权图中边权的DNA编码方案,给出了用该方案求解中国邮递员问题的DNA算法,并利用Markov链分析了DNA算法中生成各种路径的随机过程.对于任一赋权图G=(V,E),首先通... 权编码方法是DNA计算中一个重要且有挑战性的问题.设计了一种新的用于表示赋权图中边权的DNA编码方案,给出了用该方案求解中国邮递员问题的DNA算法,并利用Markov链分析了DNA算法中生成各种路径的随机过程.对于任一赋权图G=(V,E),首先通过边到点映射把它转换为广义边图G′=(V′,E′).图G的每条边ei被分别映射为图G′的一个顶点v′i.若G中ei与ej邻接,则连接G′中v′i和v′j.若G中vi为奇顶点,则在与vi关联的边对应的G′的顶点上添加自环.用于编码顶点v′i的DNA串si的长度等于边ei的权值.用于编码边v′iv′j的DNA串sij为si的后半部分与sj的前半部分并置后的逆补.所提出的DNA编码方案具有易于编码、易于推广且错误率低的特点.该工作可提高DNA计算中表示和处理数值的能力,扩展DNA计算求解最优化问题的范围. 展开更多

关键词 DNA计算 权编码方法 算法 组合优化 广义边图 中国邮递员问题

下载PDF 职称材料

中国邮递员问题的DNA计算 被引量：7

3

作者 李玮 王雷 《计算机应用》 CSCD 北大核心 2009年第7期1880-1883,共4页

提出了"虚拟权值"和"虚拟节点"的概念,给出了中国邮递员问题的一种基于DNA计算的求解算法。新算法首先利用多聚酶链式反应技术来排除非解,从而得到中国邮递员问题的所有可行解;然后,结合基于表面的DNA计算方法与荧... 提出了"虚拟权值"和"虚拟节点"的概念,给出了中国邮递员问题的一种基于DNA计算的求解算法。新算法首先利用多聚酶链式反应技术来排除非解,从而得到中国邮递员问题的所有可行解;然后,结合基于表面的DNA计算方法与荧光标记等技术,最终从所有可行解中析出最优解。算法分析表明,新算法具有易于解读、编码简单等特点。 展开更多

关键词 DNA计算 中国邮递员问题 多聚酶链式反应 NP完全问题

下载PDF 职称材料

中国邮递员问题50年 被引量：5

4

作者 高敬振 高勃 《运筹学学报》 CSCD 北大核心 2013年第1期17-28,共12页

首先介绍一般邮递员问题,涉及费用、服务侧、衔接费用、次序等要素.然后简要综述过去50年来中国邮递员问题、有向图上中国邮递员问题、带风向的邮递员问题、混合图上邮递员问题以及乡村邮递员问题等一般邮递员问题的特殊情况的研究进展... 首先介绍一般邮递员问题,涉及费用、服务侧、衔接费用、次序等要素.然后简要综述过去50年来中国邮递员问题、有向图上中国邮递员问题、带风向的邮递员问题、混合图上邮递员问题以及乡村邮递员问题等一般邮递员问题的特殊情况的研究进展,突出问题的线性规划描述及相应的组合多面体结构,着重讨论问题的模型、精确算法及其时间复杂度、NP-困难情形下的近似算法及其性能比. 展开更多

关键词 中国邮递员问题 算法 计算时间复杂度 性能比

下载PDF 职称材料

水灾地区邮递员问题 被引量：4

5

作者 汤泽滢 谢政 《应用数学与计算数学学报》 2000年第1期25-30,共6页

本文首次提出了中国邮递员问题的推广问题－水灾地区邮递员问题，并对解的存在性给出了一系列的充分条件、必要条件及充要条件。

关键词 灾邮路线 欧拉图 奇点 水灾地区 邮递员问题 多项式算法

下载PDF 职称材料

基于动态拓扑网络的混合中国邮递员问题 被引量：1

6

作者 马宇红 田贵龙 李宪 《西北师范大学学报（自然科学版）》 CAS 北大核心 2015年第1期17-23,共7页

研究网络拓扑依概率动态变化的中国邮递员问题,这里的道路网络是一个混合图,连边分为服务边和行走边两类,并且邮递员受负载能力和工作时间约束.首先,根据网络的结构和邮递员问题的本质建立了恰当的数学模型;其次,给出了网络拓扑结构依... 研究网络拓扑依概率动态变化的中国邮递员问题,这里的道路网络是一个混合图,连边分为服务边和行走边两类,并且邮递员受负载能力和工作时间约束.首先,根据网络的结构和邮递员问题的本质建立了恰当的数学模型;其次,给出了网络拓扑结构依概率动态变化的具体算法;第三,基于优先权的染色体编码方法,以及结合优先权和"边走边服务"策略的染色体解码方案,建立了中国邮递员问题的遗传算法;最后,仿真求解了一个小规模的动态中国邮递员问题,验证了算法的可行性和有效性. 展开更多

关键词 中国邮递员问题 混合网络 动态拓扑 遗传算法

下载PDF 职称材料

中国邮递员问题的整数规划模型 被引量：5

7

作者 冯俊文 《系统管理学报》 CSSCI 北大核心 2010年第6期684-688,共5页

基于无向图的传统中国邮递员问题,给出了相应的显式整数规划模型,应用整数规划软件包求解可以方便地确定相应问题的最优投递路线,进一步地,讨论了一类基于有向图的广义中国邮递员问题,给出了相应的显式整数规划模型;并研究了随机中国邮... 基于无向图的传统中国邮递员问题,给出了相应的显式整数规划模型,应用整数规划软件包求解可以方便地确定相应问题的最优投递路线,进一步地,讨论了一类基于有向图的广义中国邮递员问题,给出了相应的显式整数规划模型;并研究了随机中国邮递员问题,建立了相应的确定型等价模型。举例说明了各种模型的有效性。最后,讨论了中国邮递员问题的可能推广及其建模问题。 展开更多

关键词 中国邮递员问题 整数规划 最优化模型 赋权图

下载PDF 职称材料

求解中国邮递员问题的一种思路 被引量：3

8

作者 吴杰 《科技资讯》 2007年第14期211-,共1页

对于中国邮递员问题,可以利用奇度数结点的配对来进行求解。本文根据此思想给出了一种新的求解思路——通过去掉原始图中的偶度数结点并利用最小生成树来确定奇度数结点的配对。

关键词 中国邮递员问题 奇度数结点 配对 最小生成树

下载PDF 职称材料

基于中国邮递员问题的城区烟草配送线路优化模型与算法 被引量：2

9

作者 胡安源 张新 《物流工程与管理》 2016年第5期145-149,226,共6页

文中利用中国邮递员问题研究城区烟草配送问题,首先分析城区烟草配送的特点,提出多人中国邮递员问题。然后给出最优匹配模型和生成城区烟草配送的欧拉图的方法,设计欧拉环游的有向回路分割算法。最后给出算例,通过计算说明算法的可行性。

关键词 烟草配送 中国邮递员问题 欧拉环游

下载PDF 职称材料

混合中国邮递员问题的扰动恢复讨论及其一种启发式算法 被引量：1

10

作者 覃太贵 杨磊 《湖北师范学院学报（自然科学版）》 2005年第2期29-33,共5页

提出一种决策支持系统下的混合中国邮递员问题扰动恢复问题,在分析给定实例的基础上以及给定的假设下,对各种扰动进行数学描述,给出了问题的数学模型,讨论并构造了问题受扰动后的解。

关键词 实时决策支持系统 混合中国邮递员问题 线性规划 启发式算法

下载PDF 职称材料

中国邮递员问题奇偶点图上作业法最优标准的商榷 被引量：3

11

作者 王邦兆 陈永清 +1 位作者 王海军 魏志祥 《价值工程》 2018年第36期258-259,共2页

论文讨论了关于中国邮递员问题的一种误解,分析了产生误解的原因,提出了解决中国邮递员问题的指派问题模型。

关键词 中国邮递员问题 奇偶点图上作业法 指派问题

下载PDF 职称材料

战争地区邮递员问题

12

作者 汤泽滢 卢汉清 《应用数学与计算数学学报》 2002年第1期85-89,共5页

本文首次提出了赋权有向图上中国邮递员问题的一个推广-战争地区邮递员问题,并对解的存在性给出了若干充分条件和必要条件,得到了求解该问题的一个多项式算法.

关键词 战争地区 邮递员问题 有向战邮路线 有向欧拉图 非平衡点

下载PDF 职称材料

中国邮递员问题的EXCEL求解 被引量：1

13

作者 邱家学 《中小企业管理与科技》 2010年第6期216-216,共1页

借助EXCEL规划求解的功能完成了中国邮递员问题的求解,实现的方法原理简单、操作方便、快捷易行、结果可靠、扩展性强。

关键词 EXCEL 规划求解 中国邮递员问题

下载PDF 职称材料

中国邮递员问题的研究与发展

14

作者 杨静 殷志祥 邹德杰 《科技信息》 2012年第32期I0014-I0014,I0016,共2页

中国邮递员问题是图论中的NP-困难问题,仍没有有效算法。本文仅对目前几种算法进行分析比较。

关键词 中国邮递员问题 DNA计算 动态规划

下载PDF 职称材料

中国邮递员问题的匹配算法 被引量：4

15

作者 汪海森 林耿 卓彩娥 《长江大学学报（自科版）（上旬）》 CAS 2013年第9期10-11,共2页

中国邮递员问题是运筹学中一个重要问题。提出了一种求解中国邮递员问题的匹配算法。该算法利用贪心方法对奇度顶点进行配对;然后,将配对的边加入原图得到一个欧拉图;所得欧拉图的欧拉回路为近似的投递路线。仿真试验表明,该算法是有效的。

关键词 中国邮递员问题 匹配算法 欧拉图 贪心方法

下载PDF 职称材料

遗传算法求解邮递员问题的探讨 被引量：3

16

作者 曹鱼 陈传波 《计算机与数字工程》 2000年第3期28-30,共3页

邮递员问题是目前一个尚未完全解决的图论问题,而遗传算法则是一个比较好的全局搜索算法,本文提出了一种变换方法,以此为基础,用遗传算法实现了对有向图邮递员问题的求解,较传统方法更加容易实现,在求解大规模复杂网络时,其效率更高。

关键词 有向图 邮递员问题 遗传算法 适应度函数 图论

下载PDF 职称材料

基于中国邮递员问题的图书配送线路优化 被引量：2

17

作者 张敏 《物流技术》 北大核心 2012年第12期320-322,共3页

针对图书配送线路的优化问题,以图书配送总路程最低为目标,在充分考虑中国邮递员问题基础上,建立了图书配送线路优化模型。通过该模型可以得到图书配送的总路程和配送路线。最后,基于Excel软件,通过一个实例验证了所提出模型的有效性。

关键词 中国邮递员问题 线路规划 图书配送

下载PDF 职称材料

关于中国邮递员问题研究和发展的历史回顾 被引量：15

18

作者 管梅谷 《运筹学学报》 CSCD 北大核心 2015年第3期1-7,共7页

中国邮递员问题是运筹学研究的基本问题之一.回顾了中国邮递员问题提出和解决的历史,同时,介绍了对此问题研究的发展概况.

关键词 最短路问题 图上作业法 中国邮递员问题

下载PDF 职称材料

基于Shiny与Leaflet技术的中国邮递员问题网页设计与开发 被引量：1

19

作者 亓玉潇 张昆 《软件导刊》 2021年第11期118-121,共4页

路径优化问题存在于日常生活中的诸多领域,但方便实用的路径优化软件却不多见。中国邮递员问题是一个典型的路径优化问题,要求找出一条经过所有服务边至少一次,且回到起点的最短路径。基于Shiny开发一个求解中国邮递员问题的网页应用程... 路径优化问题存在于日常生活中的诸多领域,但方便实用的路径优化软件却不多见。中国邮递员问题是一个典型的路径优化问题,要求找出一条经过所有服务边至少一次,且回到起点的最短路径。基于Shiny开发一个求解中国邮递员问题的网页应用程序CPPSolver,其采用整数规划模型寻找奇点之间的最优匹配,添加重复边构建欧拉图,然后采用Fleury算法求解欧拉回路,即中国邮递员问题的解。针对结果路径的重叠问题提出路径分解算法,将重叠路径分解为若干段,避免了路径导航的二义性。此外,CPPSolver程序采用Leaflet工具包实现了地图的可视化与交互性。 展开更多

关键词 中国邮递员问题 整数规划 路径优化 Shiny LEAFLET 路径分解算法

下载PDF 职称材料

求解中国邮递员问题的圈生成算法

20

作者 崔允汀 何胜学 《建模与仿真》 2022年第1期202-213,共12页

中国邮递员问题是运筹学与计算机应用邻域的一个重要的基础问题,有着广泛的现实应用。针对有向图上的中国邮递员问题,给出了一种全新的可以直接求解最终回路的非线性整数规划模型,同时提出了一种具有多项式时间计算复杂度的精确求解算... 中国邮递员问题是运筹学与计算机应用邻域的一个重要的基础问题,有着广泛的现实应用。针对有向图上的中国邮递员问题,给出了一种全新的可以直接求解最终回路的非线性整数规划模型,同时提出了一种具有多项式时间计算复杂度的精确求解算法。首先,通过计算所有弧段间的最短路径,得到一个以路径非服务时间为非对角线元素的费用矩阵;接着,将所有弧段构成的集合同时视为一个特殊指派问题的代理与任务集合,并基于前面获得的费用矩阵得到一个指派问题;然后,通过求解上述指派问题,得到遍历网络所有弧段的圈集合;最后,通过搜索圈与圈之间的共用节点,将所有圈合并为一个大圈,从而得到邮递员的最终服务路线。通过理论证明和算例分析,证实了算法的收敛性和多项式时间的计算复杂性。最后对如何处理混合图上的中国邮递员问题进行了讨论,给出了具体求解思路。 展开更多

关键词 中国邮递员问题 指派问题 图论 多项式时间 弧路径问题

下载PDF 职称材料