带时间窗的同时取送货车辆路径问题求解算法

doi:10.3969/j.issn.1007-7375.2021.05.009

工业工程 ›› 2021, Vol. 24 ›› Issue (5): 72-76.doi: 10.3969/j.issn.1007-7375.2021.05.009

带时间窗的同时取送货车辆路径问题求解算法

闫军¹, 常乐², 王璐璐², 赵彤³

1. 兰州交通大学甘肃省物流与信息技术研究院，甘肃兰州 730070;
2. 兰州交通大学机电技术研究所，甘肃兰州 730070;
3. 呼和浩特铁路局集团公司包头货运中心，内蒙古包头 014000

收稿日期:2020-04-08 发布日期:2021-11-02
作者简介:闫军(1971—)，男，甘肃省人，高级工程师，硕士，主要研究方向为协同物流及动态规划
基金资助:
甘肃省自然科学基金资助项目(148RJZA049)；甘肃省教育厅战略研究资助项目(2018F-08)

A Solution Algorithm for the Problem of Taking Delivery Vehicle Path at the Same Time with Time Window

YAN Jun¹, CHANG Le², WANG Lulu², ZHAO Tong³

1. Gansu Institute of Logistics and Information Technology;
2. Mechatronics T&R-Institute, Lanzhou Jiaotong University, Lanzhou 730070, China;
3. Baotou Freight Center, Hohhot Railway Bureau Group Company, Baotou 014000, China

Received:2020-04-08 Published:2021-11-02

摘要/Abstract

摘要： 为了整合物流配送过程的退货与送货服务，依据实际情况建立带时间窗的同时取送货车辆路径规划模型，设计一种基于K-means聚类处理的Q-Leaning自启发式蚁群算法解决此类问题。根据配送服务的特性，在基本的K-means算法上作相应的改进，同时提高蚁群算法的局部搜索能力，完成两算法的合理衔接。选用相关文献数据和标准算例进行实验，验证所提算法具有较好的性能，可以解决所描述的此类问题。

关键词: 车辆路径问题, 取送货问题, 时间窗, 蚁群算法

Abstract: In order to integrate the return and delivery service in the process of logistics and distribution, a vehicle routing model with time window is established according to the actual situation, and a Q-learning self-heuristic ant colony algorithm based on K-means clustering processing is designed to solve such problems. According to the characteristics of distribution service, by improving the basic k-means algorithm, the local search ability of the ant colony algorithm is improved, and the reasonable connection of the two algorithms completed. Experiments are carried out according to the relevant literature data and standard examples to verify that the proposed algorithm has good performance and can solve the described problems.

Key words: vehicle routing problem, pickup and delivery problem, time windows, ant colony algorithm

中图分类号:

TP301.6

闫军, 常乐, 王璐璐, 赵彤. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76.

YAN Jun, CHANG Le, WANG Lulu, ZHAO Tong. A Solution Algorithm for the Problem of Taking Delivery Vehicle Path at the Same Time with Time Window[J]. Industrial Engineering Journal, 2021, 24(5): 72-76.

参考文献

[1] 江海, 陈峰. 面向快递同城运输的车辆路径问题研究[J]. 工业工程, 2019, 22(4): 58-63
JIANG Hai, CHEN Feng. A study of vehicle routing problem for urban transport of express[J]. Industrial Engineering Journal, 2019, 22(4): 58-63
[2] WANG L Y, SONG Y B. Multiple charging station location routing problem with time window of electric vehicle[J]. Journal of Engineering Science and Technology Review, 2015, 8(5): 190-201
[3] DUMAS Y, DESROSIERS J, SOUMIS F. The pickup and delivery problem with time windows[J]. European Journal of Operational Research, 1991, 54(1): 7-22
[4] FURTADO M G S, MUNARI P, MORABITO R. Pickup and delivery problem with time windows: a new compact two-index formulation[J]. Operations Research Letters, 2017, 45(4): 334-341
[5] NANRY W P, BARNES J W. Solving the pickup and delivery problem with time windows using reactive tabu search[J]. Transportation Research Part B: Methodological, 2000, 34(2): 107-121
[6] LI H, LIM A. A met heuristic for the pickup and delivery problem with time windows[J]. International Journal on Artificial Intelligence Tools, 2003, 12(2): 173-186
[7] 吴璟莉. 求解复杂有时间窗装卸货问题的遗传算法[J]. 计算机应用, 2006, 26(6): 1459-1462
WU Jingli. Genetic algorithm for solving the complex pickup and delivery problem with time windows[J]. Computer Applications, 2006, 26(6): 1459-1462
[8] NAGATA Y, KOBAYASHI S. Guided ejection search for the pickup and delivery problem with time windows[C]// European Conference on Evolutionary Computation in Combinatorial Optimization. Berlin, Heidelberg: Springer, 2010: 202-213.
[9] ZOU S, LI J, LI X. A hybrid particle swarm optimization algorithm for multi-objective pickup and delivery problem with time windows[J]. Journal of Computers, 2013, 8(10): 2583-2590
[10] TCHOUPO M N, YALAOUI A, AMODEO L, et al. Ant colony optimization algorithm for pickup and delivery problem with time windows[C/OL]// Internationl Conference on Optimization and Decision Science. Sorrento: Springer, 2017 [2017-11-05]. https://link.springer.com/chapter/10.1007/978-3-319-67308-0_19.
[11] MARCO D, LUCA M G. A study of some properties of ANT-Q[C]// The Proceedings of PPSN IV–Fourth International Conference on Parallel Problem Solving from Nature. Berlin: Springer-Verlag, 1996: 656–665.
[12] 周世兵, 徐振源, 唐旭清. K-means算法最佳聚类数确定方法[J]. 计算机应用, 2010, 30(8): 1995-1998
ZHOU Shibing, XU Zhenyuan, TANG Xuqing. Method for determining optimal number of clusters in K-means clustering algorithm[J]. 计算机应用, 2010, 30(8): 1995-1998
[13] 孙彧, 曹雷, 陈希亮, 等. 多智能体深度强化学习研究综述[J]. 计算机工程与应用, 2020, 56(5): 13-24
SUN Yu, CAO Lei, CHEN Xiliang, et al. Overview of multi-agent deep reinforcement learning[J]. Computer Engineering and Applications, 2020, 56(5): 13-24
[14] WANG H F, CHEN Y Y. A genetic algorithm for the simultaneous delivery and pickup problems with time window[J]. Computers & Industrial Engineering, 2012, 62(1): 84-95
[15] 王超, 刘超, 穆东, 等. 基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[J]. 计算机集成制造系统, 2018, 24(3): 570-582
WANG Chao, LIU Chao, MU Dong, et al. VRPSPDTW problem solving by discrete cuckoo search[J]. Computer Integrated Manufacturing Systems, 2018, 24(3): 570-582

带时间窗的同时取送货车辆路径问题求解算法

A Solution Algorithm for the Problem of Taking Delivery Vehicle Path at the Same Time with Time Window

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	刘电霆, 胡浩平, 吴丹玲. 社会化产品开发众包设计任务间加权网络建模与模块划分[J]. 工业工程, 2021, 24(5): 95-100.
[2]	周游, 朱文斌. 大规模基站运维优化与车队规划研究[J]. 工业工程, 2021, 24(3): 115-120,160.
[3]	王宁, 张玉萍, 赵姣, 金子阳. 考虑碳排放及时间窗的LIRP模型与算法研究[J]. 工业工程, 2021, 24(2): 34-42.
[4]	李玉民, 邱梦, 黑柏林, 方曾利. 考虑高铁时间窗和客户满意度的生鲜品公铁联运路径选择[J]. 工业工程, 2021, 24(2): 49-56.
[5]	周晓晔, 马小云, 崔瑶, 王思聪. 单线超市车辆配置与路径问题优化研究[J]. 工业工程, 2020, 23(6): 83-88,116.
[6]	李博威, 户佐安, 贾叶子, 唐诗韵. 带软时间窗的同时取送货车辆路径问题研究[J]. 工业工程, 2020, 23(5): 75-81.
[7]	芦娟, 夏扬坤, 邹安全, 符卓, 王松, 魏占国, 符瑛. 带装载能力的需求依背包拆分车辆路径问题[J]. 工业工程, 2019, 22(6): 67-73.
[8]	江海, 陈峰. 面向快递同城运输的车辆路径问题研究[J]. 工业工程, 2019, 22(4): 58-63.
[9]	冯春, 秦冰芳, 叶露. 共享电动车电池配送问题研究[J]. 工业工程, 2019, 22(3): 52-56.
[10]	户佐安, 贾叶子, 李博威, 刘陆. 考虑客户满意度的车辆路径优化研究[J]. 工业工程, 2019, 22(1): 100-107.
[11]	王维军, 罗伟. 基于改进智能水滴算法的冷链物流配送路径优化问题研究[J]. 工业工程, 2017, 20(2): 38-43.
[12]	周娜, 舒帆, 金佩卿. 基于混合启发式算法的设备混合布局问题[J]. 工业工程, 2017, 20(1): 77-82.
[13]	朱婷1，王旭磊2，赵来军1. 带时间窗的时变多目标危险化学品道路运输路径优化[J]. 工业工程, 2016, 19(2): 62-67.
[14]	阮焕1，耿亮1,2，肖人彬1. 基于极值—蚁群算法的电商末端物流弹性配送策略研究[J]. 工业工程, 2016, 19(1): 51-60.
[15]	何利娟1, 李欣2. 基于蚁群算法的资源均衡优化决策及其MATLAB实现[J]. 工业工程, 2015, 18(6): 125-129.