东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2008, Vol. 29 ›› Issue (4): 484-487.DOI: -

• 论著 • 上一篇    下一篇

动态车辆路径问题的优化方法

刘士新;冯海兰;   

  1. 东北大学流程工业综合自动化教育部重点实验室;东北大学流程工业综合自动化教育部重点实验室 辽宁沈阳110004;辽宁沈阳110004
  • 收稿日期:2013-06-22 修回日期:2013-06-22 出版日期:2008-04-15 发布日期:2013-06-22
  • 通讯作者: Liu, S.-X.
  • 作者简介:-
  • 基金资助:
    国家自然科学基金资助项目(70301007,70771020,70431003);;

Optimization approach to solving dynamic vehicle routing problems

Liu, Shi-Xin (1); Feng, Hai-Lan (1)   

  1. (1) Key Laboratory of Integrated Automation of Process Industry, Northeastern University, Shenyang 110004, China
  • Received:2013-06-22 Revised:2013-06-22 Online:2008-04-15 Published:2013-06-22
  • Contact: Liu, S.-X.
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

1437

摘要： 设计了在动态环境下进行车辆路径优化的导向局域搜索算法.算法在产生初始解以后的动态求解过程中,不再做车辆之间的顾客调整,而只应用2-opt局域搜索算子更新车辆服务顾客的顺序,即针对每辆车辆的旅行路线求解一个旅行商问题.建立了在动态环境下车辆执行运输任务过程的仿真模型.仿真过程中,应用算法根据交通路网实际情况实时优化车辆路径,并采用4种接受准则判别是否接受新的车辆路径.仿真结果表明:算法具有实时、高效的特点,满足动态车辆路径问题的求解要求.

关键词: 智能交通系统, 动态车辆路径问题, 交通模拟, 导向局部搜索

Abstract: A guided local search (GLS) algorithm is presented to solve dynamic vehicle routing problems (DVRP). In the dynamic solving process after an initial solution, the GLS does not exchange customers between vehicles but applies the 2-opt local search operator to updating the servicing sequence for customers, i.e., to solve a traveling salesman problem of traveling routing of each vehicle. A simulation model is thus developed for the dynamic process during which vehicles are in traffic. In the simulation model the GLS algorithm is applied to optimizing the vehicle routes in accordance to the real-time traffic situation, and four rules are applied to judging if the newly optimized vehicle routes are accepted. The simulation results reveal that the GLS algorithm can provide real-time response to dynamic information to satisfy the requirements of solving DVRP.

中图分类号: