Research Article
PDF EndNote BibTex RIS Cite

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

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

Year 2022, Volume 9, Issue 4, 263 - 273, 31.12.2022
https://doi.org/10.17350/HJSE19030000279

Abstract

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

Details

Primary Language English
Subjects Engineering
Journal Section Research Articles
Authors

Emrehan YAVŞAN> (Primary Author)
Necmettin Erbakan University
0000-0001-9521-4500
Türkiye


İlhan İLHAN>
NECMETTIN ERBAKAN UNIVERSITY
0000-0002-8567-8798
Türkiye

Publication Date December 31, 2022
Submission Date July 14, 2022
Acceptance Date November 16, 2022
Published in Issue Year 2022, Volume 9, Issue 4

Cite

Bibtex @research article { hjse1143907, journal = {Hittite Journal of Science and Engineering}, eissn = {2148-4171}, address = {Hitit Üniversitesi Mühendislik Fakültesi Kuzey Kampüsü Çevre Yolu Bulvarı 19030 Çorum / TÜRKİYE}, publisher = {Hitit University}, year = {2022}, volume = {9}, number = {4}, pages = {263 - 273}, doi = {10.17350/HJSE19030000279}, title = {An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem}, key = {cite}, author = {Yavşan, Emrehan and İlhan, İlhan} }
APA Yavşan, E. & İlhan, İ. (2022). An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem . Hittite Journal of Science and Engineering , 9 (4) , 263-273 . DOI: 10.17350/HJSE19030000279
MLA Yavşan, E. , İlhan, İ. "An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem" . Hittite Journal of Science and Engineering 9 (2022 ): 263-273 <https://dergipark.org.tr/en/pub/hjse/issue/74853/1143907>
Chicago Yavşan, E. , İlhan, İ. "An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem". Hittite Journal of Science and Engineering 9 (2022 ): 263-273
RIS TY - JOUR T1 - An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem AU - EmrehanYavşan, İlhanİlhan Y1 - 2022 PY - 2022 N1 - doi: 10.17350/HJSE19030000279 DO - 10.17350/HJSE19030000279 T2 - Hittite Journal of Science and Engineering JF - Journal JO - JOR SP - 263 EP - 273 VL - 9 IS - 4 SN - -2148-4171 M3 - doi: 10.17350/HJSE19030000279 UR - https://doi.org/10.17350/HJSE19030000279 Y2 - 2022 ER -
EndNote %0 Hittite Journal of Science and Engineering An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem %A Emrehan Yavşan , İlhan İlhan %T An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem %D 2022 %J Hittite Journal of Science and Engineering %P -2148-4171 %V 9 %N 4 %R doi: 10.17350/HJSE19030000279 %U 10.17350/HJSE19030000279
ISNAD Yavşan, Emrehan , İlhan, İlhan . "An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem". Hittite Journal of Science and Engineering 9 / 4 (December 2022): 263-273 . https://doi.org/10.17350/HJSE19030000279
AMA Yavşan E. , İlhan İ. An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem. Hittite J Sci Eng. 2022; 9(4): 263-273.
Vancouver Yavşan E. , İlhan İ. An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem. Hittite Journal of Science and Engineering. 2022; 9(4): 263-273.
IEEE E. Yavşan and İ. İlhan , "An Ant Colony Optimization Based Real-time Mobile Application for the Capacitated Vehicle Routing Problem", Hittite Journal of Science and Engineering, vol. 9, no. 4, pp. 263-273, Dec. 2022, doi:10.17350/HJSE19030000279