SetGlobalSpanCostCoefficient doesn't utilize all vehicles

[Shahar Shavit]

Hey,

I have a problem which OR Tools doesn't utilize all vehicles while it should.

I set GlobalSpanCostCoefficient with high value, and the solution have empty routes and doesn't use all vehicles, while if it would use all vehicles, the global span (MAX(end cumul) - MAX(start cumul)) surely would be lower.

To test the problem with minimal code, I took https://developers.google.com/optimization/routing/vrp code, removed the distance matrix, and changed that the transit callback returns 2 for each pair of nodes.

Here's the code snippet: https://pastebin.com/zQNRYyEw

I set that there are 30 nodes, 6 vehicles and GlobalSpanCostCoefficient as 100000.

I run the VRP and it uses only 3 vehicles, while splitting most of the nodes between only 2 of them.

While the solution should be, as I understand, 6 routes, with 5 nodes each.

The solution of my code snippet is:

Route for vehicle 0:

 0 ->  16 ->  17 ->  18 ->  19 ->  20 ->  21 ->  22 ->  23 ->  24 ->  25 ->  26 ->  27 ->  28 ->  29 -> 0

Distance of the route: 30m

Route for vehicle 1:

 0 ->  15 -> 0

Distance of the route: 4m

Route for vehicle 2:

 0 -> 0

Distance of the route: 0m

Route for vehicle 3:

 0 -> 0

Distance of the route: 0m

Route for vehicle 4:

 0 -> 0

Distance of the route: 0m

Route for vehicle 5:

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

Distance of the route: 30m

Maximum of the route distances: 30m

I'd really appreciate your help.

Thanks a lot,

Shahar

[Laurent Perron]

No. I suppose the 0->15->0 is a forced span they is greater the the span of the other 2 used vehicles.  

--
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/5946d55c-fe1a-4f62-8db2-2cf5ee650703n%40googlegroups.com.

[Mizux Seiha]

1. First you should try to enable the Guided Local Search
```python

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

```

But usually solver still have difficulty to leave from its current position

2. A better way is to use a counter dimension
```python

    data['num_nodes'] = 30

    data['num_vehicles'] = 6

    data['depot'] = 0

    data['visit_counter'] = data['num_nodes'] * [1]

    data['visit_counter'][0] = 0

``` 

```python

    distance_dimension = routing.GetDimensionOrDie(dimension_name)

    distance_dimension.SetGlobalSpanCostCoefficient(100_000)

    # Try to equaly distribute visit among the fleet

    routing.AddVectorDimension(

        data['visit_counter'],

        manager.GetNumberOfNodes(),

        True,  # start cumul to zero

        "Counter")

    counter_dimension = routing.GetDimensionOrDie("Counter")

    num_visit = sum(data['visit_counter']) // manager.GetNumberOfVehicles()

    print(f'num of visit per vehicle: {num_visit}')

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

        index = routing.End(vehicle_id)

        counter_dimension.SetCumulVarSoftLowerBound(index, num_visit, 100_000)

        counter_dimension.SetCumulVarSoftUpperBound(index, num_visit + 1, 100_000)

```

Possible output:
```sh

./vrp.py

num of visit per vehicle: 4

Objective: 1200070

Route for vehicle 0:

 0 ->  25 ->  24 ->  27 ->  26 ->  28 -> 0

Distance of the route: 12m

Route for vehicle 1:

 0 ->  7 ->  6 ->  20 ->  23 ->  22 -> 0

Distance of the route: 12m

Route for vehicle 2:

 0 ->  29 ->  17 ->  16 ->  19 ->  18 -> 0

Distance of the route: 12m

Route for vehicle 3:

 0 ->  13 ->  12 ->  15 ->  14 -> 0

Distance of the route: 10m

Route for vehicle 4:

 0 ->  21 ->  9 ->  8 ->  11 ->  10 -> 0

Distance of the route: 12m

Route for vehicle 5:

 0 ->  5 ->  4 ->  3 ->  2 ->  1 -> 0

Distance of the route: 12m

Maximum of the route distances: 12m

```

[Shahar Shavit]

1. I tried with GUIDED_LOCAL_SEARCH and it's not solving my problem (still not distributing equally and keeps most of the vehicles unused), I think there's some other problem over there :( - the solution output on the end of the email.

2. My goal is to distribute the nodes by the time dimension's end value of each vehicle and not equally numbered between vehicles. In the example, it should be equally distributed (by time dimension), but the example is just to simplify my real code that is more complex.

I feel like there's some simple thing that I'm missing, isn't it?

Does OR-Tools really not know how to do it by itself? does SetGlobalSpanCostCoefficient not work as it should?

The GUIDED_LOCAL_SEARCH solution output:

Route for vehicle 0:

 0 ->  20 ->  21 ->  22 ->  23 ->  24 ->  25 ->  26 ->  27 ->  28 ->  29 -> 0

Distance of the route: 22m

Route for vehicle 1:

 0 ->  11 ->  19 ->  18 ->  12 ->  13 ->  17 ->  16 ->  14 ->  15 -> 0

Distance of the route: 20m

Route for vehicle 2:

 0 -> 0

Distance of the route: 0m

Route for vehicle 3:

 0 -> 0

Distance of the route: 0m

Route for vehicle 4:

 0 -> 0

Distance of the route: 0m

Route for vehicle 5:

 0 ->  10 ->  9 ->  8 ->  7 ->  6 ->  5 ->  4 ->  3 ->  2 ->  1 -> 0

Distance of the route: 22m

Maximum of the route distances: 22m

[Shahar Shavit]

Laurent, the transit function returns the value 2 for each pair of nodes, so the 0->15->0 route end cost is 4, which is lower than the other routes, because they use the same transit function.

[Shahar Shavit]

I found the cause for the problem - it seems like, if the max routes global span cost is equal between two routes, the solver satisfies with the solution and doesn't try to split the routes, even though there are better solutions if it would split it.

I solved it by changing the unit of the time to a smaller scale, for example - milliseconds, and adding some random number (0-1000) to each transit time in the distance matrix, so there would be never two routes with the same time.

Thanks guys <3

Shahar