Capacitated Arc Routing & Variants

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 Challenge will consider these four variations on CARP:

  • 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.

  • Congestion is a major factor in city logistics. Time-dependent routing problems capture variation in travel times that may arise as a consequence of congestion, weather conditions, road closures, and other factors. The Time-dependent Capacitated Arc Routing Problem (TDCARP) is a variant of CARP that uses a time-dependent travel cost. Like CARP, TDCARP is stated on a network consisting of nodes and (undirected) edges, and each edge (i,j) is associated with a distance dij. TDCARP is defined over a planning horizon [0,H] during which each of the undirected edges (i,j) is associated with two directed arcs (i,j) and (j,i), and the amount of time it takes to traverse an arc depends on when it is traversed within the planning horizon. Given a planning horizon [0,H], we associate to each arc (i,j) a piecewise constant speed function with hij pieces. This function represents the travel speed (i.e. the distance traveled per unit of time) on this arc as a function of time of traversal. We note that the speed of a vehicle can change while it is traveling on a link based on this function.

Problem Instances for Algorithm Evaluation

The instances used to evaluate algorithms will be a subset of those posted previously. The selected instances place emphasis on routing in real networks. The CARP, NEARP, NEARP-TP, and TDCARP instances for this final 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

CARP instances from Li and Eglese [LE96] and Brandão and Eglese [BE08] will be used in this portion of the Challenge. These instances still represent a challenge for modern metaheuristics and mathematical programming techniques.

  • 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.

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. 

NEARP Instances

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

  • 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.

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://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 the 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. There are a total of 48 NEARP-TP instances.

TDCARP Instances

The TDCARP instances are as described in Vidal, Martinelli, Pham, and Hà [VMPH]. They are based on ten CARP instances (C01-C10) of Beullens, Muyldermans, Cattrysse, and Van Oudheusden [BMCV] built from Flanders road network and ten EGL instances of Brandão and Eglese [BE08] and Li and Eglese [LE96] associated with a winter gritting case study in Lancashire.

From each of these 20 CARP instances [VMPH] generated three instances with different degrees of time dependency: low (L), medium (M), and high (H). The medium (M) and High (H) time-dependency instances will be used in the Implementation Challenge, for a total of 40 TDCARP instances. The network information, customer demands, and vehicle capacities are the same as those of the original instance.

The TDCARP instances are in the TDCARP-withoutSP folder within the zipped directory. They can also be found at: https://github.com/vidalt/HGS-TDCARP/tree/master/Instances/TDCARP-withoutSP.

A description of the input file format is contained in the file DAT-FORMAT.pdf.

Evaluation of Algorithms for CARP Variants

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 first based on their performance on only the CARP and NEARP instances. We call this the "basic ranking".  A second "extended ranking" will consider all of the CARP, NEARP, and NEARP-TP instances.Thus, the basic ranking is based on 78 instances, while the extended ranking is based on 126. Finally, a third "TDCARP ranking" will consider only the 40 TDCARP instances.

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.

A note on TDCARP: To make it easier to complete in the extended track, teams are allowed to use the preprocessed time-dependent shortest path data associated with the instances. These data are available at https://github.com/vidalt/HGS-TDCARP/tree/master/Instances/TDCARP-withSP.

Scoring the Solvers: Solvers will be awarded points for their performance on each instance and ranked by the total number of points over CARP and NEARP instances for the basic ranking, and over all instances for the extended ranking. 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 competitor that accumulates the most points on the CARP and NEARP instances wins the basic track of CARP. The competitor that accumulates the most points over all instances win the extended CARP competition.

The top scorer according to the basic ranking and the top scorer according to the extended ranking 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 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. (The total CPU time should measure the total elapsed time from the start of a run to its conclusion.)

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)

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.

[VMPH] T. Vidal, R. Martinelli, T. A. Pham, and M. H. Hà (2021). Arc routing with time-dependent travel times and paths. Transportation Science 55(3), 706–724. Technical Report: ArXiV: 2004.14473