基于GA的MTSP问题实现

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

具有局部重复路径的多路旅行商问题的研究

首先对连通图上允许旅行商走回头路的 TSP的问题进行了研究 ,证明了问题解的存在性 ,给出了利用连通图的顶点间最短路径构造完全图的求解方法。然后 ,对连通图上允许路径部分重复的 MTSP问题进行了初步的研究 ;采取“分治”的方法并结合遗传算法 ,设计了求解路径部分重复的 MTSP问题的有效算法。讨论了关于求解多个旅行商完成任务的最短时间和最短路径的问题 ;并给出了在限定时间内完成任务的条件下 ,求最小分组 (人员配置 )的问题的方法。可重复路径的MTSP问题的研究 ,在现实中有很大的使用价值。诸如 :交通运输、管道铺设、路线的选择、计算机网络的拓扑设计、邮递员送信等 ,都可以抽象成 TSP或

巡检线路的排班问题研究

巡检线路排班优化问题可以节省人力资源,降低用人单位的劳动成本,减轻劳动者负担,从而增加收入,具有十分重要的现实意义。本文借鉴旅行商问题(MTSP),通过引入0-1变量,建立了巡检线路排班问题的优化模型,再利用Excel对数据进行处理和MATLAB辅助计算,最终得到每班需要的巡检人数以及巡检人员的巡检线路和巡检的时间安排表;针对问题二增加了休息时间和吃饭时间,在建立多目标MTSP问题模型基础上,通过加权处理,把多目标函数化为单目标函数,运用同样方法,得到每班需要的巡检人数以及巡检人员的巡检线路和巡检的时间表。针对问题三,通过对两种不同上班模式获得的数据进行分析、比较,最终得出错时上班并不比固定上班更省人力。

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

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

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

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

基于改进遗传算法的多无人机航路规划方法

在分析多无人侦察机任务需求、限制以及特性等要素基础上,建立了多无人机航路规划优化模型。以航程作为性能指标,将多无人机侦察多目标航路规划转化为多旅行商问题。通过对多旅行商问题特点分析,采用遗传算法基本思想,对编码和适应度函数以及操作算子进行合理设计,并改进了交叉和变异操作算子以取得更好优化结果。仿真结果表明所提算法的合理性和有效性。