The ant colony optimization algorithm applied in transport logistics

• Autorzy: Ostrowski Krzysztof , Starzec Mateusz , Starzec Grażyna

Identyfikatory

DOI

10.7494/csci.2024.25.3.6360

• Języki publikacji: EN

Abstrakty

EN

The Vehicle Routing Problem belongs to graph optimization and its goal is to find shortest routes visiting a given set of customers with additional constraints present. The article presents the ant colony optimization metaheuristic which solves vehicle routing problems and its real-life application in transport logistics (finding routes for delivery companies). The metaheuristic generated high-quality solutions (superior to compared methods). Our tool is flexible and enables us to solve various variants of routing problems so it is well suited to specific needs of transportation companies.

Słowa kluczowe

EN

ant colony optimization; ACO; metaheuristic; routing problems; transport logistics; delivery

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2024
• Tom: T. 25 (3)
• Strony: 331--350
• Opis fizyczny: Bibliogr. 31 poz., rys., tab., wykr.

Twórcy

autor

Ostrowski Krzysztof

• Bialystok University of Technology, Faculty of Computer Science, ul. Wiejska 45A,15-351 Bialystok, Sentio sp. z o.o., ul. Warszawska 6/32, 15-063 Bialystok

autor

Starzec Mateusz

• Sentio sp. z o.o., ul. Warszawska 6/32, 15-063 Bialystok

autor

Starzec Grażyna

• AGH University, Faculty of Computer Science, al. Adama Mickiewicza 30, 30-059 Krakow,Sentio sp. z o.o., ul. Warszawska 6/32, 15-063 Bialystok

Bibliografia

• [1] Ai J., Kachitvichyanukul V.: A Particle Swarm Optimisation for Vehicle Routing Problem with Time Windows, International Journal of Operational Research, vol. 6(4), pp. 519–537, 2009. doi: 10.1504/ijor.2009.027156.
• [2] Alvarez A., Munari P.: Metaheuristic approaches for the vehicle routing problem ´ with time windows and multiple deliverymen, Gest˜ao & Produ¸c˜ao, vol. 23(2), pp. 279–293, 2016.
• [3] Araque J.R., Kudva G., Morin T.L., Pekny J.F.: A branch-and-cut algorithm for vehicle routing problems, Annals of Operations Research, vol. 50, pp. 37–59, 1994. doi: 10.1007/bf02085634.
• [4] Balakrishnan N.: Simple heuristics for the vehicle routing problem with soft time windows, The Journal of the Operational Research Society, vol. 44(3), pp. 279–287, 1993. doi: 10.1038/sj/jors/0440308.
• [5] Bellmore M., Nemhauser G.L.: The Traveling Salesman Problem: A Survey, Operation Research, vol. 16, pp. 538–558, 1986.
• [6] Br¨aysy O.: Fast local searches for the vehicle routing problem with time windows, Information Systems and Operations Research, vol. 41, pp. 319–330, 2003.
• [7] Br¨aysy O., Gendreau M.: Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms, Transportation Science, vol. 39(1), pp. 104–118, 2005. doi: 10.1287/trsc.1030.0056.
• [8] Clarke G.U., Wright J.W.: Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, vol. 12(4), pp. 568–581, 1964. http://www.jstor.org/stable/167703.
• [9] CVRPLIB Capacitated Vehicle Routing Problem Library. Online: http: / / vrp.galgos.inf.puc-rio.br/index.php/en/. [10] Dantzig G.B., Ramser J.H.: The truck dispatching problem, Management Science, vol. 6, pp. 80–91, 1959. doi: 10.1287/mnsc.6.1.80
• [11] Di Puglia Pugliese L., Ferone D., Festa P., Guerriero F., Macrina G.: Combining variable neighborhood search and machine learning to solve the vehicle routing problem with crowd-shipping, Optimization Letters, vol. 17, pp. 1981–2003, 2023. doi: 10.1007/s11590-021-01833-x.
• [12] Dorigo M., St¨utzle T.: Ant Colony Optimization, The MIT Press, Cambridge, 2004.
• [13] Gendreau M., Hertz A., Laporte G.: A Tabu Search Heuristic for the Vehicle Routing Problem, Management Science, vol. 40(10), pp. 1207–1393, 1994. doi: 10.1287/mnsc.40.10.1276.
• [14] Gmira M., Gendreau M., Lodi A., Potvin J.Y.: Tabu search for the timedependent vehicle routing problem with time windows on a road network, European Journal of Operational Research, vol. 288, pp. 129–140, 2021. doi: 10.1016/ j.ejor.2020.05.041.
• [15] Homberger J., Gehring H.: A two-phase hybrid metaheuristic for the vehicle routing problem with time windows, European Journal of Operations Research, vol. 62, pp. 220–238, 2005. doi: 10.1016/j.ejor.2004.01.027.
• [16] Ibrahim A.A., Lo N., Abdulaziz R.O., Ishaya J.A.: Capacitated Vehicle Routing Problem, International Journal of Research – Granthaalayah, vol. 7(3), pp. 310–327, 2019. doi: 10.29121/granthaalayah.v7.i3.2019.976.
• [17] Kek A.G.H., Cheu R.L., Meng Q.: Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots, Mathematical and Computer Modelling, vol. 47(1–2), pp. 140–152, 2008. doi: 10.1016/ j.mcm.2007.02.007.
• [18] Lau H.C., Sim M., Teo K.M.: Vehicle routing problem with time windows and a limited number of vehicles, European Journal of Operational Research, vol. 148, pp. 559–569, 2003. doi: 10.1016/s0377-2217(02)00363-6.
• [19] Lenstra J.K., Rinnooy Kan A.H.G.: Computational Complexity of Discrete Optimization Problems, Annals of Discrete Mathematics, vol. 4, pp. 121–140, 1979. doi: 10.1016/s0167-5060(08)70821-5.
• [20] de Melo Menezes B.A., Herrmann N., Kuchen H., de Lima Neto F.B.: HighLevel Parallel Ant Colony Optimization with Algorithmic Skeletons, International Journal of Parallel Programming, vol. 49, pp. 776–801, 2021. doi: 10.1007/ s10766-021-00714-1.
• [21] Niu Y., Shao J., Xiao J., Song W., Cao Z.: Multi-objective evolutionary algorithm based on RBF network for solving the stochastic vehicle routing problem, Information Sciences, vol. 609, pp. 387–410, 2022. doi: 10.1016/j.ins.2022.07.087.
• [22] Openroute Service. Online: https://openrouteservice.org/.
• [23] OR-Tools. Online: https://developers.google.com/optimization.
• [24] Ostrowski K., Karbowska-Chilinska J., Koszelew J., Zabielski P.: Evolutioninspired local improvement algorithm solving orienteering problem, Annals of Operations Research, vol. 253, pp. 519–543, 2017. doi: 10.1007/s10479-016-2278-1.
• [25] Prins C.: A simple and effective evolutionary algorithm for the vehicle routing problem, Computers and Operations Research, vol. 31(12), pp. 1985–2002, 2004. doi: 10.1016/s0305-0548(03)00158-8.
• [26] Qi R., Li J.Q., Wang J., Jin H., Han Y.Y.: QMOEA: A Q-learning-based multiobjective evolutionary algorithm for solving time-dependent green vehicle routing problems with time windows, Information Sciences, vol. 608, pp. 178–201, 2022. doi: 10.1016/j.ins.2022.06.056.
• [27] Starzec M., Starzec G., Byrski A., Turek W.: Distributed ant colony optimization based on actor model, Parallel Computing, vol. 90(1), 102573, 2019. doi: 10.1016/ j.parco.2019.102573.
• [28] St¨utzle T.: Parallelization strategics for Ant Colony Optimization, Lecture Notes in Computer Science, vol. 1498, pp. 722–731, 1998.
• [29] Tan K.C., Lee K.O.: Artificial intelligence heuristics in solving vehicle routing problems with time window constraints, The Engineering Applications of Artificial Intelligence, vol. 14, pp. 825–837, 2001. doi: 10.1016/s0952-1976(02)00011-8.
• [30] TRASA – development and validation of algorithms for routes optimization and resources allocation. Online: https://getsent.io/en/projects/trasa.
• [31] Voudouris C., Tsang E.P., Alsheddy A.: Guided Local Search. In: M. Gendreau, J.Y. Potvin (eds.), Handbook of Metaheuristics, pp. 321–361, Springer, 2010.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).