Efficient algorithms under dynamic graphs to solve the Capacitated Arc Routing Problem with feasible sparse graph

¹ Université Le Havre Normandie, LMAH, FR CNRS 3335, ISCN, 76600 Le Havre, France
² Brest Business School (BBS), 29200 Brest, France
³ Université Le Havre Normandie, ISEL, 76600 Le Havre, France

^* Corresponding author: abdelkader.sbihi@brest-bs.com

Received: 7 May 2017
Accepted: 21 September 2018

Abstract

In this paper we develop several approaches to approximately solve the capacitated arc routing problem (CARP) on sparse graphs namely sparse CARP. First, we give a mathematical model for the sparse CARP and we present a brief survey about a transformation technique to transform the sparse CARP into a sparse capacitated vehicle routing problem namely sparse CVRP. Later, we propose several approaches to solve the sparse CARP by solving its equivalent obtained sparse CVRP. The first approach is a constructive heuristic (CH) used to construct an initial feasible solution. The second approach is an improving randomized procedure (IRP) used to improve the quality of the initial solution. Finally, we introduce the main adapted tabu search approach (TS) under a sparse dynamic graph. The algorithm starts by applying the first two procedures CH and IRP and attempts to compute a better solution for the sparse CARP. Extensive computational tests on randomly generated problem instances show the effectiveness of the proposed approach. The TS algorithm yields satisfactory results within reasonable computational time. The approach outperformed also the commercial solver Cplex v12.71 which was able to solve only small instances with relatively a big CPU time for medium size instances.