Vehicle Routing Problem with Divisible Deliveries and Pickups (VRPDDP)

Category: Routing
Formulation: Mixed-integer
Objective: Minimize
Time limit: 60 s per instance
Paper: The Vehicle Routing Problem with Divisible Deliveries and PickupsGábor Nagy, Niaz A. Wassan, M. Grazia Speranza, Claudia Archetti · Transportation Science, 2013

Description

A logistics company operates a fleet of identical vehicles from a single depot to serve a set of customers. Each customer has a delivery demand (goods to be brought from the depot) and a pickup demand (goods to be collected and returned to the depot). All delivery goods originate at the depot and all pickup goods must be transported back to the depot; goods may not be transferred directly between customers. The key feature of this problem is that a customer's delivery request and its pickup request may be served on separate visits by different vehicles. Each individual request (delivery or pickup) must, however, be fulfilled entirely in a single visit. The company has an unlimited number of vehicles available, all sharing the same capacity. The input data consists of the number of customers n, the vehicle capacity C, the delivery demand for each customer, the pickup demand for each customer, and a symmetric distance matrix giving the distance between the depot and every customer and between every pair of customers. Distances are Euclidean, rounded to the nearest integer. The company must design vehicle routes that serve every customer's delivery demand and every customer's pickup demand. Each individual delivery request must be fulfilled in a single visit by one vehicle, and each individual pickup request must be fulfilled in a single visit by one vehicle; the delivery and pickup for the same customer may be performed on the same trip or on separate trips by different vehicles. Each vehicle starts and ends at the depot. At any point during a vehicle's trip the total cargo on board (delivery goods still to be dropped off plus pickup goods already collected) must not exceed the vehicle capacity. A vehicle leaves the depot carrying only delivery goods and returns to the depot carrying only pickup goods. The goal is to minimize the total distance traveled by all vehicles, summed over all legs of all trips.

Instance schema

{
  "num_customers": "<int> Number of original customers to be served.",
  "vehicle_capacity": "<int> Maximum combined delivery and pickup load a single vehicle can carry at any time.",
  "depot": {
    "id": "<int> Identifier for the depot node (always 0).",
    "x": "<int> Horizontal coordinate of the depot.",
    "y": "<int> Vertical coordinate of the depot."
  },
  "customers": [
    {
      "id": "<int> Unique identifier for the customer (1-indexed).",
      "x": "<int> Horizontal coordinate of the customer location.",
      "y": "<int> Vertical coordinate of the customer location.",
      "delivery_demand": "<int> Quantity of goods to be delivered from the depot to this customer.",
      "pickup_demand": "<int> Quantity of goods to be picked up from this customer and returned to the depot."
    }
  ],
  "distance_matrix": "<list[list[int]], shape [num_customers+1][num_customers+1]> Rounded Euclidean distance between each pair of locations, where row/column 0 is the depot and rows/columns 1 through num_customers are the customers."
}

Solution schema

{
  "objective_value": "<float> Total distance traveled by all vehicles across every arc of every route.",
  "routes": "<list[list[int]]> Sequence of expanded node IDs visited by each vehicle, beginning and ending at the depot (node 0), with linehaul nodes numbered 1..n and backhaul nodes numbered n+1..2n.",
  "routes_detailed": "<list[list[dict]]> Same per-vehicle visit sequences as 'routes' with each stop annotated by its role (depot, linehaul, or backhaul), the original customer it corresponds to, and the delivery or pickup quantity served at that stop."
}

Public instances

For development. Scoring uses private instances, which are never published. Sign in to download them.

large_instance_1.json60 s
tiny_instance.json60 s

Checker

The checker our evaluation runs, from the FrontierOR benchmark (CC BY 4.0) with the recomputed objective added to its result. How to run it. Sign in to download it.

feasibility_check.py