Vehicle routing optimization algorithm based on time windows and dynamic demand

Abstract

To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand, customer cancellation service, and change of customer delivery address, based on the ideas of pre-optimization and real-time optimization, a two-stage planning model of dynamic demand based vehicle routing problem with time windows was established. At the pre-optimization stage, an improved genetic algorithm was used to obtain the pre-optimized distribution route, a large-scale neighborhood search method was integrated into the mutation operation to improve the local optimization performance of the genetic algorithm, and a variety of operators were introduced to expand the search space of neighborhood solutions; At the real-time optimization stage, a periodic optimization strategy was adopted to transform a complex dynamic problem into several static problems, and four neighborhood search operators were used to quickly adjust the route. Two different scale examples were designed for experiments. It is proved that the algorithm can plan the better route, and adjust the distribution route in time under the real-time constraints. Therefore, the proposed algorithm can provide theoretical guidance for suppliers to solve the dynamic demand based vehicle routing problem.

Keywords

vehicle routing problem / dynamic demand / genetic algorithm / large-scale neighborhood search / time windows

References

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem. Management Science, 1959, 6(1): 80-91.

[2] ZHOU X C, WANG L, ZHOU K J, et al. Research progress and development trend of dynamic vehicle routing problem. Control and Decision, 2019, 34(3): 449-458.

[3] LI J, HAO L Y, HE Y T, et al. Improved bacterial foraging algorithm for solving vehicle routing optimization problem with time windows. Computer Engineering, 2021, 47(11): 44-53.

[4] LI Y, FAN H M, ZHANG X N. A periodic optimization model and solution for capacitated vehicle routing problem with dynamic requests. Chinese Journal of Management Science, 2022, 30(8): 254-266.

[5] ZHANG J L, ZHAO Y W, WANG H Y, et al. Modeling and algorithms for a dynamic multi-vehicle routing problem with Customers' dynamic requests. Computer Integrated Manufacturing Systems, 2010, 16(3): 543-550.

[6] FAN H M, ZHANG Y G, TIAN P J, et al. Dynamic vehicle routing problem of heterogeneous fleets with time- dependent networks. System Engineering-Theory & Practice, 2022, 42(2): 455-470.

[7] PANG Y, LUO H L, XING L N, et al. A survey of vehicle routing optimization problems and solution methods. Control Theory & Applications, 2019, 36(10): 1573-1584.

[8] WANG F, LIAO F S, LI Y X, et al. An ensemble learning based multi-objective evolutionary algorithm for the dynamic vehicle routing problem with time windows. Computers & Industrial Engineering, 2021, 154: 107131.

[9] NAN L J, CHEN Y R, ZHANG Z C. Electric vehicle routing problem with time windows and mixed fleet considering dynamic demands. Application Research of Computers, 2021, 38(10): 2926-2934.

[10] ZHANG W B, SU Q, CHENG G L. Vehicle routing problem with time windows based on dynamic demands. Industrial Engineering and Management, 2016, 21(6): 68-74.

[11] YANG Y, ZHANG J. Vehicle routing problem with soft time windows based on dynamic demands// 2019 4th International Conference on Intelligent Transportation Engineering, September 5-7, 2019, Singapore. New York: IEEE, 2019: 222-226.

[12] SCHYNS M. An ant colony system for responsive dynamic vehicle routing. European Journal of Operational Research, 2015, 245(3): 704-718.

[13] LU X F, TANG K, MENZEL S, et al. A competitive co-evolutionary optimization method for the dynamic vehicle routing problem//2020 IEEE Symposium Series on Computational Intelligence, December 1-4, 2020, Canberra, ACT, Australia. New York: IEEE, 2020: 305-312.

[14] EUCHI J, YASSINE A, CHABCHOUB H. The dynamic vehicle routing problem: Solution with hybrid metaheuristic approach. Swarm and Evolutionary Computation, 2015, 21: 41-53.

[15] CHEN S F, CHEN R, WANG G G, et al. An adaptive large neighborhood search heuristic for dynamic vehicle routing problems. Computers & Electrical Engineering, 2018, 67: 596-607.

[16] OKULEWICZ M, MAŃDZIUK J. A metaheuristic approach to solve Dynamic Vehicle Routing Problem in continuous search space. Swarm and Evolutionary Computation, 2019, 48: 44-61.

[17] HE X H. Research on dynamic vehicle routing problem with soft time window and system implementation. Harbin:Harbin Institute of Technology, 2017.

[18] JIANG D J, LIU X W. Two-echelon vehicle routing optimization with time windows and “gray zone” customers based on LNS alogorithm. Journal of Chongqing Normal University (Natural Science), 2020, 37 (4): 15-23.