[1]胡明伟,唐浩.时相关旅行时间车辆路径高效启发式算法[J].深圳大学学报理工版,2009,26(3):315-320.
 HU Ming-wei and TANG Hao.Efficient heuristics for vehicle routing problems with time-dependent travel times[J].Journal of Shenzhen University Science and Engineering,2009,26(3):315-320.
点击复制

时相关旅行时间车辆路径高效启发式算法()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第26卷
期数:
2009年3期
页码:
315-320
栏目:
出版日期:
2009-07-31

文章信息/Info

Title:
Efficient heuristics for vehicle routing problems with time-dependent travel times
文章编号:
1000-2618(2009)03-0315-06
作者:
胡明伟1唐浩2
1)深圳大学土木工程学院, 深圳 518060;
2)美国联邦快递公司,美国田纳西 38125
Author(s):
HU Ming-wei1 and TANG Hao2
1)College of Civil Engineering,Shenzhen University,Shenzhen 518060,P.R.China
2)FedEx Express Corporation Memphis,TN 38125,USA
关键词:
时相关车辆路径问题启发式算法智能交通系统局部搜索算法动态路径诱导
Keywords:
time-dependent vehicle routing problem(TDVRP)heuristicsintelligent transportation systems(ITS)local search algorithmdynamic route guidance
分类号:
U 116.2;O 221.2
文献标志码:
A
摘要:
研究时相关旅行时间车辆路径问题经典启发式算法的改进策略,通过更新路线的到达时间和最晚出发时间,减少局部搜索算法的计算时间.该策略可用于Or-opt、2-opt、 1-shift和CROSS等交换算法.通过数值计算实验,评估改进策略的性能,结果表明,对于单路线和多路线过程,高效启发式算法的计算复杂度明显低于常规算法.
Abstract:
An efficient heuristics,which is improving classical heuristics for vehicle routing with time-dependent travel times through updating arrival and latest departure times,was proposed.The computational time of local search algorithms can be significantly reduced by the proposed method.The improved method can be used to Or-opt,2-opt,1-shift,and CROSS exchanges.The simulation results indicate that the computational complexities of the proposed heuristics for both single- and multi-tour procedures are significantly reduced compared with the conventional heuristics.

参考文献/References:

[1]Dantzig G B,Ramser J H.卡车调度问题[J].管理科学,1959,6(1):80-91 (英文版).
[2]Beasley J.针对可变客户间旅行时间的改进节约式算法[J].Omega管理科学国际学报,1981,9(6):658-659 (英文版).
[3]Ichoua S,Gendreau M,Potvin J Y.时相关旅行时间的车辆调度[J].欧洲运筹学学报,2003,144(2):379-396 (英文版).
[4]Fleischmann B,Gietz M,Gnutzmann S.车辆路径中的时变旅行时间[J].运输科学, 2004,38(2):160-173 (英文版).
[5]Haghani A,Jung S.时相关旅行时间动态车辆路径问题[J].计算机和运筹学,2005,32(11):2959-2986 (英文版).
[6]唐健,史文中,孟令奎.基于遗传算法的时相关动态车辆路径规划模型[J].武汉大学学报信息科学版,2008,33(8):875-879.
[7]Kindervater G,Savelsbergh M.车辆路径:处理边界交换[M].新泽西州:John Wiley & Sons出版社,1997:337-360 (英文版).
[8]Tang H,Hu M W.多目标动态车辆路径问题:解决框架和计算实验[J].美国交通研究委员会学报,2005(1923):199-207 (英文版).


[1]Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.
[2]Beasley J.Adapting the savings algorithm for varying inter-customer travel times[J].Omega International Journal of Managment Science,1981,9(6):658-659.
[3]Ichoua S,Gendreau M,Potvin J Y.Vehicle dispatching with time-dependent travel times[J].European Journal of Operational Research,2003,144(2):379-396.
[4]Fleischmann B,Gietz M,Gnutzmann S.Time-varying travel times in vehicle routing[J].Transportation Science, 2004,38(2):160-173.
[5]Haghani A,Jung S.A dynamic vehicle routing problem with time-dependent travel times[J].Computers and Operations Research,2005,32(11):2959-2986.
[6]TANG Jian,SHI Wen-zhong,MENG Ling-kui.Time-dependent dynamic vehicle routing based on genetic algorithm[J].Geomatics and Information Science of Wuhan University,2008,33(8):875-879 (in Chinese).
[7]Kindervater G,Savelsbergh M.Vehicle Routing:Handling Edge Exchanges[M].New Jersey:John Wiley & Sons,1997:337-360.
[8]Tang H,Hu M W.A dynamic vehicle routing problem with multiple objectives:solution framework and computational experiments[J].Journal of Transportation Research Board,2005(1923):199-207.

相似文献/References:

[1]胡明伟,唐浩.动态车辆路径问题的多目标优化模型与算法[J].深圳大学学报理工版,2010,27(2):230.
 HU Ming-wei and TANG Hao.Multi-objective optimization model of dynamic vehicle routing problem[J].Journal of Shenzhen University Science and Engineering,2010,27(3):230.
[2]刘万峰,李霞.车辆路径问题的快速多邻域迭代局部搜索算法[J].深圳大学学报理工版,2015,32(2):196.[doi:10.3724/SP.J.1249.2015.02000]
 Liu Wanfeng,and Li Xia,A fast multi-neighborhood iterated local search algorithm for vehicle routing problem[J].Journal of Shenzhen University Science and Engineering,2015,32(3):196.[doi:10.3724/SP.J.1249.2015.02000]
[3]马江山,李昱莹.基于卷积的自助银行选址分析[J].深圳大学学报理工版,2018,35(1):92.[doi:10.3724/SP.J.1249.2018.01092]
 MA Jiangshan and LI Yuying.Self-help bank location analysis based on convolution[J].Journal of Shenzhen University Science and Engineering,2018,35(3):92.[doi:10.3724/SP.J.1249.2018.01092]

备注/Memo

备注/Memo:
收稿日期:2008-12-29;修回日期:2009-05-01
基金项目:深圳市科技计划资助项目(SY200806270087A)
作者简介:胡明伟(1972-),男(汉族),湖南省衡阳市人,深圳大学副教授、博士.E-mail:humw2005@126.com
更新日期/Last Update: 2009-08-26