Vehicle Routing with Pickups and Deliveries

In this section we describe a VRP in which each vehicle picks up items at various locations and drops them off at others. The problem is to assign routes for the vehicles to pick up and deliver all the items, while minimizing the length of the longest route.

VRP example with pickups and deliveries

The diagram below shows the pickup and delivery locations on a grid similar to the one in the previous VRP example. For each item, there is a directed edge from the pickup location to the delivery location.

Solving the example with OR-Tools

The following sections describe how to solve the VRP with pickups and deliveries. Much of the code is borrowed from the previous VRP example, so we'll focus on the parts that are new.

Create the data

The data for the problem includes the distance matrix from the previous VRP example, along with a list of pairs of pickup and delivery locations, data['pickups_deliveries'], corresponding to the directed edges in the diagram above. The code below defines the pickup and delivery locations.

Python

    data['pickups_deliveries'] = [
        [1, 6],
        [2, 10],
        [4, 3],
        [5, 9],
        [7, 8],
        [15, 11],
        [13, 12],
        [16, 14],
    ]

C++

  const std::vector<std::vector<RoutingIndexManager::NodeIndex>>
      pickups_deliveries{
          {RoutingIndexManager::NodeIndex{1},
           RoutingIndexManager::NodeIndex{6}},
          {RoutingIndexManager::NodeIndex{2},
           RoutingIndexManager::NodeIndex{10}},
          {RoutingIndexManager::NodeIndex{4},
           RoutingIndexManager::NodeIndex{3}},
          {RoutingIndexManager::NodeIndex{5},
           RoutingIndexManager::NodeIndex{9}},
          {RoutingIndexManager::NodeIndex{7},
           RoutingIndexManager::NodeIndex{8}},
          {RoutingIndexManager::NodeIndex{15},
           RoutingIndexManager::NodeIndex{11}},
          {RoutingIndexManager::NodeIndex{13},
           RoutingIndexManager::NodeIndex{12}},
          {RoutingIndexManager::NodeIndex{16},
           RoutingIndexManager::NodeIndex{14}},
      };

Java

    public final int[][] pickupsDeliveries = {
        {1, 6},
        {2, 10},
        {4, 3},
        {5, 9},
        {7, 8},
        {15, 11},
        {13, 12},
        {16, 14},
    };

C#

    public int[][] PickupsDeliveries = {
      new int[] {1, 6},
      new int[] {2, 10},
      new int[] {4, 3},
      new int[] {5, 9},
      new int[] {7, 8},
      new int[] {15, 11},
      new int[] {13, 12},
      new int[] {16, 14},
    };

For each pair, the first entry is index of the pickup location, and the second is the index of the delivery location.

Define pickup and delivery requests

The following code defines pickup and delivery requests, using pickup and delivery locations in data['pickups_deliveries'].

Python

    for request in data['pickups_deliveries']:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(
            routing.VehicleVar(pickup_index) == routing.VehicleVar(
                delivery_index))
        routing.solver().Add(
            distance_dimension.CumulVar(pickup_index) <=
            distance_dimension.CumulVar(delivery_index))

C++

  Solver* const solver = routing.solver();
  for (const auto& request : data.pickups_deliveries) {
    int64 pickup_index = manager.NodeToIndex(request[0]);
    int64 delivery_index = manager.NodeToIndex(request[1]);
    routing.AddPickupAndDelivery(pickup_index, delivery_index);
    solver->AddConstraint(solver->MakeEquality(
        routing.VehicleVar(pickup_index), routing.VehicleVar(delivery_index)));
    solver->AddConstraint(
        solver->MakeLessOrEqual(distance_dimension.CumulVar(pickup_index),
                                distance_dimension.CumulVar(delivery_index)));
  }

Java

    Solver solver = routing.solver();
    for (int[] request : data.pickupsDeliveries) {
      long pickupIndex = manager.nodeToIndex(request[0]);
      long deliveryIndex = manager.nodeToIndex(request[1]);
      routing.addPickupAndDelivery(pickupIndex, deliveryIndex);
      solver.addConstraint(
          solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex)));
      solver.addConstraint(solver.makeLessOrEqual(
          distanceDimension.cumulVar(pickupIndex), distanceDimension.cumulVar(deliveryIndex)));
    }

C#

    Solver solver = routing.solver();
    for(int i=0; i < data.PickupsDeliveries.GetLength(0); i++) {
      long pickupIndex = manager.NodeToIndex(data.PickupsDeliveries[i][0]);
      long deliveryIndex = manager.NodeToIndex(data.PickupsDeliveries[i][1]);
      routing.AddPickupAndDelivery(pickupIndex, deliveryIndex);
      solver.Add(solver.MakeEquality(
            routing.VehicleVar(pickupIndex),
            routing.VehicleVar(deliveryIndex)));
      solver.Add(solver.MakeLessOrEqual(
            distanceDimension.CumulVar(pickupIndex),
            distanceDimension.CumulVar(deliveryIndex)));
    }

For each pair, the command

routing.AddPickupAndDelivery(pickup_index, delivery_index)

creates a pickup and delivery request for an item.

The following line adds the requirement that each item must be picked up and delivered by the same vehicle.

routing.solver().Add(
            routing.VehicleVar(pickup_index) ==
            routing.VehicleVar(delivery_index))

Finally, we add the obvious requirement that each item must be picked up before it is delivered. To do so, we require that a vehicle's cumulative distance at an item's pickup location is at most its cumulative distance at the delivery location.

routing.solver().Add(
            distance_dimension.CumulVar(pickup_index) <=
            distance_dimension.CumulVar(delivery_index))

Running the program

The complete programs for the VRP with pickups and deliveries are shown in the next section. When you run the program, it displays the following routes.

Objective: 226116
Route for vehicle 0:
 0 ->  13 ->  15 ->  11 ->  12 -> 0
Distance of the route: 1552m

Route for vehicle 1: 0 -> 5 -> 2 -> 10 -> 16 -> 14 -> 9 -> 0 Distance of the route: 2192m

Route for vehicle 2: 0 -> 4 -> 3 -> 0 Distance of the route: 1392m

Route for vehicle 3: 0 -> 7 -> 1 -> 6 -> 8 -> 0 Distance of the route: 1780m

Total Distance of all routes: 6916m

The following diagram shows the routes:

Complete programs

The complete programs are shown below.

Python

"""Simple Pickup Delivery Problem (PDP)."""

from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['distance_matrix'] = [
        [
            0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,
            468, 776, 662
        ],
        [
            548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
            1016, 868, 1210
        ],
        [
            776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164,
            1130, 788, 1552, 754
        ],
        [
            696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
            1164, 560, 1358
        ],
        [
            582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
            1050, 674, 1244
        ],
        [
            274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,
            514, 1050, 708
        ],
        [
            502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,
            514, 1278, 480
        ],
        [
            194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320,
            662, 742, 856
        ],
        [
            308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662,
            320, 1084, 514
        ],
        [
            194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388,
            274, 810, 468
        ],
        [
            536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,
            730, 388, 1152, 354
        ],
        [
            502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114,
            308, 650, 274, 844
        ],
        [
            388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194,
            536, 388, 730
        ],
        [
            354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0,
            342, 422, 536
        ],
        [
            468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536,
            342, 0, 764, 194
        ],
        [
            776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274,
            388, 422, 764, 0, 798
        ],
        [
            662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730,
            536, 194, 798, 0
        ],
    ]
    data['pickups_deliveries'] = [
        [1, 6],
        [2, 10],
        [4, 3],
        [5, 9],
        [7, 8],
        [15, 11],
        [13, 12],
        [16, 14],
    ]
    data['num_vehicles'] = 4
    data['depot'] = 0
    return data


def print_solution(data, manager, routing, assignment):
    """Prints assignment on console."""
    total_distance = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            previous_index = index
            index = assignment.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
        print(plan_output)
        total_distance += route_distance
    print('Total Distance of all routes: {}m'.format(total_distance))


def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data['distance_matrix']), data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)


    # Define cost of each arc.
    def distance_callback(from_index, to_index):
        """Returns the manhattan distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Distance constraint.
    dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        3000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Define Transportation Requests.
    for request in data['pickups_deliveries']:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(
            routing.VehicleVar(pickup_index) == routing.VehicleVar(
                delivery_index))
        routing.solver().Add(
            distance_dimension.CumulVar(pickup_index) <=
            distance_dimension.CumulVar(delivery_index))

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)

    # Solve the problem.
    assignment = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if assignment:
        print_solution(data, manager, routing, assignment)


if __name__ == '__main__':
    main()

C++

#include <vector>
#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"

namespace operations_research {
struct DataModel {
  const std::vector<std::vector<int64>> distance_matrix{
      {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468,
       776, 662},
      {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
       1016, 868, 1210},
      {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130,
       788, 1552, 754},
      {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
       1164, 560, 1358},
      {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
       1050, 674, 1244},
      {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514,
       1050, 708},
      {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514,
       1278, 480},
      {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662,
       742, 856},
      {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320,
       1084, 514},
      {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274,
       810, 468},
      {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730,
       388, 1152, 354},
      {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308,
       650, 274, 844},
      {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536,
       388, 730},
      {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342,
       422, 536},
      {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342,
       0, 764, 194},
      {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388,
       422, 764, 0, 798},
      {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536,
       194, 798, 0},
  };
  const std::vector<std::vector<RoutingIndexManager::NodeIndex>>
      pickups_deliveries{
          {RoutingIndexManager::NodeIndex{1},
           RoutingIndexManager::NodeIndex{6}},
          {RoutingIndexManager::NodeIndex{2},
           RoutingIndexManager::NodeIndex{10}},
          {RoutingIndexManager::NodeIndex{4},
           RoutingIndexManager::NodeIndex{3}},
          {RoutingIndexManager::NodeIndex{5},
           RoutingIndexManager::NodeIndex{9}},
          {RoutingIndexManager::NodeIndex{7},
           RoutingIndexManager::NodeIndex{8}},
          {RoutingIndexManager::NodeIndex{15},
           RoutingIndexManager::NodeIndex{11}},
          {RoutingIndexManager::NodeIndex{13},
           RoutingIndexManager::NodeIndex{12}},
          {RoutingIndexManager::NodeIndex{16},
           RoutingIndexManager::NodeIndex{14}},
      };
  const int num_vehicles = 4;
  const RoutingIndexManager::NodeIndex depot{0};
};

//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution) {
  int64 total_distance{0};
  for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
    int64 index = routing.Start(vehicle_id);
    LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
    int64 route_distance{0};
    std::stringstream route;
    while (routing.IsEnd(index) == false) {
      route << manager.IndexToNode(index).value() << " -> ";
      int64 previous_index = index;
      index = solution.Value(routing.NextVar(index));
      route_distance += const_cast<RoutingModel&>(routing).GetArcCostForVehicle(
          previous_index, index, int64{vehicle_id});
    }
    LOG(INFO) << route.str() << manager.IndexToNode(index).value();
    LOG(INFO) << "Distance of the route: " << route_distance << "m";
    total_distance += route_distance;
  }
  LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

void VrpGlobalSpan() {
  // Instantiate the data problem.
  DataModel data;

  // Create Routing Index Manager
  RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles,
                              data.depot);

  // Create Routing Model.
  RoutingModel routing(manager);

  // Define cost of each arc.
  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](int64 from_index, int64 to_index) -> int64 {
        // Convert from routing variable Index to distance matrix NodeIndex.
        auto from_node = manager.IndexToNode(from_index).value();
        auto to_node = manager.IndexToNode(to_index).value();
        return data.distance_matrix[from_node][to_node];
      });
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

  // Add Distance constraint.
  routing.AddDimension(transit_callback_index,  // transit callback
                       0,                       // no slack
                       3000,  // vehicle maximum travel distance
                       true,  // start cumul to zero
                       "Distance");
  const RoutingDimension& distance_dimension =
      routing.GetDimensionOrDie("Distance");
  const_cast<RoutingDimension&>(distance_dimension)
      .SetGlobalSpanCostCoefficient(100);

  // Define Transportation Requests.
  Solver* const solver = routing.solver();
  for (const auto& request : data.pickups_deliveries) {
    int64 pickup_index = manager.NodeToIndex(request[0]);
    int64 delivery_index = manager.NodeToIndex(request[1]);
    routing.AddPickupAndDelivery(pickup_index, delivery_index);
    solver->AddConstraint(solver->MakeEquality(
        routing.VehicleVar(pickup_index), routing.VehicleVar(delivery_index)));
    solver->AddConstraint(
        solver->MakeLessOrEqual(distance_dimension.CumulVar(pickup_index),
                                distance_dimension.CumulVar(delivery_index)));
  }

  // Setting first solution heuristic.
  RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
  searchParameters.set_first_solution_strategy(
      FirstSolutionStrategy::PARALLEL_CHEAPEST_INSERTION);

  // Solve the problem.
  const Assignment* solution = routing.SolveWithParameters(searchParameters);

  // Print solution on console.
  PrintSolution(data, manager, routing, *solution);
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::VrpGlobalSpan();
  return EXIT_SUCCESS;
}

Java

import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.RoutingDimension;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.Solver;
import com.google.ortools.constraintsolver.main;
import java.util.logging.Logger;

/** Minimal Pickup & Delivery Problem (PDP).*/
public class VrpPickupDelivery {
  static {
    System.loadLibrary("jniortools");
  }

  private static final Logger logger = Logger.getLogger(VrpPickupDelivery.class.getName());

  static class DataModel {
    public final long[][] distanceMatrix = {
        {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662},
        {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210},
        {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754},
        {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358},
        {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244},
        {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708},
        {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480},
        {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856},
        {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514},
        {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468},
        {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354},
        {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844},
        {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730},
        {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536},
        {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194},
        {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798},
        {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0},
    };
    public final int[][] pickupsDeliveries = {
        {1, 6},
        {2, 10},
        {4, 3},
        {5, 9},
        {7, 8},
        {15, 11},
        {13, 12},
        {16, 14},
    };
    public final int vehicleNumber = 4;
    public final int depot = 0;
  }

  /// @brief Print the solution.
  static void printSolution(
      DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
    long totalDistance = 0;
    for (int i = 0; i < data.vehicleNumber; ++i) {
      long index = routing.start(i);
      logger.info("Route for Vehicle " + i + ":");
      long routeDistance = 0;
      String route = "";
      while (!routing.isEnd(index)) {
        route += manager.indexToNode(index) + " -> ";
        long previousIndex = index;
        index = solution.value(routing.nextVar(index));
        routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
      }
      logger.info(route + manager.indexToNode(index));
      logger.info("Distance of the route: " + routeDistance + "m");
      totalDistance += routeDistance;
    }
    logger.info("Total Distance of all routes: " + totalDistance + "m");
  }

  public static void main(String[] args) throws Exception {
    // Instantiate the data problem.
    final DataModel data = new DataModel();

    // Create Routing Index Manager
    RoutingIndexManager manager =
        new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);

    // Create Routing Model.
    RoutingModel routing = new RoutingModel(manager);

    // Create and register a transit callback.
    final int transitCallbackIndex =
        routing.registerTransitCallback((long fromIndex, long toIndex) -> {
          // Convert from routing variable Index to user NodeIndex.
          int fromNode = manager.indexToNode(fromIndex);
          int toNode = manager.indexToNode(toIndex);
          return data.distanceMatrix[fromNode][toNode];
        });

    // Define cost of each arc.
    routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

    // Add Distance constraint.
    routing.addDimension(transitCallbackIndex, // transit callback index
        0, // no slack
        3000, // vehicle maximum travel distance
        true, // start cumul to zero
        "Distance");
    RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
    distanceDimension.setGlobalSpanCostCoefficient(100);

    // Define Transportation Requests.
    Solver solver = routing.solver();
    for (int[] request : data.pickupsDeliveries) {
      long pickupIndex = manager.nodeToIndex(request[0]);
      long deliveryIndex = manager.nodeToIndex(request[1]);
      routing.addPickupAndDelivery(pickupIndex, deliveryIndex);
      solver.addConstraint(
          solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex)));
      solver.addConstraint(solver.makeLessOrEqual(
          distanceDimension.cumulVar(pickupIndex), distanceDimension.cumulVar(deliveryIndex)));
    }

    // Setting first solution heuristic.
    RoutingSearchParameters searchParameters =
        main.defaultRoutingSearchParameters()
            .toBuilder()
            .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PARALLEL_CHEAPEST_INSERTION)
            .build();

    // Solve the problem.
    Assignment solution = routing.solveWithParameters(searchParameters);

    // Print solution on console.
    printSolution(data, routing, manager, solution);
  }
}

C#

using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;

/// <summary>
///   Minimal Pickup & Delivery Problem (PDP).
/// </summary>
public class VrpPickupDelivery {
  class DataModel {
    public long[,] DistanceMatrix = {
      {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662},
      {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210},
      {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754},
      {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358},
      {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244},
      {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708},
      {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480},
      {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856},
      {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514},
      {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468},
      {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354},
      {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844},
      {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730},
      {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536},
      {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194},
      {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798},
      {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0}
    };
    public int[][] PickupsDeliveries = {
      new int[] {1, 6},
      new int[] {2, 10},
      new int[] {4, 3},
      new int[] {5, 9},
      new int[] {7, 8},
      new int[] {15, 11},
      new int[] {13, 12},
      new int[] {16, 14},
    };
    public int VehicleNumber = 4;
    public int Depot = 0;
  };

  /// <summary>
  ///   Print the solution.
  /// </summary>
  static void PrintSolution(
      in DataModel data,
      in RoutingModel routing,
      in RoutingIndexManager manager,
      in Assignment solution) {
    long totalDistance = 0;
    for (int i = 0; i < data.VehicleNumber; ++i) {
      Console.WriteLine("Route for Vehicle {0}:", i);
      long routeDistance = 0;
      var index = routing.Start(i);
      while (routing.IsEnd(index) == false) {
        Console.Write("{0} -> ", manager.IndexToNode((int)index));
        var previousIndex = index;
        index = solution.Value(routing.NextVar(index));
        routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
      }
      Console.WriteLine("{0}", manager.IndexToNode((int)index));
      Console.WriteLine("Distance of the route: {0}m", routeDistance);
      totalDistance += routeDistance;
    }
    Console.WriteLine("Total Distance of all routes: {0}m", totalDistance);
  }

  public static void Main(String[] args) {
    // Instantiate the data problem.
    DataModel data = new DataModel();

    // Create Routing Index Manager
    RoutingIndexManager manager = new RoutingIndexManager(
        data.DistanceMatrix.GetLength(0),
        data.VehicleNumber,
        data.Depot);


    // Create Routing Model.
    RoutingModel routing = new RoutingModel(manager);

    // Create and register a transit callback.
    int transitCallbackIndex = routing.RegisterTransitCallback(
        (long fromIndex, long toIndex) => {
        // Convert from routing variable Index to distance matrix NodeIndex.
        var fromNode = manager.IndexToNode(fromIndex);
        var toNode = manager.IndexToNode(toIndex);
        return data.DistanceMatrix[fromNode, toNode]; }
        );

    // Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

    // Add Distance constraint.
    routing.AddDimension(transitCallbackIndex, 0, 3000,
        true,  // start cumul to zero
        "Distance");
    RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
    distanceDimension.SetGlobalSpanCostCoefficient(100);

    // Define Transportation Requests.
    Solver solver = routing.solver();
    for(int i=0; i < data.PickupsDeliveries.GetLength(0); i++) {
      long pickupIndex = manager.NodeToIndex(data.PickupsDeliveries[i][0]);
      long deliveryIndex = manager.NodeToIndex(data.PickupsDeliveries[i][1]);
      routing.AddPickupAndDelivery(pickupIndex, deliveryIndex);
      solver.Add(solver.MakeEquality(
            routing.VehicleVar(pickupIndex),
            routing.VehicleVar(deliveryIndex)));
      solver.Add(solver.MakeLessOrEqual(
            distanceDimension.CumulVar(pickupIndex),
            distanceDimension.CumulVar(deliveryIndex)));
    }

    // Setting first solution heuristic.
    RoutingSearchParameters searchParameters =
      operations_research_constraint_solver.DefaultRoutingSearchParameters();
    searchParameters.FirstSolutionStrategy =
      FirstSolutionStrategy.Types.Value.PathCheapestArc;

    // Solve the problem.
    Assignment solution = routing.SolveWithParameters(searchParameters);

    // Print solution on console.
    PrintSolution(data, routing, manager, solution);
  }
}

Envoyer des commentaires concernant…