摘要: 旅行商问题是计算机科学和运筹学中一个经典的组合优化问题，而多旅行商问题和分群旅行商问题是它的两个被广泛关注的推广变形。这两个问题在现实生活中具有广泛应用，例如车辆路径规划、生产制造流程优化、计算机操作、印刷机调度、校车调度等等。因... 展开 旅行商问题是计算机科学和运筹学中一个经典的组合优化问题，而多旅行商问题和分群旅行商问题是它的两个被广泛关注的推广变形。这两个问题在现实生活中具有广泛应用，例如车辆路径规划、生产制造流程优化、计算机操作、印刷机调度、校车调度等等。因此，对这两个问题及其它们的推广变形进行科学研究具有重要的理论意义和实际价值。 本文研究最小最大分群旅行商问题，它是多旅行商问题和分群旅行商问题的推广变形，其可以描述为：给定若干城市，它们分布在一个网络中。所有城市被划分成若干子集，每个子集称为一个群。给定若干旅行商，他们需要访问所有城市。问题的要求是，为每个旅行商设计一个环游，使得所有城市均能被访问且每个子集内的城市被连续访问。问题的目标是极小化权重最大环游的权重。本文从遗传算法的角度，对单仓库和多仓库最小最大分群旅行商问题展开了研究，其主要结果如下： 本文研究的第一个问题是单仓库最小最大分群旅行商问题。给定一个完全无向图G=(V,E)和m个旅行商，V={1,2,...n}是该无向图的顶点集，其中1为所有旅行商的公共出发顶点，{2,...,n}中每个顶点对应一个城市。顶点集V被划分成l个子集V1,V2,...,Vl，其中V1={1}。E是该无向图的边集，E中的每条边(i,j)关联一个非负实数dij，表示城市i与城市j之间的距离。给定一个子集E''(∈)E，定义E''的权重为该子集内所有边的权重之和。问题的要求是，为每个旅行商设计一个环游，使得每个环游的起点和终点均为公共出发顶点1，同时所有环游综合一起能够访问所有城市，且每个子集内的城市被连续访问。问题的目标是极小化权重最大环游的权重。针对该问题，设计了一个基于遗传算法的两阶段求解方法。具体地，在第一阶段，首先在每个子集中抽象出一个旅行商问题，然后应用求解旅行商问题的遗传算法，最终确定子集内顶点的访问顺序；在第二阶段，首先将每个子集视为一个整体，然后结合第一阶段的结果并综合应用贪婪与随机的思想，定义每两个子集之间的距离，进而抽象出一个多旅行商问题，并应用求解多旅行商问题的遗传算法，最终确定子集间的访问顺序。仿真实验结果表明，在小规模算例中，与Cplex软件求解得到的精确结果相比，本文算法求解得到的最好结果的相对误差不超过1.5%，但求解时间显著减少；在中等规模和大规模算例中，与文献中两个相关求解策略相比，本文算法也表现出了良好的求解性能。 本文研究的第二个问题是多仓库最小最大分群旅行商问题。与第一个问题相比，在该问题中，仓库的个数由1个增加至m个，即每个旅行商对应一个仓库。问题的要求是，为每个旅行商设计一个从它所在的仓库出发且最终回到该仓库的环游，使得所有城市均能被访问且每个子集内的城市被连续访问。问题的目标仍是极小化权重最大环游的权重。针对该问题，亦设计了一个基于遗传算法的两阶段求解方法。与第一个问题相比，在本求解方法的第二阶段，亦将每个子集视为一个整体，然后抽象出一个多旅行商问题。但在求解该多旅行商问题时，由于每个旅行商对应一个仓库，相同的子集分组，顺序不同对应的可行解也不同，故本阶段采用基于无序分组的遗传算法进行求解。仿真实验结果表明，在小规模算例中，与Cplex软件在限定时间内求解得到的结果相比，本文算法求解时间显著减少，同时求解精度更高；在中等规模和大规模算例中，与文献中两个相关求解策略相比，本文算法也表现出了良好的求解性能。 收起