作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (13): 137-141. doi: 10.3969/j.issn.1000-3428.2012.13.041

• 人工智能及识别技术 • 上一篇    下一篇

带时间窗动态车辆路径问题的优化调度策略

王 君1,李 波2,卢志刚1   

  1. (1. 天津财经大学商学院,天津 300222;2. 天津大学管理与经济学部,天津 300072)
  • 收稿日期:2011-12-31 出版日期:2012-07-05 发布日期:2012-07-05
  • 作者简介:王 君(1983-),男,博士,主研方向:物流工程,智能优化;李 波,教授、博士生导师;卢志刚,教授
  • 基金资助:
    国家社科基金资助项目(11CGL102);新世纪优秀人才支持计划基金资助项目(NCET-06-0236);高等学校博士学科点专项科研基金资助项目(20100032110034);天津财经大学科研发展基金资助项目(Y1110, Q1208)

Optimization Schedule Strategy for Dynamic Vehicle Routing Problem with Time Window

WANG Jun   1, LI Bo   2, LU Zhi-gang   1   

  1. (1. School of Business, Tianjin University of Finance & Economics, Tianjin 300222, China; 2. College of Management and Economics, Tianjin University, Tianjin 300072, China)
  • Received:2011-12-31 Online:2012-07-05 Published:2012-07-05

摘要: 针对带时间窗动态车辆路径问题(DVRPTW),根据优化时间点的选取建立DVRPTW的一系列静态子模型,研究优化调度策略,分别是基于新顾客插入后的重复优化方法、批处理的方法或两者的混合。通过定义紧急顾客,提出一种新的紧急顾客插入和分批驱动调度策略,该策略只需实时插入紧急顾客,具有快速响应、计算负荷小和路径计划更新频率低的优点。仿真对比实验比较了4种策略的优劣,并探讨分批优化间隔长度对调度性能的影响。

关键词: 动态车辆路径问题, 调度策略, 批优化, 实时优化, 时间窗, 紧急顾客

Abstract: Aiming at the Dynamic Vehicle Routing Problem with Time Windows(DVRPTW), a series of static DVRPTW sub-models are established according to the optimization times, and four dynamic schedule strategies are provided to optimize the DVRPTW. Three of the strategies are based on a repeated reoptimization of various instances of the static problem, the batch optimization and a hybrid of both. The fourth is a new one called the emergency customer insertion and batch optimization strategy. This strategy only distinguishes the emergency customers and inserts them into real-time routing plan, and hence has the advantages of quick response, small computational load and low update frequency while routing the vehicles. Simulation experiments compare four strategies and discuss the impact of batch schedule intervals on the schedule performance.

Key words: Dynamic Vehicle Routing Problem(DVRP), schedule strategy, batch optimization, real-time optimization, time window, emergency customer

中图分类号: