求解多旅行商问题的进化多目标优化和决策算法研究

扫码查看

原文链接

NETL

中文摘要：多旅行商问题作为经典的旅行商问题的一种扩展，通过附加一定的约束条件，可以模拟生活中的很多实际问题，例如物流规划、无人机巡检、任务调度等。多旅行商问题已经被证明属于NP-hard问题，精确的方法无法满足于大规模问题的求解需求，而启发式算法能够在较短的时间内得到质量较好的解，这使得研究人员对于此问题求解方法的关注更倾向于后者。对于多旅行商问题而言，增加的推销人员数量并不是为了减少总路程上的花费，而通常是用作平衡推销员之间的工作量或是减少为每个客户服务时间的举措。大部分已有文献在讨论该问题的时候都从两个方面出发，其一是通过减少总路程来使得总花费最小，其二是最小化推销员中的最长路线以平衡推销员之问的工作量。然而平衡工作负载和减少总路程的长度是两个相互冲突的目标，因此本文从多目标优化的角度对多旅行商问题进行分析和求解。 NSGA-Ⅱ是众多进化多目标优化算法中备受欢迎的一种，已经被应用到很多实际问题之中，并取得了较好的效果。本文基于NSGA-Ⅱ算法框架，通过对遗传算法中染色体、交叉算子以及变异算子的设计来求解多旅行商问题，以得到分布性较好、收敛性较强的Pareto前沿。考虑到现实生活中，多数优化问题在不同目标之间无明显权重和偏好关系，因此本文在NSGA-Ⅱ的基础上进一步融合了决策方法，提出了一种进化多目标决策算法，通过拐点引导进化过程，使得算法在整个程序运行完毕后直接能够输出一个比较令人满意的解。该方法避免了对于分布均匀的Pareto前沿的求解麻烦和决策者在而对大量Pareto前沿所产生的选择压力，使得整个求解过程无需决策者的参与，通过借助于已有的计算结果作为参考，对比证明了所提算法的可行性。

作者：

杨帅

展开 >

关键词：

多旅行商问题进化多目标优化启发式算法遗传算法

授予学位：

硕士

学科专业：

计算机科学与技术

导师：

张凯

学位年度：

2020

学位授予单位：

武汉科技大学

语种：

中文

中图分类号：