交通运输系统工程与信息

交通运输系统工程与信息 ›› 2008, Vol. 8 ›› Issue (1): 113-117 .

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

带时间窗的多车型多费用车辆路径问题的模型和算法

陶胤强;牛惠民*   

  1. 兰州交通大学 交通运输学院，兰州 730070
  • 收稿日期:2007-07-23 修回日期:2007-10-20 出版日期:2008-02-25 发布日期:2008-02-25
  • 通讯作者: 牛惠民
  • 作者简介:陶胤强（1974-），男，安徽合肥人，硕士生.

Model and Heuristic Algorithim for the Multi-type Vehicles Routing Problem with Multiple Costs and Time Windows Limits

TAO Yin-qiang ;NIU Hui-min   

  1. School of Traffic and Transportation，Lanzhou Jiaotong University，Lanzhou 730070，China
  • Received:2007-07-23 Revised:2007-10-20 Online:2008-02-25 Published:2008-02-25
  • Contact: NIU Hui-min

PDF

被引次数

27

摘要： 创新性地考虑了多车型车辆路径问题中不同车型具有不同的边际费用和行驶费用的问题，并同时考虑车型与任务的相容性，对带时间窗约束的多车型多费用非满载车辆路径问题，以最小化总费用为目标建立了数学模型。由于该模型的NP-hard性质，基于高费用车型的边际费用和单位行驶费用比低费用车型的相应费用都要高以及低费用车型的边际费用远大于高费用车型的单位行驶费用的思想，对该模型设计了一个启发式算法。

关键词: 车辆路径问题, 多车型, 多费用, 相容性, 时间窗, 排序, 启发式算法

Abstract: In this paper, using multiple-type vehicles to collect or deliver cargos with time windows and non-full loads vehicle routing problem is innovatively considered that different type vehicles have different marginal costs and travel costs. The compatibility constraints among vehicle types and cargos are also considered. Mathematical model aims at minimize the total cost for the problem is then presented. Because of the NP-hard attribute of the model, a new heuristic is designed based on the idea that the marginal cost and the unit travel cost of high-cost vehicle are higher than those of low-cost vehicle and the marginal cost of low-cost vehicle is still much higher than the unit travel cost of high-cost vehicle.

Key words: vehicle routing problem;multiple-type vehicles;multiple costs;compatibility constraints, time windows;ranking;heuristic

中图分类号: