分享
 
 
 

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

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

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

杨贺宏

(中南大学 数学科学与计算技术学院 长沙 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经渐升温回火退火算法优化后的路线

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有