Adding transit hubs to pickup and delivery VRP

[Tue Boesen]

I am looking for a way to add transit hubs to my pickup and delivery VRP (with time windows, capacitated).

A transit hub is an intermediate place that goods can be placed on their way to the final destination such that other trucks can pick them up and do the final part of the delivery.

So far I have not found a good way of implementing such transit hubs.

Essentially it means that each pickup and delivery, which used to be a simple move p0 from location A to B (using the same truck to get to A and B), can now also be move p0 from A to C,D,E, and then later on move p0 from C,D,E to B (using a different truck). (I guess technically it could even involve multiple transit hubs before the package finally arrive, but lets just start with one if that makes it simpler.)

Does anyone know of a good way of implementing something like that in OR-tools? or have you seen it implemented anywhere else?

Cheers

Tue

[blind.lin...@gmail.com]

I have not done this myself, but seeing as how no one else has replied I thought I'd give my (possibly unhelpful) thoughts.

My first thought is that given how pdptw problems are formulated in OR Tools, you'd basically have to create dummy destination nodes for every item-transithub pair, and then dummy pickup nodes for evvery item-transithub pair. That could be a lot of nodes.

Then I'd collect the dummy transit hubs for each item and put them together in a disjunction with zero penalty for dropping.

Then I'd maybe play with expanding the pickup and delivery API calls to include the dummy node delivery and dummy node pickup for each item, reversing the sense of the pickup and delivery API call.

All together, my guess is that formulation would not end up with a solution that I want.

My guess is that the solutions generated would tend to avoid transit hubs as much as possible, as they generate longer routes.

My guess is that transit hubs exist not because they create more efficient delivery routes, but because they are easier for people to use to generate efficient routes, as well as to optimize staffing etc. A person can't solve a large scale NP Hard problem, but it isn't so bad to reason out an acceptable solution for making deliveries from a transit hub to a local area. Plus the drivers probably prefer sticking to known areas, because they learn the ins and outs of the area and get more efficient on their own.

So the trick is going to be figuring out exactly why the transit hubs are desirable, and coding those reasons into your formulation.

As an example, suppose the transit hubs are really break bulk depots, and you have large capacity trucks doing line haul, and then small delivery vans/cargo bicycles doing the last mile deliveries. Then the transit hub dummies only have to be one or two per item, picking the transit hub(s) closest to the destination. The final delivery nodes I'd restrict to being serviceable only by my local vehicle fleet.

Hope that gives you some ideas,

James

-- You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/b2ee9997-3ae9-4ba9-8eb6-3d1a2256ef93n%40googlegroups.com.

--

James E. Marca  
Activimetrics LLC  

[Tue Boesen]

Thank you for your reply James, for some reason I didn't see it before going on holiday.

I think disjointed sets of deliveries are the way to go as you suggest.

I don't agree that transit hubs will lead to longer travel times. For a simple example look at the image below, where I have 3 pickups/deliveries.

Pickup 1 (p1) needs to go to destination 1 (d1), and similar for p2/d2, p3/d3.

H is a transit hub where pickups can be stored.

The lines are the roads, meaning the routes the vehicles will have to follow. The number next to a segment of road is the time it takes to travel that section of road.

Imagine we have 2 vehicles, one starting at (p1,p2), and one at (p3).

Without the transit hub:

The total travel distance of vehicle 1 is 1+1+2+2+2=8, while vehicle 2 needs to travel 2+1+2=5.

Alternatively the order could be completed by vehicle 2 alone in 2+1+1+1+2+2+2=11

With a transit hub:

The total travel distance of vehicle 1 is: 1+1+2=4, since it can drop off p1 at the hub and only deliver p2. While vehicle 2 would travel 2+1+2=5 where it picks up package p1 from the hub on the way.

I will try and see whether I can make a small working example over the coming days.

Cheers

[Tue Boesen]

I have run into a problem trying to create this.

The problem is that when I add a transit hub to a route, I essentially split the route into two pickup and deliveries, where I need to ensure that the first delivery is completed before the second one can be picked up.

I first tried to do this using :

routing.AddPickupAndDelivery(delivery1_index,pickup2_index),

but this didn't work.

Instead I tried to do it using a cumulated time dimension:

routing.solver().Add(time_dimension.CumulVar(delivery1_index) <= time_dimension.CumulVar(pickup2_index))

This sucessfully enforced that the delivery of the first package was completed before pickup of the second, and it also still allowed the two packages to be handled by different vehicles. Unfortunately, it seems that it somehow prevents the earlier disjunction from being active, meaning that when I add this constraint it no longer has the option of either using the transit hub or delivering the package directly, instead it now has to use the transit hub, which is not what I want.

I tried to fix this by using the method suggested here: https://github.com/google/or-tools/issues/847 and using:

constraintActive = routing.ActiveVar(delivery1_index) * routing.ActiveVar(pickup2_index)
routing.solver().Add(constraintActive * time_dimension.CumulVar(delivery1_index) <= constraintActive * time_dimension.CumulVar(pickup2_index))

however this didn't seem to have any effect either.

So how can I enforce that one delivery is completed before another is picked up, without making those two deliveries obligatory (removing the disjunction).

Full code for reproduceability:

from functools import partial
from time import perf_counter

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

def vrp(data):
    matrix_len = len(data['demands'])
    n_v = data['num_vehicles']
    v_start = [len(data['demands'])-1]*n_v
    v_end = [len(data['demands'])-1]*n_v
    M = 10*np.ones((matrix_len,matrix_len),dtype=np.int64)
    M[:,-1] = 0
    # M[0,1] = 10
    # M[1,0] = 10
    M[-1,:] = 0
    M = M.tolist()

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

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

    routing.AddDisjunction([manager.NodeToIndex(0), manager.NodeToIndex(2)])
    routing.AddDisjunction([manager.NodeToIndex(0), manager.NodeToIndex(3)])
    routing.AddDisjunction([manager.NodeToIndex(1), manager.NodeToIndex(4)])
    routing.AddDisjunction([manager.NodeToIndex(1), manager.NodeToIndex(5)])

    pickup_index = manager.NodeToIndex(0)
    delivery_index = manager.NodeToIndex(1)
    routing.AddPickupAndDelivery(pickup_index, delivery_index)
    routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
    #
    pickup_index = manager.NodeToIndex(2)
    delivery_index = manager.NodeToIndex(3)
    routing.AddPickupAndDelivery(pickup_index, delivery_index)
    routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))

    pickup_index = manager.NodeToIndex(4)
    delivery_index = manager.NodeToIndex(5)
    routing.AddPickupAndDelivery(pickup_index, delivery_index)
    routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))

    # Add time dimension.
    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)

    dimension_name = "Time"
    routing.AddDimension(
        transit_callback_index,
        100,  # no slack
        3000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name,
    )
    time_dimension = routing.GetDimensionOrDie(dimension_name)


    pickup_index = manager.NodeToIndex(3)
    delivery_index = manager.NodeToIndex(4)
    constraintActive = routing.ActiveVar(pickup_index) * routing.ActiveVar(delivery_index)
    routing.solver().Add(constraintActive * time_dimension.CumulVar(pickup_index) <= constraintActive * time_dimension.CumulVar(delivery_index))
    # routing.solver().Add(routing.VehicleVar(pickup_index) != routing.VehicleVar(delivery_index)) # Used to check whether the 2 pickup and deliveries can be forced to use 2 different vehicles (which we want to make sure is possible)


    # Define the metric which we want to minimize
    def cost_callback(from_index, to_index):
        """The cost function which we want to minimize."""
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return M[from_node][to_node]

    cost_callback_index = routing.RegisterTransitCallback(cost_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(cost_callback_index)

    model_parameters = pywrapcp.DefaultRoutingModelParameters()

    # 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(1)
    search_parameters.solution_limit = 100

    # 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, assignment):
    """Prints assignment on console."""
    print(f"Objective: {assignment.ObjectiveValue()}")
    # Display dropped nodes.
    dropped_nodes = "Dropped nodes:"
    for node in range(routing.Size()):
        if routing.IsStart(node) or routing.IsEnd(node):
            continue
        if assignment.Value(routing.NextVar(node)) == node:
            dropped_nodes += f" {manager.IndexToNode(node)}"
    print(dropped_nodes)
    # Display routes
    total_distance = 0
    total_load = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        route_distance = 0
        route_load = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += data["demands"][node_index]
            plan_output += f" {node_index} Reward({route_load}) -> "
            previous_index = index
            index = assignment.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id
            )
        plan_output += f" {manager.IndexToNode(index)} Reward({route_load})\n"
        plan_output += f"Distance of the route: {route_distance}m\n"
        plan_output += f"Reward of the route: {route_load}\n"
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print(f"Total Distance of all routes: {total_distance}m")
    print(f"Total Reward of all routes: {total_load}")

if __name__ == "__main__":
    data = {}
    data['num_vehicles'] = 2
    data['demands'] = [1,2,3,4,5,6,0]

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

    print('done')