An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem

Year 2022, Volume: 9 Issue: 4, 263 - 273, 31.12.2022

Emrehan Yavşan , İlhan İlhan

https://doi.org/10.17350/HJSE19030000279

Abstract

This work focuses on the capacitated vehicle routing problem. In this work, a real-time application is developed using online real-world data for mobile devices have IOS and Android operating systems. The fuzzy c-means clustering algorithm is used to group the demand points and the ant colony optimization algorithm is employed to determine the best route within each group. The customer demand points and distances between these points are obtained via Google Places and Google Directions APIs. The deviations in the route that result from the environmental and road conditions are identified immediately with the help of global positioning system technology allowing the route suggestions to be made. The developed application was evaluated on two datasets for testing. The test results showed that this real-time application can be used to find the optimum route for the capacitated vehicle routing problem and follow the route optimally.

Keywords

Ant Colony Optimization, Fuzzy C-Means, Global Positioning System, Mobile Devices, Real Time Application, Vehicle Routing Problem

References

• R.H. Ballou, Business Logistics/supply Chain Management: Planning, Organizing, and Controlling the Supply Chain, Bus. Logist. (2004).
• A. Rushton, P. Croucher, P. Baker, The handbook of logistics and distribution management, Proj. Manag. J. (2006).
• G.B. Dantzig, J.H. Ramser, The Truck Dispatching Problem, Manage. Sci. (1959).
• J. Euchi, S. Zidi, L. Laouamer, A Hybrid Approach to Solve the Vehicle Routing Problem with Time Windows and Synchronized Visits In-Home Health Care, Arab. J. Sci. Eng. 45 (2020) 10637–10652.
• C.H. Häll, H. Andersson, J.T. Lundgren, P. Värbrand, I. Nedregård, Paolo Toth & Daniele Vigo, I. Nedregård, O. Gurobi, E. Pimpler, J. Laflaquiere, U.M. Sundar, C. Yang, J.F. Cordeau, M. Posada, Vehicle Routing, Public Transp. 1 (2006) 573–586.
• Z. Bozyer, A. Alkan, A. Fığlalı, Cluster-First, Then-Route Based Heuristic Algorithm for the Solution of Capacitated Vehicle Routing Problem, Int. J. Informatics Technol. (2014).
• L. Santos, J. Coutinho-Rodrigues, C.H. Antunes, A web spatial decision support system for vehicle routing using Google Maps, Decis. Support Syst. (2011).
• B. Yu, Z.Z. Yang, B. Yao, An improved ant colony optimization for vehicle routing problem, Eur. J. Oper. Res. (2009).
• H. Harmanani, D. Azar, N. Helal, W. Keirouz, A simulated annealing algorithm for the capacitated vehicle routing problem, Proc. ISCA 26th Int. Conf. Comput. Their Appl. CATA 2011. (2011).
• H. Nazif, L.S. Lee, Optimised crossover genetic algorithm for capacitated vehicle routing problem, Appl. Math. Model. (2012).
• S.Z. Zhang, C.K.M. Lee, An Improved Artificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem, in: Proc. - 2015 IEEE Int. Conf. Syst. Man, Cybern. SMC 2015, 2016.
• B.E. Teoh, S.G. Ponnambalam, G. Kanagaraj, Differential evolution algorithm with local search for capacitated vehicle routing problem, Int. J. Bio-Inspired Comput. (2015).
• Mohammed MA, Ghani MKA, Hamed RI, Mostafa SA, Ibrahim DA, Jameel HK, Alallah AH. Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution, J. Comput. Sci. 21 (2017) 232–240.
• Rabbouch B, Saâdaoui F, Mraihi R. Empirical-type simulated annealing for solving the capacitated vehicle routing problem, J. Exp. Theor. Artif. Intell. 32 (2020) 437–452.
• Altabeeb AM, Mohsen AM, Ghallab A. An improved hybrid firefly algorithm for capacitated vehicle routing problem, Appl. Soft Comput. J. 84 (2019) 105728.
• İlhan İ. An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem, Swarm Evol. Comput. (2021).
• E. Osaba, X.-S. Yang, J. Del Ser, Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics, in: Nature-Inspired Comput. Swarm Intell., 2020.
• İ. İlhan, An Application on Mobile Devices with Android and IOS Operating Systems Using Google Maps APIs for the Traveling Salesman Problem, Appl. Artif. Intell. 31 (2017) 332–345.
• P. Toth, D. Vigo, Exact Solution of the Vehicle Routing Problem, in: Fleet Manag. Logist., 1998.
• M. Dell’Amico, G. Righini, M. Salani, A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection, Transp. Sci. (2006).
• P. Toth, D. Vigo, An exact algorithm for the vehicle routing problem with backhauls, Transp. Sci. (1997).
• D. Vigo, A heuristic algorithm for the asymmetric capacitated vehicle routing problem, Eur. J. Oper. Res. (1996).
• J.C. Bezdek, R. Ehrlich, W. Full, FCM: The fuzzy c-means clustering algorithm, Comput. Geosci. (1984).
• G.R. van Brummelen, Heavenly Mathematics: The Forgotten Art of Spherical Trigonometry, 2013.
• M. Dorigo, Optimization, Learning and Natural Algorithms, Ph.D. Thesis, Politec. Di Milano. (1992). https://cir.nii.ac.jp/crid/1573668926038702080.bib?lang=ja (accessed May 22, 2022).
• P. Augerat, J.M. Belenguer, E. Benavent, A. Corberán, D. Naddef, G. Rinaldi, Computational results with a branch-and-cut code for the capacitated vehicle routing problem, Inst. Syst. Comput. Anal. (1995).
• N. Christofides, S. Eilon, An Algorithm for the Vehicle-Dispatching Problem, OR. (1969).