Computer Engineering and Applications 计算机工程与应用2010，46（15）47
考虑工作量平衡的多旅行商问题及其求解
2
刘伟民1，，李苏剑1，郑爱云2，赵方庚3
2，LIU Wei-min 1，LI Su-jian 1，ZHENG Ai-yun 2，ZHAO Fang-geng 3
北京1000831. 北京科技大学机械工程学院物流工程系，
河北唐山0630092. 河北理工大学机械工程学院，
安徽蚌埠2330113. 汽车管理学院车管系，
1.Department of Logistics Engineering ，School of Mechanical Engineering ，University of Science and Technology Beijing ，Beijing
China 100083，
2.School of Mechanical Engineering ，Hebei Polytechnic University ，Tangshan ，Hebei 063009，China
Vehicle Management Institute ，Bengbu ，Anhui 233011，China 3.Department of Vehicle Management ，
E-mail ：lzh-tsh@163.com
LIU Wei-min ，LI Su-jian ，ZHENG Ai-yun ，et al.Multiple traveling salesmen problem with workload balance and its res －
（15）：olution.Computer Engineering and Applications ，2010，4647-50. （IACO ）algorithm for the MTSP is proposed.The optimized objective is that mini －Abstract ：An improved ant colony optimization
mizing the maximum tour length of each salesman which related with balancing the workload among salesmen.The minmax objec －
tive has more application meaning in practice.In the algorithm ，the pheromone trail updating and limits follow the MAX-MIN Ant
（MMAS ）scheme ，System and a hybrid local search procedure is designed to improve the performance of the algorithm.The pro －
（GA ）posed algorithm is tested using some benchmark instances in literatures and compared with three genetic algorithms .The ex －perimental results show that the proposed algorithm is competitive.
（MTSP ）Key words ：ant colony optimization ；local search ；Multiple Traveling Salesmen Problem
摘要：根据多旅行商问题（MTSP ）特点，针对最小化各旅行商最长路线这一优化目标，提出改进蚁群算法（IACO ）。最小化各旅行商最长路线考虑各旅行商的工作量平衡，更具实际应用意义。算法中信息素更新与限制遵循最大最小蚁群算法（MMAS ）框架，为提高算
法性能设计混合局域搜索算法。利用文献中标准算例进行检验，结果表明，所设计蚁群算法与三种遗传算法相比表现出较强竞争性。关键词：蚁群算法；局域搜索算法；多旅行商问题DOI ：10.3778/j.issn.1002-8331.2010.15.015
文章编号：（2010）1002－833115-0047-04
文献标识码：A
中图分类号：TP301.6
1引言
多旅行商问题MTSP （Multiple Traveling Salesmen Problem ）是旅行商问题TSP （Traveling Salesmen Problem ）的泛化形式。
由于要为m （m >1）名旅行商确定TSP 是著名的NP-hard 问题，
不包含子回路的汉密尔顿回路，MTSP 具有更高的计算复杂度。现实应用中，大量问题可以定义为MTSP ，如：报刊生产/配送问题[1-2]、热轧生产计划问题[3-4]、港口起重设备调度问题[5]等。因此，寻找MTSP 的优化解决方法、设计针对MTSP 的高性能优化算法具有重要现实意义。
一般的MTSP 可定义为：给定n 个城市，（n>m）；m 名旅行商
所有旅行商从某一设定为仓库节点的城市出发并最终返回该节点，使除仓库节点之外MTSP 需为所有旅行商确定回游路线，的所有城市，被且仅被访问一次，路线成本（可为距离、时间等）
根据仓库节点数目可分为单最低。MTSP 可扩展为多种形式，
仓库问题、多仓库问题[6]和开放式问题[7]，开放式问题的区别在
于旅行商可不返回仓库节点。如旅行商途中需拣取货物，MTSP 转化为MTSP 装卸问题[8]。如旅行商行程受时间限制，问题转化
8]
为带时间窗MTSP [5，。根据现实中应用的具体情况，MTSP 可为上述各种类型的组合。
许多研究者试图将MTSP 松弛为TSP 并用精确算法求解，但结果往往退化[9]，于是研究集中于启发式算法，主要包括：禁忌搜索算法[10]、邻域搜索算法[11]、神经网络[12]、同步广义爬山算法[13]等。近年来，遗传算法在许多优化领域广泛应用，成为MTSP 求解的最新研究热点。
自从第一个蚁群优化算法[14]（Ant Colony Optimization ，）ACO 成功应用于TSP 问题后，ACO 被大量应用于NP-hard 组合优化问题。但针对MTSP 的ACO 应用，见于公开出版文献的很少。目前为止，只有文献[15]针对旅行商有能力限制的MTSP 问
作者简介：刘伟民（1974－），男，博士研究生，讲师，主要研究领域为物流系统规划，物流系统优化，智能优化；李苏剑（1959－），男，博士，博士生导
师，教授，主要研究领域为企业物流管理，物流系统优化；郑爱云（1972-），女，讲师，主要研究领域为管理信息系统，机械优化设计；赵方收稿日期：2008-12-02
修回日期：2009-03-02
482010，46（15）Computer Engineering and Applications 计算机工程与应用
Σ胰胰胰胰胰胰
胰k ∈S 胰胰胰胰
题设计了基本蚁群算法。针对最小化各旅行商最长路线为优化目标的MTSP ，设计了改进蚁群优化算法（Improved ACO ，IA －），拓展了MTSP 的求解思路。最小化总路线为一般路径优CO
化问题常研究的优化目标，但在现实应用中，各路径的工作量平衡更为重要，因此该文重点考虑最小化各旅行商最长路线这一负载均衡优化目标。
）P （=ij t
）[τ（][ηij ]ij t
ik
α
，if j ∈S
αik
Σ[τ（t ）][η]
（4）
0otherwis e
根据该规则，当邻域中没有未被访问的城市时，算法以概率q （）选择最佳的下一城市，以概率（1-q 0）按式（4）的00≤q 0≤1这一过程直到所有城市被访问即概率分布随机选择下一城市。解构造完成为止。
2改进蚁群算法
蚁群算法是一种随机搜索迭代技术，启发于真实蚁群觅食
2.3信息素轨迹更新
行为。蚂蚁在寻找食物时，会在经过的路径上释放化学物质：信息素。随着时间推移，路径上信息素浓度会随过路蚂蚁的不断堆积和信息素自身的挥发而变化。这样蚂蚁通过选择信息素浓度高的路径而找到通向食物的较短路线，从而形成单个蚂蚁与蚁群间基于信息素的正反馈与自催化机制。在ACO 中，蚂蚁成为人工蚁，具有距离识别、路径记忆等特殊能力；解的构造通过基于数字信号形式的信息素的概率选择机制完成；当解的构造结束后，一些较好的解被用来更新信息素，以期在未来的解构造过程中对搜索过程进行扰动以获得更优解。
所设计IACO 算法中，信息素轨迹更新基本遵循最大最小
蚁群算法框架[17]：算法开始时每条路径上的信息素轨迹初始化为τmax ，迭代过程中信息素轨迹限制在区间[τmin ，τmax ]。τmax 和τmin 定义如下：
1τmax =1（f s ）τmin =τmax gb
）（5（6）
gb
其中ρ为信息素轨迹保持系数（1-ρ即为挥发系数）；（是f S ）全局最优解（S ）的路径长度；n 是所有城市的数目。
解的构造过程之后，信息素轨迹以全局最优解为基础更新，更新规则如下：
（t +1）（t ）τij =ρτij +Δτij
其中
gb 1，（，）if i j ∈s gb gb
Δτij =（f s ）
0，otherwis e
Σ胰胰胰胰胰胰胰
2.1定义MTSP 问题
为成功应用ACO 算法，必须把问题定义为算法易处理的形式，并且设计在解的构造和改进过程中易于利用且启发性较将MTSP 定义为带权无向好的启发式信息结构。不失一般性，
图G （V ，）。各城市由图上的顶点（vertex ）表示，用V j 标记，E j =…，各城市间的路径由图上的边（edge ）表示，用e i 标记，1，2，n 。
…，（e ）代表成本。MTSP 中，在图i =1，2，m 。ωi 边e i 上的权值，（V ，）上需定义m 个闭合回路C 1，…，G E C 2，C m ，V 0∈C i ，i=1，2，
…，（c ）则最小化各旅行商m ，V 0为仓库节点。ωi 为回路i 成本。最长路线MTSP 可定义为下述模型：
[16]
gb
（7）
（8）
Min
（C ）argmax[ωi ]
胰
（）（i =1，…，）v 0∈C 2，m i V 胰
胰
胰胰m 胰胰胰胰i =1
（1）（2）
公式（8）表明只有属于全局最优解的那些边才会得到加强。
为保持解搜索过程中的变化多样性，采用文献[17]中的重新初始化机制，即当经过规定次迭代后仍没有解的改进出现，信息素轨迹被强制重新初始化为τmax 。图1为针对MTSP 的IACO 算法流程图。
参数初始化non_improved=0
算法终止
是
达到最大迭代次数？否
每只蚂蚁每个旅行商应用改进最近邻算法
产生初始解初始化信息素按式（3）（4）随机构造路径
否
解改善?
是
按式（5）（6）限
制信息素否
应用混合局域搜索
是
Subject to
）（V ）=G胰C （i V
式（1）为最小化单个旅行商最长路线优化目标；限制条件（2）规定了单仓库节点及m 个汉密尔顿回路。
2.2状态转移规则
根据MTSP 特点，在初始解构造阶段，设计了一种改进最近邻算法：首先，每名旅行商随机选择某一城市作为初始节点；然后，各自从未访问城市列表中选择最近者作为下一节点；如果初始解构造完毕，该过程结束，否则继续访问最近节点。
在解的构造过程中，既用到了信息素又用到了启发式信息，启发式信息包括边长度和已构造解的邻接关系等；信息素即为各条边上的信息素轨迹。解的改进过程中，每只蚂蚁选择下一城市时按如下伪随机概率选择规则进行：
j =
按式（7）（8）全局更新信息素
信息素轨迹挥发
J otherwis e
其中τik （t ）为t 时刻城市i 与城市j 间的信息素轨迹值；（ηik =ηik ）为相对于城市i ，城市j 的能见度，α是能见度在概率选1/d ik
择因素中的相对重要性系数；S 为未访问城市的集合；q 为满足均匀分布的随机数，参数q 0为贪婪选择系数，q 0值越低进
J 定义：
≤
（t ）·argmax {[τik ][ηik ]}，if q ≤q 0
k ∈S
α
non_improved++non_improved=0
（3）
non_improved>=100?
是
信息素轨迹重新初始化
否
信息素轨迹在
[τmin ，τmax ]内? 信息素轨迹更新
图1针对MTSP 的改进蚁群算法流程图
2.4局域搜索能显著提高ACO 的性能[17]。论文设计算法是结合
刘伟民，李苏剑，郑爱云，等：考虑工作量平衡的多旅行商问题及其求解
了构造机制和局域搜索的混合ACO 算法，在每次迭代过程中，通过局域搜索允许所有邻域结构中得到最好解的一个蚂蚁改善解。在局域搜索过程中，用到三种启发式算子以改进解。其中包括两种路径间算子，同时改变几条路径：Relocation 、Exchange ；和一种路径内算子2-opt ，对单个路径进行操作。Relocation 算子将一条路径上的某一节点移出并插入到另一路径；Exchange
同时交换两条不同路径中的两个节点的位置。2-opt 算子试图通过将某一路径的两条不相邻的边用其它边替换来改进这条局域搜索算法是上述算子的组合，在搜索过程中，当路径路径。
内算子找到更好解时，该解被接受为最新当前解。此外，当前解从而进一步降低当前解的中改变的路径将由2-opt 过程优化，总成本。
MTSP100[19]MTSP51
算例名称
m 35103
MTSP100[18]
5
2010，46（15
）49
表1IACO 与GA 优化结果对照
GGA 均值[***********]7
GA2PC GGA-SS 均值203164123----[***********]-----[***********]448775
均值[***********][***********][***********][***********]25247
最优[***********][***********][***********][***********]65246
IACO 最差[***********][***********][***********][***********]25246
均值160118108
改进0.62%0.84%3.57%
8821-3.11%6980-2.26%63686356
0.03%0.05%
[***********]2035
----[***********]876-----
8817-3.22%6964-1.63%63636356
0.11%0.05%
2508-3.42%1847-4.88%[1**********]2
1.33%0.13%0.13%
3实验验证及结果分析3.1参数设置
该文设计的IACO 算法为C 语言编码，运行于Visual C++.net环境。运行平台Pentium M 1.5GHz （512MB RAM ）操作系PC ，统Windows XP 。一些基本参数设置如下：α=2，ρ=0.95，q 0=0.9，
当迭代次数达到1000次或者经蚂蚁数与旅行商个数m 相等。
多次迭代没有解的提高时迭代终止。为防止随机性和得到具有统计意义的结果，IACO 在每个算例上独立运行10次。
MTSP150
[18]
10203035
[***********]85-4.65%
9270-7.04%5968-1.58%52505246
0.04%0.02%
MTSP150
[19]
102030
3.2实验结果及分析
与典型TSP 不同，MTSP 没有开放的典型算例用于算法测
试。利用文献[18]和[19]中的算例验证所设计IACO 。这些算例为二维对称算例，算例中城市节点分别为51、欧氏距离、100和（包括仓库节点）。150
文献[18]和[19]分别对应用于MTSP 的遗传算法中染色体表示方法和相应遗传算子进行研究，文献[18]提出将城市分为应用分组遗传算法（Grouping Genetic Algorithm ，）求m 组，GGA 解；文献[19]提出两段式基因表示并设计相应遗传算法（Genetic ）。文献[20]对文Algorithm with Two-Part Chromosome ，GA2PC 献[18]的染色体表示方法进行了改进，并设计稳态分组遗传算法（Steady-State Grouping Genetic Algorithm ，，该算GGA-SS ）法相对文献[18]和[19]结果大大改善。
表1中列出该文设计IACO 算法与文献中遗传算法优化结果对比。从结果看出，IACO 算法性能明显优于文献[18]和
与文献[20]中的GGA-SS 相比，[19]中的遗传算法，IACO 在多数算例上较优，尤其对于旅行商数目多的算例效果更明显，对于其他算例，在实验中当增加蚂蚁数时，均能得到优于文献[20]所列结果，但随着蚂蚁数增加计算时间也会相应增加。从图2、表2中可以清楚看到IACO 针对最小化各旅行商最长路线这一优
化目标的线路平衡效果。表2中，最短总路线为各次独立运行所产生的各旅行商路线总和中的最小值；平均总路线为各次独立运行各旅行商路线总和平均值；旅行商线路长度差值=（单旅行商最大线路长度-单旅行商最小线路长度）/平均线路长度×100%
所设计的IACO 算法能够得到较优结果原因如下：首先，IACO 中既利用了启发式信息又利用了信息素，这些均可作为解构造过程中解质量的全局信息，因此有可能找到更好的解；其次，该文设计的局域搜索算法对解空间探索更深入，从而能素轨迹重新初始化和信息素轨迹区间限制，有效的防止可能由
注：改进=（（GGA-SS 均值-IACO 均值）））/GGA-SS均值×100%
图2MTSP51问题m =3、5、10线路图表2IACO 求解最小最大问题线路平衡效果
名称MTSP51
m 35103
MTSP100[18]
510203
MTSP100[19]
5102035
MTSP150
[18]
最短总路线
[***********][***********][***********][***********][***********]8329144561
平均总路线
476.10579.20976.3026320.0034476.5061309.10114628.4026275.8034351.7060485.80115568.407496.909061.1015300.1028931.3041381.1041532.9045873.9053711.40101289.00147958.00
旅行商线路长度差值
00.84%18.55%0.18%0.99%5.92%21.14%0.13%2.08%11.48%26.96%0.08%0.06%2.96%15.60%28.06%0.26%1.37%1.87%7.58%18.17%
10203035
MTSP150
[19]
102030
局域搜索带来的算法早熟收敛。
4针对最小化各旅行商最长路线MTSP ，提出改进蚁群算法：
502010，46（15）Computer Engineering and Applications 计算机工程与应用
[10]Ryan J L ，Bailey T G ，Moore J T ，et al.Reactive Tabu search in
unmanned aerial reconnaissance simulations[C]//Proceedingof the 1998Winter Simulation Conference ，1998：873-882.
Psaraftis H N.Cyclic transfer algorithms for mu －[11]Thompson P M ，
tivehicle routing and scheduling problems[J].OperationsResearch ，（5）：1993，41935-946.
[12]Somhom S ，Modares A ，Enkawa T.Competition -based neural net －
work for the multiple travelling salesmen problem with minmax objective[J].Computers&Operations Research ，1999，26：395-407. McLay L A ，Hall S N ，et al.Optimal search strate －[13]Jacobson S H ，
gies using simultaneous generalized hill climbing algorithms [J].Mathematical and Computer Modelling ，2006，43：1061-1073. [14]Dorigo M ，Gambardella L M.Ant colonies for the travelling sales －
man problem[J].BioSystems，1997，43：73-81.
[15]Pan J ，Wang D W.An ant colony optimization algorithm for mul －
tiple travelling salesman problem[C]//Proceedingsof the First In －ternational Conference on Innovative Computing ，Information and （ICICIC ’）Control 06.Washington ，DC ，USA ：IEEE Computer Society ，2006：210-213.
[16]Qu H ，Yi Z ，Tang H.A columnar competitive model for solving
multi-traveling salesman problem[J].Chaos，Solitons and Fractals ，2007，31：1009-1019.
[17]St ützle T ，Hoos H.MAX-MIN ant system[J].FutureGeneration Com －
（8）：puter Systems ，2000，16889-914.
[18]Brown E C ，Ragsdale C T ，Carter A E.A grouping genetic algo －
rithm for the multiple traveling salesperson problem[J].Internation－al Journal of Information Technology &Decision Making ，2007，6（2）：333-347.
[19]Carter A E ，Ragsdale C T.A new approach to solving the multi －
ple traveling salesperson problem using genetic algorithms[J].Eu－ropean Journal of Operational Research ，2006，175：246-257. [20]Alok S ，Anurag S B.A new grouping genetic algorithm approach to
the multiple traveling salesperson problem[J].SoftComput ，2009，13：95-101.
算法针对初始解构造设计了改进的最近邻算法；算法中信息素更新及限制遵循最大最小蚁群算法框架；算法结合了包含多种搜索算子的混合局域搜索算法，能够更充分地利用解空间信息，该算法与文献中的三提高了性能。通过来自文献的算例验证，种遗传算法相比有很强的竞争性。
参考文献：
[1]Buer M G V ，Woodru D L ，Olson R T.Solving the medium news －
paper production/distributionproblem[J].EuropeanJournal of Oper －ational Research ，1999，115：237-253.
[2]Carter A E ，Ragsdale C T.Scheduling pre-printed newspaper adver －
tising inserts using genetic algorithms[J].Omega，2002，30：415-421. 汪定伟. 热轧计划中的多旅行商问题及其计算方法[J].计算[3]黄可为，
（7）：机应用研究，2007，2443-46.
Liu J Y ，Ronga A Y ，et al.A multiple traveling sales －[4]Tang L X ，
man problem model for hot rolling schedule in Shanghai Baoshan Iron and Steel Complex[J].EuropeanJournal of Operational Research ，（2）：2000，124267-282.
[5]Kim K H ，Park Y M.A crane scheduling method for port container
terminals[J].EuropeanJournal of Operational Research ，2004，156：752-768.
Baker S F.The multiple depot ，multiple traveling sales －[6]Chan Y P ，
men facility-location problem ：Vehicle range ，service frequency ，and heuristic implementations[J].Mathematicaland Computer Modelling ，2005，41：1035-1053.
[7]Sariel S ，Balch T.Real time action based allocation of tasks for mul －
ti-robot exploration problem in dynamic environments[C]//the20th （AAAI-05），Pittsburgh ，National Conference on Artificial Intelligence Pennsylvania ，July 9-13，2005.
[8]Wang X B ，Regan A C.Local truckload pickup and delivery with
hard time window constraints[J].TransportationResearch Part B ，2002，36：97-112.
An overview of [9]Bektas T.The multiple traveling salesman problem ：
formulations and solution procedures[J].Omega，2006，34：209-219.
（上接17页）
这样得到的α，（5），因为：（U+V）β也能上述满足式U ′+V′=α+（H ID +YID ）（U ′+V′，）（α（U+V）（H ID +YID ），）。因此，αβ圳e P CA =e +αβP CA 只须证明α，（U ′+V′，）（α（U+V）（H ID +YID ），β能满足e P CA =e +αβ）即可。由于（U ′，是有效的签名，因此有e （W ′，P CA V ′，W ′）P ）=（U ′+V′+h′H ID +h′Y ID ，）。e P CA （α（U+V）（H ID +YID ），）e +αβP CA =（）（）H （））（），）e log W W （′U+V+logW W （′h -log W W ′U ′，V ′H ID +YID P CA =1m ，（log W W （（H ID +YID ）），）（h （），）=e ′U+V+hP CA e ′H ID +YID P CA （log W W ′W ，）（W ′，）e （U ′+V′，）e P e P P CA =（αW ，）（W ′，）e （U ′，）（U ′+V′，）e P e P P CA =e P CA
-1
-1
-1
-1
参考文献：
[1]Chaum D.Blind signature for untraceable payments[C]//Advancesin
Cryptology ：Crypto ’82.Berlin ，1982：199-203.
[2]Girault M.Self-certified public key[C]//LNCS434：Proceedings of Eu －
rocrypt ’91.Berlin ：Springer-Verlag ，1991：491-497.
Stern J ．Provably secure blind signature schemes[C]//[3]Pointcheval D ，
Advances in Cryptology-ASIACRYPT ’96.Berlin ：Springer ，1996：252-265.
[4]Zhang F G ，Kim K.Efficient ID -based blind signature and proxy
signature from bilinear pairings[C]//Advancesin ACISP 2003.Berlin ：Springer ，2003：312-323.
·[5]Chen X F ，Zhang F G ，Liu S L.ID based restrictive partially blind
signatures and applications[J].TheJournal of Systems and Software ，（2）：2007，80164-171.
[6]Shao Z H.Self-certified signature scheme from parings[J].TheJour －
（2）：nal of Systems and Software ，2007，80388-395.
[7]张学军. 高效的使用双线性对的自认证公钥签名[J].计算机应用，
（2）：2009，29355-356.
D ，LNCS 2248：Advances in Cryptology ，2001：514-532.
5结束语
结合盲签名和自认证公钥签名，使用双线性对，首次构造了一种高效的自认证公钥盲签名方案。分析表明，新方案不仅是安全的，由于仅使用了两个双线性对，因而其效率也非常高。重要的作用。