VRP Collect and Deliver

vrp_collect_deliver.py

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

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 = {}
    # 1 Depot: S, 10 Deliveries D0-D9, 6 Pickups P0-P5
    # 17 nodes
    data['distance_matrix'] = [
        [  #S D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 P0 P1 P2 P3 P4 P5
            0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1
        ],
        [
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0
        ],
    ]
    #                    [S  D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 P0 P1 P2 P3 P4 P5
    data['deliveries'] = [0, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0, 0, 0, 0, 0, 0]
    data['loads']      = [0, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,+1,+1,+1,+1,+1,+1]
    data['vehicle_capacities'] = [5, 5]
    data['num_vehicles'] = 2
    data['depot'] = 0
    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    total_distance = 0
    total_load = 0
    deliveries_dimension = routing.GetDimensionOrDie('Deliveries')
    loads_dimension = routing.GetDimensionOrDie('Loads')
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        delivery_var = deliveries_dimension.CumulVar(index)
        load_var = loads_dimension.CumulVar(index)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        route_deliveries = solution.Value(delivery_var)
        route_load = solution.Value(load_var)
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            delivery_var = deliveries_dimension.CumulVar(index)
            load_var = loads_dimension.CumulVar(index)
            route_deliveries = solution.Value(delivery_var)
            route_load = solution.Value(load_var)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
            plan_output += ' {0} Deliveries({1}) Load({2}) ->'.format(node_index, route_deliveries,route_load)
        delivery_var = deliveries_dimension.CumulVar(index)
        load_var = loads_dimension.CumulVar(index)
        route_deliveries = solution.Value(delivery_var)
        route_load = solution.Value(load_var)
        plan_output += ' {0} Deliveries({1}) Load({2})\n'.format(
            manager.IndexToNode(index),
            route_deliveries,
            route_load)
        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
        plan_output += 'Deliveries of the route: {}\n'.format(route_deliveries)
        plan_output += 'Load of the route: {}\n'.format(route_load)
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print('Total distance of all routes: {}m'.format(total_distance))
    print('Total load of all routes: {}'.format(total_load))


def main():
    """Solve the CVRP problem."""
    # 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)

    # 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 Deliveries constraint.
    def delivery_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data['deliveries'][from_node]
    delivery_callback_index = routing.RegisterUnaryTransitCallback(delivery_callback)
    routing.AddDimensionWithVehicleCapacity(
        delivery_callback_index,
        0,  # null capacity slack
        data['vehicle_capacities'],  # vehicle maximum capacities
        False,  # start cumul to zero
        'Deliveries')

    # Add Load constraint.
    def load_callback(from_index):
        """Returns the load of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data['loads'][from_node]
    load_callback_index = routing.RegisterUnaryTransitCallback(load_callback)
    routing.AddDimensionWithVehicleCapacity(
        load_callback_index,
        0,  # null capacity slack
        data['vehicle_capacities'],  # vehicle maximum capacities
        False,  # start cumul to zero
        'Loads')

    # Add Constraint Both cumulVar are identical at start
    deliveries_dimension = routing.GetDimensionOrDie('Deliveries')
    loads_dimension = routing.GetDimensionOrDie('Loads')
    for vehicle_id in range(data['num_vehicles']):
      index = routing.Start(vehicle_id)
      routing.solver().Add(
          deliveries_dimension.CumulVar(index) == loads_dimension.CumulVar(index))

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.log_search = True
    #search_parameters.first_solution_strategy = (
    #    routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC)
    #search_parameters.first_solution_strategy = (
    #    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    #search_parameters.first_solution_strategy = (
    #    routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)
    #search_parameters.first_solution_strategy = (
    #    routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_INSERTION)


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

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


if __name__ == '__main__':
    main()

zz.md

Potential output:

./vrp_collect_deliver.py 
WARNING: Logging before InitGoogleLogging() is written to STDERR
I1119 08:19:04.735839  2225 search.cc:264] Start search (memory used = 14.12 MB)
I1119 08:19:04.793701  2225 search.cc:264] Root node processed (time = 0 ms, constraints = 90, memory used = 14.16 MB)
I1119 08:19:06.883544  2225 search.cc:264] Solution #0 (18, time = 2 ms, branches = 66, failures = 9, depth = 33, memory used = 14.16 MB)
I1119 08:19:11.085449  2225 search.cc:264] Finished search tree (time = 6 ms, branches = 101, failures = 45, neighbors = 1154, filtered neighbors = 0, accepted neigbors = 0, memory used = 14.16 MB)
I1119 08:19:11.110839  2225 search.cc:264] End search (time = 6 ms, branches = 101, failures = 45, memory used = 14.16 MB, speed = 16833 branches/s)
Route for vehicle 0:
 0 Deliveries(5) Load(5) -> 1 Deliveries(5) Load(5) -> 2 Deliveries(4) Load(4) -> 3 Deliveries(3) Load(3) -> 4 Deliveries(2) Load(2) -> 5 Deliveries(1) Load(1) -> 11 Deliveries(0) Load(0) -> 13 Deliveries(0) Load(1) -> 15 Deliveries(0) Load(2) -> 0 Deliveries(0) Load(3)
Distance of the route: 9m
Deliveries of the route: 0
Load of the route: 3

Route for vehicle 1:
 0 Deliveries(5) Load(5) -> 6 Deliveries(5) Load(5) -> 7 Deliveries(4) Load(4) -> 8 Deliveries(3) Load(3) -> 9 Deliveries(2) Load(2) -> 10 Deliveries(1) Load(1) -> 12 Deliveries(0) Load(0) -> 14 Deliveries(0) Load(1) -> 16 Deliveries(0) Load(2) -> 0 Deliveries(0) Load(3)
Distance of the route: 9m
Deliveries of the route: 0
Load of the route: 3

Total distance of all routes: 18m
Total load of all routes: 6

Hi @Mizux ,

I have a couple of questions if you don't mind me asking:

1. What does [5, 5] stands for in vehicle_capacities? one of them will prob. refer to items but what about the other one?

2. What does 0, # null capacity slack refer to?

3. Is there a way to add time limits for each pickup? ie. The truck is on pickup P0, the driver has 15 mins to pick up all items.

4. Is there a way to add time limits for each delivery? ie. The truck is delivering the item, the driver has <5 mins to accomplish that.

5. The current example assumes we have 10 deliveries and 6 pickups.
   I have this scenario: Load P0 has 10 items and Load P1 has 8. The driver has to deliver these items to 18 different locations. The driver grabs all items on P0 and starts his route. When the driver is closer to P1, he goes there and starts picking up all items on P1. After that, he proceeds with his route. Now, he's delivering items from P0 and P1. Can I handle this scenario with this implementation?

Regards,

Hi @Mizux,

Thank you for sharing vrp collect and deliver. I want to build on top of this along with cvrp reload. I want to allow vehicles to reload their capacities after coming back to the depot. I went through the cvrp_reload.py sample file (link). There we create a dummy depot and allow for slack up to the vehicle's capacity.

But here since we have two dimensions for deliveries and overall load, so in the dummy depot we cannot just keep negative of the vehicle's capacity. So, i tried creating two dummy depots where one has positive vehicle capacity and the other dummy depot has negative vehicle capacity. Now case 1 works with 0 or vehicle_capcity slack. But case 1 only works with a slack of vehicle capacity, but case 3 works with 0 slack only. I think that allowing slack in capacity leads to infeasible intermediate routes, if this can be achieved with zero slack that would be great. Cases 4 and 5 would require correct working of case 3. It would be really helpful if you could help me out here. PFA my source code for you reference. Thank you.

"""Capacited Vehicles Routing Problem (CVRP)."""

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, 10, 15, 20, 30,  4000,  4000],  # depot
            [10, 0, 35, 25, 10, 10, 10],  # location 1
            [15, 35, 0, 30, 15, 15, 15],  # location 2
            [20, 25, 30, 0, 20, 20, 20],  # location 3
            [20, 30, 25, 10, 0, 20, 20],  # location 4
            [0, 10, 15, 20, 30,  0,  0],  # dummy depot 1
            [0, 10, 15, 20, 30,  0,  0],  # dummy depot 2
        ]

    

    # case 1: all pickups without reload
    # data['deliveries'] = [0,  0,  0,  0,  0,  0,  0]
    # data['loads']      = [0, +4, +6,  0,  0,  0,  0]
    
    # case 2: all pickups with reload
    data['deliveries'] = [0,  0,  0,  0,  0, -10,  0]
    data['loads']      = [0, +4, +6, +4, +6, -10, 10]
    
    # case 3: all deliveries without reload
    # data['deliveries'] = [0, -4, -6,  0,  0,  0,  0]
    # data['loads']      = [0, -4, -6,  0,  0,  0,  0]

    # case 4: all deliveries with reload
    # data['deliveries'] = [0, -4, -6, -4, -6, -10,   0]
    # data['loads']      = [0, -4, -6, -4, -6, -10, +10]
    
    # case 5: pickups and deliveries but nothing is linked without reload.
    # data['deliveries'] = [0, -2, -4,  0,  0, 0, 0]
    # data['loads']      = [0, -2, -4, +6, +4, 0, 0]

    # case 6: pickups and deliveries but nothing is linked with reload.
    # data['deliveries'] = [0, -2, -4,  0,  0, -10,   0]
    # data['loads']      = [0, -2, -4, +6, +4, -10, +10]

    
    data['vehicle_capacities'] = [10]
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    total_distance = 0
    total_load = 0
    deliveries_dimension = routing.GetDimensionOrDie('Deliveries')
    loads_dimension = routing.GetDimensionOrDie('Loads')
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        delivery_var = deliveries_dimension.CumulVar(index)
        load_var = loads_dimension.CumulVar(index)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        route_deliveries = solution.Value(delivery_var)
        route_load = solution.Value(load_var)
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            delivery_var = deliveries_dimension.CumulVar(index)
            load_var = loads_dimension.CumulVar(index)
            route_deliveries = solution.Value(delivery_var)
            route_load = solution.Value(load_var)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
            plan_output += ' {0} Deliveries({1}) Load({2}) ->'.format(node_index, route_deliveries,route_load)
        delivery_var = deliveries_dimension.CumulVar(index)
        load_var = loads_dimension.CumulVar(index)
        route_deliveries = solution.Value(delivery_var)
        route_load = solution.Value(load_var)
        plan_output += ' {0} Deliveries({1}) Load({2})\n'.format(
            manager.IndexToNode(index),
            route_deliveries,
            route_load)
        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
        plan_output += 'Deliveries of the route: {}\n'.format(route_deliveries)
        plan_output += 'Load of the route: {}\n'.format(route_load)
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print('Total distance of all routes: {}m'.format(total_distance))
    print('Total load of all routes: {}'.format(total_load))


def main():
    """Solve the CVRP problem."""
    # 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)

    # 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
        3000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    

    
    # Add Deliveries constraint.
    def delivery_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data['deliveries'][from_node]
    delivery_callback_index = routing.RegisterUnaryTransitCallback(delivery_callback)
    routing.AddDimensionWithVehicleCapacity(
        delivery_callback_index,
        # 0,  # null capacity slack
        data['vehicle_capacities'][0],
        data['vehicle_capacities'],  # vehicle maximum capacities
        False,  # start cumul to zero
        'Deliveries')

    # Add Load constraint.
    def load_callback(from_index):
        """Returns the load of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data['loads'][from_node]
    load_callback_index = routing.RegisterUnaryTransitCallback(load_callback)
    routing.AddDimensionWithVehicleCapacity(
        load_callback_index,
        # 0,  # null capacity slack
        data['vehicle_capacities'][0],
        data['vehicle_capacities'],  # vehicle maximum capacities
        False,  # start cumul to zero
        'Loads')

    # Add Constraint Both cumulVar are identical at start
    deliveries_dimension = routing.GetDimensionOrDie('Deliveries')
    loads_dimension = routing.GetDimensionOrDie('Loads')
    for vehicle_id in range(data['num_vehicles']):
      index = routing.Start(vehicle_id)
      routing.solver().Add(
          deliveries_dimension.CumulVar(index) == loads_dimension.CumulVar(index))


    # For dummy depot nodes
    routing.AddDisjunction([manager.NodeToIndex(5)], 0)
    routing.AddDisjunction([manager.NodeToIndex(6)], 0)


    
    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.log_search = False
    # search_parameters.first_solution_strategy = (
    #     routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC)
    
    # search_parameters.local_search_metaheuristic = (
    #         routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

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

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("No solution found!")


if __name__ == '__main__':
    main()