Dial-a-Ride Problem (DARP)

Category
Routing
Formulation
Combinatorial
Objective
Minimize
Time limit
60 s per instance
Paper
A Branch-and-Cut Algorithm for the Dial-a-Ride ProblemJean-François Cordeau · Operations Research, 2006

Description

A dial-a-ride service operates a fleet of vehicles to transport users between specified origins and destinations. There are n users, each requesting transportation from a pickup location to a drop-off location, and a fleet of vehicles, all based at a single depot. The service network contains a direct connection from every node to every other node. The nodes comprise one pickup node and one drop-off node for each user, plus an origin depot node and a destination depot node representing the start and end of each vehicle's route. The first half of users formulate outbound requests (from home to a destination) and the second half formulate inbound requests (from an origin back home). Each node has a two-dimensional coordinate, and the routing cost and travel time for every pair of nodes equal the Euclidean distance between them.

Each vehicle has a passenger capacity and a maximum route duration. Every node has an associated load value: pickup nodes carry a positive load equal to the number of passengers boarding, drop-off nodes carry the corresponding negative load, and both depot nodes carry zero load. Every node also has a service duration representing the time needed to board or alight passengers, with zero service duration at the depots. A time window is specified at each node, giving the earliest and latest times at which service may begin. For outbound users the time window is specified at the destination (drop-off) node and then tightened at the origin (pickup) node using the maximum ride time and direct travel time; for inbound users the time window is specified at the origin (pickup) node and then tightened at the destination (drop-off) node analogously. The depot time windows are derived from the tightest user time windows and the planning horizon. A global maximum ride time limits how long any user may spend traveling aboard a vehicle from pickup to drop-off.

The service must decide, for each vehicle, which sequence of pickup and drop-off nodes to visit, thereby determining every vehicle's route and schedule. Specifically, the planner must determine which direct connections each vehicle traverses between nodes, the time at which each vehicle begins service at each node it visits, the onboard load of each vehicle after visiting each node, and the ride time experienced by each user.

Every user request must be served exactly once, meaning exactly one vehicle visits that user's pickup node. The same vehicle that picks up a user must also deliver that user, so the pickup and drop-off of each user appear on the same vehicle's route. Every vehicle's route must begin at the origin depot and end at the destination depot. At every pickup and drop-off node, the number of times a vehicle arrives at that node must equal the number of times it departs. If a vehicle travels directly from one node to another, the time at which service begins at the second node must be no earlier than the service-start time at the first node plus the service duration at the first node plus the travel time between them. Similarly, if a vehicle travels directly from one node to another, the vehicle's load after visiting the second node must be at least the load after visiting the first node plus the load associated with the second node. Each user's ride time equals the difference between the time service begins at that user's drop-off node and the sum of the time service begins at that user's pickup node plus the service duration at the pickup node. The total duration of each vehicle's route, measured as the difference between the service-start time at the destination depot and the service-start time at the origin depot, must not exceed that vehicle's maximum route duration. Service at every node must begin within the node's time window. Each user's ride time must be at least the direct travel time from that user's pickup to drop-off and must not exceed the global maximum ride time. After visiting any node, a vehicle's load must be at least the greater of zero and that node's load value, and at most the lesser of the vehicle's capacity and the vehicle's capacity plus that node's load value.

The goal is to minimize the total routing cost, computed as the sum of the travel costs on all connections traversed by all vehicles.

Instance schema

{
  "num_vehicles": "<int> Number of vehicles available in the dial-a-ride fleet.",
  "num_users": "<int> Number of users requesting transportation service.",
  "vehicle_capacity": "<int> Maximum number of passengers that each vehicle can carry simultaneously.",
  "maximum_ride_time": "<int> Maximum time any user may spend aboard a vehicle from pickup to drop-off.",
  "num_nodes": "<int> Total number of nodes in the service network, equal to 2 * num_users + 2 (one pickup and one drop-off per user, plus origin and destination depots).",
  "nodes": [
    {
      "node_id": "<int> Unique identifier for this node, ranging from 0 (origin depot) to num_nodes - 1 (destination depot).",
      "x": "<float> Horizontal coordinate of this node's location.",
      "y": "<float> Vertical coordinate of this node's location.",
      "earliest_time": "<float> Earliest time at which service may begin at this node.",
      "latest_time": "<float> Latest time at which service may begin at this node.",
      "service_duration": "<float> Time required to board or alight passengers at this node.",
      "load": "<int> Change in vehicle occupancy when visiting this node (positive at pickups, negative at drop-offs, zero at depots).",
      "node_type": "<str> Role of this node: 'origin_depot', 'destination_depot', 'pickup', or 'dropoff'.",
      "user_id": "<int> Identifier of the user associated with this pickup or drop-off node (present only for pickup and dropoff nodes).",
      "paired_node": "<int> Node identifier of the corresponding drop-off node for a pickup, or the corresponding pickup node for a drop-off (present only for pickup and dropoff nodes).",
      "request_type": "<str> Whether this user's trip is 'outbound' (from home to a destination) or 'inbound' (from an origin back home) (present only for pickup and dropoff nodes)."
    }
  ],
  "maximum_route_duration": "<int> Maximum total duration of any single vehicle's route from depot departure to depot return."
}

Solution schema

{
  "objective_value": "<float> Total routing cost across all vehicles, computed as the sum of Euclidean distances of all arcs traversed.",
  "routes": "<dict, key: '{vehicle}'> Ordered sequence of node identifiers visited by each vehicle, starting at the origin depot (node 0) and ending at the destination depot (node 2 * num_users + 1).",
  "service_times": "<dict, key: '{node}' or 'depot_start_{vehicle}' or 'depot_end_{vehicle}'> Time at which service begins at each pickup or drop-off node, and the departure and return times at the depot for each vehicle.",
  "ride_times": "<dict, key: '{user}'> Time each user spends aboard the vehicle from the end of pickup service to the beginning of drop-off service."
}

Public instances

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

  • large_instance_3.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