计算机应用 ›› 2012, Vol. 32 ›› Issue (11): 3042-3070.DOI: 10.3724/SP.J.1087.2012.03042

• 人工智能 • 上一篇    下一篇

求解带硬时间窗车辆路径问题的时差插入启发式算法

潘立军1,符卓2   

  1. 1. 湖南工程学院 管理学院,湖南 湘潭 411201
    2. 中南大学 交通运输工程学院,长沙 410075
  • 收稿日期:2012-03-29 修回日期:2012-06-12 发布日期:2012-11-12 出版日期:2012-11-01
  • 通讯作者: 潘立军
  • 作者简介:潘立军(1977-),男,湖南衡阳人,讲师,博士研究生,主要研究方向:物流系统优化;
    符卓(1960-),男,海南文昌人,教授,博士生导师,主要研究方向:物流系统优化、交通运输规划与管理。
  • 基金资助:
    国家自然科学基金资助项目(70671108);湖南省教育厅资助项目(10C0558)

Time difference insertion heuristics algorithm for vehicle routing problem with hard time window

PAN Li-jun1,FU Zhuo2   

  1. 1. Management Department, Hunan Institute of Engineering, Xiangtan Hunan 411201, China
    2. School of Traffic and Transportation Engineering, Central South University, Changsha Hunan 410075,China
  • Received:2012-03-29 Revised:2012-06-12 Online:2012-11-12 Published:2012-11-01
  • Contact: PAN Li-jun

摘要: 针对已有求解带硬时间窗车辆路径问题时插入启发式算法结构复杂、参数多、求解效率不高的缺点,提出了求解该问题的时差插入启发式算法。该算法引入时差的概念,将时差作为启发规则的评价指标。相比已有求解该问题的经典启发式算法,该算法有参数个数少、算法结构简单等特点。应用标准测试算例测试表明,所提算法的求解质量优于Solomon的插入启发式算法和Potvin的平行插入启发式算法。

关键词: 车辆路径问题, 时间窗, 时差, 插入启发式算法

Abstract: The Vehicle Routing Problem with Hard Time Window (VRPHTW) is a kind of Vehicle Routing Problem (VRP) which has a lot of applications. The existing heuristics of this problem hold shortcomings such as complex structure, lots of parameters and low efficiency. Therefore, Time Difference Insertion Heuristics (TDIH) for VRPHTW was proposed. The algorithm introduced the concept of Time Difference (TD), and took TD as a heuristic rule evaluation indicator. Compared to other classic heuristics, the algorithm was characterized with fewer parameters and simpler structure. The computational results on the benchmark problems show that the algorithm is better than the Solomons insertion heuristics and Potvins parallel insertion heuristics.

Key words: vehicle routing problem, time window, time difference, insertion heuristics

中图分类号: