SDVRP Competitors: View Registered Teams.
SDVRP Problem Statement
The Split Delivery Vehicle Routing Problem (SDVRP) is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) where each customer can be visited more than once.
Like the CVRP, input to SDVRP consists of locations for a depot and a set of n customers, a matrix D specifying the distance (or some other cost) to travel between each pair of locations, a quantity qi that specifies the demand for some resource by each customer i, and the maximum quantity, Q, of the resource that a vehicle can carry.
A feasible solution to the CVRP consists of a set of routes that begin and end at the depot, such that each customer is visited on exactly one route and the total demand by the customers assigned to a route does not exceed the vehicle capacity Q. The SDVRP removes the requirement that each customer is visited exactly once. Thus, a feasible solution to SDVRP is a set of routes that begin and end at the depot together with amounts qik specifying the amount of the demand by customer i assigned to route k, such that the total amount delivered to i over all routes k is equal to its demand, and such that the total demand assigned to each route does not exceed the capacity Q of a vehicle.
An optimal solution for SDVRP is a feasible solution that minimizes the sum of the "costs" of the routes.
Full Details for the SDVRP Challenge
The most complete and up-to-date information for the SDVRP competition is contained in the following document:
SDVRP Track Details & Rules [last updated: November 21, 2021]
Information is summarized on this webpage, but the SDVRP Track document is the definitive source for complete information.
SDVRP Algorithm Evaluation
Evaluation will take place in single evaluation 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.
A solver will be assessed based on the quality of the solutions obtained for each instance within a given amount of time. To mitigate the effect of processor speed, the time limit will be scaled for each individual processor. Solvers will be awarded points for their performance on each instance and ranked by the total number of points over all instances. The top three solvers, based on points, will be invited to present at the workshop, provided that the method is adequately described in an accompanying paper. Full details on scoring are contained in the SDVRP Rules document.
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.
SDVRP Instances
Since SDVRP is a relaxation of CVRP, instances are plentiful, and there are a wide variety available in the literature. Thus, for this particular variant, our goal is not so much to add new instances, as it is to get a clear picture of performance of various methods by engaging the community in a common competition.
Although we do not necessarily need additional instances, we welcome contribution of interesting new instances, particularly those derived from real applications. If you have instances you would like to contribute, please contact the organizers.
The instances to be used in the initial phase of the SDVRP Challenge are provided in a zipped directory (SDVRP_R1_instances.zip) for download. The instances are from four different sources, each contained in a separate folder. A description of the instances is contained in a PDF file that is also included in the downloadable directory.
Travel cost: The instance files contain node locations, customer demands, and vehicle capacity. To calculate the transportation cost, we will use a rounded Euclidean distance between consecutive customers i and j. That is calculated using the following formula to compute, dij,, the cost to travel from customer i to customer j.
dij = int((sqrt((xi - xj)2 + (yi - yj)2)+0.5)
where "sqrt" is the square root and "int" is a function truncating to the integer value.
Download the zipped SDVRP instances.
Input File Format
Each SDVRP instance is given in a separate file whose format is as follows.
In the first line there are two parameters:
n Q
where
n = number of customers
Q = capacity of the vehicles
The second line contains customers demands.
The remaining n+1 lines of the file contain the coordinates of the depot location, followed by those of each customer location. (The first pair of coordinates are always those for the depot.)
Output File Format
The name of the output file associated with an instance called "NAME" should be of the form out_NAME.txt.
The output file should be formatted such that each row in the file corresponds to a route in the solution. Routes should be numbered from 1 to K, where K is the total number of routes in the solution. Since each route begins and ends at the depot, each route provided in the output should begin and end at node 0. The customers on the route should appear in order, each followed by the amount of demand delivered to them on this route in parentheses. The routes should be provided from 1 to K in the first K rows of the file. The last three rows of the file summarize the solution cost and time by providing:
Total cost of the solution
Processor type as listed in PassMark
Solution time (wall clock)
The format of the output is as follows:
Route 1: 0 – customer ( quantity delivered ) – customer ( quantity delivered ) – … customer ( quantity delivered ) – 0
Route 2: 0 – customer ( quantity delivered ) – … customer ( quantity delivered ) – 0
¦
Route K: 0 – customer ( quantity delivered ) – customer ( quantity delivered ) – … customer( quantity delivered ) – 0
Total cost
Processor
Solution time
A few points to clarify details about the format:
- Nodes in routes are separated by “blank_space – blank_space”
- The quantity delivered to each customer is reported after the customer node this way: “customer_node blank_space left_parenthesis quantity blank_space right_parenthesis”.
The following is an example of example of a route that delivers 10 units to node 2 and 15 units to node 5:
0 – 2 ( 10 ) – 5 ( 15 ) – 0
Output files will be read and processed automatically, so they must comply with the above format.
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).
SDVRP Organizer(s)
Claudia Archetti (lead)
Questions
If you have questions, please email the organizers using this link.