Skip to Main content Skip to Navigation
Journal articles

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

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [51 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02436338
Contributor : Ibrahima Diarrassouba <>
Submitted on : Saturday, August 29, 2020 - 11:48:23 AM
Last modification on : Tuesday, September 1, 2020 - 4:55:34 PM

File

ro170191.pdf
Publication funded by an institution

Identifiers

Collections

Citation

Sara Tfaili, Hamdi Dkhil, Abdelkader Sbihi, Adnan Yassine. Efficient algorithms under dynamic graphs to solve the Capacitated Arc Routing Problem with feasible sparse graph. RAIRO - Operations Research, EDP Sciences, 2019, 53 (1), pp.303-322. ⟨10.1051/ro/2018087⟩. ⟨hal-02436338⟩

Share

Metrics

Record views

72

Files downloads

17