Vol.23,No.2Feb.,2005
任务均分的多旅行商问题
卢厚清,王辉东,黄 杰,李 波
X
(解放军理工大学工程兵工程学院,江苏南京 210007)
摘 要:多旅行商问题是单旅行商问题的扩展,具有更广泛的实际意义。在研究MTSP解的特点的基础上,提出了最小化总行程和均分多个旅行商访问点数、最小化总行程及均分访问路程的两个多目标的MTSP问题,并分别给出了相应的数学模型、求解算法和应用实例,实例表明模型的正确性。关键词:MTSP;算法;多目标
中图分类号:O22 文献标识码:A
多旅行商回路(MTSP)是旅行商问题(TSP)的扩展。MTSP是指给出N个城市的集合,M个推销商从各自所在的城市出发,分别走一条旅行路线,使得每个城市有且仅有一个推销商走过,最后回到原来的出发城市,且总旅程最短。研究MTSP具有重要的现实意义,TSP是MTSP的一个特例(M=1),MTSP是TSP的一般形式。与TSP相比,如今企业管理中的更多的问题属于MTSP。MTSP又分为从同一中心城市出发的MTSP和从不同中心城市出发的MTSP。本文主要讨论了从同一中心城市出发的MTSP问题。目前,关于MTSP的研究较少,已有的研究主要集中在求解算法的设计上,尚未见到对MTSP解的特点及均分各旅行商均分访问顾客数和均分各旅行商访问路程的研究。
图1给出了一个20个城市(城市1为中心)的3个旅行商的MTSP问题。我们采用上面的变换方法将它变成单TSP问题。使用MTSP的遗传算法得到三条最短路线为L1为(1 10 1)、L2为(1 17 1)、L3为(1 13 16 14 3 12 4 19 8 2 18 5 9 7 20 15 11 6 1)。其中,L1选择最接近中心城市1的城市10,L2
择次接近中心城市1的城市17。路程L1的长度d(L1)=2d1,10,路程L2的长度d(L2)=2d1,17,这样两次使用了两个最接近中心城市,因而其总长度应该是较优的结果。
M个旅行商中,有M-1个旅行商仅访问了一个点,而由一个旅行商访问留下的所有点。这种情况不符合企业管理的实际。企业既然使用多个旅行商(车辆)来从事这项工作,一般不会让一个旅行商(车辆)去完成几倍于甚至几十倍于另一个旅行商(车辆)的工作;如果这样的话,便失去了使用多个旅行商问题的意义。因而平均分配各旅行商的任务是多旅行商问题的一个重要的具有实际意义研究领域。平均分配任务又可分为两种情况:一是平均分配M个旅行商的访问城市(点)数;二是平均分配M个旅行商的访问路径长度。
对于均分访问点数的MTSP,如果我们仅考虑平均分配访问点数这一个目标,则该问题变得十分简单,此时只要令每个点访问的点数为[N/M]或[N/M]+1即可。所以,均分访问点数的MTSP应是一个多目标规划问题,需要研究的既要使得访问的总路程最短,又要使得各旅行商访问点数得以尽量均衡分配。同样,均分访问路程的MTSP也是一个多目标规划问题,其目标分别为M个旅行商访问总路程最短及各旅行商访问路程尽量均衡分配。
1 一般MTSP解的特点与多目标MTSP
为了使用TSP的算法研究解决MTSP,可引入M-1个虚拟点,记为N+1,…,N+M-1。第i(1 X收稿日期:2004-11-15作者简介:卢厚清,解放军理工大学工程兵工程学院。20系 统 工 程 2005年 图1 MTSP解的特点的图示之一 2 均分访问顾客数的多旅行商问题 均分访问顾客数的MTSP问题实际上是一个多目标规划问题。目标函数有两个:一是M个旅行商所走的总路程最短;二是M个旅行商的访问点数之差最小化。若设Ni为第i个旅行商访问的顾客数。则均分访问顾客数的MTSP的目标函数为 目标函数1:min n n 比,故总行程 ∑∑d i=0j=0 nn ij xij越小则总目标函数也越小。另一 方面,总目标函数与最大访问点数与最小访问点数之差成单调上升关系,即{max(Ni)-min(Ni)}越大,则总目标函数越大,即{max(Ni)-min(Ni)}越小,则总目标函数越小。所以,总目标函数既能使总行程达到最小,同时也能达到平均分配M个旅行商的访问点数的目的。 使用上述变换将两个目标函数转换成一个目标函数后,采用上述MTSP的遗传算法便可得到均分访问顾客数的MTSP的近似最优解。图2给出了20个城市(坐标随机生成且城市1为中心)的4个旅行商的MTSP问题,使用上述MTSP的遗传算法得到的在均分访问点数量和最短访问路程两个目标下的四条路径。 ∑∑d i=0j=0 ij xij 目标函数2:min{max(Ni)-min(Ni)} 将目标函数1和目标函数2合成一个总目标函数为min:{max(Ni)-min(Ni)} n n n n ∑∑d i=0j=0 ij xij+ n ∑∑d i=0j=0n ij xij 这样,一方面,总目标函数与总行程 ∑∑ i=0j=0 dijxij成正 图2 最小化总路程和均分访问点数量的MTSP的解第2期 卢厚清,王辉东等:任务均分的多旅行商问题21 3均分行驶路程的多旅行商问题及其解法 对N个点M条回路的MTSP,当要求M条路径的行驶的路程尽量相等时,目标函数有两个,一是总路程最短,二是平均分配各旅行商的访问路程。若设Di为第i个旅行商访问的路程。则均分访问顾客数的MTSP的目标函数为: 目标函数1:min n n 一项则是总路径长度。k为调节总目标函数中两个组成部分之间比例的系数(k>0),一般取正整数。k取值较大时,总目标受总行程距离影响较大,所求得的结果总行程距离较小,但路径长度的差异较大,均分路程的效果不理想。当k较小时,均分M个旅行商的路径长度在目标函数中的影响较大。特别地,当k=∞时,即为均分路程的影响值为0;此时,影响总目标函数的仅为总行程一个因素。 将两个目标函数合成一个目标函数后,使用上述图3给MTSP的遗传算法便可得到MTSP的近似最优解。 出了12个城市(坐标随机生成且城市1为中心)的4个旅行商的MTSP问题,使用MTSP的遗传算法得到的在均分访问路径和最短访问路程双目标下的四条路径。 ∑∑d i=0j=0 ij xij 目标函数2:min{max(Di)-min(Di)} 将目标函数1和目标函数2合成一个总目标函数为{max(Di)-min(Di)}min kõmin(Di) n n n n ∑∑d i=0j=0 ij xij+ ∑∑d i=0j=0 ij xij 总目标函数中,前一项体现均分M个路径长度的效果,后 图3 最小化总路程和均分各旅行商访问路程的MTSP的解 4 结论 本文首先研究了MTSP解的特点,然后提出了最小化总行程和均分M个旅行商访问点数、最小化总行程和 均分M个旅行商访问路径的两个多目标MTSP问题,给出了相应的模型、求解的方法及应用实例。 参考文献: [1] 卢厚清,王宁生.信息成组与系统划分的一种方法[J].计算机软件与应用,2001,12(9):122～125. [2] BezdekJC,HathawayR.LocalconvergenceoffuzzyC-meansalgorithms[J].PathernRecognition,1986,19(16).[3] 陈守煜.工程模糊集理论与应用[M].北京:国防工业出版社,1998. DividingintoEqualTaskofMTSP LUHou-qing,WANGHui-dong,HUANGJie,LIBo (EngineeringInstitueofEngineeringCorps,PLAUniversitofScienceandTechnology,Nanjing210007,China)Abstract:ThepapergivesthecharacterofthesolutionofMTSP,putsforwardtheproblemsofdividingintoequallenghtofrouteanddividingintoequalofnumbersonMTSP,themodel,algorithmandtheexamplesoftheproblemsaregiven.Keywords:MTSP;Algorithm;Multi-objective 因篇幅问题不能全部显示，请点此查看更多更全内容