How to add a time dimension for each node in Google OR-Tools

Viewed 427

I am solving the multi-depot multiple vehicles vehicle routing problem using OR-Tools and so far I have managed to set up a model in which one vehicle leaves from each depot and between them they visit each node within their maximum time allowance and then exit via the dummy node 0. However, as this is a real-world problem, at each node the vehicle is required to stop for a set time to carry out a service, with each node having a set waiting time, such as in the table below:

Node Duration
4 9
38 8
... ...
8545 17

I am unsure how to add these to each node, although the arc lengths between nodes so far represent the travel time between each node (with the assumption that all vehicles are travelling at the same speed). So my question is how I can add these wait times into the model, while still minimizing the travel time for each vehicle and keeping them below their maximum threshold of 25200 seconds (corresponding to a 7-hour shift). I have included my working code below:

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

The distance matrix was fed in from a csv laid out like so:

Blank 4 38 71 90 94 ... 8545
4 0 1280 1762 1406 1589 ... 1017
38 1280 0 681 202 385 ... 1433
71 1762 681 0 503 0 ... 0
90 1406 202 503 0 0 ... 1559
94 1589 385 0 0 0 ... 1742
.. .. ... ... ... ... 0 ...
8545 1017 1433 0 1559 1742 ... 0
CareDist_Matrix = np.loadtxt(open("CareDistances-FULL.csv", "rb"), dtype=int, delimiter=",", skiprows=1)
CareDist_Matrix

And the main body of the model follows:

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['distance_matrix'] = CareDist_Matrix
    data['num_vehicles'] = 6
    data['starts'] = [3, 7, 14, 104, 185, 220]
    data['ends'] = [0, 0, 0, 0, 0, 0]
    return data

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    max_route_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 = solution.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)
        max_route_distance = max(route_distance, max_route_distance)
    print('Maximum of the route distances: {}m'.format(max_route_distance))
    """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['starts'],
                                           data['ends'])

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


    # Create and register a transit callback.
    def distance_callback(from_index, to_index):
        """Returns the 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)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

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

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

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

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)
if __name__ == '__main__':
    main()
1 Answers

You can simply add the duration to the travel in the callback function. So, total time to visit a node is the travel time to that node plus the action time in that node:

def distance_callback(from_index, to_index):
    """Returns the 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] + duration['to_index']
Related