Time vs Duration sample for svili

cvrptw-open-start-times.py

#!/usr/bin/env python3
#import pandas as pd
from ortools.constraint_solver import pywrapcp

def cvrptw(
        distance_mtx,
        duration_mtx,
        capacities,
        demands,
        loading_times,
        time_windows,
        vehicle_time_limit,
        vehicle_duration_limit,
        slack_time,
        start_cumul_to_zero):

    manager = pywrapcp.RoutingIndexManager(len(distance_mtx), len(capacities), 0)
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_mtx[from_node][to_node]
    distance_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(distance_callback_index)


    def time_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return duration_mtx[from_node][to_node]+loading_times[to_node]
    time_callback_index = routing.RegisterTransitCallback(time_callback)

    # Add Time Dimension
    routing.AddDimension(
            time_callback_index,
            slack_time,
            vehicle_time_limit,
            False,
            "Time")
    time_dimension = routing.GetDimensionOrDie("Time")

    # Add Duration Dimension
    routing.AddDimension(
            time_callback_index,
            slack_time,
            vehicle_duration_limit,
            True,
            "Duration")
    duration_dimension = routing.GetDimensionOrDie("Duration")

    # Add time windows
    for node, time_window in enumerate(time_windows):
        if node == 0:
            continue
        # No time window for the depot
        index = manager.NodeToIndex(node) # From external to internal index
        time_dimension.CumulVar(index).SetRange(time_window[0],time_window[1])
        routing.AddToAssignment(time_dimension.TransitVar(index))
        routing.AddToAssignment(time_dimension.SlackVar(index))
        routing.AddToAssignment(duration_dimension.SlackVar(index))
    # Adding car start nodes' slackvar and transitvar to assignment so we can print it:
    for car_ix in range(manager.GetNumberOfVehicles()):
        index = routing.Start(car_ix)
        routing.AddToAssignment(time_dimension.TransitVar(index))
        routing.AddToAssignment(time_dimension.SlackVar(index))
        routing.AddToAssignment(duration_dimension.SlackVar(index))
        time_dimension.SlackVar(index).SetValue(0) # Setting slack to 0 in start - Didn't work
        #time_dimension.CumulVar(index).SetRange(0,vehicle_time_limit) # Setting slack to 0 - Didnt work

    # link SlackVar
    for node in range(len(duration_mtx)):
        if node == 0:
            continue
        index = manager.NodeToIndex(node)
        routing.solver().Add(duration_dimension.SlackVar(index) == time_dimension.SlackVar(index))

    def demand_callback(from_index):
        from_node = manager.IndexToNode(from_index)
        return demands[from_node]
    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(demand_callback_index, 0, capacities, True, "capacity_dimension")

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.time_limit.seconds = 10

    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        print_solution(manager, routing, solution)
    else:
        print('No solution found !')
    return routing, manager, solution


def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    time_dimension = routing.GetDimensionOrDie("Time")
    duration_dimension = routing.GetDimensionOrDie("Duration")
    total_distance = 0
    total_time = 0
    total_duration = 0
    for vehicle_id in range(manager.GetNumberOfVehicles()):
        print(f'Route for vehicle {vehicle_id}:\n')
        index = routing.Start(vehicle_id)
        route_distance = 0
        output = ''
        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            time_var = time_dimension.CumulVar(index)
            time_slack = time_dimension.SlackVar(index)
            duration_var = duration_dimension.CumulVar(index)
            duration_slack = duration_dimension.SlackVar(index)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            distance = routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
            output += '{0} Time:[{1},{2}] Slack:[{3},{4}] Duration:[{5},{6}] Slack:[{7},{8}] -> '.format(
                    node,
                    solution.Min(time_var), solution.Max(time_var),
                    solution.Min(time_slack), solution.Max(time_slack),
                    solution.Min(duration_var), solution.Max(duration_var),
                    solution.Min(duration_slack), solution.Max(duration_slack)
                    )
            route_distance += distance
        node = manager.IndexToNode(index)
        time_var = time_dimension.CumulVar(index)
        duration_var = duration_dimension.CumulVar(index)
        output += '{0} Time:[{1},{2}] Duration:[{3},{4}]\n'.format(
                node,
                solution.Min(time_var), solution.Max(time_var),
                solution.Min(duration_var), solution.Max(duration_var)
                )
        output += f'Distance of the route: {route_distance}m\n'
        output += f'Duration of the route: {solution.Min(duration_var)}min\n'
        print(output)
        total_distance += route_distance
        total_duration += solution.Min(duration_var)
    print('Total Distance of all routes: {}m'.format(total_distance))
    print('Total Duration of all routes: {}min'.format(total_duration))


# The problem:
capacities = [2,2]
distance_mtx = [
    [0,1,1,1,1],
    [1,0,1,1,1],
    [1,1,0,1,1],
    [1,1,1,0,1],
    [1,1,1,1,0]
]
duration_mtx = [
    [0,1,1,1,1],
    [1,0,1,1,1],
    [1,1,0,1,1],
    [1,1,1,0,1],
    [1,1,1,1,0]
]
loading_times = [0,0,0,0,0]
demands = [0,1,1,1,1]
time_windows = [None,(1,3),(2,3),(6,9),(7,9)]

routing, manager, solution = cvrptw(
        distance_mtx,
        duration_mtx,
        capacities,
        demands,
        loading_times,
        time_windows,
        vehicle_time_limit=9,
        vehicle_duration_limit=3,
        slack_time=1,
        start_cumul_to_zero=False)
# No solution :(

zz.md

Possible output:

[0]─[/tmp]
[^v^]─mizux@nuc10i7 %./cvrptw-open-start-times.py     
Objective: 6
Route for vehicle 0:

0 Time:[1,1] Slack:[0,0] Duration:[0,0] Slack:[0,0] -> 2 Time:[2,2] Slack:[0,0] Duration:[1,1] Slack:[0,0] -> 1 Time:[3,3] Slack:[0,0] Duration:[2,2] Slack:[0,0] -> 0 Time:[4,4] Duration:[3,3]
Distance of the route: 3m
Duration of the route: 3min

Route for vehicle 1:

0 Time:[6,6] Slack:[0,0] Duration:[0,0] Slack:[0,0] -> 4 Time:[7,7] Slack:[0,0] Duration:[1,1] Slack:[0,0] -> 3 Time:[8,8] Slack:[0,0] Duration:[2,2] Slack:[0,0] -> 0 Time:[9,9] Duration:[3,3]
Distance of the route: 3m
Duration of the route: 3min

Total Distance of all routes: 6m
Total Duration of all routes: 6min