Abstract
The Capacitated Vehicle Routing Problem (CVRP) is an optimization problem that involves arranging vehicle routes while considering vehicle capacity. This research aims to compare the effectiveness of several heuristic (Path Cheapest Arc, Path Most Constrained Arc, Savings, Christofides) and metaheuristic (Greedy Descent, Guided Local Search, Simulated Annealing, Tabu Search) algorithms for determining the routing scenarios and vehicle types for faculty transportation between the male campus in Ponorogo and the female campus in Mantingan Ngawi at Universitas Darussalam Gontor. The research involves decision variables for vehicle routing determination and the objective of minimizing the distance traveled. The constraint function includes two options: one vehicle with a capacity of 60 passengers and four vehicles. This research utilizes Google OR Tools with the Python programming language using Google Colab to facilitate the calculation process. The research results indicate that metaheuristic algorithms outperform heuristics for complex case studies (four vehicles). This study recommends using metaheuristic methods, specifically Christofides Guided Local Search and Christofides Simulated Annealing, for determining the best routes with the shortest distance and time. Further research was developed using algorithms such as hyperheuristics or matheuristics.
Original language | English |
---|---|
Pages (from-to) | 494-501 |
Number of pages | 8 |
Journal | Procedia Computer Science |
Volume | 234 |
DOIs | |
Publication status | Published - 2024 |
Event | 7th Information Systems International Conference, ISICO 2023 - Washington, United States Duration: 26 Jul 2023 → 28 Jul 2023 |
Keywords
- Algorithm Comparison
- Capacitated Vehicle Routing Problem
- Google OR Tools
- heuristics
- metaheuristics