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

doi:10.3724/SP.J.1087.2012.03042

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

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

潘立军¹,符卓²

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-jun¹,FU Zhuo²

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

摘要/Abstract

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

中图分类号:

O22
TP18

潘立军符卓. 求解带硬时间窗车辆路径问题的时差插入启发式算法[J]. 计算机应用, 2012, 32(11): 3042-3070.

PAN Li-jun FU Zhuo. Time difference insertion heuristics algorithm for vehicle routing problem with hard time window[J]. Journal of Computer Applications, 2012, 32(11): 3042-3070.

[1]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[2]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[3]	林剑, 叶璟轩, 刘雯雯, 邵晓雯. 求解带容量约束车辆路径问题的多模态差分进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2248-2254.
[4]	肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2926-2935.
[5]	刘亚平, 张惠珍, 张莉, 刘优优. 带时间窗同时送取货选址路径问题及其烟花算法求解[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2292-2300.
[6]	刘志硕, 刘若思, 陈哲. 基于混合蚁群算法的冷链电动汽车车辆路径问题[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3244-3251.
[7]	徐郁, 朱韵攸, 刘筱, 邓雨婷, 廖勇. 基于深度强化学习的电力物资配送多目标路径优化[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3252-3258.
[8]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[9]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[10]	李华峰, 黄樟灿, 张蔷, 湛航, 谈庆. 求解需求可拆分车辆路径问题的改进的金字塔演化策略[J]. 计算机应用, 2021, 41(1): 300-306.
[11]	张庆华, 吴光谱. 带时间窗的同时取送货车辆路径问题建模及模因求解算法[J]. 计算机应用, 2020, 40(4): 1097-1103.
[12]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.
[13]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[14]	张玉州, 徐廷政, 郑军帅, 饶舜. 考虑紧急度的救灾车辆路径问题建模与优化[J]. 计算机应用, 2019, 39(8): 2444-2449.
[15]	王吉祥, 过弋, 戚天梅, 王志宏, 李真, 汤敏伟. 嵌入互联网舆情强度的人民币汇率预测[J]. 计算机应用, 2019, 39(11): 3403-3408.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics