Heuristics and Metaheuristics for Solving Capacitated Vehicle Routing Problem: An Algorithm Comparison

Dihin Muriyatmoko, Arif Djunaidy*, Ahmad Muklason

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

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 languageEnglish
Pages (from-to)494-501
Number of pages8
JournalProcedia Computer Science
Volume234
DOIs
Publication statusPublished - 2024
Event7th Information Systems International Conference, ISICO 2023 - Washington, United States
Duration: 26 Jul 202328 Jul 2023

Keywords

  • Algorithm Comparison
  • Capacitated Vehicle Routing Problem
  • Google OR Tools
  • heuristics
  • metaheuristics

Fingerprint

Dive into the research topics of 'Heuristics and Metaheuristics for Solving Capacitated Vehicle Routing Problem: An Algorithm Comparison'. Together they form a unique fingerprint.

Cite this