A Study on the Vehicle Routing Problem Considering Infeasible Routing Based on the Improved Genetic Algorithm

Xiao-Yun Jiang; Wen-Chao Chen; Yu-Tong Liu

doi:10.46604/ijeti.2023.12612

Authors

Xiao-Yun Jiang School of Economics and Management, Xiamen University of Technology, Fujian, China
Wen-Chao Chen School of Economics and Management, Xiamen University of Technology, Fujian, China
Yu-Tong Liu School of Economics and Management, Xiamen University of Technology, Fujian, China

DOI:

https://doi.org/10.46604/ijeti.2023.12612

Keywords:

vehicle routing problem, infeasible routing, hard time window, genetic algorithm

Abstract

The study aims to optimize the vehicle routing problem, considering infeasible routing, to minimize losses for the company. Firstly, a vehicle routing model with hard time windows and infeasible route constraints is established, considering both the minimization of total vehicle travel distance and the maximization of customer satisfaction. Subsequently, a Floyd-based improved genetic algorithm that incorporates local search is designed. Finally, the computational experiment demonstrates that compared with the classic genetic algorithm, the improved genetic algorithm reduced the average travel distance by 20.6% when focusing on travel distance and 18.4% when prioritizing customer satisfaction. In both scenarios, there was also a reduction of one in the average number of vehicles used. The proposed method effectively addresses the model introduced in this study, resulting in a reduction in total distance and an enhancement of customer satisfaction.

References

G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, vol. 6, no. 1, pp. 80-91, October 1959.

M. M. Solomon, “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operations Research, vol. 35, no. 2, pp. 254-265, March-April 1987.

P. Cappanera, C. Requejo, and M. G. Scutella, “Temporal Constraints and Device Management for the Skill VRP: Mathematical Model and Lower Bounding Techniques,” Computers & Operations Research, vol. 124, article no. 105054, December 2020.

Y. Wang, L. Wang, G. C. Chen, Z. Q. Cai, Y. Q. Zhou, and L. N. Xing, “An Improved Ant Colony Optimization Algorithm to the Periodic Vehicle Routing Problem with Time Window and Service Choice,” Swarm and Evolutionary Computation, vol. 55, article no. 100675, June 2020.

L. Zhen, C. L. Ma, K. Wang, L. Y. Xiao, and W. Zhang, “Multi-Depot Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates,” Transportation Research Part E-Logistics and Transportation Review, vol. 135, article no. 101866, March 2020.

D. A. Neira, M. M. Aguayo, R. De la Fuente, and M. A. Klapp, “New Compact Integer Programming Formulations for the Multi-Trip Vehicle Routing Problem with Time Windows,” Computers & Industrial Engineering, vol. 144, article no. 106399, June 2020.

A. Bortfeldt and J. M. Yi, “The Split Delivery Vehicle Routing Problem with Three-Dimensional Loading Constraints,” European Journal of Operational Research, vol. 282, no. 2, pp. 545-558, April 2020.

Y. Yao, X. N. Zhu, H. Y. Dong, S. N. Wu, H. L. Wu, L. C. Tong, et al., “ADMM-Based Problem Decomposition Scheme for Vehicle Routing Problem with Time Windows,” Transportation Research Part B-Methodological, vol. 129, pp. 156-174, November 2019.

V. Q. Hien, T. C. Dao, and H. T. T. Binh, “A Greedy Search Based Evolutionary Algorithm for Electric Vehicle Routing Problem,” Applied Intelligence, vol. 53, no. 3, pp. 2908-2922, February 2023.

F. E. Zulvia, R. J. Kuo, and D. Y. Nugroho, “A Many-Objective Gradient Evolution Algorithm for Solving a Green Vehicle Routing Problem with Time Windows and Time Dependency for Perishable Products,” Journal of Cleaner Production, vol. 242, article no. 118428, January 2020.

O. Dominguez, A. A. Juan, B. Barrios, J. Faulin, and A. Agustin, “Using Biased Randomization for Solving the Two-Dimensional Loading Vehicle Routing Problem with Heterogeneous Fleet,” Annals of Operations Research, vol. 236, no. 2, pp. 383-404, January 2016.

X. H. Cai, L. Jiang, S. H. Guo, H. J. Huang, and H. W. Du, “TLHSA and SACA: Two Heuristic Algorithms for Two Variant VRP Models,” Journal of Combinatorial Optimization, vol. 44, no. 4, pp. 2996-3022, November 2022.

M. Salavati-Khoshghalb, M. Gendreau, O. Jabali, and W. Rei, “A Hybrid Recourse Policy for the Vehicle Routing Problem with Stochastic Demands,” EURO Journal on Transportation and Logistics, vol. 8, no. 3, pp. 269-298, 2019.

P. Xu, Q. X. Liu, and Y. H. Wu, “Energy Saving-Oriented Multi-Depot Vehicle Routing Problem with Time Windows in Disaster Relief,” Energies, vol. 16, no. 4, article no. 1992, February 2023.

G. Kim, “Dynamic Vehicle Routing Problem with Fuzzy Customer Response,” Sustainability, vol. 15, no. 5, article no. 4376, March 2023.

S. F. Ghannadpour, S. Noori, R. Tavakkoli-Moghaddam, and K. Ghoseiri, “A Multi-Objective Dynamic Vehicle Routing Problem with Fuzzy Time Windows: Model, Solution and Application,” Applied Soft Computing, vol. 14, pp. 504-527, January 2014.

H. Yao, “Application of Artificial Intelligence Algorithm in Mathematical Modelling and Solving,” Applied Mathematics and Nonlinear Sciences, vol. 7, no. 1, pp. 449-456, January 2022.

Y. Xue, Q. Sun, C. Li, W. Dang, and F. Hao, “Distribution Network Monitoring and Management System Based on Intelligent Recognition and Judgement,” Applied Mathematics and Nonlinear Sciences, vol. 7, no. 1, pp. 685-694, January 2022.

P. Shaw, “A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems,” APES Group, Dept of Computer Science, University of Strathclyde, Working paper, July 14, 1997.