Volume 53, Number 1, January–March 2019
|Page(s)||303 - 322|
|Published online||15 February 2019|
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
2 Brest Business School (BBS), 29200 Brest, France
3 Université Le Havre Normandie, ISEL, 76600 Le Havre, France
* Corresponding author: firstname.lastname@example.org
Accepted: 21 September 2018
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.
Mathematics Subject Classification: 90B06 / 90C05 / 90C10 / 90C27 / 90C59
Key words: Routing problems / graph theory / sparsity / tabu search
© EDP Sciences, ROADEF, SMAI 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.