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

发布时间：2024-04-21 00:45

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

【文章页数】：66 页

【学位级别】：硕士

【部分图文】：

图3.9eil51-3实例交叉对比和berlin52-3实例交叉对比

武汉科技大学硕士学位论文24代次数设置为1400，而eil76和rat99两个实例的迭代次数则设置为1800，实验结果如下，其中横坐标轴均表示总路程（距离），纵坐标轴均表示平衡度（平衡度的衡量标准是推销员中最长行程与最短行程的差），此两个标准的数学公式已经在第二章给出，在此不做赘....

图3.10eil76-3实例交叉对比和rat99-3实例交叉对比

武汉科技大学硕士学位论文24代次数设置为1400，而eil76和rat99两个实例的迭代次数则设置为1800，实验结果如下，其中横坐标轴均表示总路程（距离），纵坐标轴均表示平衡度（平衡度的衡量标准是推销员中最长行程与最短行程的差），此两个标准的数学公式已经在第二章给出，在此不做赘....

图3.11rat99-3在平衡度200以内的结果对比

武汉科技大学硕士学位论文25图3.11rat99-3在平衡度200以内的结果对比综上4个实例的对比测试，在保证算法中其他变量相同的情况下，以同样的迭代次数不同的交叉方法进行对比试验，结果表明SNX都有着较好的效果，具体表现在良好的收敛性和多样性上面，上述测试实例中SNX相对于PM....

图3.14eil51-5实例和berlin52-5实例

武汉科技大学硕士学位论文2612345678937第一部分第二部分12765438926反转顺序重新产生00图3.12变异方式112345678937第一部分第二部分34512678926重新生成12312300图3.13变异方式2同样的，对于eil51实例和berlin52实例....

本文编号：3960165