Труды Института системного программирования РАН (Oct 2019)

Local search metaheuristics for Capacitated Vehicle Routing Problem: a comparative study

  • Sergey Mikchailovitch Avdochin,
  • Ekaterina Nikolaevna Beresneva

DOI
https://doi.org/10.15514/ISPRAS-2019-31(4)-8
Journal volume & issue
Vol. 31, no. 4
pp. 121 – 138

Abstract

Read online

This study is concerned with local search metaheuristics for solving Capacitated Vehicle Routing Problem (CVRP). In this problem the optimal design of routes for a fleet of vehicles with a limited capacity to serve a set of customers must be found. The problem is NP-hard, therefore heuristic algorithms which provide near-optimal polynomial-time solutions are still actual. This experimental analysis is a continue of previous research on construction heuristics for CVRP. It was investigated before that Clarke and Wright Savings (CWS) heuristic is the best among constructive algorithms except for a few instances with geometric type of clients’ distribution where Nearest Neighbor (NN) heuristic is better. The aim of this work is to make a comparison of best-known local search metaheuristics by criteria of error rate and running time with CWS or NN as initial algorithms because there were not found any such state-of-the-art comparative study. An experimental comparison is made using 8 datasets from well-known library because it is interesting to analyze “effectiveness” of algorithms depending on type of input data. Overall, five different groups of Pareto optimal algorithms are defined and described.

Keywords