Time Dependent Capacitated Arc Routing


TDCARP Problem Statement

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. Time-dependent arc routing problems have not been well-studied in the literature, which is somewhat surprising because most related applications occur in urban contexts where travel times are greatly impacted by congestion. The Implementation Challenge will study Time-dependent Capacitated Arc Routing Problems (TDCARPs) in this portion of the competition.

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. An edge (i,j) between nodes i and j can be used to travel over. Each edge (i,j) is associated with a distance dij, and some of the edges require demand for a service quantity qij ≥ 0. Each vehicle has a capacity Q that limits the demand it can serve along a route. TDCARP 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 travel time is minimized.

TDCARP is defined over a planning horizon [0,H]. Each undirected edge (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.

TDCARP Instances

As in the CARP competition, we will focus on instances that are based on real city networks.

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. (The Buellens and EGL instances are also used in the CARP Challenge.)

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

The TDCARP instances can be found at: https://github.com/vidalt/HGS-TDCARP/tree/master/Instances/TDCARP-withoutSP.

A description of the input file format is contained in this file.

TDCARP Organizer(s)

Thibaut Vidal (lead)

Questions

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

References

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

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

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

[RWC] N. Rincon-Garcia, B. J. Waterson, and T. J. Cherrett (2018). Requirements from vehicle routing software: Perspectives from literature, developers and the freight industry. Transport Reviews, 38(1), 117–138.

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