CVRP Reload (multi trip) with CVRP collect and deliver

[mohit-at-delhivery]

I want a vehicle to do pickups and deliveries, where for deliveries all the items to be delivered by a vehicle are to be picked up from the depot and should be delivered at the given locations. For pickup the items are just collected from the given locations and stored in the vehicle and brought back to the depot. This is solved here by @Mizux in vrp collect and deliver: link.

Now I want a vehicle to take multiple trips if the demand is not fullfilled in one trip because of the capacity constraint of the vehicle. Now here is cvrp reload link, but here we are just having positive demands and we have just created dummy reload nodes at depot, but in our case our demands are both positive and negative as well.

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. If there is some other better way of doing so please let me know. 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()

[mohit-at-delhivery]

Hi guys, kindly let us know if you find any implementation of multi trip with some unlinked pickup and delivery nodes (that is the vehicle takes the load from the depot to fulfil dropoff order and picks up the pickup order and bring them to the depot). If we can avoid using non-zero slack that would be better as well. Thank you.

[mohit-at-delhivery]

@Mizux @jmarca is there any official way of handling multi trip in ortools where our orders can be:

1. delivery nodes -> deliver from depot to the order location
2. pickup nodes -> just pickup the load from the order location and bring back to the depot
3. pickup and delivery nodes -> pickup orders from one location and deliver to the other location in between the route's start depot and end depot.

We have a solution for all these cases here (link) but its just not a multi trip solution. kindly let us know what will be the right way of doing so? Thank you

[rohan1790]

Facing similar problem, how can we address this?

[Mizux]

Basically you want to have the "delivery" dimension to be equal to the "total load" dimension when leaving any refill station.
Unfortunately dimension.CumulVar(idx) is evaluated upon arrival at the node not at departure once the refill has been performed
-> One solution is to use two nodes as refill station (aka, refill_in and refill_out) so you can model this constraint on the refill_out node...

TIPS: you can make refill_in and refill_out part of the same pickup&delivery pair so solver will have insight to manage both nodes at a time and avoid to generate candidate solution with nodes placed in different routes etc...

[mohit-at-delhivery]

@Mizux thank you for the response. The issue is that for case 2 (requires reload) to work in the above example, we need "Deliveries" and "Loads" dimensions to have slack equivalent to the vehicle's capacity, but for case 3 (normal delivery using collect and delivery example), we need 0 slack the both the dimensions. Can we do normal collect and deliver(link) without 0 slack?

[Mizux]

don't get it, I suggest to:

• Set SlackVar to maximum vehicle capacity in addDimension() otherwise it is replaced by a constVar(0) and any subsequent call to SetRange() will be ignored also you can only reduce the range with set Range not increase it otherwise the solver will turn a fail flag to True which should instant kill the solve as infeasible...
• Set SlackVar to 0 for all nodes except refill station nodes (ed maybe only refill_in node imho)
• Add bunch of constraint on refill_out so CumulVar of both dimension (load and delivery) are the same.

Thus regular nodes will still have 0 slackVar as usual BUT refill_in will be allow to use it to simulate refill of delivery package.

[mohit-at-delhivery]

Hi @Mizux,

Thank you so much for sharing your suggestions and insights regarding the refill nodes and slack variables. It really helped a lot. Found out that we need to set non zero slack for refill out node as well else it is not able to function properly in case of pickup and dropoff orders within the same payload. Thank you