Modeling open vehicle routing problem with real life costs and solving via hybrid civilized genetic algorithm

Year 2024, Volume: 42 Issue: 3, 714 - 730, 12.06.2024

Erhan Tonbul Melis Alpaslan Takan , Gamze Tuna Büyükköse , Nihal Erginel

Abstract

Many companies prefer to use third party logistics firms to deliver their goods and as such planning the return of the vehicles to the depot is not required. This is called open vehicle routing problem (OVRP). In literature, the OVRP is handled with minimum distance as objective function like vehicle routing problem. But in the real world, the objective function achieves minimum many costs like standard routing cost, stopping by cost and the deviation cost. The standard routes are previously defined under free market conditions by third party logistic firms. The deviation from the standard route is required to arrive cities which are not on the standard route. The stop by cost occurs on the delivery points. In this paper mentioned three costs are considered in the objective function while many papers consider only distance related costs in the literature. This paper proposes a new mathematical model for the OVRP. In the constraints, the last points of the routes are researched in detail. The standard route costs are determined by considering the last point of the route. Because of the NP-hard structure of the OVRP, the proposed mathematical model is solved with a hybrid metaheuristic called Civilized Genetic Algorithm (CGA). CGA is developed by hybridizing a modified genetic algorithm and a local search algorithm. The application of this study is implemented for the delivery routing of a combi boiler producer in Turkey. The third party logistic firms may use this proposed model and the solution approach for the real life applications.

Keywords

Genetic Algorithm, Hybrid Metaheuristic, Open Vehicle Routing Problem, Real Life Transportation Costs

References

• [1] Dantzig GB, Ramser JH. The truck dispatching problem. Manag Sci 1959;6:80–91. [CrossRef]
• [2] Ombuki B, Nakamura M, Maeda O. A hybrid search based on genetic algorithms and tabu search for vehicle routing. Proceedings of 6th IASTED International Conference on Artificial Intelligence and Soft Computing; 2002 May; Canada. 2002. pp. 176181.
• [3] Awad H, Elshaer R, AbdElmo’ez A, Nawara, G. An effective genetic algorithm for capacitated vehicle routing problem. Proceedings of the International Conference on Industrial Engineering and Operations Management; 2018 Mar 6–8; Bandung, Indonesia. IEOM Society International; 2018. pp. 374–384.
• [4] Cordeau JF, Gendreau M, Laporte G. A tabu search heuristic for periodic and multi‐depot vehicle routing problems. Netw Int J 1997;30:105–119. [CrossRef]
• [5] Brandão J. A tabu search algorithm for the open vehicle routing problem. Eur J Oper Res 2004;157:552–564. [CrossRef]
• [6] Baños R, Ortega J, Gil C, Fernández A, de Toro F. A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows. Expert Syst Appl 2013;40:1696–1707. [CrossRef]
• [7] Kahar NHA, Zobaa, AF. Application of mixed integer distributed ant colony optimization to the design of undamped single-tuned passive filters based harmonics mitigation. Swarm Evol Comput 2018;44:187–199. [CrossRef]
• [8] Goel R, Maini R. Evolutionary ant colony algorithm using firefly based transition for solving vehicle routing problems: EAFA for VRPs. Int J Swarm Intell Res 2019;10:46–60. [CrossRef]
• [9] Yi JH, Wang J, Wang GG. Using Monarch butterfly optimization to solve the emergency vehicle routing problem with relief materials in sudden disasters. Open Geosci 2019;11:391–413. [CrossRef]
• [10] Schrage L. Formulation and structure of more complex/realistic routing and scheduling problems. Netw Int J 1981;11:229–232. [CrossRef]
• [11] Sariklis D, Powell S. A heuristic method for the open vehicle routing problem. J Oper Res Soc 2000;51:564–573. [CrossRef]
• [12] Fu Z, Eglese R, Li LY. Corrigendum to the paper: A new tabu search heuristic for the open vehicle routing problem. J Oper Res Soc 2006;57:1018. [CrossRef]
• [13] Tarantilis CD, Ioannou G, Kiranoudis C, Prastacos G. Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm. J Oper Res Soc 2005;56:588–596. [CrossRef]
• [14] Repoussis PP, Tarantilis CD, Ioannou G. The open vehicle routing problem with time windows. J Oper Res Soc 2007;58:355–367. [CrossRef]
• [15] Pisinger D, Ropke S. A general heuristic for vehicle routing problems. Comput Oper Res 2007;34:2403–2435. [CrossRef]
• [16] Li F, Golden B, Wasil EA. The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Comput Oper Res 2007;34:2918– 2930. [CrossRef]
• [17] Pessoa A, De Aragao MP, Uchoa E. Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems. In: Golden B, Raghavan S, Wasil E, editors. The vehicle routing problem: Latest advances and new challenges. 1st ed. Boston, MA: Springer; 2008. p. 297–325. [CrossRef]
• [18] Derigs U, Reuter K. A simple and efficient tabu search heuristic for solving the open vehicle routing problem. J Oper Res Soc 2009;60:1658–1669. [CrossRef]
• [19] Fleszar K, Osman IH, Hindi KS. A variable neighbourhood search algorithm for the open vehicle routing problem. Eur J Oper Res 2009;195:803–809. [CrossRef]
• [20] Zachariadis EE, Kiranoudis CT. An open vehicle routing problem metaheuristic for examining wide solution neighborhoods. Comput Oper Res 2010;37:712–723. [CrossRef]
• [21] Erbao C, Mingyong L. The open vehicle routing problem with fuzzy demands. Expert Syst Appl 2010;37:2405–2411. [CrossRef]
• [22] MirHassani SA, Abolghasemi N. A particle swarm optimization algorithm for open vehicle routing problem. Expert Syst Appl 2011;38:11547–11551. [CrossRef]
• [23] Li X, Leung SC, Tian P. A multistart adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem. Expert Syst Appl 2012;39:365–374. [CrossRef]
• [24] Marinakis Y, Marinaki M. A bumble bees mating optimization algorithm for the open vehicle routing problem. Swarm Evol Comput 2014;15:80–94. [CrossRef]
• [25] Şevkli AZ, Güler B. A multi-phase oscillated variable neighbourhood search algorithm for a real-world open vehicle routing problem. Appl Soft Comput 2017;58:128–144. [CrossRef]
• [26] Soto M, Sevaux M, Rossi A, Reinholz A. Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem. Comput Ind Eng 2017;107:211–222. [CrossRef]
• [27] Brandão J. Iterated local search algorithm with ejection chains for the open vehicle routing problem with time windows. Comput Ind Eng 2018;120:146–159. [CrossRef]
• [28] Hashemi S, Salari M, Ranjbar M. Multi-trip open vehicle routing problem with time windows: A case study. Int J Ind Eng 2020;27.
• [29] Dasdemir E, Testik MC, Öztürk DT, Şakar CT, Güleryüz G, Testik ÖM. A multi-objective open vehicle routing problem with overbooking: Exact and heuristic solution approaches for an employee transportation problem. Omega 2022;108:102587. [CrossRef]
• [30] Dutta J, Barma PS, Mukherjee A, Kar S, De T. A hybrid multi-objective evolutionary algorithm for open vehicle routing problem through cluster primary-route secondary approach. IntJ Manag Sci Eng Manag 2022;17:132–146. [CrossRef]
• [31] Sun L, Pan QK, Jing XL, Huang JP. A light-robust-optimization model and an effective memetic algorithm for an open vehicle routing problem under uncertain travel times. Memetic Comput 2021;13:149–167. [CrossRef]
• [32] Yu NK, Jiang W, Hu R, Qian B, Wang L. learning whale optimization algorithm for open vehicle routing problem with loading constraints. Discrete Dyn Nat Soc 2021;2021:8016356. [CrossRef]
• [33] Hosseinabadi AAR, Zolfagharian A, Alinezhad P. An Efficient Hybrid Meta-Heuristic Algorithm for Solving the Open Vehicle Routing Problem. In: Recent developments and the new direction in soft-computing foundations and applications. New York: Springer; 2021. p. 257–274. [CrossRef]
• [34] Ruiz E, García-Calvillo I, Nucamendi-Guillén S. Open vehicle routing problem with split deliveries: Mathematical formulations and a cutting-plane method. Oper Res 2020;22:1017–1037. [CrossRef]
• [35] López-Sánchez AD, Hernández-Díaz AG, Vigo D, Caballero R, Molina J. A multi-start algorithm for a balanced real-world open vehicle routing problem. Eur J Oper Res 2014;238:104–113. [CrossRef]
• [36] Niu Y, Yang Z, Chen P, Xiao J. Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost. J Clean Prod 2018;171:962–971. [CrossRef]
• [37] Li Y, Soleimani H, Zohal M. An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. J Clean Prod 2019;227:1161–1172. [CrossRef]
• [38] Vincent FY, Jewpanya P, Redi AP. Open vehicle routing problem with cross-docking. Comput Ind Eng 2016;94:617. [CrossRef]
• [39] Miller CE, Tucker AW, Zemlin RA. Integer programming formulation of traveling salesman problems. Journal ACM 1960;7:326–329. [CrossRef]
• [40] Liu R, Jiang Z, Geng N. A hybrid genetic algorithm for the multi-depot open vehicle routing problem. OR Spect 2014;36:401–421. [CrossRef]
• [41] Holland JH. Adaptation in Natural and Artificial Systems: An introductory Analysis with Applications to Biology, Control, and Artificial intelligence. Michigan: University of Michigan Press; 1975.
• [42] Katoch S, Chauhan SS, Kumar V. A review on genetic algorithm: past, present, and future. Multimed Tools Appl 2021;80:8091–8126. [CrossRef]
• [43] Jebari K, Madiafi M. Selection methods for genetic algorithms. Int J Emerg Sci 2013;3:333–344.
• [44] Soon GK, Guan TT, On CK, Alfred R, Anthony P. A comparison on the performance of crossover techniques in video game. In Proceedings of the 2013 IEEE International Conference on Control System, Computing and Engineering; 2013 Nov 29 — Dec 1; Penang, Malaysi. IEEE; 2013. pp. 493–498. [CrossRef]
• [45] Elmihoub T, Hopgood AA, Nolle L, Battersby A. Performance of hybrid genetic algorithms incorporating local search. In Proceedings of 18th European Simulation Multiconference; 2004 Mar; Erlangen, Germany. Gruner Duck; 2004. pp. 154–160. [CrossRef]
• [46] Espinoza FP, Minsker BS, Goldberg DE. Performance evaluation and population reduction for a self adaptive hybrid genetic algorithm (SAHGA). In Proceedings of Genetic and Evolutionary Computation Conference; 2003 July; Heidelberg, Berlin. Springer; 2003. pp. 922–933. [CrossRef]
• [47] Hedar AR, Fukushima M. Simplex coding genetic algorithm for the global optimization of nonlinear functions. In Proceedings of Multi-Objective Programming and Goal Programming; 2003; Heidelberg, Berlin. Springer; 2003. pp. 135–140. [CrossRef]
• [48] Tan KC, Li Y, Murray-Smith DJ, Sharman KC. System identification and linearisation using genetic algorithms with simulated annealing. In Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications; 1995; Sheffield, UK. IEET; 1995. pp. 164–169. [CrossRef]
• [49] Guo C, Wang C, Zuo X. A genetic algorithm based column generation method for multi-depot electric bus vehicle scheduling. In Proceedings of the Genetic and Evolutionary Computation Conference Companion; 2019 Jul 13–17; Prague, Czech Republic. 2019. pp. 367–368. [CrossRef]
• [50] Luo Y, Pan Y, Li C, Tang H. A hybrid algorithm combining genetic algorithm and variable neighborhood search for process sequencing optimization of large- size problem. Int J Comput Integr Manuf 2020;33:962–981. [CrossRef]
• [51] Augerat P, Belenguer JM, Benavent E, Corberan A, Naddef D, Rinaldi G. Computational results with a branch and cut code for the capacitated vehicle routing problem. Available at: https://www.osti.gov/etdeweb/servlets/purl/289002. Accessed on May 10, 2024.
• [52] Christofides N, Mingozzi A, Toth P. The Vehicle Routing Problem. In: Christofides N, Mingozzi A, Toth P, Sandi C, editors. Combinatorial optimization. Chichester: Wiley; 1979. p. 315–338.