Logo PTI Logo FedCSIS

Communication Papers of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 45

Smart Routes: Hybrid Metaheuristics for Efficient Vehicle Routing Problem

, ,

DOI: http://dx.doi.org/10.15439/2025F2457

Citation: Communication Papers of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 45, pages 103–110 ()

Full text

Abstract. This article presents a hybrid algorithm developed to solve the Vehicle Routing Problem with Time Windows (VRPTW), which involves finding optimal routes for a fleet of vehicles serving a set of geographically dispersed customers within specified time intervals. The proposed solution combines Ant Colony Optimization (ACO) as the primary method for global solution construction, with the 2-opt local search technique used for route refinement, and a Tabu Search strategy to escape local optima and further improve solution quality. The algorithm dynamically adapts pheromone levels to favor both spatial and temporal proximity between customers, enhancing decision making during route construction. Experimental results demonstrate that the hybrid approach yields high-quality solutions, significantly improving known results by up to 30\% in some cases, while maintaining reasonable computation times. This makes the algorithm well-suited for real-time logistics scenarios where time efficiency and solution accuracy are both critical.

References

  1. A. Schirjver, On the history of combinatorial optimization (till 1960). In: K. Aardal, G.L. Nemhauser, R. Weismantel (Eds.), Handbook of Discrete Optimization, 2005, Amsterdam.
  2. C. Rego, D. Gamboa, F. Glover, C. Osterman, Traveling salesman problem heuristics: leading methods, implementations and latest advances, European Journal of Operational Research, 20144, vol. 211 (3).
  3. G.B. Dantzig, J.H. Ramser, The Truck Dispatching Problem, 1959, Management Science, vol. 6 (1).
  4. G. Ghiani, G. Laporte, R. Musmanno, Introduction to Logistics Systems Management (2nd ed.), 2013, Wiley.
  5. P. Toth, D. Vigo, The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications, 2001, SIAM, Philadelphia.
  6. G. A. Croes, A method for solving traveling-salesman problems, 1958, Operations Research, vol. 6(6), pp. 791–812, https://doi.org/10.1287/opre.6.6.791
  7. S. Lin, Computer solutions of the traveling salesman problem, 1965, Bell System Technical Journal, vol. 44(10), pp. 2245–2269, urlhttps://doi.org/10.1002/j.1538-7305.1965.tb04146.x.
  8. N. Christofides, A. Mingozzi, P. Toth, The vehicle routing problem, In Combinatorial Optimization, 1979, Wiley, pp. 315–338.
  9. F. Uddin, N. Riaz, A. Manan, I. Mahmood, O.-Y. Song, A.J. Malik, A.A. Abbasi, An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour, 2023, Applied Sciences, 13(12):7339, urlhttps://doi.org/10.3390/ app13127339
  10. M. Dorigo, V. Maniezzo, A. Colorni, Ant system: Optimization by a colony of cooperating agents, (1996, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26(1), pp. 29–41, https://doi.org/10.1109/3477.484436
  11. K. F. Doerner, R.F. Hartl, M. Reimann, Metaheuristics for the vehicle routing problem with loading constraints, 2006, Networks, vol. 49(4), pp. 294–307.
  12. J. Ochelska-Mierzejewska, Ant Colony Optimization Algorithm for Split Delivery Vehicle Routing Problem, In International Conference on Advanced Information Networking and Applications (was ICOIN), 2020, https://link.springer.com/chapter/10.1007/978-3-030-44041-1_67.
  13. F. Glover, Future paths for integer programming and links to artificial intelligence, 1986, Computers and Operations Research, vol. 13(5), pp. 533–549, https://doi.org/10.1016/0305-0548(86)90048-1
  14. J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, F. Semet, A guide to vehicle routing heuristics, 2001, Journal of the Operational Research Society, vol. 53(5), pp. 512–522, urlhttps://doi.org/10.1057/palgrave.jors.2601319
  15. M. Gendreau, A. Hertz, G. Laporte, A tabu search heuristic for the vehicle routing problem, 1994, Management Science, vol. 40(10), pp. 1276–1290, urlhttps://doi.org/10.1287/mnsc.40.10.1276
  16. J. Ochelska-Mierzejewska, Tabu Search Algorithm for Vehicle Routing Problem with Time Windows, 2020, https://link.springer.com/chapter/10.1007/978-3-030-34706-2_7. DOI: 10.1007/978-3-030-34706-2_7.
  17. N. Paisarnvirosrak, P. Rungrueang, Firefly Algorithm with Tabu Search to Solve the Vehicle Routing Problem with Minimized Fuel Emissions: Case Study of Canned Fruits Transport, 2023, LOGI – Sci- entific Journal on Transport and Logistics, vol. 14(1), pp. 263–274, https://doi.org/10.2478/logi-2023-0024.
  18. X. Ma, C. Liu, Improved Ant Colony Algorithm for the Split Delivery Vehicle Routing Problem, 2024, Applied Science, vol 14(5090, https://doi.org/10.3390/app14125090
  19. L.M. Gambardella, É.D. Taillard, G. Agazzi, MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows, In D. Corne, M. Dorigo, F. Glover (Eds.), New ideas in optimization, 1999, McGraw-Hill, pp. 63–76.
  20. M. Tadaros, N.A. Kyriakakis, A Hybrid Clustered Ant Colony Optimization Approach for the Hierarchical Multi-Switch Multi-Echelon Vehicle Routing Problem with Service Times, 2024, Computers & Industrial Engineering, https://diva-portal.org/smash/get/diva2:1802273/FULLTEXT01.pdf
  21. J.B. Holliday, E. Osaba, K. Luu, An Advanced Hybrid Quantum Tabu Search Approach to Vehicle Routing Problem, 2025, https://arxiv.org/pdf/2501.12652v1
  22. Z. Zheng, B. Ji, S.S. Yu, An Adaptive Tabu Search Algorithm for Solving the Two-Dimensional Loading Constrained Vehicle Routing Problem with Stochastic Customers, 2023, Sustainability, vol. 15(2), 1741, https://www.mdpi.com/2071-1050/15/2/1741
  23. Y. Liu, Z. Wang, J. Liu, A Quick Pheromone Matrix Adaptation Ant Colony Optimization for Dynamic Customers in the Vehicle Routing Problem, 2024, vol. 12(7), 1167, https://doi.org/10.3390/jmse12071167
  24. Google Colaboratory, 2024, https://colab.research.google.com/
  25. M. Solomon, Solomon VRPTW Benchmark, 1987, http://w.cba.neu.edu/~msolomon/problems.htm
  26. Top, VRPTW for 100 customers, 2008, https://www.sintef.no/projectweb/top/vrptw/100-customers/