VRP - want to maximize the number of vehicles used

[Hanna Hamilton]

Hello - 

I would like to maximize the number of vehicles used in my VRP. Is there a way to create a variable for the number of unused vehicles and pass this into routing.AddVariableMinimizedByFinalizer()? Or is there a better way to do this?

Thanks,

Hanna

[Mizux Seiha]

What about having a counter dimension and having a soft upper bound on each vehicle's end node being "num location // num of vehicles" ?
i.e. give incentive to the solver to dispatch visit.

AND/OR having a soft lower bound to penalize vehicle with no visit
e.g.
```python

 routing.AddConstantDimension(

1, # +1 for each visit (note start node is counted so unused vehicle is still 1)

LARGE_ENOUGH, # max visit allowed,  hard limit

True,  # start cumul to zero

"Counter")

counter_dimension = routing.GetDimensionOrDie("Counter")

for vehicle_id in range(manager.GetNumberOfVehicles()):

        index = routing.End(vehicle_id)

       counter_dimension.SetCumulVarSoftLowerBound(index, 2, 100_000) # penalty of 100_000 for each empty vehicle since counter will be 1 aka (2 - 1) * 100_000  

```

[Hanna Hamilton]

Thank you so much!

[Hanna Hamilton]

Hi there - I have a follow up question. I am just trying to understand my objective value. It is 2424. I have two vehicles and the one with the largest distance has a distance of 24 miles. I have distance_dimension.SetGlobalSpanCostCoefficient(100), so that gets me to 24*100 = 2400.  The other vehicle actually is empty (distance = 0 miles), so this penalty applies. I am not sure what 100_100 means, but could it just be 1% of 2400? That would add on 24 and get me to 2424.

Thanks,

Hanna

[Mizux Seiha]

Using global span you'll have:
extra cost = ( max(all vehicle end) - min(all vehicle start) ) * global_span_cost_coefficient 
according to what you said and few hypotheses
max(all vehicle end) = 24

min(all vehicle start) = 0 # supposing vehicle start distance dimension at zero aka force cumul start to zero is set to true

global_span_cost_coefficient = 100 # since you are using distance_dimension.SetGlobalSpanCostCoefficient(100)

so we have:
extra_cost = ( 24 - 0) * 100 = 2 400 added to the objective value

For penalty since the vehicle is empty it should have a counter dimension equals to 1 at the end node, and according to the SetCumulVarSoftLowerBound(index, 2, 100_000) in my above message
extra cost= max(0, lower_bound - cumulvar value) * 100 000 = max(0, (2 - 1)) * 100 000 = 100 000 added to the objective value

For the 24 my guess is: you are using the method "routing.SetArcCostEvaluatorOfAllVehicles(distance_transit_callback_index)" so the sum of all visited arcs aka vehicle routes is also added to the objective.

You have an empty vehicle i.e. 0 and a vehicle whose distance is 24 thus the sum of all arcs should be 24...

[Hanna Hamilton]

Thank you for that explanation. That clears some things up, but now I'm wondering why the objective value is not 2424 + 100000 = 102424 (since the penalty should be applied)?

Also, I added service times to my time_matrix and I got a smaller objective value. Prior to this change, some vehicles were going back to the same pickups (just duplicated nodes). I think this makes sense because now there is less traveling (all pickups for a given location done at once now), but I don't understand how there is this relationship between the time_matrix and the objective value since the objective value seems to take distance numbers and no time numbers. Do you have any insight on this?

Thanks,

Hanna

[Mizux Seiha]

By default any dimension won't participate to the objective (ed you can see it as the span cost coefficient is set to 0 by default).

To add the span cost to the objective you could use: 

```cpp

void RoutingDimension::SetSpanCostCoefficientForVehicle(int64_t coefficient, int vehicle);

void RoutingDimension::SetSpanCostCoefficientForAllVehicles(int64_t coefficient);

```

ref:  https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L2482-L2489

Also you have the "special" arc cost function (mainly use by first strategy heuristic): 

void SetArcCostEvaluatorOfAllVehicles(int evaluator_index);

ref: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L901-L906

note: you can see it as a dimension with no slack, unlimited capacity and a span cost coefficient of 1 

My guess is beside having two dimensions (distance and time) you've used the distance callback for the SetArcCostEvaluatorOfAllVehicles()

For the penalty did you set this soft lower bound on all end nodes ?

ps: don't hesitate to share a gist

[hannes]

Hi all,

I am currently implementing the constraint that a delivery is on the vehicle for at most x seconds.

The delivery is modelled by a pickup-dropoff constraint with two locations.
Given the max_transport_seconds (int) I tried the following:

```
# ix = pickup index, iy = dropoff index

pickup_time = dimension_seconds.CumulVar(ix)
dropoff_time = dimension_seconds.CumulVar(iy)``
solver.Add(dropoff_time - pickup_time <= max_transport_seconds)
```

It works fine, but there may be a slack at ix that is not technically part of the transport time.
So I would like to make the pickup_time more precise by adding the slack at ix to it.

```
pickup_time = dimension_seconds.CumulVar(ix) + dimension_seconds.SlackVar(ix)
...
```

Again, I do get a solution, but this time it violates the condition "dropoff_time - pickup_time <= max_transport_seconds".
This looks strange because now pickup_time should be greater than in the first encoding (since I add the slack).
Not sure if this is due to a bug somewhere or whether the problem is in the expression of adding a cumul to a slack var.

Is it ok to add cumul and slack vars?

Any help appreciated,
Hannes.

[Hanna Hamilton]

Yes, I am using the distance callback for the SetArcCostEvaluatorOfAllVehicles(). What does this do exactly? I am wondering if I need to be using the time callback for this instead.

Yes, I set the soft lower bound on all end nodes. What does a penalty of 100_00 mean? Also, how does this penalty work within the model if it is not incorporated into the objective function?

Thanks,

Hanna

[Hanna Hamilton]

Please disregard my first question. I looked at the link you sent and it is making sense. How do you know whether to use the distance callback or time callback for the SetArcCostEvaluatorOfAllVehicles()?

[Hanna Hamilton]

If I am understanding this correctly, it seems counterintuitive to use SetSpanCostCoefficientForAllVehicles(). I am using counter_dimension.SetCumulVarSoftLowerBound(index, 2, 100_000) as a way to get solutions with no empty vehicles whenever possible. If I use SetSpanCostCoefficientForAllVehicles(), then there are costs associated with each additional vehicle, and thus solutions with less vehicles will have lower objective values? Am I thinking about this correctly?

[Corentin "Mizux" Le Molgat]

1. Iff the difference between your distance matrix and the time matrix is just a matrix scalar multiplication, I don't think it will change the search.

2. Now if you want to take into account vehicle speed, road type (street, highway) then I would go for time matrix since you'll incorporate more information than the raw metric distance and both matrices can differs...

3. Mainly the SetArcCostEvaluatorOfAllVehicles() is used by first strategy when comparing arc/route/transit(A, *) e.g. PATH_CHEAPEST_ARC will create a route node by node by selecting the closest node from the current node according to this evaluator cost.

4. That's why we use 100_000 as penalty to make it the dominant factor, aka first solver will try to use all vehicles to avoid to pay 100_000 per empty one, then it will still try to optimize the route of each vehicle to futher reduce the overall cost if possible.

So while 100_000 is arbitrary it should be one or two order of magnitude bigger than the sum of all visited arc so solver has strong incentive to first avoid this penalty cost....

i.e. solution with an objective value of 100_0XX is still worse than solution with an objective value of YYY. 

[Vincent Furnon]

If you are only interested by actual travel time without slack, you could add another "travel time" dimension with no time windows (and no slack) and constrain the cumuls on that dimension. 

On your current issue this is indeed strange since slacks are positive.

--
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/bafab424-bbd5-835c-63e5-51246cf1cee0%40yahoo.de.

[hannes]

Yes, that's exactly my problem and I am also surprised because the constraint behaves as if slack is negative.

Regarding a dimension of travel times: I wish I could follow your advice (because I am confident it works and is easy to implement) but I do have to consider the slacks in between pickup and dropoff. It is just the first slack, the one at the pickup, that should be discarded.

I am always nervous when I touch the slacks as I am fairly sure that even the formula cumul(y) = transit(x, y) + cumul(x) + slack(x) may be violated by ortools.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAPz%2Bj2Us%3DKsrqsR4Dnb-qRc1gHO50-BVzf%2B%3Dc_D1BX4NdGRzdg%40mail.gmail.com.

[Hanna Hamilton]

Hi Mizux,

Thank you for the detailed response. Just some follow-up questions:

3. I am not currently using PATH_CHEAPEST_ARC. In fact, I don't think I am currently specifying a first_solution_strategy. However, my code is running and producing reasonable results, so might there be a default first_solution_strategy?

4. I am confused about the "_" inside 100_000. Does 100_000 = 100,000? Also, when I get a solution with an empty vehicle, I do not see a penalty added to the objective value. I think I might need to fix something here, but not sure what to do.

Thanks,

Hanna

[Mizux Seiha]

3. https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing_search.cc#L162-L178

4. python 3.6 PEP 515 "Underscores in Numeric Literals"
ref: https://www.python.org/dev/peps/pep-0515/

Again don't hestitate to share a pet example so we can debug it ;)

[Hanna Hamilton]

Okay, sounds like my first_solution_strategy is PARALLEL_CHEAPEST_INSERTION by default since I have pickups and deliveries, and 100_000 is equal to 100,000. Thank you for your help.

[Manuel Renner]

For those joining the conversation later and having issues with the penalty not appearing (point 4.), this is because empty vehicle costs are not considered by default.

In order to consider these costs as well, use  ConsiderEmptyRouteCostsForVehicle (v9.1) or  SetVehicleUsedWhenEmpty (v9.2+):

i.e.

for vehicle_id in range(manager.GetNumberOfVehicles()):

    routing.SetVehicleUsedWhenEmpty(True, vehicle_id)

see https://github.com/google/or-tools/issues/2161 and https://github.com/google/or-tools/issues/3241