Vehicle Routing Problem Issue

[Prashant Dave]

Greetings,

I am new to this group and to the world of AI & ML. I have recently started using the Python and found it too interesting. I have been working on ORTOOLS for couple of days and tried to use it in my use case.

I have got a sample dataset online having LoanNos, Sourcing Branch ID, Branch Geo Coordinates and Customer Geo Coordinates. I want my sales person to visit all these customers places. To achieve this, I tried using VRP as provided in Google ORTOOLS using Python.

The code works well if I copy paste the existing code and execute it. However if I try to simply change the Data Matrix based on the sample data Location details, the  code gives me output for only last person. FYR, I have pasted the python code. I am not sure where I am going wrong...

May I get your assistance pls on the same... !

[Mizux Seiha]

Solver try to minimize distance so it is more efficient to perform all visit with one vehicle...

Simple example with tree location Depot, A, B with 2 vehicles, usually you have `dst(A -> Depot) + dst(Depot, B) > dst(A, B)` so solver have incentive to use a single route "Depot -> A -> B > Depot" than two routes "Depot -> A -> Depot + Depot -> B -> Depot"

Two solutions to mitigate this issue (at the cost of having the total distance increase):

1. Use of `RoutingDimension::SetGlobalSpanCoefficient()` to minimize the max length route, so it will tend to distribute visits among vehicles/persons

see: 

https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/doc/VRP.md#vehicle-routing-problem

code to add:

```python

    distance_dimension = routing.GetDimensionOrDie(dimension_name)

    distance_dimension.SetGlobalSpanCostCoefficient(100)

```

ref: https://github.com/google/or-tools/blob/b77bd3ac69b7f3bb02f55b7bab6cbb4bab3917f2/ortools/constraint_solver/samples/vrp_global_span.py#L170-L171

2. You can try to use `SetCumulVarSoftLowerBound()` and `SetCumulVarSoftUpperBound()`

Something like this:

```python

# Distribution

routing.AddConstantDimension(

   1,

  manager.GetNumberOfNodes(),

True, # start cumul to zero

"Counter")

counter_dimension = routing.GetDimensionOrDie("Counter")

penalty = 10_000 # must be adapted to your problem

nb_visit = (manager.GetNumberOfNodes()) // manager.GetNumberOfVehicles()

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

    index = routing.End(vehicle_id)

    counter_dimension.SetCumulVarSoftLowerBound(index, nb_visit, 10_000)

    counter_dimension.SetCumulVarSoftUpperBound(index, nb_visit + 1, 10_000)

````

Uppon arrival at each end node, vehicle should have visited nb_visit to avoid any penalty...

ref:

* https://github.com/google/or-tools/blob/b77bd3ac69b7f3bb02f55b7bab6cbb4bab3917f2/ortools/constraint_solver/routing.h#L2494-L2503

* https://github.com/google/or-tools/blob/b77bd3ac69b7f3bb02f55b7bab6cbb4bab3917f2/ortools/constraint_solver/routing.h#L2516-L2526

[Prashant Dave]

Many Thanks for your assistance. I have tried using the code however I am still facing the same problem. Let me ask you one more favour if you can help... ! Below is the data matrix I want to pass and the same is also saved in the list variable. Can you help me using this matrix and show me the o/p by passing below matrix

c = [[0, 768, 630, 454, 674, 642, 363, 1228, 680, 376, 394, 554, 412, 96, 580, 524],

[768, 0, 138, 314, 94, 126, 405, 460, 88, 392, 374, 214, 356, 672, 188, 244],
[630, 138, 0, 176, 44, 12, 267, 598, 50, 254, 236, 76, 218, 534, 50, 106],
[454, 314, 176, 0, 220, 188, 91, 774, 226, 78, 60, 100, 42, 358, 126, 70],
[674, 94, 44, 220, 0, 32, 311, 554, 6, 298, 280, 120, 262, 578, 94, 150],
[642, 126, 12, 188, 32, 0, 279, 586, 38, 266, 248, 88, 230, 546, 62, 118],
[363, 405, 267, 91, 311, 279, 0, 865, 317, 13, 31, 191, 49, 267, 217, 161],
[1228, 460, 598, 774, 554, 586, 865, 0, 548, 852, 834, 674, 816, 1132, 648, 704],
[680, 88, 50, 226, 6, 38, 317, 548, 0, 304, 286, 126, 268, 584, 100, 156],
[376, 392, 254, 78, 298, 266, 13, 852, 304, 0, 18, 178, 36, 280, 204, 148],
[394, 374, 236, 60, 280, 248, 31, 834, 286, 18, 0, 160, 18, 298, 186, 130],
[554, 214, 76, 100, 120, 88, 191, 674, 126, 178, 160, 0, 142, 458, 26, 30],
[412, 356, 218, 42, 262, 230, 49, 816, 268, 36, 18, 142, 0, 316, 168, 112],
[96, 672, 534, 358, 578, 546, 267, 1132, 584, 280, 298, 458, 316, 0, 484, 428],
[580, 188, 50, 126, 94, 62, 217, 648, 100, 204, 186, 26, 168, 484, 0, 56],
[524, 244, 106, 70, 150, 118, 161, 704, 156, 148, 130, 30, 112, 428, 56, 0]]

Thanks.

BRgds, PD

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/jJBR2_yBeyk/unsubscribe.
To unsubscribe from this group and all its topics, 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/beb7d650-e7c0-4f13-8b38-1d8feb29dd4cn%40googlegroups.com.

--

Thanks.

Best Regards,

Prashant Dave

[Mizux Seiha]

seems using the GlobalSpanCoefficient the solver didn't manage to escape it when running the local search:

I got:

```

objective: 248056

Route for vehicle 0:

 0 -> 0

Distance of the route: 0km

Number of visit: 0

Route for vehicle 1:

 0 ->  13 ->  6 ->  9 ->  10 ->  12 ->  3 ->  15 ->  11 ->  14 ->  2 ->  5 ->  4 ->  8 ->  1 ->  7 -> 0

Distance of the route: 2456km

Number of visit: 15

Maximum of the route distances: 2456km

```

BUT using SoftBound it seems to works

full code (side note I'm using master and the RegisterTransitMatrix() "new" API):

```py

#!/usr/bin/env python3

"""Vehicles Routing Problem (VRP)."""

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

def create_data_model():

    """Stores the data for the problem."""

    data = {}

    data['distance_matrix'] = [

        [0, 768, 630, 454, 674, 642, 363, 1228, 680, 376, 394, 554, 412, 96, 580, 524],

        [768, 0, 138, 314, 94, 126, 405, 460, 88, 392, 374, 214, 356, 672, 188, 244],

        [630, 138, 0, 176, 44, 12, 267, 598, 50, 254, 236, 76, 218, 534, 50, 106],

        [454, 314, 176, 0, 220, 188, 91, 774, 226, 78, 60, 100, 42, 358, 126, 70],

        [674, 94, 44, 220, 0, 32, 311, 554, 6, 298, 280, 120, 262, 578, 94, 150],

        [642, 126, 12, 188, 32, 0, 279, 586, 38, 266, 248, 88, 230, 546, 62, 118],

        [363, 405, 267, 91, 311, 279, 0, 865, 317, 13, 31, 191, 49, 267, 217, 161],

        [1228, 460, 598, 774, 554, 586, 865, 0, 548, 852, 834, 674, 816, 1132, 648, 704],

        [680, 88, 50, 226, 6, 38, 317, 548, 0, 304, 286, 126, 268, 584, 100, 156],

        [376, 392, 254, 78, 298, 266, 13, 852, 304, 0, 18, 178, 36, 280, 204, 148],

        [394, 374, 236, 60, 280, 248, 31, 834, 286, 18, 0, 160, 18, 298, 186, 130],

        [554, 214, 76, 100, 120, 88, 191, 674, 126, 178, 160, 0, 142, 458, 26, 30],

        [412, 356, 218, 42, 262, 230, 49, 816, 268, 36, 18, 142, 0, 316, 168, 112],

        [96, 672, 534, 358, 578, 546, 267, 1132, 584, 280, 298, 458, 316, 0, 484, 428],

        [580, 188, 50, 126, 94, 62, 217, 648, 100, 204, 186, 26, 168, 484, 0, 56],

        [524, 244, 106, 70, 150, 118, 161, 704, 156, 148, 130, 30, 112, 428, 56, 0],

        ]

    data['num_vehicles'] = 2

    data['depot'] = 0

    return data

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

    """Prints solution on console."""

    print(f'objective: {solution.ObjectiveValue()}')

    max_route_distance = 0

    counter_dimension = routing.GetDimensionOrDie("Counter")

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

        index = routing.Start(vehicle_id)

        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)

        route_distance = 0

        while not routing.IsEnd(index):

            plan_output += ' {} -> '.format(manager.IndexToNode(index))

            previous_index = index

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

            route_distance += routing.GetArcCostForVehicle(

                previous_index, index, vehicle_id)

        plan_output += '{}\n'.format(manager.IndexToNode(index))

        plan_output += 'Distance of the route: {}km\n'.format(route_distance)

        counter_var = counter_dimension.CumulVar(index)

        plan_output += f'Number of visit: {solution.Value(counter_var) - 1}\n'

        print(plan_output)

        max_route_distance = max(route_distance, max_route_distance)

    print('Maximum of the route distances: {}km'.format(max_route_distance))

def main():

    """Solve the CVRP problem."""

    # Instantiate the data problem.

    data = create_data_model()

    manager = pywrapcp.RoutingIndexManager(

            len(data['distance_matrix']),

            data['num_vehicles'],

            data['depot'])

    routing = pywrapcp.RoutingModel(manager)

#    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)

#        dst = data['distance_matrix'][from_node][to_node]

#        #print(f'dst({from_node},{to_node}): {dst}')

#        return dst

    transit_callback_index = routing.RegisterTransitMatrix(data['distance_matrix'])

    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Distance constraint.

    dimension_name = 'Distance'

    routing.AddDimension(

        transit_callback_index,

        0,  # no slack

        3500,  # vehicle maximum travel distance

        True,  # start cumul to zero

        dimension_name)

    #distance_dimension = routing.GetDimensionOrDie(dimension_name)

    #distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Distribution

    routing.AddConstantDimension(

            1,

            manager.GetNumberOfNodes(),

            True, # start cumul to zero

            "Counter")

    counter_dimension = routing.GetDimensionOrDie("Counter")

    penalty = 10_000 # must be adapted to your problem

    nb_visit = (manager.GetNumberOfNodes()) // manager.GetNumberOfVehicles()

    print(f'visit_mean: {nb_visit}')

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

      index = routing.End(vehicle_id)

      counter_dimension.SetCumulVarSoftLowerBound(index, nb_visit, 1_000)

      counter_dimension.SetCumulVarSoftUpperBound(index, nb_visit + 1, 1_000)

    # Setting first solution heuristic.

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    search_parameters.first_solution_strategy = (

            routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

            #routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_ARC)

            #routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC)

    search_parameters.local_search_metaheuristic = (

            routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

    search_parameters.log_search = True

    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()

```

potential output:

```sh

./plop.py

...

I0117 20:58:52.010986 22591 search.cc:260] Solution #20153 (3740, objective minimum = 3504, objective maximum = 9456, time = 9999 ms, branches = 99723, failures = 54620, depth = 33, Exchange, neighbors = 6316541, filtered neighbors = 20153, accepted neighbors = 20153, memory used = 14.12 MB, limit = 99%)

I0117 20:58:52.864990 22591 search.cc:260] Finished search tree (time = 9999 ms, branches = 99730, failures = 54652, neighbors = 6317534, filtered neighbors = 20153, accepted neigbors = 20153, memory used = 14.12 MB)

I0117 20:58:52.889892 22591 search.cc:260] End search (time = 10000 ms, branches = 99730, failures = 54652, memory used = 14.12 MB, speed = 9973 branches/s)

objective: 3504

Route for vehicle 0:

 0 ->  14 ->  7 ->  1 ->  8 ->  4 ->  5 ->  2 ->  11 -> 0

Distance of the route: 2456km

Number of visit: 8

Route for vehicle 1:

 0 ->  6 ->  9 ->  10 ->  12 ->  15 ->  3 ->  13 -> 0

Distance of the route: 1048km

Number of visit: 7

Maximum of the route distances: 2456km

```

EDIT: My hypothesis, you can see in this solution that the max distance of the route is still 2456km (even if we only serve 8  nodes !) which is exactly the same distance than when ONE vehicle serve all nodes...

so since the objective is the composition of arc cost + the GlobalSpanCost (aka 100*2456) you can reduce the objective by having only one route over two i.e. 2456km < 2456km + 1048km

Maybe this problem is ill-formed ?

While when using the Upper/LowerBound you only have an extra cost when you are out of bound

[Prashant Dave]

I have used your code directly in my Jupyter Notebook and got following error !

AttributeError: 'RoutingModel' object has no attribute 'RegisterTransitMatrix'

As you mentioned above that you are using a new API RegisterTransitMatrix(). I tried to check the solution however I was unable to find it.. Seems I am quite near to get my solution. Once I have it, I will have to fine-tune the code further for my needs. May I request your assistance here pls... !

Thanks.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/959ba025-bd9f-4a28-9173-9f325df3f0dcn%40googlegroups.com.

[Mizux Seiha]

As I said, simply replace this new call by your previous code (I.e. simply uncoment the callback def and change the Register call...)

replace

```python

 transit_callback_index = routing.RegisterTransitMatrix(data['distance_matrix'])

```

by

```python

 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)

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

        return dst

 transit_callback_index = routing.RegisterTransitCallback(distance_callback)

```

[Prashant Dave]

GM, Based on your suggestion, the code is working now. However it is working for a limited set of combinations instead of all. Below is the link FYR. May I seek your assistance for one more time :) 

Sample DataSet with dummy Values: https://drive.google.com/file/d/1AOxbromnNHIwyfCYyP_sJig-2ioXowED/view?usp=sharing

Python Code File: https://drive.google.com/file/d/1S-SCOpqSHkNr3_3DevFaWvQY3Ole8z6L/view?usp=sharing

The error message: 

I have tried to pitch in the code by incorporating if else code, if vehicle=0 then 1. But still it wasn't working for me.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/7e93be84-e6ba-4208-9bcf-f104ed8dbaccn%40googlegroups.com.

[Prashant Dave]

Greetings Mizux,

just wanted to top up on the mail. I am quite near to my closure... However I am unable to crack the solution. May I seek your assistance once more pls... ! Kindly review my earlier email where I am getting an exceptional error as below screenshot. I have shared with you my dummy files FYR too... Many thanks in advance for your assistance.

[Mizux Seiha]

Please send us a gist with a working python sample (or at least, a one cell colab we can copy/paste in a python file), here it is a mess of disjoint code cells

e.g. You have a cell which define the distance_callback() function which depends on the "data" variable.

And in the next cell you have your main() function which instantiate the "data" variable.

That could explain why your call to GetArcCostForVehicle() behaves oddly...

[Prashant Dave]

GM Mizux,

I am enclosing you the code as an attachment. I was trying to figure out the reason for the error on my own but i was unable to do so... !

FYR, If you are using the sample data set as per below, then you will observe that the code is working fine for BranchId = 1027. However for others, it is throwing an error.

Sample DataSet with dummy Values: https://drive.google.com/file/d/1AOxbromnNHIwyfCYyP_sJig-2ioXowED/view?usp=sharing

Thanks for your help here.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/71783816-fc71-425f-9f1d-31d98355461bn%40googlegroups.com.

[Prashant Dave]

Greetings, May I please get help on the below... !

[Prashant Dave]

Good Day... ! I have enclosed the py file as required. Can you help me here... 

 I am on the last leg of finalizing the code here..