多阶段动态车辆路径问题实时优化策略

上海交通大学学报（自然版） ›› 2013, Vol. 47 ›› Issue (03): 450-453.

多阶段动态车辆路径问题实时优化策略

熊浩，鄢慧丽，周和平，柳伍生

(长沙理工大学交通运输工程学院，长沙 410076)

收稿日期:2012-04-16 出版日期:2013-03-28 发布日期:2013-03-28
基金资助:
国家自然科学基金项目（71072027，51178061），交通运输部科技示范工程项目（交函科技［2009］333），2011中国物流学会研究课题（2011CSLKT152），湖南省自然科学基金项目（11JJ6044）

Real-Time Optimization Strategy of the Multi-Period Dynamic Vehicle Routing Problems

XIONG Hao, YAN Hui-Li, ZHOU He-Ping, LIU Wu-Sheng

(School of Traffic and Transportation Engineering, Changsha University of Science & Technology, Changsha 410076, China)

Received:2012-04-16 Online:2013-03-28 Published:2013-03-28

摘要/Abstract

摘要： 针对多阶段动态车辆路径单决策和多决策问题，分别提出了平均距离策略和分区分批旅行商策略.前者优先安排不能延迟的顾客，然后根据路径的平均顾客距离选择可延迟顾客；后者根据阶段内决策的时间界限只在最后一次决策才考虑拒绝和延迟.实例仿真结果表明，新策略都具有较好的优化效果.

关键词: 实时优化策略, 车辆路径问题, 动态, 多阶段

Abstract: The multi-period dynamic vehicle routing problem(MPDVRP) belongs to the emerging problem of dynamic vehicle routing problem, which can be divided into single decision-making problem and multi-decision-making problem. Average distance strategy and cutting-and-batch TSP strategy were constructed for these two types of problems. The average distance strategy gives priority to customers those cannot be delayed, and then selects the customers those can be delayed according to the average path distance. In cutting-and-batch TSP strategy, the customers will be delayed or refused only in the last decision according to decision-making time limit. Simulations of the two strategies were carried out, and the numerical results show that the two strategies are both better than the existing strategies.

Key words: real-time optimization strategy, vehicle routing problem, dynamic, multi-period

中图分类号:

N 945

熊浩, 鄢慧丽, 周和平, 柳伍生. 多阶段动态车辆路径问题实时优化策略 [J]. 上海交通大学学报（自然版）, 2013, 47(03): 450-453.

XIONG Hao, YAN Hui-Li, ZHOU He-Ping, LIU Wu-Sheng. Real-Time Optimization Strategy of the Multi-Period Dynamic Vehicle Routing Problems[J]. Journal of Shanghai Jiaotong University, 2013, 47(03): 450-453.

参考文献

［1］Larsen A, Madsen O, Solomon M M. Recent developments in dynamic vehicle routing systems［J］. The Vehicle Routing Problem: Latest Advances and New Challenges, 2008, 23(2):199218.
［2］Angelelli E, Savelsbergh M, Grazia Speranza M. Competitive analysis of a dispatch policy for a dynamic multiperiod routing problem［J］. Operations Research Letters, 2007, 35(6):713721.
［3］Angelelli E, Speranza M G, Savelsbergh M. Competitive analysis for dynamic multiperiod uncapacitated routing problems［J］. Networks, 2007, 49(4):308317.
［4］Tuchscherer A, Saliba S, Krumke S O, et al. Randomized online algorithms for dynamic multiperiod routing problems［R］. D14195 BerlinDahlem, Germany, 2009.
［5］Kleywegt A J, Savelsbergh M, Uyar E. A dynamic stochastic routing problem［R］. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology, Atlanta, GA 303320205, 2009.
［6］Angelelli E, Bianchessi N, Mansini R, et al. Short term strategies for a dynamic multiperiod routing problem［J］. Transportation Research Part C: Emerging Technologies, 2009,17(2):106119.
［7］Angelelli E, Bianchessi N, Mansini R, et al. Management policies in a dynamic multi period routing problem［J］. Innovations in Distribution Logistics, 2009, 13(4):115.
［8］Wen M, Cordeau J F, Laporte G, et al. The dynamic multiperiod vehicle routing problem［J］. Computers & Operations Research, 2010,37(9):16151623.
［9］Bertsimas D J, Van Ryzin G. Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles［J］. Operations Research, 1993, 41(1):6076.

[1]	刘亚辉, 申兴旺, 顾星海, 彭涛, 鲍劲松, 张丹. 面向柔性作业车间动态调度的双系统强化学习方法[J]. 上海交通大学学报, 2022, 56(9): 1262-1275.
[2]	王红, 齐彦昆, 何勇, 杨国军. 双目标优化的动车组系统多阶段机会维修决策[J]. 上海交通大学学报, 2022, 56(9): 1276-1284.
[3]	姜俊豪, 陈刚. 驾驶机器人转向操纵的动态模型预测控制方法[J]. 上海交通大学学报, 2022, 56(5): 594-603.
[4]	王宁, 付云鹏, 李艇, 李铁, 依平. 基于FloMaster-Simulink联合仿真的大流量海水冷却系统控制方案优化[J]. 上海交通大学学报, 2022, 56(3): 379-385.
[5]	马丽萍, 张骁煜, 白雨鑫, 陈鑫, 张颖. 基于近似计算的精度动态可调FFT处理器[J]. 上海交通大学学报, 2022, 56(2): 223-230.
[6]	袁振钦, 邹科, 孙亚峰, 刘刚, 屈衍, 李居跃. 基于时域分析法的动态电缆疲劳分析[J]. 海洋工程装备与技术, 2022, 9(2): 50-55.
[7]	金戈, 范珉, 周振栋, 谭勇, 钟小波. 升降式止回阀动态特性分析与改进[J]. 上海交通大学学报, 2021, 55(S2): 110-118.
[8]	金皓纯, 葛敏辉, 徐波. 基于极限学习机的双馈感应风力发电机综合自适应调频参数优化方法[J]. 上海交通大学学报, 2021, 55(S2): 42-50.
[9]	郭志远, 虞培祥, 欧阳华. 基于大涡模拟的圆柱绕流剪切层不稳定性[J]. 上海交通大学学报, 2021, 55(8): 924-933.
[10]	郭德平, 李铮, 彭森林, 曾志凯, 吴岱峰. 基于Newmark隐式时间积分方案的裂纹动态扩展的数值计算方法[J]. 上海交通大学学报, 2021, 55(6): 689-697.
[11]	邱忠宇, 赵文龙, 高文, 潘洪涛, 史冉东. 动态视觉传感器的目标检测算法对比分析[J]. 空天防御, 2021, 4(4): 101-106.
[12]	王浩凝, 唐胜景, 郭杰, 黄繁. 带有动态攻角剖面的时间约束再入制导[J]. 空天防御, 2021, 4(1): 71-76.
[13]	谢海润，吴亚东，欧阳华，王安正. 基于本征正交分解和动态模态分解的尾涡激振现象瞬态过程的模态分析[J]. 上海交通大学学报, 2020, 54(2): 176-185.
[14]	来颜博, 阎高伟, 程兰, 陈泽华. 基于动态独立成分分析和动态主成分分析的测地线流式核无监督回归模型[J]. 上海交通大学学报, 2020, 54(12): 1269-1277.
[15]	祝米鑫, 葛亚雄, 周晓军. 动态生产计划下多工序柔性制造系统预防维护决策[J]. 上海交通大学学报, 2020, 54(11): 1124-1133.