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.
Output Format
The output file format and naming convention is the same as that described for the CARP variant.
Algorithm Evaluation
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 all 60 TDCARP instances.
Teams are allowed to use the preprocessed time-dependent shortest path data associated with the instances that is available at https://github.com/vidalt/HGS-TDCARP/tree/master/Instances/TDCARP-withSP.
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 all 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 1 point. When there are ties, the points at play are split evenly between the tied solvers.
The competitor that accumulates the most points over all instances is declared the winner and 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.
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).
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.
[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