Different types of trailers for different types of goods

[tueboesen]

I have a routing problem where I have 3 different types of trailers, and each vehicles needs to start by driving to a trailer and then do pickup and deliveries.
However, the pickup and deliveries all require different types of trailers. For instance suppose I have 3 different pickup and deliveries, where the requirements are: {1,2}, {3}, {1,2,3}
meaning that the first pickup needs a type 1 or 2 trailer, while the second pickup can only be handled by a type 3 trailer, while the last package can be handled by any of the trailers.

Assuming that a vehicle cannot change its type of trailer, the above example would require 2 vehicles to complete all 3 deliveries, with one being of type 3, and the other being of type 1 or 2.

So far I do not have much of a plan on how to solve this problem:
I figure I can make a new dimension called trailer, and limit each vehicles capacity to 1, thereby preventing each vehicle from picking up more than 1 trailer.
But I am not sure how I can make the other pickups dependent on having the correct trailer already picked up.

Any suggestions would be appreciated.

[tueboesen]

I found a solution to the problem. Attached below is a small working example of how to do it.

from time import perf_counter

import numpy as np
from ortools.constraint_solver import pywrapcp, routing_enums_pb2



def convert_to_list(data):
    if isinstance(data, list):
        pass
    else:
        data = data.tolist()
    return data

def solve_vrp(data):
    # Create the routing index manager.
    matrix_len = len(data["time_matrix"])
    n_v = data["n_vehicles"]

    v_start = convert_to_list(data['vehicle_start'])
    v_end = convert_to_list(data['vehicle_end'])
    M = convert_to_list(data["time_matrix"])
    trailers = convert_to_list(data["trailers"])
    trailer_types = convert_to_list(data["trailer_types"])
    pickups_deliveries = convert_to_list(data["pickups_deliveries"])
    delivery_trailer_requirements = data['delivery_trailer_requirements']

    manager = pywrapcp.RoutingIndexManager(matrix_len, n_v, v_start, v_end)


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

    def time_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return M[from_node][to_node]
    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    def trailer_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return trailers[from_node]
    trailer_callback_index = routing.RegisterUnaryTransitCallback(trailer_callback)
    dimension_name = "trailer_capacity"
    routing.AddDimensionWithVehicleCapacity(
        trailer_callback_index,
        0,  # null capacity slack
        [1]*n_v,  # vehicle maximum capacities
        True,  # start cumul to zero
        dimension_name,
    )
    trailer_dimension = routing.GetDimensionOrDie(dimension_name)

    def trailer_type_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return trailer_types[from_node]
    trailer_type_callback_index = routing.RegisterUnaryTransitCallback(trailer_type_callback)
    dimension_name = "trailer_types"
    routing.AddDimensionWithVehicleCapacity(
        trailer_type_callback_index,
        0,  # null capacity slack
        [100]*n_v,  # vehicle maximum capacities
        True,  # start cumul to zero
        dimension_name,
    )
    trailer_type_dimension = routing.GetDimensionOrDie(dimension_name)

    # Trailer constraint.
    for i,request in enumerate(pickups_deliveries):
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        pickup_types = delivery_trailer_requirements[i]
        routing.solver().Add(trailer_dimension.CumulVar(pickup_index) > 0)
        cond = routing.solver().MemberCt(trailer_type_dimension.CumulVar(pickup_index), pickup_types)
        routing.solver().Add(cond)
        # routing.solver().Add(trailer_type_dimension.CumulVar(pickup_index) == pickup_types[0])
        # routing.solver().Add(trailer_type_dimension.CumulVar(delivery_index) == pickup_types[0])

    # Add disjunction to make all trailers optional
    penalty = 0
    for node in range(len(data['trailers'])):
        if data['trailers'][node] == 1:
            routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
            print(f"adding node {node} -> {manager.NodeToIndex(node)} as a trailer")


    # Add Time Windows constraint.
    dimension_name = "Time"
    routing.AddDimension(
        transit_callback_index,
        100000,  # allow waiting time
        100000,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        dimension_name,
    )
    time_dimension = routing.GetDimensionOrDie(dimension_name)


    # Define Transportation Requests.
    for request in pickups_deliveries:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
        routing.solver().Add(time_dimension.CumulVar(pickup_index) <= time_dimension.CumulVar(delivery_index))

    # Instantiate route start and end times to produce feasible times.
    for i in range(data["n_vehicles"]):
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))

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

    search_parameters.time_limit.FromSeconds(2) # You can set a time limit for how long it is allowed to search for a solution. If you set a time limit you are not guaranteed to find a solution (Finding the first solution might take a long time).
    # search_parameters.solution_limit = 100 # Or you can set a limit for how many solutions it should look for.

    # Solve the problem.
    t3 = perf_counter()
    print("Starting solver...")
    solution = routing.SolveWithParameters(search_parameters)
    t4 = perf_counter()

    if solution:
        print(f"Found solution in {t4 - t3:2.2f}s")
    else:
        print(f"Failed to find solution in {t4 - t3:2.2f}s")
    return manager, routing, solution

def print_solution(data, manager, routing, solution):
    """The standard solution printer from google or-tools."""
    print(f"Objective: {solution.ObjectiveValue()}")
    total_distance = 0
    total_volume_load = 0
    total_weight_load = 0
    for vehicle_id in range(data["n_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        route_distance = 0
        route_volume_load = 0
        route_weight_load = 0
        route_trailer_type = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_trailer_type += data["trailer_types"][node_index]
            plan_output += f" {node_index} -> "
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += f" {manager.IndexToNode(index)} \n"
        plan_output += f"Arc cost of the route: {route_distance}\n"
        plan_output += f"Trailer type for the route: {route_trailer_type}\n"
        print(plan_output)
        total_distance += route_distance
        total_volume_load += route_volume_load
        total_weight_load += route_weight_load
    print(f"Total arc cost of all routes: {total_distance}")



if __name__ == "__main__":
    data = {}
    data['n_vehicles'] = 2
    # Pickup1, delivery1, pickup2, delivery2, Trailer1, Trailer2, Trailer2, Vehicle_start1, Vehicle_start2, Vehicle_end
    M = np.ones((10,10), dtype=np.int64)
    M[4,7] = 10
    M[7,4] = 10
    M[4,8] = 9
    M[8,4] = 9
    M[:,-1] = 0
    M[-1,:] = 0
    M = M.tolist()
    data['time_matrix'] = M
    data['vehicle_start'] = [7,8]
    data['vehicle_end'] = [9,9]
    data['n_deliveries'] = 2
    data['pickups_deliveries'] = [[0, 1],[2,3]]
    data['trailers'] = [0, 0, 0, 0, 1, 1, 1, 0, 0, 0]
    data['trailer_types'] = [0, 0, 0, 0, 1, 2, 2, 0, 0, 0]
    data['delivery_trailer_requirements'] = [[2,3],[1,3,4,5,6,7,8,9]]

    manager, routing, solution = solve_vrp(data)
    print_solution(data, manager, routing, solution)