（毕业论文 字数：3425页数：4）摘要：Modeling BGTP Problems and Solving them with 2-tier Genetic Algorithm
Abstract: Best Group Tour-path Problems (BGTP)is a basic problem in intellectual logistic planning. In this paper, a mathematics model for BGTP problems is presented ,and a new 2-tier parallel genetic algorithm (2tGA) for the problem is proposed. The 2tGA solves the BGTP problems by dividing it into two tiers. The outer tier solve the Set Partition Problems, and the inner one solves the Traveling Salesman Problems. The 2tGA makes some use of problem domain knowledge and therefore have better performace. The ideas of the 2tGA and the designs of chromosome and genetic operators are descripted. At last, we give the experimental results of the algorithm in solving the Question B of MCM in 1998. The results are better than the one we know.

Keyword: Intellectual Logistic Planning, the 2-tier Genetic Algorithm, The Set Partion Problem, Traveling Salesman Problem

目录

一、 引言
二、 最优分组周游路线问题的模型
三、 双层遗传算法
四、 测试结果分析
五、 总结、评价与进一步研究

一、 引言
最优分组周游路线问题是一类物流智能调度问题，是众多的计算难度极大的组合爆炸问题之一。自从运输问题最早是由Hitchcock在1941年提出的[2][4]后，人们对这一类问题给予了极大的关注并进行了大量的研究，提出了有效解决问题的优化算法——单纯形法的变形[2]。但由于问题规模的扩大，纯数学方法在允许的时间和空间上都很难找到问题的最优解，于是人们开始转向寻找问题的近似最优解，遗传算法以其在求解最优化问题中的独特的自组织性、自适应性很快进入人们的视野。 经典的遗传算法对于求解多目标的NP完全性问题非常有效，但对于有多个限制条件的多目标最优化问题缺显得有点力不从心，很难得到稳定度较高、收敛较快的解。本文提出的双层遗传算法模型给这一类问题提供了一个很好的解决方法，虽然建模条件限制了描述的问题的通用性，有待推广，但它能有效利用问题的领域知识，提高了求解效率，保证了解的可行性和最优性，算法思想极具推广潜力，可在其它物流智能调度问题求解算法设计中借鉴。
二、 最优分组周游路线问题的模型
最优分组周游路线问题可描述为：有一个出发点，它拥有提供某种服务的若干辆服务车。服务车将从出发点出发到割区内各个客户点提供上门服务，已知出发点以及各个客户点之间的路线及其长度、服务车的总数k（k≤m，m为客户点数）求出如何安排服务车使得行驶总里程最少。
在建立此题的数学模型时，我们可以这样假设：
1． 服务车可满足所有的所有客户的服务要求；
2． 客户点对服务时间无具体限制；
3． 服务车的油量充足，可以跑完它所要求的路线回到出发点；
4． 忽略所有致使道路堵塞的意外，不发生道路不通的情况；
从这道问题来看，可以利用运筹学的方法来解[3]。算法思路为：首先根据客户的地理位置划分成若干个区域，区域的个数等于所用的服务车数，然后对每个区域求出最短的哈密顿回路，每个区域的回路长度之和则为总的行驶里程。
用公式表示为：
其中n表示区域的个数，si表示第i个区域卡车所走的路程长度， 为最短的行驶里程。
可见，上述解法的关键是确定区域个数以及它的范围。由于区域个数与区域内的服务车走的路程的关系是非线性的，所以求出精确解的难度很大，即使花上相当多时间来对区域内的点进行调整的逐次改进法[3]也难以保证求出的解为最佳值。
下面我们就引入双层遗传算法，从计算的效率和精度来看，此算法不失为一个好的快速算法。
三、 双层遗传算法
双层遗传算法的特点是外层为内层提供具体条件和参数，内层返回给外层部分结果。此问题采用的双层遗传算法大致描述为：外层遗传算法产生客户划分方案，内层提供的各车辆服务客户的最短路线，将最短的路线长度返回给外层，以选择最优的客户划分方案。具体的算法介绍如下：
1、 外层遗传算法
服务车到哪些客户点的服务是集合划分问题，所以我们采用集合划分的编码方案，假设k辆服务车的编号为T1,T2,…，Tk，到客户点Ci的服务车的编号排列则可为该问题的染色体编码。此染色体的长度恒定，为客户点的总数m。
初始群体的T1，T2，…，Tk的排列可以随机生成，通过计算一条染色体编码不但可以确定用了所使用的服务车数，而且可得到每辆车的客户列表。
目标函数和适应度函数：
这种选择算子的优点是可确保适应度比平均适应度高的一些个体一定能遗传到下一代群体里，选择误差比较小。
交叉算子采用单点交叉方式，即在个体染色体基因串上随机产生一个交叉点，在该点相互交叉两个配对个体的部分染色体。该算法在破坏个体状态和降低个体适应度的可能性最小。
变异算子采用的是 范围内的均匀随机变异，思想是：逐个在染色体的基因上先随机产生一个概率，比较此概率是否小于变异概率，如果小于，则用在 范围内的一个不同与该基因位上的数替换该染色体基因上的数。
2、内层遗传算法
已知服务车所必须经过的客户点以及各个客户点之间的路线，问题是服务车应该按什么次序访问客户点再返回出发点使得卡车所走的线路总长最短。很明显，这是一个旅行商问题。
染色体编码方法，采用Grefensette等提出的一种新的巡回路线编码方法。假定对于一辆卡车的客户列表W，列表上有n个客户点，在各点服务顺序C为

规定服务车每在一个客户点服务后则在W中将此点删除，而第i（i＝1，2，…，n）个服务点在已经删除了之前访问的客户的列表W中对应的位置序号gi则(1≤gi≤n-i+1)代表了服务车具体的服务的客户点，以此类推，处理完W中的所有客户点，所有的gi全部排列在一起形成新表G：

则就是一条巡回路线，它即为一个内层遗传算法的染色体方案。初始群体的gi可在它的取值范围内随机生成。
目标函数和适应性函数：
设出发点的编号为0，客户点的编号为1，2，…，m，出发点以及客户点之间的最短距离为 ,i,j表示出发点或客户点的编号，服务车服务的顺序 ，因此目标函数为
这里的Gmax等于从出发点到服务车要求的客户点的最短距离之和的2倍。
选择、交叉算子均采用外层的选择、交叉算子。变异算子思想与外层变异算子思想相同，不同的是染色体基因位上随机数的取值范围，内层基因的变化范围是由该基因在染色体上的位置决定的，例如设染色体长度为n，第i个基因上的数在[1,n-i+1]内变化。
上述的双层算法的效率通过以下方法可以提高算法效率：
1）外层和内层初始群体可引入启发性信息。算法思想：先对客户点编号，使得相邻的客户点的编号相邻，具体的方法有以出发点为原点，按照角度或象限划分区域，区域中各个点的编号为相邻的数字。内层初始群体时可以在染色体基因里随机地设置随机长度的0串，增加适应性高的个体。
2）我们在进化群体的过程中采用了保留最佳个体的策略，如果前一代的最好的个体比当代的最好的个体还要好，则替换当前的最好的个体，否则替换当前最差的个体。这样，使得遗传算法能够以概率1找到最优解[1]
3）在交叉和变异算法里，我们增加了子代与父代的适应度比较，如果新产生的子代适应度比父代的适应度要低，则保留父代在下一代，否则替换父代遗传到下一代。
4）根据De Jong提出的几条重要结论[1]，我们可以增大群体规模，调整交叉、变异算子来提高算法的效率。
四、 测试结果分析
以1998年全国数学建模竞赛B题“最优灾情巡视路线”为例，要求如何在组数一定（3
组）的情况下，小组从县政府出发，走遍17个乡（镇）和35个村，使得总路线最短（乡、镇编号有改动，图略）。采用上述的遗传算法，我们可以得到以下三组线路总长度为578.2公里，而逐次改进法的最优值为600公里[3]