交通运输系统工程与信息

交通运输系统工程与信息 ›› 2011, Vol. 11 ›› Issue (1): 85-89 .

• 系统工程理论与方法 • 上一篇    下一篇

一种基于时空距离的带时间窗车辆路径问题算法

戚铭尧*1;丁国祥2;周游1;缪立新1   

  1. 1. 清华大学 深圳研究生院，广东 深圳 518055；2.俄亥俄州立大学 地理系，美国
  • 收稿日期:2010-07-15 修回日期:2010-11-02 出版日期:2011-02-25 发布日期:2012-12-20
  • 通讯作者: 戚铭尧
  • 作者简介:戚铭尧（1974-），男，湖北省武穴市人，副教授，博士.
  • 基金资助:

    国家自然科学基金项目（70702003）；国家基础研究计划项目(2006CB705500); 东莞市高等院校科研机构科技计划项目（200910810115）

Vehicle Routing Problem with Time Windows Based on Spatiotemporal Distance

QI Ming-yao1; DING Guo-xiang2;ZHOU You1;MIAO Li-xin1   

  1. 1. Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, Guangdong, China;2. Department of Geography, The Ohio State University, Columbus, OH USA
  • Received:2010-07-15 Revised:2010-11-02 Online:2011-02-25 Published:2012-12-20
  • Contact: QI Ming-yao

被引次数

31

摘要： 带时间窗的车辆路径问题是典型的NP难题，一种常用的求解方法是先对顾客分组,后进行路径优化的两阶段启发式算法. 传统算法在顾客分组时主要考虑顾客的空间位置关系，但是忽略了顾客对服务时间窗口的要求. 本文同时考虑顾客的时间和空间特性，提出了一种基于时空度量的顾客分组方法. 在路径优化阶段，本文提出了一种禁忌搜索算法来进行求解，该算法中禁忌的对象不是解，而是这些解的目标函数值的区间，以便于提高收敛效率. 作为验证，本文以Solomon标杆问题集为算例进行演算，结果表明，在窄时间窗约束下，基于时空距离的两阶段启发式算法明显优于基于空间距离的算法，且部分算例的解达到了国内外已发表的最好解.

关键词: 物流工程, 时空距离, 禁忌搜索算法, 车辆路径问题, 两阶段启发式算法, 广义指派问题

Abstract: Vehicle Routing Problem with Time Windows (VRPTW) is a well known NP-hard problem. A typical way to solve this problem is to partition the customers into groups first and then construct optimal routes for each group or groups. Conventionally, customers are partitioned according to the spatial distance only, while ignoring their time window requirements. In this paper, we consider jointly spatial and temporal characteristics of customers and propose a spatiotemporal distance based criteria for customers partitioning. To improve the initial solution, a tabu search algorithm is developed. To improve the convergence efficiency, this algorithm limits the objective value ranges that around the recently visited solutions, Instead of limiting recently visited solutions, the performance of the proposed algorithm is examined with Solomon benchmark problems. The results indicate that spatiotemporal distance is more effective than spatial distance when solving vehicle routing problems with narrow time windows. Some results are even comparable to the best results obtained so far.

Key words: logistics engineering, spatiotemporal distance, tabu search algorithm, vehicle routing problem, two-phase heuristic algorithm, generalized assignment problem

中图分类号: