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

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

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

权编码方法是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计算

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

中国邮递员问题50年

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

水灾地区邮递员问题

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

基于动态拓扑网络的混合中国邮递员问题

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

中国邮递员问题的整数规划模型

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

求解中国邮递员问题的一种思路

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

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

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

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

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

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

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

战争地区邮递员问题

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

中国邮递员问题的EXCEL求解

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

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

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

中国邮递员问题的匹配算法

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

遗传算法求解邮递员问题的探讨

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

基于中国邮递员问题的图书配送线路优化

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

关于中国邮递员问题研究和发展的历史回顾

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

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

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

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

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