Pickup and Delivery without mixing clients

[angelo manzatto]

Pickup and Delivery without mixing clients

I am working on a constraint for pickup->delivery problem where a vehicle cannot mix demands from different clients. 

So taking the following example where I define pickup->delivery pairs on data['routes'] and client on data['clients'] containing a dictionary of nodes that belongs to certain clients.

data = {}

data['distance_matrix'] = [

        [ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,468, 776, 662       ],

        [ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210   ],

        [ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754  ],

        [ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358   ],

        [ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244   ],

        [ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,514, 1050, 708      ],

        [ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,514, 1278, 480     ],

        [ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856      ],

        [ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514     ],

        [ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468      ],

        [ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,730, 388, 1152, 354   ],

        [ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844    ],

        [ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730     ],

        [ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536     ],

        [ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194   ],

        [ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ],

        [ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0   ],

    ]

if use_random_matrix:

    data['distance_matrix'] = get_random_distance_matrix()

data['num_vehicles'] = 4

data['starts'] = [0,0,0,0]

data['ends'] = [0,0,0,0]

data['routes'] = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12], [13, 14], [15, 16]]

data['clients'] = {

    "A" : [1, 2, 3, 4], 

    "B" : [5, 6, 7, 8],

    "C" : [9, 10, 11, 12], 

    "D" : [13, 14, 15, 16]

    }

The goal is to formulate a constraint that I cannot mix demands on the same vehicle from different clients. 

So: 

Valid routes for a single vehicle: 

 - [1, 2, 5, 6] 

 - [1, 3, 2, 4, 9, 10, 13, 15, 14 , 16]

Invalid routes for a single vehicle: 

 - [1, 5, 6, 2] (mix client B goods while carrying goods for client A)

 - [13, 15, 14, 1, 3, 16, 2, 4] (mix client A goods while carrying goods for client D)

[Mizux Seiha]

You could:

1. Create one dimension per Client

2. at each pickup increase by 1 the corresponding client dimension

3. at each delivery decrease by 1 the corresponding client dimension

4. Add constraints so at each location for client X, all other client dim must be zero.

On my way to create a simple python sample...

[angelo manzatto]

Thanks a lot for the help @mizu. Unfortunately my implementation just freezes when I try to run after I add the constraint on step 4.

I added the following code:

On data:

data['is_start'] = [0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0] # pickup node

data['is_end'] = [0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1] # delivery node

data['clients'] = {

    "A" : [1, 2, 3, 4, 5, 6], 

    "B" : [7, 8, 9, 10, 11,12],

    "C": [13, 14, 15, 16]

    }

Step 2 and 3 - OK

##################################################################################################

# Client Dimension

##################################################################################################

for client in data['clients']:

    

    def add_client_callback_by_id(client):

        

        def client_callback_by_id(from_index):

        

            return client_callback(from_index, client)

        

        return routing.RegisterUnaryTransitCallback(client_callback_by_id)

    

    dimension_name = "Client" + client

    

    routing.AddDimensionWithVehicleCapacity(

        add_client_callback_by_id(client),

        0,  # null capacity slack

        [99999 for _ in range(data['num_vehicles'])],  # vehicle maximum capacities

        True,  # start cumul to zero

        dimension_name)

    

    client_dimension = routing.GetDimensionOrDie(dimension_name)

    

    dimensions[dimension_name] = client_dimension

# Create and register a transit callback.

def client_callback(from_index, client):

    

    from_node = manager.IndexToNode(from_index)

    

    # Convert from routing variable Index to demands NodeIndex.

    is_pickup = 0

    

    if from_node in data['clients'][client]:

        if data['is_start'][from_node] == 1:

            is_pickup = 1

        if data['is_end'][from_node] == 1:

            is_pickup = -1

    return is_pickup

Step 4 - NOT OK - Freezes the application

for c in data['clients']:

    

    other_dims = [dimensions["Client" + k] for k in data['clients'].keys() if k != c]

    

    for node in data['clients'][c]:

        

        index = manager.NodeToIndex(node)

        

        for other_dim in other_dims:

            routing.solver().Add(

                other_dim.CumulVar(index) == 0

                )

I don't know why this is happening. When I try to add a single node constraint as well it freezes. Ex:

routing.solver().Add(

    dimensions["ClientC"].CumulVar(manager.NodeToIndex(12))

    )

     

Can you give a hand ? Thanks in advance

[angelo manzatto]

"""

Created on Thursday Sep 09 13:45:42 2021

@author: Angelo Antonio Manzatto

"""

##################################################################################################

# Libraries

##################################################################################################

import random

from ortools.constraint_solver import routing_enums_pb2

from ortools.constraint_solver import pywrapcp

##################################################################################################

# Methods

##################################################################################################

def print_solution(data, manager, routing, solution, dimensions):    

    dropped_vehicles = []

    

    dash = 120 * "-"

    star = 120 * "*"

    

    print(star)

    print("VEHICLE ITINERARIES - START")

    print(star)

    

    """Prints solution on console."""

    

    for vehicle_id in range(data['num_vehicles']):

        

        # Check if vehicle is used

        if not routing.IsVehicleUsed(solution, vehicle_id):

            dropped_vehicles.append(vehicle_id)

            continue

        

        index = routing.Start(vehicle_id)

        

        print(dash)

        print("Route for vehicle: {}"

              .format(vehicle_id))

        

        print(dash)

        

        print('{:<4s}{:>15s}{:>15s}{:>15s}{:>15s}{:>15s}{:>15s}{:>15s}'

                  .format("Location",

                          "Distance",

                          "Cumul",

                          "Route",

                          "Client",

                          "ClientA",

                          "ClientB",

                          "ClientC"

                          ))

        

        print(dash)

        currt_distance = 0

        while not routing.IsEnd(index):

            

            cumul_distance = solution.Value(dimensions['distance'].CumulVar(index))

            currt_distance = cumul_distance - currt_distance

            

            cumul_clientA = solution.Value(dimensions['ClientA'].CumulVar(solution.Value(routing.NextVar(index))))

            cumul_clientB = solution.Value(dimensions['ClientB'].CumulVar(solution.Value(routing.NextVar(index))))

            cumul_clientC = solution.Value(dimensions['ClientC'].CumulVar(solution.Value(routing.NextVar(index))))

            

            node = manager.IndexToNode(index)

            

            route = []

            

            for r in data['routes']:

                if node in r:

                    route = r

                    break

                

            client = ""

            

            for c in data['clients']:

                

                if node in data['clients'][c]:

                    client = c

            

            details = "{:4d}".format(node)

            details += "{:>15.0f}".format(currt_distance)

            details += "{:>18.0f}".format(cumul_distance)

            details += "{:>15}".format(str(route))

            details += "{:>15}".format(client)

            details += "{:>15}".format(cumul_clientA)

            details += "{:>15}".format(cumul_clientB)

            details += "{:>15}".format(cumul_clientC)

            

            print(details)

            

            currt_distance = cumul_distance

        

            index = solution.Value(routing.NextVar(index))

            

        node = manager.IndexToNode(index)

        

        route = []

            

        for r in data['routes']:

            if node in r:

                route = r

                break

            

        client = ""

            

        for c in data['clients']:

            

            if node in data['clients'][c]:

                client = c

        

        cumul_distance = solution.Value(dimensions['distance'].CumulVar(index))

        currt_distance = cumul_distance - currt_distance

        

        cumul_clientA = solution.Value(dimensions['ClientA'].CumulVar(index))

        cumul_clientB = solution.Value(dimensions['ClientB'].CumulVar(index))

        cumul_clientC = solution.Value(dimensions['ClientC'].CumulVar(index))

        

        details = "{:4d}".format(node)

        details += "{:>15.0f}".format(currt_distance)

        details += "{:>18.0f}".format(cumul_distance)

        details += "{:>15}".format("")

        details += "{:>15}".format(client)

        details += "{:>15}".format("")

        details += "{:>15}".format("")

        details += "{:>15}".format("")

            

        print(details)

    print(dash)

    

##################################################################################################

# Data model

##################################################################################################

data = {}

data['distance_matrix'] = [

        [ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,468, 776, 662       ],

        [ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210   ],

        [ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754  ],

        [ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358   ],

        [ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244   ],

        [ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,514, 1050, 708      ],

        [ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,514, 1278, 480     ],

        [ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856      ],

        [ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514     ],

        [ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468      ],

        [ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,730, 388, 1152, 354   ],

        [ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844    ],

        [ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730     ],

        [ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536     ],

        [ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194   ],

        [ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ],

        [ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0   ],

    ]

data['num_vehicles'] = 4

data['starts'] = [0,0,0,0]

data['ends'] = [0,0,0,0]

data['routes'] = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12], [13, 14], [15, 16]]

data['is_start'] = [0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0]

data['is_end'] = [0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]

data['clients'] = {

    "A" : [1, 2, 3, 4, 5, 6], 

    "B" : [7, 8, 9, 10, 11,12],

    "C": [13, 14, 15, 16]

    }

##################################################################################################

# Optimizar routing model and manager

##################################################################################################

        

# Create the routing index manager.

manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),

                                       data['num_vehicles'], 

                                       data['starts'],

                                       data['ends'])

# Create Routing Model.

routing = pywrapcp.RoutingModel(manager)

##################################################################################################

# Optimizar dimensions

##################################################################################################

dimensions = {}

##################################################################################################

# Distance Dimension

##################################################################################################

def distance_callback(from_index, to_index):

    from_node = manager.IndexToNode(from_index)

    to_node = manager.IndexToNode(to_index)

    distance = data['distance_matrix'][from_node][to_node]

    return distance

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

    999999,  # vehicle maximum travel distance

    True,  # start cumul to zero

    dimension_name)

distance_dimension = routing.GetDimensionOrDie(dimension_name)

distance_dimension.SetGlobalSpanCostCoefficient(100)

   

dimensions['distance'] = distance_dimension 

##################################################################################################

# Constraint

##################################################################################################

# Same vehicle constraint

for route in data['routes']:

    for i in range(len(route) - 1):

        current_index = manager.NodeToIndex(route[i])

        next_index = manager.NodeToIndex(route[i+1])

        if len(route) == 2:

            routing.AddPickupAndDelivery(current_index, next_index)

        # same vehicle condition

        routing.solver().Add(

            routing.VehicleVar(current_index) == routing.VehicleVar(

                next_index)

            )

        

# Pickup before Delivery order

for route in data['routes']:

    

    for i in range(len(route) - 1):

        current_index = manager.NodeToIndex(route[i])

        next_index = manager.NodeToIndex(route[i+1])

        

        routing.solver().Add(

            distance_dimension.CumulVar(current_index) <=

            distance_dimension.CumulVar(next_index)

            )

        

# Client constraint - NOT WORKING!!!

# Coment the following code to make it work

for c in data['clients']:

    

    other_dims = [dimensions["Client" + k] for k in data['clients'].keys() if k != c]

    

    for node in data['clients'][c]:

        

        index = manager.NodeToIndex(node)

        

        for other_dim in other_dims:

            routing.solver().Add(

                other_dim.CumulVar(index) == 0

                )

##################################################################################################

# Optimizer parameters

##################################################################################################

# Setting first solution heuristic.

search_parameters = pywrapcp.DefaultRoutingSearchParameters()

search_parameters.first_solution_strategy = (

    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.

solution = routing.SolveWithParameters(search_parameters)

# Search time limit to find a solution

search_parameters.time_limit.seconds = 60

# Print solution on console.

if solution:

    print_solution(data, manager, routing, solution, dimensions)

else:

    print('No solution found !')

[Mizux Seiha]

```sh

%./plop.py

********************************************************************************

VEHICLE ITINERARIES - START

********************************************************************************

------------------------------------------------------------------------------------------------------------------------

Route for vehicle: 0

------------------------------------------------------------------------------------------------------------------------

Location       Distance          Cumul          Route         Client        ClientA        ClientB        ClientC

------------------------------------------------------------------------------------------------------------------------

   0              0                 0             []              _              0              0              0

   5            274               274         [5, 6]              A              1              0              0

   1            502               776         [1, 2]              A              2              0              0

   2            684              1460         [1, 2]              A              1              0              0

   6            274              1734         [5, 6]              A              0              0              0

   0            502              2236                             _              0              0              0

------------------------------------------------------------------------------------------------------------------------

Route for vehicle: 1

------------------------------------------------------------------------------------------------------------------------

Location       Distance          Cumul          Route         Client        ClientA        ClientB        ClientC

------------------------------------------------------------------------------------------------------------------------

   0              0                 0             []              _              0              0              0

  13            354               354       [13, 14]              C              0              0              1

  15            422               776       [15, 16]              C              0              0              2

  16            798              1574       [15, 16]              C              0              0              1

  14            194              1768       [13, 14]              C              0              0              0

   0            468              2236                             _              0              0              0

------------------------------------------------------------------------------------------------------------------------

Route for vehicle: 2

------------------------------------------------------------------------------------------------------------------------

Location       Distance          Cumul          Route         Client        ClientA        ClientB        ClientC

------------------------------------------------------------------------------------------------------------------------

   0              0                 0             []              _              0              0              0

   7            194               194         [7, 8]              B              0              1              0

   9            388               582        [9, 10]              B              0              2              0

  10            342               924        [9, 10]              B              0              1              0

   8            388              1312         [7, 8]              B              0              0              0

   0            308              1620                             _              0              0              0

------------------------------------------------------------------------------------------------------------------------

Route for vehicle: 3

------------------------------------------------------------------------------------------------------------------------

Location       Distance          Cumul          Route         Client        ClientA        ClientB        ClientC

------------------------------------------------------------------------------------------------------------------------

   0              0                 0             []              _              0              0              0

   3            696               696         [3, 4]              A              1              0              0

   4            114               810         [3, 4]              A              0              0              0

  11            400              1210       [11, 12]              B              0              1              0

  12            114              1324       [11, 12]              B              0              0              0

   0            388              1712                             _              0              0              0

------------------------------------------------------------------------------------------------------------------------

```
still investigating but it seems your loop which build client dimensions do not work as expected -> unroll it

[angelo manzatto]

Thanks a lot Mizu! Something important to mention here! 

The first time I downloaded your code I got "No solution found" when running it, but after I updated ortools from version 7.7 (something) to the latest one it worked. 

[angelo manzatto]

Now I am trying to figure why the "not unrolled loop" version still does not work since it is still freezing the program. Also why do you find a solution only when using the PARALLEL_CHEAPEST_INSERTION and not the PATH_CHEAPEST_ARC ?

[Mizux Seiha]

PARALLEL_CHEAPEST_INSERTION is the strategy to use when having some pickup and delivery constraints

PATH_CHEAPEST_ARC is good otherwise.

When not unrolled, I think 'client' is captured by reference inside the loop which create the lambda so all registered functions use the same value for client aka the last one 'C'.

see: https://docs.python.org/3/faq/programming.html#how-do-i-write-a-function-with-output-parameters-call-by-reference.

note: you can test it by adding `print(f'client: {client}')` in the transit callback if you don't see some 'A', 'B' and 'C' but only 'C' then you have this assignment issue.

[angelo manzatto]

This seems to work:

##################################################################################################

# Client Dimension

##################################################################################################

def add_client_callback_by_id(client):

    

    def client_callback_by_id(from_index):

        

        return client_callback(from_index, client)

    

    return routing.RegisterUnaryTransitCallback(client_callback_by_id)

def client_callback(from_index, client):

    """Returns the counter of the current node."""

    from_node = manager.IndexToNode(from_index)

    value = data[client][from_node]

    #print(f'Callback:A, node:{from_node}, val:{value}')

    return value

for client in data['clients']:

    

    client_callback_index = add_client_callback_by_id(client)

    dimension_name = "Client" + client

    

    routing.AddDimension(

        client_callback_index,

        0, # no slack

        1000, # capacity

        True, # start cumul to zero

        dimension_name)

    

    client_dimension = routing.GetDimensionOrDie(dimension_name)

    

    dimensions[dimension_name] = client_dimension 

# Client Constraint

for c in data['clients']:

    

    other_dims = [dimensions["Client" + k] for k in data['clients'].keys() if k != c]

    

    for node in data['clients'][c]:

        index = manager.NodeToIndex(node)

        

        for other_dim in other_dims:

            routing.solver().Add(other_dim.CumulVar(index) == 0)

Now:

Works Ok:

search_parameters.first_solution_strategy = (

    routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)

Freezes the program:

search_parameters.first_solution_strategy = (

    routing_enums_pb2.FirstSolutionStrategy. PATH_CHEAPEST_ARC)

I believe that despite not being optimized for solving the problem I don't see a reasonable explanation for the program to silent stop (freeze forever) while running with the above strategy.

Full example, now with the possibility to generate random pickup deliveries for clients for testing.