配送收集旅行商问题的改进算法
配送收集旅行商问题的改进算法
杨贺宏
（中南大学 数学科学与计算技术学院 长沙 410083）
【摘要】 针对配送收集旅行商问题的模拟退火算法，本文提出一种改进算法—渐升温回火退火算法。通过对三种规模的配送收集旅行商问题的仿真实验，表明该算法有效的提高了优化的效率。
关键词：配送\收集；旅行商问题；模拟退火算法；渐升温回火退火算法；组合优化
引言
配送\收集混合旅行商问题(Traveling Salesman Problem with Pickup and Delivery, TSPPD) 是一个典型的NP难问题，经常出现在交通运输、物流管理等领域，却没有引起人们的足够重视，这个问题涉及到两类顾客需要：一类是配送需求，要求将货物从配送中心送到需求点；另一类是收集需求，要求将货物从需求点运往配送中心。当所有的配送和收集需求都由一辆从 配送中心出发、给定容量的车辆来完成时，怎样安排行驶线路才能构成一条行驶路程最短的哈密尔顿回路。
根据配送需求与收集需求的先序关系，TSPPD可以分为三类：1.同时配送和收集，即每个顾客点既有配送需求，又有收集需求；2. 要求在服务所有有配送需求的顾客后，再服务有收集需求的顾客；3.混合配送、收集，放松2的约束，允许在某些配送需求前满足一些收集需求。文【1】考虑的是第三种。
问题的数学模型
将其定义为网络G=(V,A,C) ,其中 为一点集，O表示配送中心集，配送中心在该问题中仅有一个，编号为0；D表示配送需求点集合，各点分别编号为1，2，。。。n。点j需要运进的货物数量为 (j=1,2,…,n.)。P表示收集需求点集合，各点分别编号为n+1,n+2,..,n+m，点j需要运出的货物数量为 (j=n+1,n+2,..n+m)。 为一弧集，表示车辆可能走过的路线集合， 为弧长矩阵。决策变量 为1表示车辆通过弧 。 为通过弧 时，车上装载的已收集货物总量； 为通过弧 时，车上装载的还未配送的货物总量，
文【1】中还不失一般性地假设：车辆容量等于总配送量等于总收集量；每个需求点的配送量或收集量均为1。故该问题的数学模型可表达为：
S.T.
.
或 ，
S为子回路消去约束。
文【1】将模拟退火算法用于此问题的求解。 典型的模拟退火算法可用伪PASCAL语言描述为（文【2】）：
模拟退火算法（SA）
Procedure SIMULATED-ANNEALING;
Begin
INITIALIZE( , , );
k:=0;
i:= ;
repeat
for l:=1 to do
begin
GENERATE ( j from );
If then i:=j
else
if then i:=j
end;
k:=k+1;
CALCULATE-LENGTH( );
CALCULATE-CONTROL( );
Until stopcriterion
end;
表示第k次迭代时控制参数t（温度）的值， 表示第k次迭代时产生的变换个数（马氏链长）。
这其中的冷却进度表，邻域结构，新解产生机制，温度衰减函数等要针对具体问题适当选取。
文【1】所用模拟退火算法具有以下特征：
1)初始解：
2)初始温度 估计为：
3）温度衰减函数采用指数式，衰减因子 。
4）马氏链长采用固定长 .
5)邻域结构及新解产生机制：2点交换，2变换和3变换随机交替使用。
6）在Metropolis接受准则中加入解的可行性判断，即车的容量约束。
7）算法停止规则：当前温度小于某一给定正数或者一个解连续保持x代就停止计算。
8）计算过程中，记忆当前最优解。
顺便一说，该停止规则有缺陷，当前温度小于某一给定正数即停止计算，可能优化还未彻底，或者徒增计算时间，所以在后面用文【1】的模拟退火算法计算时，用的是修正了的停止规则：一个解连续保持X代就停止计算。
笔者尝试改进此算法，提出新的改进模拟退火算法—渐升温回火退火算法。
渐升温回火退火算法
为提高解的质量，模拟退火算法已有诸多改进，当提高解的质量的同时也较多的增加了计算的时间。
文【2】中，回火退火算法获得了其书中所有模拟退火算法及各种改进算法中最好的解的质量，但却大大增加了CPU时间。
传统回火退火算法采用降序温度序列反复进行模拟退火，先用与一般模拟退火相当的温度进行退火，时间就与一般模拟退火相当了，后面再反复执行较低温度的退火，计算时间自然就增加了。
如果把降序的温度序列改为阶梯式的升序呢？先用较低的温度做模拟退火，其时间比一般模拟退火所费时间短，再把其得到的结果作为下一回较高温度的模拟退火的初始解，而由于有前面的基础，后面所用时间应该有所减少，整个过程就有可能不增加时间，甚至可能缩短时间。
笔者就此对收集配送旅行商问题做试验，结果发现解的质量改善了，计算时间不仅没有增加，反而减少了。暂且称之为“渐升温模拟退火算法”。
渐升温回火退火算法的一般步骤可描述为：
为一般模拟退火算法确定冷却进度表，其中当然包括初温 。
,(step为一正整数，为升温序列长度)。
令初温为T进行模拟退火。
若 ，转5）。将2）得到的优化解作为初始解， ，转3）。
输出结果，算法结束。
这里是等差升温序列，也可以是其他升温序列，原理相同。
模拟实验
用文【1】的初始温度估计式得到 ，构造升温序列：
，step为温度个数。Step分别取5和10。
对每个温度实施文【1】所述一般的模拟退火，当然每个温度得到的优化解都作为下一个温度的模拟退火的起点。
随机产生规模分别为21，41，81的配送收集旅行商问题的三个实例，分别用文【1】的模拟退火算法和本文提出的渐升温回火退火算法，模拟20次。其中马氏链都取为2（n+m）,衰减因子为0.92，模拟退火停止规则为一个马氏链没有接受新解或者连续2（n+m）个解没有改进。表1到表3为在Celeron 1.7GHz+WindowXP+Matlab6.5下得到的结果。
TSPPD-21 最好解 平均解 最差解 总时间(s) 平均时间（s）
模拟退火算法 1.2886e+003 1.3382e+003 1.5948e+003 81.2820 4.0641
渐升温回火退火算法（step=5） 1.2886e+003 1.3425e+003 1.5164e+003 65.7350 3.2868
渐升温回火退火算法(step=10) 1.2886e+003 1.3118e+003 1.3748e+003 59.6720 2.9836
表1. TSPPD-21模拟20次的结果
TSPPD-41 最好解 平均解 最差解 总时间(s) 平均时间（s）
模拟退火算法 1.8833e+003 2.0585e+003 2.2747e+003 201.2340 10.0617
渐升温回火退火算法(step=5) 1.8886e+003 2.0452e+003 2.2846e+003 192.4840 9.6242
渐升温回火退火算法(step=10) 1.8754e+003 2.1202e+003 2.4371e+003 173.1250 8.6563
表2. TSPPD-41模拟20次的结果
TSPPD-81 Best Average Worst Total Mean
模拟退火算法 2.9571e+003 3.1560e+003 3.4926e+003 604.2660 30.2133
渐升温回火退火算法(step=5) 2.9345e+003 3.1561e+003 3.4923e+003 514.3910 25.7195
渐升温回火退火算法(step=10) 2.8340e+003 3.1177e+003 3.2972e+003 519.0780 25.9539
表3. TSPPD-81模拟20次的结果
由以上三个表的数据可以看到，三个实例的平均解，渐升温回火退火算法都要优于模拟退火算法；最好解也全部由渐升温回火退火算法获得；更重要的是，时间也都少于模拟退火算法；所以渐升温回火退火算法有效提高了优化效率。
以下两图分别为TSPPD-81的初始路线和经本文渐升温回火退火算法优化后的路线（本实验的最佳结果，总长为2834.0）。
图1. TSPPD-81的初始路线
图2. TSPPD-81的经渐升温回火退火算法优化后的路线
结语
仿真计算结果表明，本文提出的渐升温回火退火算法，提高了模拟退火的优化效率，将其应用到配送收集旅行商问题，是对原有算法的有效改进。
参考文献：
[1] 谢秉磊, 李良, 郭耀惶. 求解配送收集旅行商问题的模拟退火算法. 系统工程理论方法应用. 2002. 11(3): 240-243.
[2] 康立山，谢云，尤矢勇，罗祖华. 非数值并行算法（第一册）—模拟退火算法. 北京：科学出版社. 第一版. 1994.
Improved Algorithm for Traveling Salesman Problem with Pickup and Delivery
【Abstract】 In this paper, a new algorithm—Ascending Temperature Tempering Annealing Algorithm is proposed based on Simulated Annealing Algorithm for the Traveling Salesman Problem with Pickup and Delivery. Simulation experiments show that this algorithm improve the efficiency of the optimization process effectively .
Key words: pickup and delivery; traveling salesman problem; simulated annealing;; ascending temperature tempering annealing; combinatorial optimization
附 录
这里附上规模为41和21的配送收集旅行商问题的初始路线和经本文渐升温回火退火算法优化后的最佳路线（均为本文所有实验的最佳结果）。
图3. TSPPD-41初始路线
图4. TSPPD-41经渐升温回火退火算法优化后的路线
图5. TSPPD-21初始路线
图6. TSPPD-21经渐升温回火退火算法优化后的路线
