AI-Powered Software Testing for Heterogeneous Fleet Vehicle Routing Optimization with Time Constraints
DOI:
https://doi.org/10.71222/fybwaw94Keywords:
campus path planning, dynamic environments, time windows, Vehicle Routing ProblemAbstract
The Vehicle Routing Problem (VRP) is crucial in logistics, transportation, and distribution. Traditional VRP focuses on optimizing vehicle routes between a fixed starting point and multiple locations to minimize travel distance or time. However, these models perform inadequately in dynamic environments such as campus student path planning, which involve diverse movement patterns and time window constraints. This paper addresses campus student path planning as a Heterogeneous Fleet Vehicle Routing Problem with Time Windows (HFVRPTW) and introduces the Scooter-Aware Pathfinding with Time Windows (SAPTW) method. Students start from random points and navigate a grid-based campus to fixed destinations like dormitories and cafeterias, choosing either walking or using electric scooters available at specific locations. This study tackles key challenges including diverse movement modes, time windows for reaching destinations, automatic generation of campus maps, and random generation of student starting points and destinations. Additionally, ensuring AI-powered software testing, we developed the Grid-based Campus Map Randomized Generation (GMRG) method, a rule-based approach for creating grid maps with roads, obstacles, and specific buildings. This method provides a realistic and controlled environment for route planning tests and simulations, ensuring the robustness and reliability of the proposed solution in real-world applications. Our approach highlights the potential of integrating artificial intelligence with software testing to optimize complex routing problems with time constraints. Simulation results demonstrate that SAPTW significantly enhances student arrival efficiency, reducing average arrival time by approximately 3% to 44% compared to traditional methods.
References
1. G. D. Konstantakopoulos, S. P. Gayialis and E. P. Kechagias, "Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification," Oper. Res. Int. J., vol. 22, pp. 2033–2062, 2022, doi: 10.1007/s12351-020-00600-7.
2. G. Laporte, "Fifty years of vehicle routing," Transp. Sci., vol. 43, no. 4, pp. 408–416, 2009, doi: http://doi.org/10.1287/trsc.1090.0301.
3. M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints," Oper. Res., vol. 35, no. 2, pp. 254–265, 1987, doi: 10.1287/opre.35.2.254.
4. B. L. Golden, A. A. Assad, L. Levy and F. Gheysens, "The fleet size and mix vehicle routing problem," Comput. Oper. Res., vol. 11, no. 1, pp. 49–66, 1984, doi: 10.1016/0305-0548(84)90007-8.
5. M. Nazari, A. Oroojlooy, L. V. Snyder and M. Takác, "Reinforcement learning for solving the vehicle routing problem," Adv. Neural Inf. Process. Syst., vol. 31, pp. 9839–9849, 2018.
6. V. Ghilas, E. Demir and T. Van Woensel, "An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines," Comput. Oper. Res., vol. 72, pp. 12–30, 2016, doi: 10.1016/j.cor.2016.01.018.
7. L. Abbatecola, M. P. Fanti and W. Ukovich, "A review of new approaches for Dynamic Vehicle Routing Problem," in Proc. IEEE Int. Conf. Autom. Sci. Eng. (CASE), Fort Worth, TX, USA, 2016, pp. 361–366, doi: 10.1109/COASE.2016.7743429.
8. Q. Lu, T. Tettamanti, D. Hörcher and I. Varga, "The impact of autonomous vehicles on urban traffic network capacity: an ex-perimental analysis by microscopic traffic simulation," Transp. Lett., vol. 12, no. 8, pp. 540–549, 2019, doi: 10.1080/19427867.2019.1662561.
9. P. Toth and D. Vigo, "Branch-and-bound algorithms for the capacitated VRP," in The Vehicle Routing Problem, Philadelphia, PA, USA: SIAM, 2002, pp. 29–51, doi: 10.1137/1.9780898718515.ch2.
10. R. Bellman, "Dynamic programming treatment of the travelling salesman problem," J. ACM, vol. 9, no. 1, pp. 61–63, 1956, doi: 10.1145/321105.321111.
11. J.-F. Cordeau and G. Laporte, "A branch-and-cut algorithm for the dial-a-ride problem," Oper. Res., vol. 51, no. 5, pp. 831–844, 2002, doi: 10.1287/opre.1060.0283.
12. J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Arti-ficial Intelligence, Cambridge, MA, USA: MIT Press, 1992. ISBN: 9780262581110.
13. S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp. 671–680, 1983, doi: 10.1126/science.220.4598.671.
14. F. Glover, "Tabu search—Part I," ORSA J. Comput., vol. 1, no. 3, pp. 190–206, 1989, doi: 10.1287/ijoc.1.3.190.
15. M. Dorigo, V. Maniezzo and A. Colorni, "Ant system: optimization by a colony of cooperating agents," IEEE Trans. Syst., Man, Cybern., Part B (Cybern.), vol. 26, no. 1, pp. 29–41, Feb. 1996, doi: 10.1109/3477.484436.
16. H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina and L. Song, "Learning combinatorial optimization algorithms over graphs," arXiv preprint arXiv:1704.01665, 2017, doi: 10.48550/arXiv.1704.01665.
17. W. Kool, H. van Hoof and M. Welling, "Attention, learn to solve routing problems!" arXiv preprint arXiv:1803.08475, 2018, doi: 10.48550/arXiv.1803.08475.
18. I. Bello, H. Pham, Q. V. Le, M. Norouzi and S. Bengio, "Neural combinatorial optimization with reinforcement learning," arXiv preprint arXiv:1611.09940, 2016, doi: 10.48550/arXiv.1611.09940.
19. H. Mao, M. Alizadeh, I. Menache and S. Kandula, "Resource management with deep reinforcement learning," arXiv preprint arXiv:1605.06676, 2016, doi: 10.1145/3005745.3005750.
20. S. Panigrahi, A. Nanda and T. Swarnkar, "A survey on transfer learning," in Intelligent and Cloud Computing, D. Mishra, R. Buyya, P. Mohapatra and S. Patnaik, Eds., Singapore: Springer, 2021, vol. 194, Smart Innov. Syst. Technol., pp. 871–883, doi: 10.1007/978-981-15-5971-6_83.
21. M. Okulewicz and J. Mańdziuk, "Application of Particle Swarm Optimization Algorithm to Dynamic Vehicle Routing Prob-lem," in Artificial Intelligence and Soft Computing. ICAISC 2013, L. Rutkowski, M. Korytkowski, R. Scherer, R. Tadeusiewicz, L.A. Zadeh, and J.M. Zurada, Eds., vol. 7895, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 2013, pp. 423–434, doi: 10.1007/978-3-642-38610-7_50.
22. F. Hutter, H. H. Hoos, K. Leyton-Brown and T. Stützle, "ParamILS: An automatic algorithm configuration framework," J. Artif. Intell. Res., vol. 36, pp. 267–306, 2009, doi: 10.1613/jair.2861.
23. R. Shahbazian, L. D. P. Pugliese, F. Guerriero and G. Macrina, "Integrating machine learning into vehicle routing problem: Methods and applications," IEEE Access, vol. 12, pp. 93087–93115, 2024, doi: 10.1109/ACCESS.2024.3422479.
