基于MTSP的机车运用分析与优化

不固定牵引区段机车交路极大地提高了机车运用效率,是机车运用工作的发展方向。基于多旅行商问题模型(MTSP)分析武汉局集团公司江岸机务段机车运用情况,并提出优化方案。武汉局集团公司地处全国铁路网中部和地理位置中心,是全国铁路的重要枢纽,也是华中地区综合交通体系的重要组成部分,对于疏解全路车流起到了至关重要的作用。通过结合江岸机务段不同机车交路,针对不固定机车交路牵引方式建立数学模型,在满足列车开行和机车整备约束的条件下,以机车使用台数最少为目标,给出目标函数的具体求解。最后,结合不同分界口机车交路的MTSP模型,给出武汉局集团公司机车运用优化建议,对其他地区的机车运用工作也具有一定指导意义。

基于Spark的双阶段SA及GA求解MTSP

针对总路径长度最小的单站点多旅行商问题,提出了基于Spark的模拟退火和遗传算法结合的两阶段KSAGA算法。在第一阶段,通过k-means聚类将多旅行商问题拆分为多个单旅行商问题,并使用模拟退火算法对组内城市的遍历次序进行优化。在第二阶段,通过遗传算法对城市的分组进行优化,并基于染色体分组编码方式设计了交叉、变异算子以及混合局部优化算子,以提高算法的搜索空间和收敛速度。随着城市数量的增加,计算规模变大,利用遗传算法的特性实现算法的并行,以加快算法运行效率。最后,通过选取TSPLIB的部分数据集进行仿真实验,将KSAGA与ACO、GA、SPKSA、ALNS和NSGA-Ⅱ的求解质量以及GA和NSGA-Ⅱ的收敛速度进行对比。研究结果表明:KSAGA在解决单站点多旅行商问题时能够快速收敛,并且相较于其他算法,求解质量得到了很大提升。同时,随着城市数量和旅行商数量增加,KSAGA的优势更为明显。

基于MTSP的机车周转图编制模型与算法

为了提高机车的工作效率,探讨了机车周转图编制模型与算法.对于给定的列车运行图,综合考虑机车使用台数最少和图形均衡性,提出了一种编制机车周转图的新算法.将机车周转图编制问题转化为多旅行商问题(MTSP)并建立数学模型,从而求得问题的最优解.最后,用列车运行图实际数据进行了验证,证明了该算法的有效性.

神经网络求解 MTSP 的应用研究

对多路旅行商问题（ＭＴＳＰ）根据出发城市的不同和返回情况分成了四个子问题，建立了各问题的神经网络计算能量函数和迭代公式，提出了智能化的优化方法，并用中国３１个直辖市、省会和自治区首府为例对ＭＴＳＰ进行了计算机模拟，说明了神经网络用于求解组合优化问题是十分有效的。

一种求解MTSP的遗传算法

提出了一种求解 MTSP 的遗传算法,首先通过引入虚拟点将 MTSP 转化成标准的 TSP,然后采用一种改进的遗传算法进行求解.计算机仿真结果表明了该算法的有效性.

途径节点不确定的MTSP路轨规划模型及其遗传算法研究

一般的路径规划问题假设道路网络是确定的,并且采用实时优化的方法建立优化路径,这种方法的结果不具有实用性。在高速发展的中国,道路网络实际上变化很快,而路网的电子地图往往无法实时更新;即使实时规划的路径本身是可行的,各配送点也会因为对新道路缺少经验而导致实际行驶时间大大超出预计,尤其对多个司机的情况。根据途径节点,考虑不同途径节点的不确定性,阶段性地产生稳定线路,是可行的方案。能够在路径成本和时间取得综合的平衡,多配送点工作量的相对均衡。利用MTSP问题的解决,提出了具有不确定途径节点的多目标路径规划模型,并且设计了随机遗传算法。仿真研究表明,该模型是有效的,该算法具有良好的求解性能。该成果有望集成在配送或运输决策支持系统中,为阶段性路径规划提供支持。

求解TSP和MTSP的混合遗传算法(英文)

许多应用涉及多推销员问题 (MTSP) ,已有许多启发式算法求解 TSP的最优或近似最优路线 ,但研究 MTSP的算法并不多 .结合启发式算法和遗传算法 ,设计了求解 TSP和 MTSP的混合遗传算法 。

基于GA的MTSP问题实现

多旅行商问题(Multiple Traveling Salesperson Problem,简称MTSP)是讨论m位旅行商如何访问n座城市,要求每个城市都被访问,且仅被访问一次,求得所有旅行商经过的路径和最小。本文通过对MTSP特点的分析,依据遗传算法的基本思想,对编码和遗传算子进行合理选取。通过仿真表明,该优化方法能够取得较优解。

基于MTSP的给水管网定线优化设计

为优化城市给水管网系统设计以减少工程投资、降低给水泵站扬程、保证供水运行安全、方便维护管理,基于MTSP优化理论,结合城市给水管网设计理论和实际工程中管道定线的要求,针对目前城市给水管网管道定线设计中存在的一些问题,提出了一种基于MTSP的管道定线优化设计方法,并尝试将MTSP基本方法应用于给水管网优化设计中。实例计算表明,该方法能够使管道定线总长度最短,从而达到优化设计的目的。

基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法

考虑了在二维欧式平面内的多旅行商问题,通过Delaunay三角剖分的方法,将问题转化为求解多个旅行商问题。树分解算法的核心是Delaunay边的空圆性质并且可以证明该算法的近似比为2。最后,通过数值模拟验证了算法的有效性。

连铸组中间包问题的MTSP模型及混合优化算法

针对连铸计划中的组中间包问题,建立了多旅行商问题(MTSP)模型,提出了一种结合启发式、k-opt邻域搜索和EDA进化的混合优化算法.该算法首先利用启发式规则确定虚拟炉次的个数,从而确定染色体编码长度,每个染色体代表一种中包组合方案,然后设计了基于概率矩阵模型的EDA进化算法对染色体进行全局寻优,并使用k-opt邻域搜索进行局部优化.EDA算法不需要设计如遗传算法(GA)那样的交叉算子,避免了交叉导致的编码非法性问题.通过对企业实际生产数据进行仿真计算,其结果表明了算法具有良好的优化性能和实用性.

基于混合算法的均衡路程MTSP研究

给出了MTSP的整数线性规划模型、分类,提出了均衡各旅行商访问路程和均衡各旅行商访问人数的多目标MTSP问题。针对均衡各旅行商访问路程的MTSP设计了相应的求解算法,求解算法为遗传算法和2-opt的混合算法。给出了相应的示例和实验结果,并对实验结果的有效性进行了研究。

MTSP的改进模拟退火算法及其求解

文章给出了一种改进模拟退火算法,继承了模拟退火算法在求解经典旅行商问题(TSP)上高精度、全局最优解的优点。同时通过引进综合目标函数,满足了求解多旅行商问题(MTSP)时总路径较短与其他多方因素相对均衡的双重要求。

求解加权MTSP问题的CUDA并行群智能方法

针对混合迭代算法执行时间长的问题,根据粒子群优化(PSO)算法和蚁群优化(ACO)算法的并行特点,结合其在GPU上并行化实现技术和编程优化技巧,提出一种基于CUDA的粒子群聚类蚁群的并行群智能混合方法GPSO-AC。该算法利用GPU的多个流处理器(SM)和单指令多线程(SIMT)的指令架构,将GPSO-AC算法在运行中的独立个体的搜索过程同时并行执行,在保证算法精度的基础上,加快混合迭代法的执行速度。考虑到实际场景中旅行商在每个路段上各项开销不同,可以抽象为每段路程区间上都有一个与之对应的代价,将路程代价考虑到MTSP问题中。采用TSPLIB库中6个测试数据集,将GPSO-AC与PSO-AC、TPHA、K-means-AC等算法进行比较,并进一步探讨了加入代价均衡约束后对加权MTSP问题最优解收敛性能的影响。使用chn31数据集上不同旅行商数时,GPSO-AC在不考虑代价均衡、代价均衡约束、加权代价均衡的情况下的代价标准差分别为1165.26、54.97、6.74。结果表明:在求解一般MTSP问题及其衍生加权、代价均衡MSTP问题上,GPSO-AC在执行速度和收敛精度上均优于CPU串行算法,且随着模型规模增加,其速度优势更加明显。

使用遗传算法解决MTSP问题的一种新的染色体设计

多旅行商问题(Multiple Traveling Salesperson Problem,简称MTSP)讨论的是如何安排m(>1)位旅行商访问n(>m)座城市,要求每个城市只允许被访问一次时,求解所有旅行商花费的费用和是最小(或最大)的问题。MTSP问题其实与单旅行商问题(Traveling Salesperson Problem,简称TSP)相似,但是由于添加了任何城市只要被某一旅行商访问到即可这个附加条件,因而增加了问题复杂度。在以前使用遗传算法(GA)研究解决MTSP问题时,通常采用标准的TSP染色体和处理方法。现为解决MTSP问题给出了一种新的染色体设计和相关的处理方法,并与以往的理论设计和计算性能进行比较。计算测试显示,新的方法能够获得较小的查找空间,在许多方面,新的方法产生的解空间更好。

基于混合遗传算法的MTSP问题研究

为了得到多旅行商问题的优化路线,提出一种基于实数编码的混合遗传算法。即先建立数学模型,将多旅行商问题转化为单旅行商问题,然后详细介绍了混合遗传算法设计过程,同时对该算法进行了收敛性分析与仿真试验。结果表明基于实数编码的混合遗传算法是一种有效的多旅行商问题求解方法,该算法能以较大的概率获得全局最优解。

基于双层规划的装备保障优化预调度

装备保障影响作战任务完成质量甚至直接关系任务成败,装备保障优化调度是提升装备保障系统效益的关键。针对装备保障系统双层决策和组合优化的特点,提出一种基于双层规划的装备保障优化预调度模型。分析装备保障系统运行过程和建模框架;结合组合优化问题,建立双层规划模型,上层为粗粒度层,采用MTSP(multiple travelling salesman problem)方法,下层为细粒度层,采用JSP(job-shop scheduling problem)方法;通过改进MTSP算法设计和迁移JSP算法描述构建双层迭代算法进行模型求解。算例分析表明:该方法在大规模系统优化调度中具有结构开放性和参数适应性。

路径交叉测绘任务规划问题

不同于传统多旅行商问题,小型飞机测绘任务规划问题的每个测绘目标需要测绘多个测绘载荷,同时多次测绘间要有时间间隔,称之为路径交叉的多旅行商路径规划问题。针对点目标测绘任务场景,将最少飞机数量的求解目标转化为求解最短航行路径。在采用遗传算法求解最短路径的基础上,结合探测载荷约束、探测任务时长约束等条件,进一步规划出最优的调度方案。针对点目标和区域目标测绘任务规划问题,考虑各机场测绘任务工作量的均衡,定义测绘工作量指标为每个机场完成的测绘目标点和目标道路的数目,求解调度策略和飞机数量。在此基础上求解均衡性,使3个机场探测的目标点和目标道路数量相当。结果表明,所提方案兼顾了测绘代价与任务分配的均衡性。

基于多旅行商问题模型解决工作量均衡的任务规划问题应用研究

针对常见的工作量均衡的任务规划问题,基于MTSP(多旅行商问题)模型,利用遗传算法,通过设置平均分隔点确保各保障组工作量均衡,构建3种适应度函数论证总路径长度和各保障组路径差的控制方法,比较2种选择方法确定遗传迭代过程,采取3种变异方式丰富种群多样性;最后利用Python语言编写程序,有效解决基于TSP(旅行商问题)、不同起点的MTSP、相同起点的MTSP模型的3类任务规划问题,具有较强的实践性和可操作性。

基于小生境遗传算法的MTSP问题求解

将生物学的小生境概念引入到基本遗传算法(GA)中,并对遗传操作作了改进,形成了小生境遗传算法,可应用于典型的组合优化问题——MTSP问题的求解,用共享度改变个体的适应值,同时加速淘汰适应值低的个体,提高每一代个体的平均适应值水平,以减少迭代的次数。给出的算例验证了算法的有效性。