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

doi:10.3969/j.issn.1007-7375.2021.05.009

Abstract

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

CLC Number:

TP301.6

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.

References

[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