配送收集旅行商问题的改进算法.pdf-资料库

weixin_38717579-12160241-4744300845184931166.pdf-第1页.png

第1页 / 共10页

weixin_38717579-12160241-4744300845184931166.pdf-第2页.png

第2页 / 共10页

weixin_38717579-12160241-4744300845184931166.pdf-第3页.png

第3页 / 共10页

weixin_38717579-12160241-4744300845184931166.pdf-第4页.png

第4页 / 共10页

weixin_38717579-12160241-4744300845184931166.pdf-第5页.png

第5页 / 共10页

weixin_38717579-12160241-4744300845184931166.pdf-第6页.png

第6页 / 共10页

weixin_38717579-12160241-4744300845184931166.pdf-第7页.png

第7页 / 共10页

weixin_38717579-12160241-4744300845184931166.pdf-第8页.png

第8页 / 共10页

配送收集旅行商问题的改进算法中南大学数学科学与计算技术学院长沙 (410083 ）杨贺宏 E-mail: yanghehong@yahoo.com.cn 【摘要】针对配送收集旅行商问题的模拟退火算法，本文提出一种改进算法—渐升温回火退火算法。通过对三种规模的配送收集旅行商问题的仿真实验，表明该算法有效的提高了优化的效率。关键词：配送\收集；旅行商问题；模拟退火算法；渐升温回火退火算法；组合优化引言配送\收集混合旅行商问题(Traveling Salesman Problem with Pickup and Delivery, TSPPD) 是一个典型的 NP 难问题，经常出现在交通运输、物流管理等领域，却没有引起人们的足够重视，这个问题涉及到两类顾客需要：一类是配送需求，要求将货物从配送中心送到需求点；另一类是收集需求，要求将货物从需求点运往配送中心。当所有的配送和收集需求都由一辆从配送中心出发、给定容量的车辆来完成时，怎样安排行驶线路才能构成一条行驶路程最短的哈密尔顿回路。根据配送需求与收集需求的先序关系，TSPPD 可以分为三类：1.同时配送和收集，即每个顾客点既有配送需求，又有收集需求；2. 要求在服务所有有配送需求的顾客后，再服务有收集需求的顾客；3.混合配送、收集，放松 2 的约束，允许在某些配送需求前满足一些收集需求。文【1】考虑的是第三种。问题的数学模型将其定义为网络 G=(V,A,C) ,其中V OP D =¨ 为一点集，O 表示配送中心集，配送中心在该问题中仅有一个，编号为 0；D 表示配送需求点集合，各点分别编号为 1，2，。。。 n。点 j 需要运进的货物数量为 jg (j=1,2, …,n.)。P 表示收集需求点集合，各点分别编号为 n+1,n+2,..,n+m ，点 j 需要运出的货物数量为 jg (j=n+1,n+2,..n+m) 。为一弧集，表示车辆可能走过的路线集合， ==+ Aijijmni {(,)|,0,1,2,,, j = Ccij A {|(,) ij L } 为弧长矩阵。决策变量 ijx } 为 1 表示车辆通过弧(, )i 为通过弧(, )i j 时，车上装载的已收集货物总量； ijz j 时，车上装载的还未配送的货物总量，文【1】中还不失一般性地假设：车辆容量等于总配送量等于总收集量；每个需求点的配送量或收集量均为 1。故该问题的数学模型可表达为：为通过弧(, )i j 。 ijy PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn ______________________________________________________________________________________________www.paper.edu.cn¨ „ ˛

min + mnm n + = i 0 = j 0 c x ijij S.T. == xjm n ij 1,0,1, + L , == xim n ij 1,0,1, + , L + m n = i 0 + m n = j 0 + mnm n -=- yyq i ijki k = j 0 = + = 0 gi P i , 0 , i D 0, . = , gi D i , 0 i P 0, + ,,0,1, , + mnm n -= zzq i ijki k + = 0 = j 0 +£= ijijijyzqxijm n S˛ ijx jgjm n== 1,1,2, , L +L + = i 1 ijijy z ‡ , 0 == nm n qgg m i == + ii n 1 m n= ijx = 0 ijm n= ,0,1, 或 , ijx = 1 +L ， S 为子回路消去约束。文【1】将模拟退火算法用于此问题的求解。典型的模拟退火算法可用伪 PASCAL 语言描述为（文【2】）：模拟退火算法（SA） Procedure SIMULATED-ANNEALING; Begin PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn 中国科技论文在线______________________________________________________________________________________________www.paper.edu.cn ˛ ˛ - ˛ ˛

0i , 0t , 0L ); INITIALIZE( k:=0; i:= 0i ; repeat for l:=1 to kL do begin GENERATE ( j from iS ); i £ fjf ()( ) then i:=j fif j ()( ) exp()[0,1) t k > random then i:=j If else if end; k:=k+1; CALCULATE-LENGTH( CALCULATE-CONTROL( Until stopcriterion kL ); kt ); end; kt 表示第 k 次迭代时控制参数 t（温度）的值， kL 表示第 k 次迭代时产生的变换个数（马氏链长）。这其中的冷却进度表，邻域结构，新解产生机制，温度衰减函数等要针对具体问题适当选取。文【1】所用模拟退火算法具有以下特征： ﬁ+ﬁ ﬁ+ 1)初始解：011 2)初始温度 0t 估计为： nnn m 0 ﬁ L L + mnm n = i 0 max{|,0,1,,}min{|,0,1,, L cjijmncjijm n ijij + } „=+- „= 3）温度衰减函数采用指数式，衰减因子 [0.9,0.95] + = 0 i s ˛ L 。 4）马氏链长采用固定长 =+ Lwnm w (),0.5,1,2 = . PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn 中国科技论文在线______________________________________________________________________________________________www.paper.edu.cn- ﬁ ﬁ ﬁ

5)邻域结构及新解产生机制：2 点交换，2 变换和 3 变换随机交替使用。 6）在 Metropolis 接受准则中加入解的可行性判断，即车的容量约束。 7）算法停止规则：当前温度小于某一给定正数或者一个解连续保持 x 代就停止计算。 8）计算过程中，记忆当前最优解。顺便一说，该停止规则有缺陷，当前温度小于某一给定正数即停止计算，可能优化还未彻底，或者徒增计算时间，所以在后面用文【1】的模拟退火算法计算时，用的是修正了的停止规则：一个解连续保持 X 代就停止计算。笔者尝试改进此算法，提出新的改进模拟退火算法—渐升温回火退火算法。渐升温回火退火算法为提高解的质量，模拟退火算法已有诸多改进，当提高解的质量的同时也较多的增加了计算的时间。文【2】中，回火退火算法获得了其书中所有模拟退火算法及各种改进算法中最好的解的质量，但却大大增加了 CPU 时间。传统回火退火算法采用降序温度序列反复进行模拟退火，先用与一般模拟退火相当的温度进行退火，时间就与一般模拟退火相当了，后面再反复执行较低温度的退火，计算时间自然就增加了。如果把降序的温度序列改为阶梯式的升序呢？先用较低的温度做模拟退火，其时间比一般模拟退火所费时间短，再把其得到的结果作为下一回较高温度的模拟退火的初始解，而由于有前面的基础，后面所用时间应该有所减少，整个过程就有可能不增加时间，甚至可能缩短时间。笔者就此对收集配送旅行商问题做试验，结果发现解的质量改善了，计算时间不仅没有增加，反而减少了。暂且称之为“渐升温模拟退火算法”。渐升温回火退火算法的一般步骤可描述为： 1）为一般模拟退火算法确定冷却进度表，其中当然包括初温 mT 。 = T mT step 2） 3）令初温为 T 进行模拟退火。 ,(step 为一正整数，为升温序列长度)。 T T= m ，转 5）。将 2）得到的优化解作为初始解， 4）若 5）输出结果，算法结束。这里是等差升温序列，也可以是其他升温序列，原理相同。 = + T T mT step ，转 3）。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn 中国科技论文在线______________________________________________________________________________________________www.paper.edu.cn

模拟实验用文【1】的初始温度估计式得到 mT T m (),2(), , stepstep T m T m L ，构造升温序列：，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) 平均解最差解最好解平均时间模拟退火算法 1.2886e+003 1.2886e+003 渐升温回火退 1.3382e+003 1.3425e+003 1.5948e+003 1.5164e+003 81.2820 65.7350 （s） 4.0641 3.2868 火算法（step=5）渐升温回火退 1.2886e+003 1.3118e+003 1.3748e+003 59.6720 2.9836 火算法 (step=10) 表 1. TSPPD-21 模拟 20 次的结果 TSPPD-41 最好解平均解最差解总时间(s) 平均时间模拟退火算法渐升温回火退 1.8833e+003 2.0585e+003 1.8886e+003 2.0452e+003 2.2747e+003 201.2340 2.2846e+003 192.4840 火算法(step=5) （s） 10.0617 9.6242 渐升温回火退 1.8754e+003 2.1202e+003 2.4371e+003 173.1250 8.6563 火算法 (step=10) 表 2. TSPPD-41 模拟 20 次的结果 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn 中国科技论文在线______________________________________________________________________________________________www.paper.edu.cn

TSPPD-81 模拟退火算法 Best 2.9571e+003 3.1560e+003 3.4926e+003 604.2660 Average Worst Total Mean 30.2133 渐升温回火 2.9345e+003 3.1561e+003 3.4923e+003 514.3910 25.7195 退火算法 (step=5) 渐升温回火 2.8340e+003 3.1177e+003 3.2972e+003 519.0780 25.9539 退火算法 (step=10) 表 3. TSPPD-81 模拟 20 次的结果由以上三个表的数据可以看到，三个实例的平均解，渐升温回火退火算法都要优于模拟退火算法；最好解也全部由渐升温回火退火算法获得；更重要的是，时间也都少于模拟退火算法；所以渐升温回火退火算法有效提高了优化效率。以下两图分别为 TSPPD-81 的初始路线和经本文渐升温回火退火算法优化后的路线（本实验的最佳结果，总长为 2834.0）。图 1. TSPPD-81 的初始路线 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn 中国科技论文在线______________________________________________________________________________________________www.paper.edu.cn

图 2. TSPPD-81 的经渐升温回火退火算法优化后的路线结语仿真计算结果表明，本文提出的渐升温回火退火算法，提高了模拟退火的优化效率，将其应用到配送收集旅行商问题，是对原有算法的有效改进。参考文献： [1] 谢秉磊, 李良, 郭耀惶. 求解配送收集旅行商问题的模拟退火算法. 系统工程理论方法应用. 2002. 11(3): 240-243. [2] 康立山，谢云，尤矢勇，罗祖华. 非数值并行算法（第一册）—模拟退火算法. 北京：科学出版社. 第一版. 1994. PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn 中国科技论文在线______________________________________________________________________________________________www.paper.edu.cn

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 的配送收集旅行商问题的初始路线和经本文渐升温回火退火算法优化后的最佳路线（均为本文所有实验的最佳结果）。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn 中国科技论文在线______________________________________________________________________________________________www.paper.edu.cn

资料库

配送收集旅行商问题的改进算法.pdf

相关推荐

开发技术

热门标签

最新资料