The Vehicle Routing Problem with Time Windows Based on Agent Travel Time: An Exploration of Genetic Algorithm Reproduction Schemes
Received: 28 June 2025 | Revised: 16 September 2025 and 6 October 2025 | Accepted: 9 October 2025 | Online: 8 December 2025
Corresponding author: Diva Kurnianingtyas
Abstract
The Vehicle Routing Problem with Time Windows (VRPTW) is a critical combinatorial optimization problem in modern logistics, where finding optimal routes is essential for minimizing operational costs and enhancing service reliability. While Genetic Algorithms (GAs) are a powerful tool for solving VRPTW, their effectiveness is often undermined by premature convergence, a phenomenon in which the algorithm stagnates at suboptimal solutions, thus failing to achieve maximum efficiency. This study directly addresses this challenge by systematically evaluating how different reproduction schemes impact GA performance. The primary objective is to identify operator combinations that mitigate premature convergence to achieve superior solution quality, measured by total travel time, while also analyzing the trade-off with computational cost. We investigate combinations of conventional operators, such as Tournament Selection (TS) and Order Crossover (OX), against more advanced schemes, including Split Rank Selection (SRS) and Multi-Parent Order Crossover (MPOX), as well as different mutation methods, namely Scramble Mutation (SM) and Inversion Mutation (IM). Results demonstrate that advanced schemes, particularly the combination of SRS, MPOX, and IM, yield the most robust convergence and the lowest average total travel time of 48,422.8 minutes. However, this superior performance requires the longest computation time at 30.9 h. In contrast, conventional operator combinations are significantly faster, with execution times as low as 8.7 h, but they produce lower-quality solutions and exhibit unstable convergence. This study highlights the crucial role of the reproduction scheme in balancing the trade-off between solution quality and computational efficiency, confirming that a synergistic combination of advanced operators is essential for solving complex VRPTW instances effectively.
Keywords:
artificial intelligence, optimization, routing problem, metaheuristics, premature convergenceDownloads
References
H. Zhang, H. Ge, J. Yang, and Y. Tong, "Review of Vehicle Routing Problems: Models, Classification and Solving Algorithms," Archives of Computational Methods in Engineering, vol. 29, no. 1, pp. 195–221, Jan. 2022. DOI: https://doi.org/10.1007/s11831-021-09574-x
L. Wenyi, "Chapter Three - Research on vehicle routing problem and application scenarios," in Handbook of Mobility Data Mining, H. Zhang, Ed. Amsterdam, Netherlands: Elsevier, 2023, pp. 63–88. DOI: https://doi.org/10.1016/B978-0-323-95892-9.00006-1
A. Maroof, B. Ayvaz, and K. Naeem, "Logistics Optimization Using Hybrid Genetic Algorithm (HGA): A Solution to the Vehicle Routing Problem With Time Windows (VRPTW)," IEEE Access, vol. 12, pp. 36974–36989, 2024. DOI: https://doi.org/10.1109/ACCESS.2024.3373699
S. Thammasang and S. Arunyanart, "Efficient Route Optimization for Ice Distribution: Enhanced VRPTW with Customer Retention Strategies," Engineering, Technology & Applied Science Research, vol. 14, no. 5, pp. 16346–16356, Oct. 2024. DOI: https://doi.org/10.48084/etasr.8239
S. N. Kumar and R. Panneerselvam, "A Survey on the Vehicle Routing Problem and Its Variants," Intelligent Information Management, vol. 4, no. 3, pp. 66–74, May 2012. DOI: https://doi.org/10.4236/iim.2012.43010
G. Chen, J. Gao, and D. Chen, "Research on Vehicle Routing Problem with Time Windows Based on Improved Genetic Algorithm and Ant Colony Algorithm," Electronics, vol. 14, no. 4, Feb. 2025, Art. no. 647. DOI: https://doi.org/10.3390/electronics14040647
L. Zeng and Z. Wang, "Research on Vehicle Routing Optimization Based on VRPTW," Theoretical and Natural Science, vol. 97, no. 1, pp. 21–28, Mar. 2025. DOI: https://doi.org/10.54254/2753-8818/2025.21231
X. Liu, Y.-L. Chen, L. Y. Por, and C. S. Ku, "A Systematic Literature Review of Vehicle Routing Problems with Time Windows," Sustainability, vol. 15, no. 15, Aug. 2023, Art. no. 12004. DOI: https://doi.org/10.3390/su151512004
R. Fauzi, A. Priansyah, P. K. Puspadewa, S. M. Z. Awal, H. T. Nguyen, and A. P. Rifai, "Optimizing Vehicle Routing for Perishable Products with Time Window Constraints: : A Case Study on Bread Distribution," Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri, vol. 27, no. 1, pp. 1–20, Jan. 2025. DOI: https://doi.org/10.9744/jti.27.1.1-20
H. Hamam, "Rethinking Intelligence: From Human Cognition to Artificial Futures," Vokasi Unesa Bulletin of Engineering, Technology and Applied Science, vol. 2, no. 3, pp. 531–548, Aug. 2025. DOI: https://doi.org/10.26740/vubeta.v2i3.44232
K. Kamsopa, K. Sethanan, T. Jamrus, and L. Czwajda, "Hybrid Genetic Algorithm for Multi-Period Vehicle Routing Problem with Mixed Pickup and Delivery with Time Window, Heterogeneous Fleet, Duration Time and Rest Area," Engineering Journal, vol. 25, no. 10, pp. 71–86, Oct. 2021. DOI: https://doi.org/10.4186/ej.2021.25.10.71
A. Susanti et al., "Application of the Orangutan Optimization Algorithm for Solving Vehicle Routing Problems in Sustainable Transportation Systems," Engineering, Technology & Applied Science Research, vol. 15, no. 3, pp. 22915–22922, June 2025. DOI: https://doi.org/10.48084/etasr.10545
S. Katoch, S. S. Chauhan, and V. Kumar, "A review on genetic algorithm: past, present, and future," Multimedia Tools and Applications, vol. 80, no. 5, pp. 8091–8126, Feb. 2021. DOI: https://doi.org/10.1007/s11042-020-10139-6
A. Sohail, "Genetic Algorithms in the Fields of Artificial Intelligence and Data Sciences," Annals of Data Science, vol. 10, no. 4, pp. 1007–1018, Aug. 2023. DOI: https://doi.org/10.1007/s40745-021-00354-9
G. Pankratz, "A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows," OR Spectrum, vol. 27, no. 1, pp. 21–41, Jan. 2005. DOI: https://doi.org/10.1007/s00291-004-0173-7
S. Mirjalili, "Genetic Algorithm," in Evolutionary Algorithms and Neural Networks: Theory and Applications, Cham, Switzerland: Springer International Publishing, 2019, pp. 43–55. DOI: https://doi.org/10.1007/978-3-319-93025-1_4
H. M. Pandey, A. Chaudhary, and D. Mehrotra, "A comparative review of approaches to prevent premature convergence in GA," Applied Soft Computing, vol. 24, pp. 1047–1077, Nov. 2014. DOI: https://doi.org/10.1016/j.asoc.2014.08.025
A. Hussain and Y. S. Muhammad, "Trade-off between exploration and exploitation with genetic algorithm using a novel selection operator," Complex & Intelligent Systems, vol. 6, no. 1, pp. 1–14, Apr. 2020. DOI: https://doi.org/10.1007/s40747-019-0102-7
B. Alhijawi and A. Awajan, "Genetic algorithms: theory, genetic operators, solutions, and applications," Evolutionary Intelligence, vol. 17, no. 3, pp. 1245–1256, June 2024. DOI: https://doi.org/10.1007/s12065-023-00822-6
A. Lambora, K. Gupta, and K. Chopra, "Genetic Algorithm- A Literature Review," in 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing, Faridabad, India, 2019, pp. 380–384. DOI: https://doi.org/10.1109/COMITCon.2019.8862255
A. K. Das and D. K. Pratihar, "A directional crossover (DX) operator for real parameter optimization using genetic algorithm," Applied Intelligence, vol. 49, no. 5, pp. 1841–1865, May 2019. DOI: https://doi.org/10.1007/s10489-018-1364-2
B. Koohestani, "A crossover operator for improving the efficiency of permutation-based genetic algorithms," Expert Systems with Applications, vol. 151, Aug. 2020, Art. no. 113381. DOI: https://doi.org/10.1016/j.eswa.2020.113381
Y. Xue, H. Zhu, J. Liang, and A. Słowik, "Adaptive crossover operator based multi-objective binary genetic algorithm for feature selection in classification," Knowledge-Based Systems, vol. 227, Sept. 2021, Art. no. 107218. DOI: https://doi.org/10.1016/j.knosys.2021.107218
K. M. Qaiduzzaman et al., "A Mutation Triggering Method for Genetic Algorithm to Solve Traveling Salesman Problem," in 11th Malaysian Technical Universities Conference on Engineering Technology, Singapore, 2019, pp. 159–170. DOI: https://doi.org/10.1007/978-981-15-6025-5_15
L. Manzoni, L. Mariot, and E. Tuba, "Balanced crossover operators in Genetic Algorithms," Swarm and Evolutionary Computation, vol. 54, May 2020, Art. no. 100646. DOI: https://doi.org/10.1016/j.swevo.2020.100646
A. Arram and M. Ayob, "A novel multi-parent order crossover in genetic algorithm for combinatorial optimization problems," Computers & Industrial Engineering, vol. 133, pp. 267–274, July 2019. DOI: https://doi.org/10.1016/j.cie.2019.05.012
M. F. Ibrahim, M. M. Putri, D. Farista, and D. M. Utama, "An Improved Genetic Algorithm for Vehicle Routing Problem Pick-up and Delivery with Time Windows," Jurnal Teknik Industri, vol. 22, no. 1, pp. 1–17, Feb. 2021. DOI: https://doi.org/10.22219/JTIUMM.Vol22.No1.1-17
M. Alolaiwy, T. Hawsawi, M. Zohdy, A. Kaur, and S. Louis, "Multi-Objective Routing Optimization in Electric and Flying Vehicles: A Genetic Algorithm Perspective," Applied Sciences, vol. 13, no. 18, Sept. 2023, Art. no. 10427. DOI: https://doi.org/10.3390/app131810427
B. Meniz and F. Tiryaki, "Genetic algorithm approach to asymmetric capacitated vehicle routing: A case study on bread distribution in Istanbul, Türkiye," Decision Science Letters, vol. 13, no. 3, pp. 605–616, May 2024. DOI: https://doi.org/10.5267/j.dsl.2024.5.002
E. Wibisono and D. N. Prayogo, "Comparison of crossover operators in genetic algorithm for vehicle routing problems," in 2nd Asia Pacific International Conference on Industrial Engineering and Operations Management, Surakarta, Indonesia, 2021, pp. 1580–1589.
I. E. Hammouti, K. Derqaoui, and M. E. Merouani, "A modified clustering search based genetic algorithm for the proactive electric vehicle routing problem," International Journal of Industrial Engineering Computations, vol. 14, no. 4, pp. 609–622, Sept. 2023. DOI: https://doi.org/10.5267/j.ijiec.2023.9.004
O. Roeva, S. Fidanova, and M. Paprzycki, "Influence of the population size on the genetic algorithm performance in case of cultivation process modelling," in 2013 Federated Conference on Computer Science and Information Systems, Krakow, Poland, 2013, pp. 371–376.
E. G. Mahadevan, "Research and Development," in Ammonium Nitrate Explosives for Civil Applications, Hoboken, NJ, USA: John Wiley & Sons, Ltd, 2013, pp. 157–162. DOI: https://doi.org/10.1002/9783527645688.ch7
J. J. Grefenstette, "Optimization of Control Parameters for Genetic Algorithms," IEEE Transactions on Systems, Man, and Cybernetics, vol. 16, no. 1, pp. 122–128, Jan. 1986. DOI: https://doi.org/10.1109/TSMC.1986.289288
V. P. Patil and D. D. Pawar, "The optimal crossover or mutation rates in Genetic algorithm : A Review," International Journal of Applied Engineering and Technology, vol. 5, no. 3, pp. 38–41, July 2015.
N. A. S. Abdullah and S. N. A. M. Razali, "Optimal Parameter Value of Genetic Algorithms for Different Size Instances in Solving Traveling Salesman Problem," Enhanced Knowledge in Sciences and Technology, vol. 4, no. 1, pp. 171–182, Aug. 2024.
I. Moon, J.-H. Lee, and J. Seong, "Vehicle routing problem with time windows considering overtime and outsourcing vehicles," Expert Systems with Applications, vol. 39, no. 18, pp. 13202–13213, Dec. 2012. DOI: https://doi.org/10.1016/j.eswa.2012.05.081
A. Hussain and S. A. Cheema, "A new selection operator for genetic algorithms that balances between premature convergence and population diversity," Croatian Operational Research Review, vol. 11, no. 1, pp. 107–119, July 2020. DOI: https://doi.org/10.17535/crorr.2020.0009
R. Poohoi, K. Puntusavase, and S. Ohmori, "Stas crossover with K-mean clustering for vehicle routing problem with time window," Decision Science Letters, vol. 13, no. 3, pp. 525–534, June 2024. DOI: https://doi.org/10.5267/j.dsl.2024.5.008
K. Q. Zhu, "A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windows," in 15th IEEE International Conference on Tools with Artificial Intelligence, Sacramento, CA, USA, 2003, pp. 176–183. DOI: https://doi.org/10.1109/TAI.2003.1250187
M. BinJubier, M. A. Ismail, M. Othman, S. Kasim, and H. Amnur, "Optimizing Genetic Algorithm by Implementation of An Enhanced Selection Operator," JOIV : International Journal on Informatics Visualization, vol. 8, no. 3–2, pp. 1643–1650, Nov. 2024. DOI: https://doi.org/10.62527/joiv.8.3-2.3449
L. Wang, R. Cai, M. Lin, and Y. Zhong, "Enhanced List-Based Simulated Annealing Algorithm for Large-Scale Traveling Salesman Problem," IEEE Access, vol. 7, pp. 144366–144380, 2019. DOI: https://doi.org/10.1109/ACCESS.2019.2945570
Z. Ahmed, N. Al-Otaibi, A. Al-Tameem, and A. Khader, "Genetic Crossover Operators for the Capacitated Vehicle Routing Problem," Computers, Materials & Continua, vol. 74, no. 1, pp. 1575–1605, Sept. 2022. DOI: https://doi.org/10.32604/cmc.2023.031325
T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, and W. Rei, "A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems," Operations Research, vol. 60, no. 3, pp. 611–624, June 2012. DOI: https://doi.org/10.1287/opre.1120.1048
Downloads
How to Cite
License
Copyright (c) 2025 Haidar Hanif, Yusuf Priyo Anggodo, Diva Kurnianingtyas, Agus Wahyu Widodo, Tutut Herawan
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
