Capacitated Arc Routing Problem (CARP)

Problem definition:

Let G(V,E) be an undirected connected graph where non-negative costs cij and non-negative demands dij are assigned to each edge (i,j). If an edge (i,j) has positive demand dij then it is called a required edge. Let ER be the set of required edges. A limited fleet of identical vehicles each one with a limited capacity D is available. The vehicle route should start and end from a special node called depot. While traversing the graph, a vehicle might service an edge, which deducts its capacity by the edge demand and increases the solution cost by the edge cost or deadhead an edge, which only increases the solution cost by the edge cost. A vehicle route is defined by a sequence of directed edges (arcs) traversed by that vehicle. A feasible CARP solution is thus composed by a set of routes which services all required edges and does not violate any vehicle capacity. The objective of CARP is to find the minimum cost set of routes.

Our methodologies developed for CARP:

GRASP: Greedy randomized adaptive search procedure with evolutionary path-relinking [1,2]

PS-Efficiency: Constructive path-scanning heuristic with efficiency-based rule [3]


Bibliography:

[1] Usberti, F. L., França, P. M., e França, A. L. M. (2011b). Grasp with evolutionary path-relinking for the capacitated arc routing problem. Computers and Operations Research. ISSN 0305-0548. doi: 10.1016/j.cor.2011.10.014.

[2] Usberti, F. L. (2012). Heuristic and exact approaches for the open capacitated arc routing problem. PhD thesis, Universidade Estadual de Campinas.

[3] Arakaki, R. K., Usberti, F. L. (2018). An efficiency-based path-scanning heuristic for the capacitated arc routing problem. Computers and Operations Research. ISSN 0305-0548. doi: 10.1016/j.cor.2018.11.018.

[4] Bode, C. , Irnich, S. (2014). The shortest-path problem with resource constraints with (k,2)-loop elimination and its application to the capacitated arc-routing problem. European Journal of Operational Research. ISSN: 0377-2217. doi: 10.1016/j.ejor.2014.04.004

Download:

The CARP instances and PS-Efficiency [3] source code and experiments data is available for download here.


Tables of results:

The following tables compare the computational results from methodologies PS-RC(k), PS-RE(k), PS-Ellipse(k,α) and PS-Efficiency(k,α).

k: Number of iterations.

α: Real parameter.

|ER|: Number of required edges.

GAP (%): Gap in percentage, defined as: 100*(UB-LB)/LB.

UB: Solution cost obtained by each method.

LB: Best known lower bound obtained by literature [4].


Table 1. Computational experiment results on benchmark instances.
GAP (%)
Instance group |ER| k PS-RC(k) PS-RE(k) PS-Ellipse(k,α) PS-Efficiency(k,α)
α=1.0 α=1.5 α=2.0 α=2.5 α=3.0 α=3.5 α=1.0 α=1.5 α=2.0 α=2.5 α=3.0 α=3.5
gdb 11-55 1000 3.95 3.77 1.63 1.50 1.98 1.92 4.83 7.82 1.70 1.44 1.19 1.24 1.83 1.85
10000 2.65 2.15 1.10 1.02 1.34 1.22 3.52 6.44 1.16 0.74 0.78 0.80 1.03 1.16
20000 2.21 2.06 1.04 0.88 1.25 1.22 3.46 6.18 1.02 0.74 0.75 0.71 0.84 1.05
val 34-97 1000 8.42 8.35 6.12 5.38 5.10 5.26 6.03 8.17 6.20 5.29 4.85 4.83 4.65 4.36
10000 5.85 6.29 4.37 3.70 3.42 3.53 4.23 6.31 4.28 3.65 3.33 3.27 2.75 3.15
20000 5.60 5.81 3.82 3.38 3.12 3.26 3.98 5.88 3.79 3.18 2.98 2.80 2.53 2.78
egl 51-190 1000 16.64 16.43 8.59 9.02 12.04 15.05 19.96 25.32 8.50 7.49 7.51 7.74 7.73 8.03
10000 15.32 15.29 7.30 7.67 10.22 13.32 18.62 23.67 7.07 6.49 6.41 6.59 6.80 6.47
20000 14.92 15.00 7.05 7.51 10.01 12.62 18.20 23.33 6.89 6.31 6.06 6.28 6.41 6.25
C 32-107 1000 16.08 16.27 10.40 9.28 9.50 10.03 10.45 12.65 9.91 9.27 8.90 8.61 8.88 8.61
10000 13.39 12.99 7.40 7.27 7.28 7.29 8.64 9.99 7.44 6.83 6.96 6.34 6.69 6.61
20000 12.76 12.22 7.26 6.71 6.64 6.60 8.20 9.77 6.74 6.27 6.36 5.96 6.09 6.34
D 32-107 1000 12.15 12.30 10.16 9.40 8.48 7.74 7.68 7.20 9.55 8.13 7.26 7.18 6.49 6.86
10000 9.23 9.45 6.74 6.28 5.91 5.66 5.35 4.97 6.34 5.74 4.75 4.86 4.93 4.48
20000 8.77 8.85 6.26 5.71 5.33 5.03 4.92 4.45 5.73 5.15 4.40 4.20 4.13 4.30
E 28-107 1000 16.10 16.18 10.90 10.06 9.91 10.05 11.56 12.62 9.57 9.54 8.26 8.28 8.20 8.27
10000 13.09 12.60 8.04 7.68 7.72 7.98 9.25 10.25 7.45 6.93 6.29 5.97 6.00 5.82
20000 12.57 11.96 7.34 7.16 6.70 7.38 8.55 9.77 6.96 6.49 5.55 5.62 5.53 5.57
F 28-107 1000 12.34 11.53 10.04 8.92 8.96 8.47 8.64 7.75 9.48 8.27 8.50 7.78 7.40 6.66
10000 9.20 9.07 7.43 6.53 6.00 6.50 6.05 5.81 6.64 6.40 5.80 5.47 4.77 4.64
20000 8.56 8.47 6.83 6.04 5.54 5.84 5.48 5.27 6.00 5.69 5.29 4.98 4.18 4.44
egl-large 347-375 1000 28.14 27.61 17.78 16.97 16.98 17.91 18.25 19.53 17.06 16.45 16.42 16.07 16.59 16.26
10000 25.50 26.37 16.23 15.65 16.03 16.49 16.79 17.81 16.12 15.47 14.76 15.19 15.22 15.08
20000 25.09 26.12 16.01 15.16 15.45 16.09 16.10 17.27 15.65 15.05 14.69 14.50 14.23 14.95
overall 11-375 1000 12.96 12.82 8.73 8.09 8.37 8.75 10.14 11.86 8.31 7.53 7.12 6.99 6.94 6.84
10000 10.50 10.45 6.55 6.20 6.42 6.90 8.23 9.87 6.28 5.75 5.38 5.27 5.20 5.12
20000 10.04 9.97 6.15 5.80 5.94 6.41 7.81 9.46 5.81 5.33 4.98 4.85 4.71 4.89

In bold: the best results for each α comparing PS-Efficiency and PS-Ellipse.
In underline: the best results regarding all algorithms.