Or-tools: How to Solve VRP with route Dependency and Constraints using this package?

[lihuiknight]

Dear authors,

I am wondering whether this package is suitable for solving this dummy problem as following:

There are four nodes (0~3) and three vehicles, which are located at node 0, 1, 2. The matrix distance is defined as follows:

_distances = [ # complete graph
         [0, 100, 200, 50], # 0
         [100, 0, 50, 200], # 1
         [200, 50, 0, 100], # 2
         [50, 200, 100, 0]  # 3
         ]

Constraints

1. Each vehicle should return back to its start location after scheduling, that is:
   python _start_locations = [0, 1, 2] _end_locations = [0, 1, 2]
2. We should deliver three different kinds of good from: 0->1, 1->2, and 2->3 respectively.
3. Suppose we don't consider other constraints, such as the capacity of each vehicle.

Clearly, the optimal solution should be 0->1->2->3->0.
That is, only the vehicle 0 works in this scheduling.

Could I use OR-Tool to solve this problem? How?

[Mizux]

Sure you can use or-tools !
For a Simple TSP with a distance matrix take a look at https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/tsp.md

For constraint 1 to define starts/ends for each vehicle take a look at:
https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/vrp.md#multiple-starts-ends

For constraint 2 they are Pickup & Delivery constraints:
-> https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/pdp.md

For constraint 3 take a look at capacity example in https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/vrp.md#capacity-constraints

note: this is based on master branch API which is the v7.0-beta

[lihuiknight]

wow, it seems that this toolbox is so powerful.
I cannot wait to have a try. Thanks a lot.

[Mizux]

note in your example an optimal solution could be:
vehicle0: 0 -> 1 -> 0
vehicle1: 1 -> 2 -> 1
vehicle2: 2 -> 3 -> 2

I respect your constraint 1 and 2 (in bold)

[lihuiknight]

@Mizux your solution above is not the optimal, because the total cost of your solution is 500.
More specifically:
vehicle0: 0 -> 1 -> 0, cost = 200
vehicle1: 1 -> 2 -> 1, cost = 100
vehicle2: 2 -> 3 -> 2, cost = 200
total cost = 500

While the actual optimal solution should be one of the solutions below:
vehicle0: 0->1->2->3->0, total cost = 300
or vehicle1: 1->2->3->0->1, total cost = 300
or vehicle2: 2->3->0->1->2, total cost = 300

Specifically, for the first solution, vehicle0 will deliver all of the goods, where we don't need vehicle1 and vehicle2, because in our problem all of those vehicles should return back their start points.

For the implementation, I am not sure the distance matrix can be defined as above, because some the locations of vehicles are same with the locations of delivery targets. Maybe I should define three dummy locations, which are same with the locations of delivery targets while having different node ids.

[lihuiknight]

I try to install v7.0-beta based on the source code according to the instruction https://developers.google.com/optimization/install/python/source_linux,
however I meet this error:
./ortools/algorithms/knapsack_solver.h:65:32: fatal error: absl/memory/memory.h: No such file or directory

BTW, my system is Ubuntu 16.04 LTS.

Finally, despite I haven't fixed this error, I install v7.0 by
pip3.6 install ortools==7.0b6150

[lihuiknight]

@Mizux two more questions about vehicle routing problem:

(1) In this scenario, some vehicles cannot select particular edges. That is, we need to specify the forbidden edges for each vehicle. How to handle this constraints?

(2) In the scenario with Pickup & Delivery constraints, suppose the cumulative weight of one vehicle is 200 and its capacity is 500. If each vehicle pickup goods (with weight=100) at one location, then we should add this weight into its cumulative weight, that is, 200+100.
After it finishes this delivery at another location, the cumulative weight should return to 200. And then it continue traverses this logistics graph. If I want to minimize total cost under the capacity constraint, how to design the algorithm based on starts/ends examples?

[Mizux]

1) I see two solutions:
First, you'll need to register a different callback for each type of vehicle.
Then:

• in your distance matrix if you use kint64max (ed sys.maxsize in python) for forbidden edge it should make it since solver can't have an objective value higher than kint64max i.e. solver can't select this edge.
  https://github.com/google/or-tools/blob/14875ce07325344ab989deb3662aabd7be7288ec/ortools/base/integral_types.h#L61-L62
  note: you can also use this to make a disjunction mandatory if you set the penalty to kint64max (i.e. solver has to fulfil the disjunction constraint since it can't pay the penalty)
• or you can remove the edge (A, B): i.e. from the node A remove the available nextVar B.
  e.g. examples/java/RandomTsp.java which remove some edges randomly
  https://github.com/google/or-tools/blob/14875ce07325344ab989deb3662aabd7be7288ec/examples/java/RandomTsp.java#L74-L85

2) Simply add Capacity contraints see https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/vrp.md#capacity-constraints

[lihuiknight]

1. I can understand your solutions for the first question. However, I think your solution only works when there is only one vehicle. In my scenario, there are multiple vehicles. Do you mean I should define a unique distance_matrix for each vehicle?

2. The provided solution with capacity constraints is not suitable for the second question. In the example, the capacity is always cumulative and cannot decrease by the weight of delivered goods. Right?

Very appreciate of your help.

[Mizux]

1. yes and no:
2. the solution 1 using kint64max if you provide an "unique" distance_matrix i.e. register a callback for each vehicle then you can "remove" an edge only for this vehicle.
   note: you can also use the same callback index for a group of vehicle sharing the same constraint

3. the solution 2 using routing.nextVar(from).removeValue(to); remove the edge for all vehicle route.

4. At delivery site you can add negative weight i.e. unload
   you can see usage here https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/cvrp_reload.py

[lihuiknight]

That's cool.

For the first question, I define the distance_matrix for each vehicle, as define the distance_callback as following, however it yields some errors:

transit_callback_index_arr = []

for vehicle_id in range(data['num_vehicles']):
    distance_matrix = copy.deepcopy(data['distance_matrix'][vehicle_id])
    print('vehicle_id=%d' % vehicle_id)
    print(distance_matrix)
    def distance_callback_vehicle(from_index, to_index):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback_vehicle)
    transit_callback_index_arr.append(transit_callback_index)

for vehicle_id in range(data['num_vehicles']):
    routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_arr[vehicle_id], vehicle_id)

    # Add Distance constraint.
    dimension_name = 'Distance_%d' % vehicle_id
    routing.AddDimension(
        transit_callback_index_arr[vehicle_id],
        0,  # no slack
        300000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Define Transportation Requests.
    for request in data['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(distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index))

Error:

File "/usr/local/lib/python3.6/dist-packages/ortools/constraint_solver/pywrapcp.py", line 3332, in SetArcCostEvaluatorOfVehicle
    return _pywrapcp.RoutingModel_SetArcCostEvaluatorOfVehicle(self, evaluator_index, vehicle)
TypeError: in method 'RoutingModel_SetArcCostEvaluatorOfVehicle', argument 2 of type 'int'

[Mizux]

Just testing on master using this diff (with a python3.5)

diff --git a/ortools/constraint_solver/samples/vrp.py b/ortools/constraint_solver/samples/vrp.py
index deb98718d..9d93952d0 100755
--- a/ortools/constraint_solver/samples/vrp.py
+++ b/ortools/constraint_solver/samples/vrp.py
@@ -151,7 +151,8 @@ def main():
         return data['distance_matrix'][from_node][to_node]

     transit_callback_index = routing.RegisterTransitCallback(distance_callback)
-    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
+    for i in range(data['num_vehicles']):
+        routing.SetArcCostEvaluatorOfVehicle(transit_callback_index, i)
     # [END arc_cost]

     # Setting first solution heuristic.

no problem spotted...

[Mizux]

bug found !

routing.SetArcCostEvaluatorOfVehicle(distance_callback_vehicle, vehicle_id)

must be

routing.SetArcCostEvaluatorOfVehicle(transit_callback_index, vehicle_id)

you must use the callback index not the callback itself (if you are using master / v7 API)
note: you can close the issue, if everything is ok for you, and don't hesitate to open a new issue for each new problem so if other users get the same issue, it's easier to find the fix/follow...

[lihuiknight]

while, i wonder how routing.SetArcCostEvaluatorOfVehicle(transit_callback_index, vehicle_id) find the corresponding distance_matrix for vehicle_id? How to define distance_matrix and distance_callback_vehicle for this case?

In my code, I define distance_matrix like
data['distance_matrix'][vehicle_id] = 2d array

Then I should specify each vehicle a corresponding distance_callback_vehicle, such as the following code.

transit_callback_index_arr = []

for vehicle_id in range(data['num_vehicles']):
    distance_matrix = copy.deepcopy(data['distance_matrix'][vehicle_id])
    print('vehicle_id=%d' % vehicle_id)
    print(distance_matrix)
    def distance_callback_vehicle(from_index, to_index):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback_vehicle)
    transit_callback_index_arr.append(transit_callback_index)

for vehicle_id in range(data['num_vehicles']):
    routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_arr[vehicle_id], vehicle_id)

    # Add Distance constraint.
    dimension_name = 'Distance_%d' % vehicle_id
    routing.AddDimension(
        transit_callback_index_arr[vehicle_id],
        0,  # no slack
        300000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Define Transportation Requests.
    for request in data['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(distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index))

It yields the following error:

WARNING: Logging before InitGoogleLogging() is written to STDERR
F0201 10:48:05.400179 16427 routing.cc:1288] Check failed: pickup < size (1969 vs. 3) 
*** Check failure stack trace: ***

[lperron]

The distance matrix is linked to the registered transit callback.
Define one per vehicle if needed.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 1 févr. 2019 à 03:03, Ken Li [e-mail] a écrit :

while, i wonder how
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index, vehicle_id)
find the corresponding distance_matrix for vehicle_id? How to define
distance_matrix for this case?

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1032#issuecomment-459578258,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKj17cRXYRanEpPeguCT_nOAOj0YVZN3ks5vI6BXgaJpZM4aXvvN
.

[lihuiknight]

Can you provide any example?

[Mizux]

You must use create just one distance Dimension but with a distance_callback_index (i.e. distance callback i.e. distance_matrix) for each vehicles, thus using:
https://github.com/google/or-tools/blob/86ab8bbd8ff720d51e4b4204cac24d986f0e16d8/ortools/constraint_solver/routing.h#L405-L407

Something like this (not tested):

for vehicle_id in range(data['num_vehicles']):
    routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_arr[vehicle_id], vehicle_id)

# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimensionWithVehicleTransits(
transit_callback_index_arr, # list of transit callback, one per vehicle
0,  # no slack
300000,  # vehicle maximum travel distance
True,  # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

# Define Transportation Requests.
for request in data['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(distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index))

note Dimension is outside the loop and for capacity constraint just create another capacity dimension...

[lihuiknight]

Finally, I have solve my problem with several constraints includes: capacity constraint, duplicate location, forbidden edge constraint, and pickup-delivery dependency.

Thanks a lot. @Mizux

[ptrdtznr]

Finally, I have solve my problem with several constraints includes: capacity constraint, duplicate location, forbidden edge constraint, and pickup-delivery dependency.

Thanks a lot. @Mizux

hey, how did you solved 'forbidden edge constraint' ? Can you give me a hint?! :)

Regards

[Mizux]

@ptrdtznr see point 1: https://github.com/google/or-tools/issues/1032#issuecomment-459257132

[lihuiknight]

@ptrdtznr set _distances[from_node][to_node] = INFINITY, where INFINITY is a very large number.

[veer5551]

Hey Hi @lihuiknight,
Looking at your example, it has different distance matrices for different vehicles, right?
https://github.com/google/or-tools/issues/1032#issuecomment-459578258
Could you help me understand your model and help me model a similar one where I Have different speeds and dimensions for vehicle fleet?

I am trying out the CVRPTW-reload example, where the distance callbacks are evaluated using locations of the nodes. So I think in my case, it would be time evaluators which would change for each vehicle type, just a preliminary thought.
I am a newbie to or tools, a lot to understand ahead though! :)

Your help is greatly valued!

Thanks a lot in advance!

[lihuiknight]

hi @veer5551

In my scenario, the vehicles share the same speed. I am not sure the or-tools can handle your problem. I think you'd better asking the authors of or-tools.

[veer5551]

Hi @lihuiknight,

Like you mentioned your vehicles share the same speed, then is there some reason for having different distance matrices for each vehicle?
I would like to know it, as I have thought of converting the distance matrix to a time matrix specific to each vehicle and use it as a constraint of variable speed.

@Mizux as @lihuiknight suggested,
Can the or tools handle the variable speed feature?
Else what do you think of the above thought of time Matrix?

Thanks a lot for your valuable suggestions in advance!!
It's really a powerful tool!!

Any help is really appreciated!

[Mizux]

@veer5551 Technically OR-Tools don't see the variable speed AT ALL, again as i said you just need to pass an array of transit evaluator when creating your time dimension (and your transit callback may use this variable)...

I'll try to make an example, this afternoon (here Paris Time)

[veer5551]

@Mizux Sir,
Thank you for the amazingly fast reply.
Really appreciate your efforts in helping!!

And thank you for trying making an example. As I am modelling around the CVRPTW-reload example, it would be really great if you model the example around the same model.

Attaching the code I am currently working on.
text3.txt

Thanks a lot once again!!

[Mizux]

@veer5551 see https://github.com/google/or-tools/issues/1891#issuecomment-589050585

[veer5551]

Thank you @Mizux sir for the incredibly great efforts for helping and modelling the example.
I would try and play around the model you suggested.

And sorry for the messy code, currently trying to get to a solution as fast as possible for the problem by adding all the constraints.
Would surely clean up the code immediately.

I can't thank you enough though!
Your help is really appreciated!!

[juanorion1]

Hi @Mizux, could you help me with something that I'm trying to do with the VRP with capacity and pickup and delivery constrain?
There are two depots, and a number of people (always variable) are going to go to this depots. I put the two depots in the first and second entry of the distance matrix.
When I'm creating the model I have something like this
```
def create_data_model():
data = {}
data['distance_matrix'] = md_time.values.tolist()
data['demands'] = nodo_personas_paradero[1]

    data['pickups_deliveries'] = [ [df.index[i],df["Sede"].values[i]] for i in range(2,df.shape[0])]

    data['num_vehicles'] = num_vehi
    data['vehicle_capacities'] = [capa_vehi]*data['num_vehicles']

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


    return data

Where data['pickups_deliveries'] and data['demands'] are something like this:

data['pickups_deliveries'] = [
    [2, 0],
    [3, 1],
    [4, 0],
    [5, 1],
    [6, 0],
    [7, 1],
    [8, 1],
    [9, 1]...]

data["demands"] = [0, 1, 1, 1,...]

Here is the rest of the code:

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 Capacity constraint.
    def demand_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['demands'][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(
        demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data['vehicle_capacities'],  # vehicle maximum capacities
        True,  # start cumul to zero
        'Capacity')


    # Add Distance constraint.
    dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        vmtd,  # vehicle maximum travel distance vmtd
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Define Transportation Requests.
    for request in data['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(
            distance_dimension.CumulVar(pickup_index) <=
            distance_dimension.CumulVar(delivery_index))

    # Allow to drop nodes.
    penalty = 100000000
    for node in range(1, len(data['distance_matrix'])):
        routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

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

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

    # Print solution on console.
    if assignment:
        dict_route = print_solution(data, manager, routing, assignment, nodo_personas, nodo_personas_paradero)

    return data, manager, routing, assignment, dict_route


return main()

```

When I run the code, there's no solution and I do not know where is the problem.

Any help is really appreciated!
Thanks.