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

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

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

陶胤强;牛惠民^*

兰州交通大学交通运输学院，兰州 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

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

摘要/Abstract

摘要： 创新性地考虑了多车型车辆路径问题中不同车型具有不同的边际费用和行驶费用的问题，并同时考虑车型与任务的相容性，对带时间窗约束的多车型多费用非满载车辆路径问题，以最小化总费用为目标建立了数学模型。由于该模型的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

中图分类号:

TP301.6

陶胤强,牛惠民. 带时间窗的多车型多费用车辆路径问题的模型和算法[J]. 交通运输系统工程与信息, 2008, 8(1): 113-117 .

TAO Yin-qiang,NIU Hui-min. Model and Heuristic Algorithim for the Multi-type Vehicles Routing Problem with Multiple Costs and Time Windows Limits[J]. Journal of Transportation Systems Engineering and Information Technology, 2008, 8(1): 113-117 .

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract17626.shtml

http://www.tseit.org.cn/CN/Y2008/V8/I1/113

[1]	高万晨, 路世昌, 赵娅彤, 刘锴. 考虑分段充电策略的电动公交时刻表和车辆调度整体优化[J]. 交通运输系统工程与信息, 2025, 25(6): 239-248.
[2]	程佳豪, 郝志丹, 李国旗, 刘思婧. 卡车-冲锋舟协同的山区洪灾应急物资配送多目标优化[J]. 交通运输系统工程与信息, 2025, 25(6): 294-304.
[3]	王彦, 王则恺, 宋美霞, 方力萱. 中转时间不确定下冷藏集装箱多式联运路径优化研究[J]. 交通运输系统工程与信息, 2025, 25(5): 124-134.
[4]	刘长石, 万城, 王凤, 陈宝玺, 岳俊羽. 基于救援效用的洪灾物资配送与灾民转移路径规划[J]. 交通运输系统工程与信息, 2025, 25(5): 320-332.
[5]	郭姝娟, 许骁, 刘智, 董彦鹭, 华梦颖, 彭康真. 考虑东北海陆大通道的中欧多式联运路径选择研究[J]. 交通运输系统工程与信息, 2025, 25(3): 32-43.
[6]	刘长石, 万城, 王凤, 刘光洪, 陈宝玺. 洪涝灾害下考虑受灾点差异的应急物资分配-配送优化[J]. 交通运输系统工程与信息, 2025, 25(3): 335-345.
[7]	徐伟汉, 李欣, 王天奇. 基于生态驾驶的常规和需求响应公交混合调度方法[J]. 交通运输系统工程与信息, 2025, 25(2): 227-240.
[8]	高攀, 黄柳森, 赵旭. 考虑转港调度的内河港口群多泊位联合配置策略[J]. 交通运输系统工程与信息, 2025, 25(2): 328-337.
[9]	段力伟, 杨航, 陈坚. 考虑枢纽延误的集装箱公铁联运多目标路径优化[J]. 交通运输系统工程与信息, 2024, 24(6): 275-285.
[10]	熊杰, 梁晶晶, 李向楠, 窦雪萍, 李同飞. 考虑分时电价和多车型的电动公交行车计划优化[J]. 交通运输系统工程与信息, 2024, 24(4): 188-199.
[11]	何美玲, 杨梅, 韩珣, 武晓晖. 带时间窗的时间依赖型同时取送货车辆路径问题研究[J]. 交通运输系统工程与信息, 2024, 24(4): 231-242.
[12]	张燕, 李子鑫, 刘进平. 考虑工作量平衡的餐饮垃圾多行程收运路线优化[J]. 交通运输系统工程与信息, 2023, 23(6): 239-249.
[13]	宋丽英, 赵世超, 卞骞, 杜鹏, 沈鹏举. 低碳视角下城乡区域混合车队生鲜配送路径问题研究[J]. 交通运输系统工程与信息, 2023, 23(6): 250-261.
[14]	辛禹辰, 李润超, 杨华龙. 基于等待策略的同时送取货车辆路径问题干扰管理研究[J]. 交通运输系统工程与信息, 2023, 23(5): 155-161.
[15]	任婧璇, 常孝亭, 巫威眺, 靳文舟. 考虑候选站点和全服务过程的需求响应接驳公交调度[J]. 交通运输系统工程与信息, 2023, 23(5): 202-214.