VRP with Split Deliveries


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 "cost" 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: May 10, 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, VRP Implementation Challenge committee will review all entries with respect to recognition categories across all variants, such as novelty of the approach taken and simplicity and versatility of a solver to work well on multiple different variants. We hope to recognize multiple entries for these attributes.

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 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:

  1. Nodes in routes are separated by “blank_space – blank_space”
  2. 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.

SDVRP Organizer(s)

Claudia Archetti (lead)

Questions

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