Capacitated Arc Routing

CARP Competitors: View Registered Teams
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.

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.

Candidate Set of Problem Instances

CARP Instances

Instances used in evaluation will be drawn from the following sets of classic CARP instances.

  • GDB instances (23) of Golden, DeArmon and Baker [GDB] - relatively small instances on random graphs.
  • kshs instances (6) of Kuichi et al [KSHS] - small instances on random graphs.
  • The (34) instances of Benavent et al. [BCCM] - also on random graphs.
  • The (100) instances of Buellens et al [BMCV] - based on an intercity road network in Flanders.
  • The (24) instances of Li and Eglese [LE96] - based on a winter gritting application in Lancashire. 
  • The (10) instances of Brandão and Eglese [BE08] are a larger winter gritting application.

The Challenge evaluation 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.

NEARP Instances

Four sets of NEARP instances will also form the basis for algorithm evaluation in the Challenge:

  • CBMix instances (23) of Prins and Bouchenoua [PB04] - randomly generated instances in planar networks.
  • BHW instances (20) of Bach, Hasle, and Wøhlk [BHW] - derived from the CARP instances of [GDB], [BCCM], and [EL96].
  • DI-NEARP instances (24) of Bach, Hasle, and Wøhlk [BHW] - 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] - derived from the random CARP instances of [GDB]/[BCCM].

Algorithm evaluation will again emphasize instances routing over real networks, such as the DI-NEARP set.

Algorithm Evaluation - Selected Instances

The instances used to evaluate algorithms are a subset of those listed above. The CARP and NEARP instances used for ranking in algorithm evaluation can be downloaded in this ZIP FILE, which contains README files with the format description for each type of instance.

CARP Instances

The CARP instances used for algorithm evaluation are:

  • The (24) instances of Li and Eglese [LE96]. The files associated with these instances begin with egl-e and egl-s.
  • The (10) instances of Brandão and Eglese [BE08]. The associated files begin with egl-g.

These instances are in the CARP folder within the zipped directory. That folder also contains the format description.

NEARP Instances

Two sets of NEARP instances will be used for algorithm evaluation:

  • The (20) BHW of Bach, Hasle, and Wøhlk [BHW].
  • The (24) DI-NEARP instances of Bach, Hasle, and Wøhlk [BHW].

These instances are in the NEARP folder within the zipped directory. That folder also contains the format description.

Algorithm Evaluation - Running the Solvers

Algorithm evaluation will take place in single round with all testing performed on the participant's own computer.

  • Runs must be performed on a processor listed in PassMark.
  • Solvers must run on a single thread.
  • If a solver solves linear relaxations or mixed integer linear programming problems, any commercial solver may be used as long as the commercial solver is run on a single thread.

Solvers will be assessed based on their performance on only the selected set of 78 CARP and NEARP instances listed immediately above and contained in this zipped directory.

Time Limits: Solvers will be assessed based on the quality of the solutions obtained for each instance within a given amount of time. The time limits are based on the number of service requests:

  • Instances with 200 or fewer service requests have a time limit of 15 minutes.
  • Instances with more than 200 service requests but no more than 400 have a time limit of 30 minutes. (I.e.,the number of service requests is in the range [201,400].)
  • Instances with more than 400 service requests have a time limit of 60 minutes.

These time limits are stated for a machine with a 1500 CPU mark. Time limits for a competitor's machine must be scaled to mitigate the effect of processor speed. If the CPU mark of the competitor's machine is C, then the time limit is multiplied by 1500/C for that machine.

Scoring the Solvers: Solvers will be awarded points for their performance on each instance and ranked by the total number of points over the all 78 selected CARP and NEARP instances. The solver that finds the best solution for an instance receives 3 points for that instance; the next-best solver receives 2 points; and the third best gets one point. When there are ties, the points at play are split evenly between the tied solvers.

The top scoring team over all instances will be invited to present at the workshop, provided that their method is adequately described in the associated extended abstract. (Failure to provide this document will result in disqualification.)

Additionally, the VRP Implementation Challenge committee will review all entries with respect to additional criteria such as novelty of the approach taken, simplicity, and versatility of a solver to work well on multiple different variants. We hope to recognize multiple entries for these attributes with invitations to present.

Output Format

The solution file corresponding to an input file called NAME.dat should be called NAME.sol.

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)

Submission

When you are ready to submit either your solver output package (a zipped file) or your Challenge paper, you may do so from the Submissions page (which is part of the navigation menu on the right-hand side of this page).

Outputs are due January 30, 2022 and must be received by 23:59 Pacific Standard Time (UTC -8).

CARP Organizer(s)

Thibaut Vidal (lead)

Questions

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.