[1]胡明伟,唐浩.动态车辆路径问题的多目标优化模型与算法[J].深圳大学学报理工版,2010,27(2):230-235.
　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(2):230-235.
点击复制

动态车辆路径问题的多目标优化模型与算法()
分享到：

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

卷:
第27卷
期数:
2010年2期
页码:
230-235
栏目:
出版日期:
2010-04-30

文章信息/Info

Title:
Multi-objective optimization model of dynamic vehicle routing problem
文章编号:
1000-2618(2010)02-0230-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,U.S.A
关键词:
动态车辆路径问题; 多目标优化; 动态旅行修理员问题; 智能交通系统; 启发式算法
Keywords:
dynamic vehicle routing problem; multi-objective optimization; dynamic traveling repairman problem; intelligent transportation systems; heuristic
分类号:
U 116.2；O221.2
文献标志码:
A
摘要:
以快递服务相关的动态车辆路径问题为研究对象，建立多目标优化模型，设计了相应的求解流程．多目标优化模型包括最大化服务客户数、最小化客户等待时间和最小化总旅行时间3个优化目标．采用基于词典式的排序方法，开发了改进的Or-opt局部搜索启发式算法．在不同基准问题数据集上进行仿真实验，结果表明，多目标优化模型与单目标模型相比，能明显降低被拒绝的客户数和等待时间，而总旅行时间未发生明显增长．
Abstract:
A dynamic vehicle routing problem (DVRP) related to courier mail services is studied. A multi-objective optimization model is proposed，and a heuristic framework is introduced for its solution. The model includes three objectives：maximization of the number of serviced customers，minimization of customer waiting，and minimization of total travel time. The solution algorithms are based on the lexicographic vectormin approach，and a revised Or-opt local search is developed. With the comprehensive simulation experiments conducted on data sets derived from benchmark problem instances，the multi-objective optimization approach is demonstrated to be efficient and effective. The proposed multi-objective model is able to offer excellent computational results as compared with single-objective models. It can reduce the rejected on-call customers and waiting time distinctly with increased total travel time.

参考文献/References:

［1］Psaraftis H. 动态车辆路径：现状和展望［J］. 运筹学年报，1995，61(1)：143-164．(英文版)
［2］Chen Z L，Xu H. 带时间窗口动态车辆路径的动态列生成方法［J］. 交通科学，2006，40(1)：74-88．(英文版)
［3］Branke J，Middendorf M，Noeth G，等. 动态车辆路径的等待策略［J］. 交通科学，2005，39(3)：298-312．(英文版)
［4］Fleischmann B，Gnutzmann S，Sandvo E. 基于在线交通信息的动态车辆路径［J］. 交通科学，2004，38(4)：420-433．(英文版)
［5］Bent R W，Van H P. 具有随机客户的部分动态车辆路径的场景规划［J］. 运筹学，2004，52(6)：977-987．(英文版)
［6］胡明伟，唐浩. 时相关旅行时间车辆路径高效启发式算法［J］. 深圳大学学报理工版，2009，26(3)：315-320.
［7］刘士新，冯海兰. 动态车辆路径问题的优化方法［J］. 东北大学学报自然科学版，2008，29(4)：484-487.
［8］Norbert A，Matteo F，Martin G. 用分支裁剪法解决带时间窗口非对称旅行商问题［J］. 数学规划，2001，90(3)：475-506．(英文版)
［9］Solomon M. 带时间窗口约束的车辆路径和调度问题的算法［J］. 运筹学，1987，35(2)：254-265．(英文版)
［10］Mingozzi A，Bianco L，Ricciardelli S. 带时间窗口和优先约束旅行商问题的动态规划策略［J］. 运筹学，1997，45(3)：365-377．(英文版)



［1］Psaraftis H. Dynamic vehicle routing：status and prospects［J］. Annals of Operations Research，1995，61(1)：143-164.
［2］Chen Z L，Xu H. Dynamic column generation for dynamic vehicle routing with time windows［J］. Transportation Science，2006，40(1)：74-88.
［3］Branke J，Middendorf M，Noeth G，et al. Waiting strategies for dynamic vehicle routing［J］. Transportation Science，2005，39(3)：298-312.
［4］Fleischmann B，Gnutzmann S，Sandvo E. Dynamic vehicle routing based on online traffic information［J］. Transportation Science，2004，38(4)：420-433.
［5］Bent R W，Van H P. Scenario-based planning for partially dynamic vehicle routing with stochastic customers［J］. Operations Research，2004，52(6)：977-987.
［6］HU Ming-wei，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．(in Chinese)
［7］LIU Shi-xin，FENG Hai-lan. Optimization approach to solving dynamic vehicle routing problems［J］. Journal of Northeastern University：Natural Science，2008，29(4)，484-487．(in Chinese)
［8］Norbert A，Matteo F，Martin G. Solving the asymmetric traveling salesman problem with time windows by branch-and-cut［J］. Mathematical Programming，2001，90(3)：475-506.
［9］Solomon M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research，1987，35(2)：254-265.
［10］Mingozzi A，Bianco L，Ricciardelli S. Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints［J］. Operations Research，1997，45(3)：365-377.

相似文献/References:

[1]蔡华利,刘鲁,樊坤,等.基于BPSO的web服务推荐策略[J].深圳大学学报理工版,2010,27(1):49.
　CAI Hua-li,LIU Lu,FAN Kun,et al.Web services recommendation based on BPSO[J].Journal of Shenzhen University Science and Engineering,2010,27(2):49.
[2]欧阳春娟,李霞,李斌.基于递进多目标蛙跳优化的LSB±K隐写算法[J].深圳大学学报理工版,2012,29(No.3(189-282)):224.[doi:10.3724/SP.J.1249.2012.03224]
　OUYANG Chun-juan,LI Xia,and LI Bin.A secure LSB plus-minus K steganography based on escalating multi-objective SFLA[J].Journal of Shenzhen University Science and Engineering,2012,29(2):224.[doi:10.3724/SP.J.1249.2012.03224]
[3]袁磊,李冰瑶.住区布局多目标自动寻优的模拟方法[J].深圳大学学报理工版,2018,35(1):78.[doi:10.3724/SP.J.1249.2018.01078]
　YUAN Lei and LI Bingyao.A multi-objective auto-optimizing simulation method of residential layout design[J].Journal of Shenzhen University Science and Engineering,2018,35(2):78.[doi:10.3724/SP.J.1249.2018.01078]

备注/Memo

备注/Memo:
收稿日期：2009-05-30；修回日期：2010-01-18
基金项目：深圳市科技计划资助项目（SYZ200806270087A）
作者简介：胡明伟（1972-），男（汉族），湖南省衡阳市人，深圳大学副教授、博士. E-mail：humw2005@126.com
更新日期/Last Update: 2010-05-08