VRP With differents speed and autonomy

vrp_multiple_transit.py

#!/usr/bin/env python3
"""Vehicles Routing Problem (VRP)."""

from functools import partial
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# Vehicle 1: slow (speed: 20)
# Vehicle 2: slow (speed: 20)
# Vehicle 3: average (speed: 18)
# Vehicle 4: fast (speed: 15)


def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    max_route_time = 0
    for vehicle_id in range(manager.GetNumberOfVehicles()):
        index = routing.Start(vehicle_id)
        plan_output = f'Route for vehicle {vehicle_id}:\n'
        route_time = 0
        while not routing.IsEnd(index):
            plan_output += f'{manager.IndexToNode(index)} '
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            time = routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
            plan_output += f'--{time}min--> '
            route_time += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
        plan_output += f'{manager.IndexToNode(index)}\n'
        plan_output += f'Time of the route: {route_time}min\n'
        print(plan_output)
        max_route_time = max(route_time, max_route_time)
    print(f'Maximum of the route time: {max_route_time}min')

def main():
    """Solve the CVRP problem."""
    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
            24, # locations
            4, # vehicle number
            0) # depot

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


    # Create and register a transit callback.
    def time_callback(from_index, to_index, speed):
        """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)
        if from_node == 0 or to_node == 0:
            return speed
        return abs(from_node - to_node) * speed

    slow_callback = partial(time_callback, speed=20)
    average_callback = partial(time_callback, speed=18)
    fast_callback = partial(time_callback, speed=15)

    slow_index = routing.RegisterTransitCallback(slow_callback)
    average_index = routing.RegisterTransitCallback(average_callback)
    fast_index = routing.RegisterTransitCallback(fast_callback)

    # Define cost of each arc for each vehicle.
    routing.SetArcCostEvaluatorOfVehicle(slow_index, 0)
    routing.SetArcCostEvaluatorOfVehicle(slow_index, 1)
    routing.SetArcCostEvaluatorOfVehicle(average_index, 2)
    routing.SetArcCostEvaluatorOfVehicle(fast_index, 3)

    # Add Distance constraint.
    dimension_name = 'Time'
    routing.AddDimensionWithVehicleTransitAndCapacity(
        [slow_index, slow_index, average_index, fast_index],
        0,  # no slack
        [250, 200, 150, 100],  # vehicle maximum travel time
        True,  # start cumul to zero
        dimension_name)

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

    #search_params.log_search = True
    search_params.local_search_metaheuristic = (
            routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_params.time_limit.seconds = 10

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

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


if __name__ == '__main__':
    main()

zz.md

[0]─[~/work/tmp]
[^v^]─mizux@nuc10i7 %./vrp_multiple_transit.py
Objective: 474
Route for vehicle 0:
0 --20min--> 11 --20min--> 10 --20min--> 9 --20min--> 8 --20min--> 7 --20min--> 6 --20min--> 5 --20min--> 4 --20min--> 3 --20min--> 2 --20min--> 1 --20min--> 0
Time of the route: 240min

Route for vehicle 1:
0 --0min--> 0
Time of the route: 0min

Route for vehicle 2:
0 --18min--> 18 --18min--> 17 --18min--> 16 --18min--> 15 --18min--> 14 --18min--> 13 --18min--> 12 --18min--> 0
Time of the route: 144min

Route for vehicle 3:
0 --15min--> 23 --15min--> 22 --15min--> 21 --15min--> 20 --15min--> 19 --15min--> 0
Time of the route: 90min

Maximum of the route time: 240min