Solving Capacitated Vehicle Routing Problem Using Football Game Algorithm

Alfian Alif(1*), Annisa Kesy Garside(2), Ikhlasul Amallynda(3), Baiq Nurul Izzah Farida Ramadhani(4),

(1) 
(2) Universitas Muhammadiyah Malang
(3) 
(4) 
(*) Corresponding Author
DOI: https://doi.org/10.23917/jiti.v21i1.15812

Abstract

The Capacitated Vehicle Routing Problem (CVRP) plays an important role in the logistics transportation sector. Determining the proper route will reduce the company's operational costs. In CVRP, a number of vehicles have a capacity limit that can serve all customers. This research completes a real case study on a bottled drinking water company where the company still uses the subjective method of the driver to determine the transportation route. Based on the conditions in the company, the selection of the best route will consider vehicle capacity and demand to determine the shortest route. The execution of this case study uses the Football Game Algorithm (FGA) which was first initiated by Fadakar & Ebrahimi which proved promising and had the strongest performance in all cases. FGA is expected to be able to determine the shortest distribution route from the existing cases to reduce the distribution costs incurred. This study takes data from 4 days of delivery that served 78 customers. The average daily transportation cost savings result is 42%. This amount indicates that the FGA algorithm is effective for completing a real case study in CVRP.

Keywords

capacitated vehicle routing problem; football game algorithm; transportation cost

Full Text:

PDF

References

Abdelatti, M., Hendawi, A., & Sodhi, M. (2021). Optimizing a GPU-accelerated genetic algorithm for the vehicle routing problem. Paper presented at the Proceedings of the Genetic and Evolutionary Computation Conference Companion.

Ahmed, A., & Sun, J. U. (2018). Bilayer local search enhanced particle swarm optimization for the capacitated vehicle routing problem. Algorithms, 11 (3), 31.

Alinezhad, H., Yaghoubi, S., Hoseini Motlagh, S. M., Allahyari, S., & Saghafi Nia, M. (2018). An improved particle swarm optimization for a class of capacitated vehicle routing problems. Int. Journal of Transp. Eng., 5(4), 331-347.

Arockia, A., Lochbrunner, M., Hanne, T., & Dornberger, R. (2021). Benchmarking Tabu Search and Simulated Annealing for the Capacitated Vehicle Routing Problem. Paper presented at the 2021 The 4th International Conference on Computers in Management and Business.

Aurachman, R., Baskara, D., & Habibie, J. (2021). Vehicle routing problem with simulated annealing using python programming. Paper presented at the IOP Conference Series: Materials Science and Engineering.

Azad, T., & Hasin, M. A. A. (2019). Capacitated vehicle routing problem using genetic algorithm: a case of cement distribution. International Journal of Logistics Systems & Management, 32 (1), 132-146.

Caballero-Morales, S.-O., Martínez-Flores, J.-L., & Sánchez-Partida, D. (2018). An evolutive tabu-search metaheuristic approach for the capacitated vehicle routing problem. In New Perspectives on Applied Industrial Tools and Techniques (pp. 477-495): Springer.

Dam, T.-L., Li, K., & Fournier-Viger, P. (2017). Chemical reaction optimization with unified tabu search for the vehicle routing problem. Soft Computing, 21 (21), 6421-6433.

Ding, H., Cheng, H., Shan, X., & Publicat, I. D. (2018). Modified artificial bee colony algorithm for the capacitated vehicle routing problem. Paper presented at the DEStech Publications.

Djunaidi, A. V., & Juwono, C. P. (2018). Football game algorithm implementation on the capacitated vehicle routing problems. Int J Comput Algoritm, 7 (1), 45-53.

Đurasević, M., & Jakobović, D. (2021). Heuristic and Metaheuristic Methods for the Unrelated Machines Scheduling Problem: A Survey. arXiv preprint arXiv: 2107.13106.

Fadakar, E., & Ebrahimi, M. (2016). A new metaheuristic football game inspired algorithm. Paper presented at the 2016 1st Conference on Swarm Intelligence and Evolutionary Computation (CSIEC).

Garside, A. K. & Rahmasari, D. (2017). Manajemen Logistik. Malang : UMMPress.

Hannan, M., Akhtar, M., Begum, R., Basri, H., Hussain, A., & Scavino, E. (2018). Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm. Waste management, 71, 31-41.

Ilhan, İ. (2020). A population based simulated annealing algorithm for capacitated vehicle routing problem. Turkish Journal of Electrical Engineering & Computer Sciences, 28 (3), 1217-1235.

Iswari, T., & Asih, A. M. S. (2018). Comparing genetic algorithm and particle swarm optimization for solving capacitated vehicle routing problem. Paper presented at the IOP Conference Series: Materials Science and Engineering.

Karaoglan, A. D., Atalay, I., & Kucukkoc, I. (2020). Distance-constrained vehicle routing problems: a case study using artificial bee colony algorithm. In Mathematical Modelling and Optimization of Engineering Problems (pp. 157-173): Springer.

Katiyar, S., Khan, R., & Kumar, S. (2021). Artificial Bee Colony Algorithm for Fresh Food Distribution without Quality Loss by Delivery Route Optimization. Journal of Food Quality, 2021.

Kurniawati, D. A., Handoko, A., Piplani, R., & Rosdiahti, R. (2022). Optimized distribution of halal products using tabu search. Journal of Islamic Marketing.

Lima, S. J. d. A., & Araújo, S. A. d. (2018). A new binary encoding scheme in genetic algorithm for solving the capacitated vehicle routing problem. Paper presented at the International Conference on Bioinspired Methods and Their Applications.

Liu, N., Pan, J.-S., & Chu, S.-C. (2020). A Competitive Learning QUasi Affine TRansformation Evolutionary for Global Optimization and Its Application in CVRP. Journal of Internet Technology, 21 (7), 1863-1883.

Mahmud, N., & Haque, M. M. (2019). Solving multiple depot vehicle routing problem (MDVRP) using genetic algorithm. Paper presented at the 2019 International Conference on Electrical, Computer and Communication Engineering (ECCE).

Mari, F., Mahmudy, W. F., & Santoso, P. B. (2018). An improved simulated annealing for the capacitated vehicle routing problem (CVRP). Jurnal Ilmiah Kursor, 9 (3).

Mauliddina, A. N., Saifuddin, F. A., Nagari, A. L., Redi, A. A. N. P., Kurniawan, A. C., & Ruswandi, N. (2020). Implementation of discrete particle swarm optimization algorithm in the capacitated vehicle routing problem. Jurnal Sistem dan Manajemen Industri, 4 (2), 117-128.

Mazidi, A., Fakhrahmad, M., & Sadreddini, M. H. (2016). A meta-heuristic approach to CVRP problem: local search optimization based on GA and ant colony. Journal of Advances in Computer Research, 7 (1), 1 - 22..

Mulloorakam, A. T., & Nidhiry, N. M. (2019). Combined objective optimization for vehicle routing using genetic algorithm. Materials Today: Proceedings, 11, 891-902.

Obaid, O. I. (2018). Solving capacitated vehicle routing problem (cvrp) using tabu search algorithm (tsa). Ibn AL-Haitham Journal For Pure & Applied Sciences, 31 (2), 199-209.

Rabbouch, B., Saâdaoui, F., & Mraihi, R. (2020). Empirical-type simulated annealing for solving the capacitated vehicle routing problem. Journal of Experimental & Theoretical Artificial Intelligence, 32 (3), 437-452.

Ramadhani, B. N. I. F., & Garside, A. K. (2021). Particle Swarm Optimization Algorithm to Solve Vehicle Routing Problem with Fuel Consumption Minimization. Jurnal Optimasi Sistem Industri, 20 (1), 1-10.

Redi, A. A. N. P., Maula, F. R., Kumari, F., Syaveyenda, N. U., Ruswandi, N., Khasanah, A. U., & Kurniawan, A. C. (2020). Simulated annealing algorithm for solving the capacitated vehicle routing problem: a case study of pharmaceutical distribution. Jurnal Sistem dan Manajemen Industri, 4 (1), 41-49.

Son, D. V. T., & Tan, P. N. (2021). Capacitated vehicle routing problem—a new clustering approach based on hybridization of adaptive particle swarm optimization and grey wolf optimization. In Evolutionary Data Clustering: Algorithms and Applications (pp. 111-128): Springer.

Toth, P., & Vigo, D. (2002). An overview of vehicle routing problems. The vehicle routing problem, 1-26.

Trachanatzi, D., Rigakis, M., Marinaki, M., Marinakis, Y., & Matsatsinis, N. (2020). Distance related: a procedure for applying directly Artificial Bee Colony algorithm in routing problems. Soft Computing, 24 (12), 9071-9089.

Wahyuningsih, S., Satyananda, D., & Oktoviana, L. T. (2020). Performance of Artificial Bee Colony algorithm and its implementation on graph theory application course. Paper presented at the AIP Conference Proceedings.

Zhu, J. (2022). Solving Capacitated Vehicle Routing Problem by an Improved Genetic Algorithm with Fuzzy C-Means Clustering. Scientific Programming, 2022, 1 - 8.

Article Metrics

Abstract view(s): 668 time(s)
PDF: 435 time(s)

Refbacks

  • There are currently no refbacks.