求解最小比率旅行商问题的大洪水算法

盛虹平

(1.杭州师范大学 钱江学院,浙江 杭州 310012;2.上海理工大学 管理学院,上海 200093)

旅行商问题(Travelling Salesman Problem，简称TSP)是运筹学中一个经典的组合优化问题，有着明显的实际意义，已经证明是一个NP-Hard问题.其一般提法为：给定n个城市和每两个城市i,j之间的距离dij，某旅行商从一个城市出发，到其他城市去推销货物，要求每个城市仅被访问一次，最后回到出发城市，问该旅行商应如何选择行走路线，才能使总行程最短？当dij=dji时，问题被称为对称型TSP.从这种标准的TSP还可以延伸出许多扩展型TSP[1-2]，如瓶颈TSP、最小比率TSP、多人TSP、时间约束TSP、Prize-collecting TSP、多目标TSP、Hamilton路、车辆路径问题等.这里只讨论最小比率TSP(Minimum Ratio Travelling Salesman Problem，简称MRTSP)，它是在标准型基础上增加收益假定，即假定旅行商从城市i到达城市j会获得某种收益pij，问题变为要确定最佳行走路线，使得回路的总行程与总收益之比最小.问题目标类似于人们日常生活中经常使用的费用效益比，与单纯的总行程最短相比，往往更具实际意义.

MRTSP相比标准TSP，目标函数由线性变为非线性，使得问题的求解变得更为困难.文献中已尝试使用模拟退火算法[3]、蚁群算法[1]、元胞蚁群算法[4]、竞争决策算法[5]等启发式算法对此类扩展型TSP进行了求解.该文基于大洪水算法(Great Deluge Algorithm)寻优思想，给出一种采用两城市互换策略进行邻域搜索的大洪水算法，能快速求解对称型MRTSP，经过数据测试和验证，获得了较好的结果.

1 模型与算法

1.1 MRTSP数学模型

TSP在图论意义下常常被称为最小Hamilton圈问题(Minimum Hamiltonian Cycle Problem).此处用数学语言描述如下：

记G=(V,E)为给定的对称赋权完全图，V=(1,2,…,n)为顶点集，E为边集.已知距离矩阵

D=[dij]n×n，dij=dji,dii=∞,dij>0(i,j∈V)，收益矩阵P=[pij]n×n，pij=pji,pii=0,

pij>0(i,j∈V).

若设

则MRTSP数学模型可描述为：

其中|S|为集合S中所含图G的顶点个数.约束(1)和(2)表示每个顶点都只有一条边进和一条边出，约束(3)则保证没有任何子回路解的产生.因此，满足约束(1)～(3)的解构成了一条Hamilton回路[6-7].这里，dij=dji，pij=pji，(i,j∈V)，问题又称为对称型MRTSP.

1.2 大洪水算法基本思想

大洪水算法最早由G. Dueck于1993年提出[8]，是一类启发式优化算法，它通过模拟洪水上涨过程来进行全局寻优.该算法基本思想可以描述为：假想有一群山脉，高低不平，山脉的最高点有一艘救生艇，某个攀岩者处于山脉中的某处位置.假定这个攀岩者有特定的工具，他可以从山脉中任意一处到达另一处位置.这时，大洪水爆发了，奔涌而来的洪水没过山脚，迅速向上蔓延.为了求生，攀岩者必须不断向上寻求最高点.随着洪水的上涨逼近，攀岩者最终将到达山脉的最高点，成功登上救生艇得以逃生.对于极小化问题，可以将大洪水算法理解为大旱算法(Great Drought Algorithm)，即山脉变为大海，大旱使得海水持续蒸发，某海洋生物为了求生不断向低处寻找水资源.

基于目标极小化的大洪水算法核心步骤如下：

步骤1初始化：

count←迭代次数；it←1(迭代因子)；

up←海平面下降水位高度；

初始H0←满足问题条件的初始解，一般随机产生；

WaterLevel←Z(H0)(海平面高度)；

步骤2对H0进行邻域搜索，得到一个新的解H，计算对应的目标函数值Z(H)；如果Z(H)

步骤3it←it+1；若it

步骤4输出H0和Z(H0).

可见，大洪水算法和模拟退火算法(SA)有着相似的结构，区别仅是迭代中候选解的接受规则不一样.相对其他启发式算法，该算法最大优势在于只有唯一的一个参数up，而且还可以对这一参数动态赋值，大大减小了因参数设置不当造成的误差机率.

2 MRTSP大洪水算法

从以上分析可以看出，大洪水算法实施的关键在于邻域搜索的设计.对TSP而言，邻域搜索可理解为对当前回路实施某种变换来生成新的回路.常用的TSP邻域搜索策略包括相邻两城市互换、两城市互换、单城市移位、城市子排列移位、城市子排列反序和城市子排列反序并移位等[9].考虑MRTSP的目标函数特点和大洪水算法的高效性，笔者采取两城市互换策略，即对回路中任意两个点对应的城市i与j进行位置交换来生成新的回路.

下面用一个简单的例子[9]说明两城市互换策略的变换思想：

设编号1,2,…,10代表10个城市，H0,H1表示解状态，H0路径编码为：

H0←1 2 3 4 5 6 7 8 9 10

对编号为3和7的城市实施两城市互换策略，路径变为：

H1←1 2 7 4 5 6 3 8 9 10

下面给出具体求解MRTSP的大洪水算法，按伪码形式叙述如下：

Begin

初始化：

count←迭代次数；it←迭代因子；

构造初始路径H0(1到n的随机排列)；

route[ ]←H0路径编码；

计算初始回路H0的总路程DWeight和总收益TWeight；

Loop

Forit←1 tocountdo

Begin

Fori←1 tondortemp[i]←route[i]；

Repeat

xx←random(n)+1；yy←random(n)+1；

Untilxx≠yy；

交换rtemp[xx]与rtemp[yy]，生成新回路H′；

计算回路H′的总路程DWeight′和总收益TWeight′；

IfZ′

Begin

H0←H′；Z←Z′；

up←(WaterLevel-Z)/500；

Ifup<0.01 thenup←0.01；

WaterLevel←WaterLevel-up；

End

End

EndLoop

输出最好解H0和相应目标函数值Z；

End

该算法已用Delphi 7编程实现.不难看出，该算法的时间复杂度为O(n)，算法的运行效率非常之高.

3 算例测试

由于MRTSP缺乏有关实际数据，笔者采用随机生成的数值算例进行测试[3-5].实验所用的硬件环境为双核Intel CPU T2250，1.73GHz，2GB RAM，软件环境为Windows XP和Delphi 7.0，问题规模n∈[8,100]，dij,pij∈[1,1 000)，求解精度为5.大量计算表明，大洪水算法对MRTSP而言，也是一种行之有效的算法，而且算法的运行速度非常快，当规模n=100时，迭代10 000次，算法运行时间只需30 s左右.下面给出文献[3]中的算例和大洪水算法求解结果.

算例1设给定对称赋权完全图G=(V,E)，n=8，距离矩阵D和收益矩阵P如下：

运算大洪水算法，最好结果为有效迭代129次，最小比率Z=0.639 10，最优TSP回路H0={1,4,6,7,5,8,2,3,1}，总路程DWeight=255，总收益PWeight=399.

为进一步测试大洪水算法的性能，再选用文献[4]中的算例进行对比测试.

算例2设给定对称赋权完全图G=(V,E)，n=10，距离矩阵D和收益矩阵P如下：

对算法循环调用，可以方便地得到目标最小比率值的平均值和最佳值，算例2的求解结果见表1.

可见，大洪水算法也能求得最小比率值0.408 71，但都在迭代10 000次的情况下，大洪水算法最佳值出现的机率要比蚁群算法和元胞蚁群算法都好，而且在收敛速度上也更胜一筹.

表1 算例2计算结果与比较

4 结束语

目前对大洪水算法的研究还不多，相比其他算法，该算法思想简单，参数依赖度低.笔者将其用于连续型优化问题及大规模TSP等一系列组合优化问题的求解，都获得了令人满意的结果，而且表现出强鲁棒性、高收敛速度和高精度等优点.对该算法稍作修改，还可用于其他扩展型TSP的求解，算法的通用性和实用性也较强.可见，大洪水算法在优化领域中也不失为一种好的求解手段和工具，笔者将继续深入展开研究.

[1] 马良,项培军.蚂蚁算法在组合优化中的应用[J].管理科学学报,2001,4(2):32-37.

[2] 马良,宁爱兵.高级运筹学[M].北京:机械工业出版社,2008：91-93.

[3] 马良.求解最小比率TSP的一个算法[J].系统工程,1998,16(4):62-65.

[4] 朱刚,马良,姚俭.若干扩展TSP的元胞蚂蚁算法[J].系统管理学报.2007,16(5):492-496.

[5] 宁爱兵,马良.最小比率旅行商(MRTSP)问题竞争决策算法[J].计算机工程与应用,2005,41(11):30-32.

[6] Laport G. The travelling salesman problem: an overview of exact and approximate algorithms[J]. European Journal of Operational Research,1992,59(2):231-247.

[7] 马良.旅行推销员问题的算法综述[J].数学的实践与认识,2000,30(2):156-165.

[8] Dueck G. New optimization heuristics: the great deluge algorithm and the record-to-record travel[J]. Journal of Computational Physics,1993,104(1):86-92.

[9] 马良,朱刚,宁爱兵.蚁群优化算法[M].北京:科学出版社,2008:34.