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

Abstract

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

• задача маршрутизации с ограничением по грузоподъемности
• локально-оптимальные метаэвристики
• lkh-3
• алгоритм переменного перемещения: метод отжига
• алгоритм управляемого поиска
• алгоритм поиска с запретами