Fixed fleet open vehicle routing problem: Mathematical model and a modified ant colony optimization

• Autorzy: Yousefikhoshbakht Majid , Didehvar Farzad , Rahmati Farhad , Ahmed Zakir Hussain

Identyfikatory

DOI

10.24425/bpasts.2023.148253

• Języki publikacji: EN

Abstrakty

EN

The fixed fleet heterogeneous open vehicle routing problem (HFFOVRP) is one of the most practical versions of the vehicle routing problem (VRP) defined because the use of rental vehicles reduces the cost of purchasing and routing for shipping companies nowadays. Also, applying a heterogeneous fleet is recommended due to the physical limitations of the streets and efforts to reduce the running costs of these companies. In this paper, a mixed-integer linear programming is proposed for HFFOVRP. Because this problem, like VRP, is related to NP-hard issues, it is not possible to use exact methods to solve real-world problems. Therefore, in this paper, a hybrid algorithm based on the ant colony algorithm called MACO is presented. This algorithm uses only global updating pheromones for a more efficient search of feasible space and considers a minimum value for pheromones on the edges. Also, pheromones of some best solutions obtained so far are updated, based on the quality of the solutions at each iteration, and three local search algorithms are used for the intensification mechanism. This method was tested on several standard instances, and the results were compared with other algorithms. The computational results show that the proposed algorithm performs better than these methods in cost and CPU time. Besides, not only has the algorithm been able to improve the quality of the best-known solutions in nine cases but also the high-quality solutions are obtained for other instances.

Słowa kluczowe

EN

open vehicle routing problem; heterogeneous; ant colony optimization; combinatorial optimization problems

PL

optymalizacja kolonii mrówek; heterogeniczność; otwarty problem wyznaczania tras pojazdów; problem optymalizacji kombinatorycznej

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2024
• Tom: Vol. 72, nr 1
• Strony: art. no. e148253
• Opis fizyczny: Bibliogr. 26 poz., rys., tab.

Twórcy

autor

Yousefikhoshbakht Majid

• Department of Mathematics, Faculty of Sciences, Bu-Ali Sina University, Hamedan, Iran

• https://orcid.org/0000-0003-1965-1594

autor

Didehvar Farzad

• Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

autor

Rahmati Farhad

• Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

autor

Ahmed Zakir Hussain

• Department of Mathematics and Statistics, College of Science, Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, Kingdom of Saudi Arabia

Bibliografia

• [1] Z.H. Ahme and M. Yousefikhoshbakht, “An improved tabu search algorithm for solving heterogeneous fixed fleet open vehicle routing problem with time windows,” Alex. Eng. J., vol. 64, pp. 349–363, 2023, doi: 10.1016/j.aej.2022.09.008.
• [2] M. Yousefikhoshbakht, N. Malekzadeh, and M. Sedighpour, “Solving the traveling salesman problem based on the genetic reactive bone route algorithm whit ant colony system,” Int. J. Prod. Manag. Engineering, vol. 4, no. 2, pp. 65–73, 2016.
• [3] F. Maleki and M. Yousefikhoshbakht, “A hybrid algorithm for the open vehicle routing problem,” International Journal of Optimization in Civil Engineering, vol. 9, no. 2, pp. 355–371, 2019.
• [4] B. Guan, Y. Zhao, and Y. Li, “An improved ant colony optimization with an automatic updating mechanism for constraint satisfaction problems,” Expert Syst. Appl., vol. 164, p. 114021, Feb. 2021, doi: 10.1016/j.eswa.2020.114021.
• [5] M. Yousefikhoshbakht and A. Dolatnejad, “A column generation for the heterogeneous fixed fleet open vehicle routing problem,” Int. J. Prod. Manag. Eng., vol. 5, no. 2, pp. 55–71, 2017.
• [6] M. Yousefikhoshbakht, E. Mahmoodabadi, and M. Sedighpour, “A modified elite ACO based avoiding premature convergence for traveling salesmen problem,” J. Ind. Eng. Int., vol. 7, no. 15, pp. 68–75, 2011.
• [7] T. Pichpibul, and R. Kawtummachai, “A heuristic approach based on clarke-wright algorithm for open vehicle routing problem,” Sci. World J., vol. 2013, p. 874349, 2013, doi: 10.1155/2013/874349.
• [8] L. Schrage, “Formulation and structure of more complex/realistic routing and scheduling problems,” Networks, vol. 11, no. 2, pp. 229–232, 1981, doi: 10.1002/net.3230110212.
• [9] S.J. Raff, “Routing and scheduling of vehicles and crews,” Comput. Oper. Res., vol. 10, no. 2, pp. 63–211, Jan. 1983, doi: 10.1016/0305-0548(83)90030-8.
• [10] C.D. Tarantilis, D. Diakoulaki, and C.T. Kiranoudis, “Combination of geographical information system and efficient routing algorithms for real life distribution operations,” Eur. J. Oper. Res., vol. 152, no. 2, pp. 437–453, Jan. 2004, doi: 10.1016/s0377-2217(03)00035-3.
• [11] C.D. Tarantilis, G.N. Ioannou, C.T. Kiranoudis, and G.P. Prastacos, “Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm,” J. Oper. Res. Soc., vol. 56, no. 5, pp. 588–596, May 2005, doi: 10.1057/palgrave.jors.2601848.
• [12] A. Mor and M. G. Speranza, “Vehicle routing problems over time: a survey,” Ann. Oper. Res., vol. 314, no. 1, pp. 255-275, 2022.
• [13] F. Li, B. Golden, and E. Wasil, “The open vehicle routing problem: Algorithms, large-scale test problems, and computational results,” Comput. Oper. Res., vol. 34, no. 10, pp. 2918–2930, Oct. 2007, doi: 10.1016/j.cor.2005.11.018.
• [14] K. Corona-Gutiérrez, S. Nucamendi-Guillén, and E. Lalla-Ruiz, “Vehicle routing with cumulative objectives: A state of the art and analysis,” Comput. Ind. Eng., vol. 169, p. 108054, 2022.
• [15] M. Salari, P. Toth, and A. Tramontani, “An ILP improvement procedure for the Open Vehicle Routing Problem,” Comput. Oper. Res, vol. 37, no. 12, pp. 2106–2120, Dec. 2010, doi: 10.1016/j.cor.2010.02.010.
• [16] S.A. MirHassani and N. Abolghasemi, “A particle swarm optimization algorithm for open vehicle routing problem,” Expert Syst. Appl., vol. 38, no. 9, pp. 11547–11551, Sep. 2011, doi: 10.1016/j.eswa.2011.03.032.
• [17] J. Brandão, “A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem,” Eur. J. Oper. Res., vol. 284, no. 2, pp. 559–571, Jul. 2020, doi: 10.1016/j.ejor.2020.01.008.
• [18] X. Li, S.C.H. Leung, and P. Tian, “A multi start adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem,” Expert Syst. Appl., vol. 39, pp. 365–374, 2012.
• [19] M. Yousefikhoshbakht, F. Didehvar, and F. Rahmati, “Solving the heterogeneous fixed fleet open vehicle routing problem by a combined metaheuristic algorithm,” Int. J. Prod. Res., vol. 52, no. 9, pp. 2565–2575, Nov. 2013, doi: 10.1080/00207543.2013.855337.
• [20] M. Yousefikhoshbakht, F. Didehvar, and F. Rahmati, “A mixed integer programming formulation for the heterogeneous fixed fleet open vehicle routing problem,” J. Optim. Ind. Eng., vol. 8, no. 18, pp. 37–46, 2015.
• [21] F. Nakhaei, M. Irannajad, and M. Yousefikhoshbakht, “Flotation column performance optimisation based on imperialist competitive algorithm,” Int. J. Min. Miner. Eng., vol. 7, no. 1, pp. 1–17, 2016.
• [22] F. Nakhaei, M. Irannajad, and M. Yousefikhoshbakht, “Simultaneous optimization of flotation column performance using genetic evolutionary algorithm,” Physicochem. Probl. Miner. Proc., vol. 52, no. 2, pp. 874–893, Jun. 2016, doi: 10.5277/ppmp160228.
• [23] A. Rahmani, and M. Yousefikhoshbakht, “Capacitated facility location problem in random fuzzy environment: using (𝛼, 𝛽)-cost minimization model under the Hurwicz criterion”, J. Intell. Fuzzy Syst., vol. 25, no. 4, pp. 953–964, 2013.
• [24] J. Kochańska, A. Burduk, D. Łapczyńska, and K. Musiał, “The solution of MRSLP with the use of heuristicalgorithms,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 72, no. 1, p. e146407, doi: 10.24425/bpasts.2023.146407.
• [25] M. Yousefikhoshbakht, A. Dolatnejad, F. Didehvar, and F. Rahmati, “A Modified Column Generation to Solve the Heterogeneous Fixed Fleet Open Vehicle Routing Problem,” J. Eng., vol. 2016, p. 5692792, 2016, doi: 10.1155/2016/5692792.
• [26] É. Taillard, “Parallel iterative search methods for vehicle routing problems,” Networks, vol. 23, no. 8, pp. 661–673, Dec. 1993, doi: 10.1002/net.3230230.

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).