Capacitated Arc Routing


CARP Problem Statement

Arc routing problems are defined on a network that consists of nodes and connections between nodes. These connections are called arcs when they are directed (one-way) from one node to the other and called edges when they are undirected. Arc routing problems involve delivery requests on the arcs and edges of a network. A generalization of this problem, called the Node, Edge, and Arc Routing Problem (NEARP), also allows service requests at the nodes.

The arc routing problem category has traditionally been separated from vehicle routing research because of differences in mathematical formulation, as well as differences in methodology for the canonical problem variants with a single vehicle. For instance, the Chinese postman problem (which requires visiting every edge) can be solved in polynomial time, whereas the traveling salesman problem (which requires visiting every node) is NP-hard.

Nowadays, most arc routing problems with multiple vehicles, capacity constraints, and service requests are solved with mathematical programming and metaheuristic techniques that are similar to those used for their vehicle routing counterparts. This led us to integrate this prominent and increasingly important variant into the challenge.

Arc routing problems are intimately linked to the characteristics of the road networks on which they are defined. One could argue, in fact, that vehicle routing problems themselves are primarily defined on the road network, but their reformulation onto a complete graph (using shortest-path distances) usually hides this aspect. Indeed, the arc routing variants considered in this Implementation Challenge are the only variants that take a detailed network, rather than a distance matrix implied by the complete graph, as input. In this way, arc routing problems can be viewed as generalizing their VRP counterparts by allowing routing on general networks and by allowing deliveries at more types of locations. Reference [CL15] provides an extensive coverage of arc routing problem variants.

We take the opportunity of the DIMACS Challenge to encourage new reproducibility and methodology studies on several arc routing variants. All of the variants we consider involve multiple capacitated vehicles.

  • The Capacitated Arc Routing Problem (CARP) is stated on a network consisting of nodes and (undirected) edges. An edge (i,j) between nodes i and j can be used to travel over and has a cost dij for traversing it. Some of the edges (i, j) require demand for a service quantity qij ≥ 0. Each vehicle has a capacity Q on the demand it can serve along a route. The CARP consists of finding a set of vehicle routes—represented as a sequence of deadheaded and serviced arcs (oriented edges) starting and ending at the depot—such that each edge with non-zero demand is serviced by exactly one vehicle, the total demand served on each vehicle does not exceed its capacity limit Q, and the total cost is minimized.
  • The Node, Edge, Arc Routing Problem (NEARP) is an arc routing problem that generalizes  CARP by allowing demand to occur at nodes, edges, or arcs. It is stated on a network that includes nodes, arcs, and edges, any of which may have a demand for service. All such demands must be serviced by a feasible set of routes.
  • A recurrent challenge in routing in urban networks comes from possible turn restrictions and delays at intersections. These aspects are indispensable for commercial routing solvers, but they are less frequently discussed in the academic literature. In Arc Routing Problems with Turn Penalties, turn costs cijk are included for each pair of connected edges and/or arcs (i,j) and (j,k). An optimal set of routes minimizes the sum of the travel costs and the turn penalties.

These arc routing variants have static travel costs associated with edge or link traversal. This Implementation Challenge also considers more difficult and more realistic time-dependent arc routing variants in another section of the Implementation Challenge.

Additional instances based on real road networks, as well as additional problem variants that capture realistic concerns can also be suggested in the context of the Challenge.

Problem Instances

We will initiate this study using instances that exist in the literature. Most of the classical CARP, NEARP, and NEARP-TP instances for this portion of the Challenge can be downloaded in this ZIP FILE, which contains README files with the format description for each type of instance.

CARP Instances

Classic CARP instances from Golden, DeArmon and Baker [GDB], Benavent et al. [BCCM], Kiuchi et al [KSHS], Beullens et al. [BMCV], Li and Eglese [LE96], and Brandão and Eglese [BE08] will be used in this portion of the Challenge.

  • GDB instances (23) of Golden, DeArmon and Baker [GDB] are relatively small instances on random graphs.
  • kshs instances (6) of Kuichi et al [KSHS] are small instances on random graphs.
  • The (34) instances of Benavent et al. [BCCM] are also on random graphs. The associated files begin with a number 1-10.
  • The (100) instances of Buellens et al [BMCV] are based on an intercity road network in Flanders. The associated file names begin with C, D, E, and F (each having instances 01-25).
  • The (24) instances of Li and Eglese [LE96] are based on a winter gritting application in Lancashire. The files associated with these instances begin with egl-e and egl-s.
  • The (10) instances of Brandão and Eglese [BE08] are a larger winter gritting application. The associated files begin with egl-g.

The Challenge will place more emphasis on routing in real networks, such as the ones in Flanders and Lancashire used in the last three sets of instances. These instances still represent a challenge for modern metaheuristics and mathematical programming techniques.

All of the above instances are in the CARP folder within the zipped directory. That folder also contains the format description. All of the CARP instances are also available at  https://github.com/vidalt/HGS-CARP/tree/master/Instances/CARP. The GBD, KSHS, and smaller egl sets can also be obtained from this website: https://www.uv.es/belengue/carp.html

NEARP Instances

Four sets of NEARP instances will also be included in the Challenge:

  • CBMix instances (23) of Prins and Bouchenoua [PB04] are randomly generated instances in planar networks.
  • BHW instances (20) of Bach, Hasle, and Wøhlk [BHW] are derived from the CARP instances of [GDB], [BCCM], and [EL96]
  • DI-NEARP instances (24) of Bach, Hasle, and Wøhlk [BHW] are based on an application in newspaper delivery over real road networks in the Nordic countries.
  • MGGDB/MGVAL instances (138/150) of Bosco, Lagana, Musmanno, and Vocaturo [BLMV] are derived from the random CARP instances of [GDB]/[BCCM].

Emphasis in the Challenge will again be on instances routing over real networks, such as the DI-NEARP set.

These instances are in the NEARP folder within the zipped directory. That folder also contains the format description in an associated README file. All of these instances are also available at https://www.sintef.no/projectweb/top/nearp/ or https://github.com/vidalt/HGS-CARP/tree/master/Instances/MCGRP.

Instances with Turn Penalties (NEARP-TP)

Instances with turn penalties are in the NEARP-TurnPenalties folder within zipped directory. That folder also contains the format description in an associated README file. These instances are derived from the set of NEARP instances above. All of these instances are also available at https://github.com/vidalt/HGS-CARP/tree/master/Instances/MCGRP-TP.

Additional Instances

We further encourage the proposal of larger-scale instances during this challenge, possibly integrating different road-network characteristics. Academic datasets rarely include more than a few hundred edges, but application cases in city logistics easily rise up to tens of thousands of streets. We welcome contribution of new instances, especially those based on real street networks.

Output Format

The solution file should first include three lines, which specify respectively the objective function value, the number of routes, and the total CPU time (in seconds) needed to obtain these results.

Then, each other line of the solution file corresponds to a route in the solution, indicating the index of the depot (0 for all instances), the day (1 for all instances), the index of the route (starting from 1), the total demand on the route, the distance of the route, the number of visits in the route (including initial and final depot visits and services), and finally a sequence of statements (X i,j,k). In each of these statements, X stands for a depot visit (D) or a service (S) to a node, arc or edge, i is the index of the service, j and k are the extremities of the edge that is serviced, in the order of the service orientation. In the case of a service to a node (for the NEARP and NEARP-TP), i and j are equal to the node index. To evaluate such a solution, the endpoints of the services should be connected via shortest paths.

Example of solution format (for a small CARP instance named gdb1.dat):

316
5
8.09
0 1 1 5 76 7 (D 0,1,1) (S 12,5,11) (S 21,11,9) (S 8,9,2) (S 7,2,4) (S 2,4,1) (D 0,1,1)
0 1 2 5 60 7 (D 0,1,1) (S 5,1,12) (S 14,6,7) (S 19,8,11) (S 22,11,10) (S 4,10,1) (D 0,1,1)
0 1 3 5 86 7 (D 0,1,1) (S 13,12,5) (S 9,3,4) (S 6,2,3) (S 10,3,5) (S 11,5,6) (D 0,1,1)
0 1 4 5 53 7 (D 0,1,1) (S 15,12,6) (S 16,7,8) (S 18,8,10) (S 20,10,9) (S 1,2,1) (D 0,1,1)
0 1 5 2 41 4 (D 0,1,1) (S 17,12,7) (S 3,7,1) (D 0,1,1)

CARP Organizer(s)

Thibaut Vidal (lead)

Contributions & Questions

We will be pleased to update this page with additional information from the participants.

If you have questions, please email the organizers using this link.

References

[BHW] L. Bach, G. Hasle, and S. Wøhlk (2013). A lower bound for the node, edge, and arc routing problem. Computers & Operations Research, 40(4), 943–952.

[BCCM] E. Benavent, V. Campos, A. Corberán and E. Mota (1992). The Capacitated Arc Routing Problem: Lower Bounds. Networks 22 (7), pp. 669–690.

[BMCV] P. Beullens, L. Muyldermans, D. Cattrysse, and D. Van Oudheusden (2003). A guided local search heuristic for the capacitated arc routing problem. European Journal of Operational Research, 147(3), 629–643.

[BLMV] A. Bosco, D. Lagana, R. Musmanno, and F. Vocaturo (2013). Modeling and solving the mixed capacitated general routing problem. Optimization Letters 7(7), 1451–1469.

[BE08] J. Brandão and R. Eglese (2008). A deterministic tabu search algorithm for the capacitated arc routing problem. Computers & Operations Research, 35(4), 1112–1126.

[CL15] Á. Corberán and G. Laporte (2015). Arc routing: Problems, methods, and applications. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics.

[GDB] B.L. Golden, J.S. DeArmon and E.K. Baker (1983). Computational Experiments with Algorithms for a Class of Routing Problems. Computers and Operations Research 10 (1), pp. 47-59.

[KSHS] M. Kiuchi, Y. Shinano, R. Hirabayashi and Y. Saruwatari (1995). An exact algorithm for the Capacitated Arc Routing Problem using Parallel Branch and Bound method. Abstracts of the 1995 Spring National Conference of the Oper. Res. Soc. of Japan, pp. 28-29.

[LE96] L.Y.O. Li and R.W. Eglese (1996). An Interactive Algorithm for Vehicle Routing for Winter-Gritting. Journal of the Operational Research Society 47, pp. 217-228.

[PB04] C. Prins and S. Bouchenoua (2004). A memetic algorithm solving the VRP, the CARP and general routing problems with nodes, edges and arcs. In W. Hart, N. Krasnogor, and J. Smith (eds.) Recent Advances in Memetic Algorithms, Studies in Fuzziness and Soft Computing, pp. 65–85. Springer.

[V17] T. Vidal (2017). Node, edge, arc routing and turn penalties: Multiple problems -- One neighborhood extension. Operations Research, 65(4), 992–1010.