Pickup and Deliveries with time windows is slow

[Akavall]

I am running a script with 8 pickup/deliveries and 17 nodes, and it takes over 1 minute on my machine. This seems very slow. Am I missing anything?

Here is the code that I am using:

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

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

import numpy as np
from scipy.spatial import distance_matrix

def create_data_model():
    """Stores the data for the problem."""
    data = {}

    locations = [[0, 0], [8, 1], [2, 7], [3, 3],
                 [4, 4], [2, 6], [7, 3], [2, 6], [7, 3], [2, 6], [5, 6], [9, 3], [9, 1], [6, 5], [1, 8], [7, 2], [10, 0]]

    # using to ensure that distances are correct
    times = distance_matrix(locations, locations).astype(int)

    print("times shape: {}".format(times.shape))

    data["time_matrix"] = times

    print("time_matrix:")
    print(times)

    data["pickups_deliveries"] = [
        [1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12], [13, 14], [15, 16]]
    data["time_windows"] = [[1, 19],
                            [1, 19],
                            [10, 30],
                            [15, 35],
                            [15, 30],
                            [15, 40],
                            [25, 45],
                            [30, 50]
                            ]

    assert(len(data["pickups_deliveries"]) == len(data["time_windows"]))

    data['num_vehicles'] = 2
    data['depot'] = 0
    return data

def print_solution(data, manager, routing, assignment):
    """Prints assignment on console."""
    time_dimension = routing.GetDimensionOrDie('Time')
    total_time = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)
            plan_output += '{0} Time({1},{2}) -> '.format(
                manager.IndexToNode(index), assignment.Min(time_var),
                assignment.Max(time_var))
            index = assignment.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += '{0} Time({1},{2})\n'.format(
            manager.IndexToNode(index), assignment.Min(time_var),
            assignment.Max(time_var))
        plan_output += 'Time of the route: {}min\n'.format(
            assignment.Min(time_var))
        print(plan_output)
        total_time += assignment.Min(time_var)
    print('Total time of all routes: {}min'.format(total_time))

def main():
    """Solve the VRP with time windows."""
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(
        len(data['time_matrix']), data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)

    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['time_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    time = 'Time'
    routing.AddDimension(
        transit_callback_index,
        300,  # allow waiting time
        1000,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time)
    time_dimension = routing.GetDimensionOrDie(time)

    # Add time window constraints for each location except depot.
    # also add pickups/dropoffs
    for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx == 0:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    for pd, tw in zip(data['pickups_deliveries'], data["time_windows"]):
        pickup, dropoff = pd
        routing.AddPickupAndDelivery(pickup, dropoff)
        routing.solver().Add(routing.VehicleVar(pickup) == routing.VehicleVar(dropoff))

        time_dimension.CumulVar(dropoff).SetRange(tw[0],
                                                  tw[1])

    for i in range(data['num_vehicles']):
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.End(i)))
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    assignment = routing.SolveWithParameters(search_parameters)
    if assignment:
        print_solution(data, manager, routing, assignment)

if __name__ == '__main__':
    main()

[Mizux]

You should change the First Solution Strategy according to the code https://github.com/google/or-tools/blob/f3fd201e68cf75b7720ff5c3cadc599a1d02b54b/ortools/constraint_solver/routing.cc#L4650-L4660 So, try to use routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION instead

[Mizux]

using it:

%time ./test.py
times shape: (17, 17)
time_matrix:
[[ 0  8  7  4  5  6  7  6  7  6  7  9  9  7  8  7 10]
 [ 8  0  8  5  5  7  2  7  2  7  5  2  1  4  9  1  2]
 [ 7  8  0  4  3  1  6  1  6  1  3  8  9  4  1  7 10]
 [ 4  5  4  0  1  3  4  3  4  3  3  6  6  3  5  4  7]
 [ 5  5  3  1  0  2  3  2  3  2  2  5  5  2  5  3  7]
 [ 6  7  1  3  2  0  5  0  5  0  3  7  8  4  2  6 10]
 [ 7  2  6  4  3  5  0  5  0  5  3  2  2  2  7  1  4]
 [ 6  7  1  3  2  0  5  0  5  0  3  7  8  4  2  6 10]
 [ 7  2  6  4  3  5  0  5  0  5  3  2  2  2  7  1  4]
 [ 6  7  1  3  2  0  5  0  5  0  3  7  8  4  2  6 10]
 [ 7  5  3  3  2  3  3  3  3  3  0  5  6  1  4  4  7]
 [ 9  2  8  6  5  7  2  7  2  7  5  0  2  3  9  2  3]
 [ 9  1  9  6  5  8  2  8  2  8  6  2  0  5 10  2  1]
 [ 7  4  4  3  2  4  2  4  2  4  1  3  5  0  5  3  6]
 [ 8  9  1  5  5  2  7  2  7  2  4  9 10  5  0  8 12]
 [ 7  1  7  4  3  6  1  6  1  6  4  2  2  3  8  0  3]
 [10  2 10  7  7 10  4 10  4 10  7  3  1  6 12  3  0]]
Route for vehicle 0:
0 Time(0,0) -> 15 Time(7,10) -> 1 Time(8,11) -> 5 Time(15,18) -> 9 Time(15,18) -> 2 Time(16,19) -> 10 Time(19,22) -> 6 Time(25,25) -> 11 Time(27,27) -> 16 Time(30,30) -> 12 Time(31,31) -> 0 Time(40,40)
Time of the route: 40min

Route for vehicle 1:
0 Time(0,0) -> 3 Time(15,18) -> 4 Time(16,19) -> 13 Time(18,23) -> 14 Time(25,28) -> 7 Time(30,30) -> 8 Time(35,35) -> 0 Time(42,42)
Time of the route: 42min

Total time of all routes: 82min
./test.py  0.45s user 0.70s system 332% cpu 0.347 total

note:

python3 -m pip show ortools scipy
Name: ortools
Version: 7.1.6720
...
---
Name: scipy
Version: 1.2.1

[Akavall]

Thank You @Mizux, it is much faster indeed.

Is there a guide that explains in what situation to use what First Solution Strategy?

I know that there is: https://developers.google.com/optimization/routing/routing_options, but the descriptions here are on the high level side.

[Roosjeva]

I've a question regarding this subject. I would like to use distance and time as variables to generate routes, is this possible?