How to model Driver Overtime cost Ortools VRP

[youssef kaichouh]

Hello, let's say a vehicle v have shift_time and max_overtime, so that the max_shift_time can never exceed shift_time + max_overtime
We can achieve that easily by:

timeDimStart = duration_dimension.CumulVar(routing.Start(v))

timeDimEnd = duration_dimension.CumulVar(routing.End(v))
solver.Add(timeDimEnd <= timeDimStart + shift_time + max_overtime)

But how can we add a penalty (soft constraint) when
timeDimEnd - timeDimStart >= shift_time ??
Basically we want to add to the objective something like:
(timeDimEnd - timeDimStart - shift_time if timeDimEnd - timeDimStart >= shift_time else 0)*penalty  
Is that possible ? 
Thank you

[Mizux Seiha]

Take a look at SetCumulVarSoftUpperBound(end node, shift time, penalty)
note: since this upperbound suppose a start at 0 you may/should add a "duration" dimension (and keep your Time dimension for TW)

ref: https://github.com/google/or-tools/blob/2a7f8724bded68426619482a20d672c5330837c9/ortools/constraint_solver/routing.h#L3007-L3016

pydoc: https://or-tools.github.io/docs/python/ortools/constraint_solver/pywrapcp.html#RoutingDimension.SetCumulVarSoftUpperBound

[youssef kaichouh]

Hello Mizux, thanks for your quick response.
But how can i add the "duration" dimension of which the CumulVar at the end node matches  timeDimEnd - timeDimStart ?

--
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/68ed4eb5-3e66-4c1f-9c0a-882f86007e41n%40googlegroups.com.

[youssef kaichouh]

Hello Mizux
Can you explicitly please tell me how can i define this "duration* dimension, it's not clear for me at all.
I was aware of SetCumulVarSoftUpperBound before opening this ticket, i just don't see how to overcome the fact that the upperbound suppose a start at 0

[youssef kaichouh]

For future readers, i managed to get this constraint with previous idea, we basically create another dimension (with callback index always 0, slack big enough)

shift_duration = 'Shift_duration'

    routing.AddDimension(

        shift_duration_callback_index,

        infinity,  

        infinity, 

        True,  

        shift_duration)

    shift_duration_dimension = routing.GetDimensionOrDie(shift_duration)

    for v in range(num_vehicles):

            timeDimStart = duration_dimension.CumulVar(routing.Start(v))

            timeDimEnd = duration_dimension.CumulVar(routing.End(v))

            shiftDuration = shift_duration_dimension.CumulVar(routing.End(v))

            solver.Add(shiftDuration == timeDimEnd-timeDimStart)

            shift_duration_dimension.SetCumulVarSoftUpperBound(

                routing.End(v),

                shift_time_soft_upper_bound(v),

                overtime_cost(v)

                )

[Madhumita Tripathy]

Hi. I am also struggling with solving driver shift using Google OR tools. Can you please provide me sample code of shift_duration_callback_index with continuation of above code. Thanks in advance.

[Rummel]

For documentation reasons, here the answer to the question of Madhumita. The callback always give back 0 (as mentioned before):

def shift_duration_callback(from_index, to_index):

    return 0

shift_duration_callback_index = routing.RegisterTransitCallback(shift_duration_callback)

The idea of the new dimension variables is, that they are unbound and almost independent of each other. Independency becomes clear if you consider the definition of a cumul variable:

    if i+1 == next(i), cumul(i+1) = cumul(i) + transit(i,j) + slack(i)

transit is alway 0, cumul(start) is also 0:

    cumul(i+1) = cumul(i) + slack(i) = cumul(i-1) + slack(i-1) + slack(i) = ... = cumul(start+1) + slack(start+1) + ... + slack(i) = slack(start) + ... + slack(i)

Because slack is always greater or equal 0:

    cumul(i+1) >= cumul(i) >= ... >= cumul(start) = 0

Now you can bound these variables to your own constraints.

I used the solution of youssef to solve a similar problem. I have a VRP with pickups and deliveries. Here, persons are transported and they only accept a maximum detour. I want to formulate this with a soft constraint. In my case I used the pickup and delivery nodes of the requests instead of the start and end nodes of the vehicles:

route_cost_dimension_name = 'route_cost'

routing.AddDimension(

    route_callback_index,

    infinity,  # maximum value of slack

    infinity,  # maximum value of cumul

    True,  # force start cumul to zero

    route_cost_dimension_name)

route_cost_dimension = routing.GetDimensionOrDie(route_cost_dimension_name)

for request in data['pickups_deliveries']:

    pickup_index = manager.NodeToIndex(request.from_node)

    delivery_index = manager.NodeToIndex(request.to_node)

    route_start = distance_dimension.CumulVar(pickup_index)

    route_end = distance_dimension.CumulVar(delivery_index)

    route_cost = route_cost_dimension.CumulVar(delivery_index)

    solver.Add(route_cost == route_end - route_start)

    route_cost_dimension.SetCumulVarSoftUpperBound(

        delivery_index,

        request.max_route_length,

        detour_cost

    )

[blind.lin...@gmail.com]

Thanks for sharing that clever hack.

One concern I have is that the route cost will slowly increase without
bound. Cutting and pasting from your code:

{.quotesubsequent}route_start = distance_dimension.CumulVar(pickup_index)  
route_end = distance_dimension.CumulVar(delivery_index)  
route_cost = route_cost_dimension.CumulVar(delivery_index)  
solver.Add(route_cost == route_end - route_start)  
route_cost_dimension.SetCumulVarSoftUpperBound(  
    delivery_index,  
    request.max_route_length,  
    detour_cost  
)  

So the second pickup and delivery by a vehicle, the
route_cost_dimension must necessarily be greater than the first, as
the slack is only positive. So there is no way at the second delivery
node that the route cost will actually be route_end - route_start,
correct?

I know the soft bound will ignore this detail and do its best, but it
seems only the first trip will really be aiming for the max route
length, whereas every future trip will be max route length less any
overage from prior trips (as the dimension will continue to increase)

I was thinking that perhaps it would be cleaner for those 2nd, 3rd,
etc dropoffs if the route cost dimension could somehow reset at
delivery nodes. A priori you know both the shortest distance from
pickup to delivery and the acceptable overage, so each delivery node
could subtract one or both quantities (leveraging the (undocumented)
fact that dimensions have a hard floor at zero). Then the soft bound
could be that the route cost dimension is zero at the end of the
route, so that the net extra time is minimized.

But again, nice hack

James

>= shift_time else 0)penalty *Is that possible ?
Thank you

--
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/68ed4eb5-3e66-4c1f-9c0a-882f86007e41n%40googlegroups.com

https://groups.google.com/d/msgid/or-tools-discuss/68ed4eb5-3e66-4c1f-9c0a-882f86007e41n%40googlegroups.com?utm_medium=email&utm_source=footer
.

--
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/4b85fc35-a81e-48ac-aa76-9abcb1b7b0f3n%40googlegroups.com.

--

James E. Marca  
Activimetrics LLC  

[Rummel]

Oh dear, your right James! And I have explained that the CumulVar can only increase in that case myself...

I need to think about your proposal. I have a feeling that this will not succeed very cleanly. Maybe it is better to introduce some other variables and add them to the solver (if it is possible in the routing solver).

[Rummel]

First:

If you like to add a dimension with callback index always 0, you can use routing.AddConstantDimensionWithSlack(...) instead of routing.AddDimension(...). Instead of registering a transit callback function you can simply use a constant value. For the example of youssef it could look like:

    shift_duration = 'Shift_duration'

    routing.AddConstantDimensionWithSlack(

        0,

        infinity,  # attention order changed, this is maximum cumul

        infinity,  # maximum slack

        True,

        shift_duration)

    shift_duration_dimension = routing.GetDimensionOrDie(shift_duration)

    for v in range(num_vehicles):

            timeDimStart = duration_dimension.CumulVar(routing.Start(v))

            timeDimEnd = duration_dimension.CumulVar(routing.End(v))

            shiftDuration = shift_duration_dimension.CumulVar(routing.End(v))

            solver.Add(shiftDuration == timeDimEnd-timeDimStart)

            shift_duration_dimension.SetCumulVarSoftUpperBound(

                routing.End(v),

                shift_time_soft_upper_bound(v),

                overtime_cost(v)

                )

Second:

My example didn't work, as James already explained. I currently have no idea how to cleanly reset the dimension on all delivery nodes (especially with combined transports). Therefore I would suggest to introduce a new dimension for each request. This makes the modeling clearer for me and works in my first tests:

for request in data['pickups_deliveries']:

    request_cost_dimension_name = 'request_cost'

routing.AddConstantDimensionWithSlack(

    0,             # Transition is 0

        matrix_costs,  # reasonable maximum request costs

        matrix_costs,  # reasonable maximum slack

        True,          # force start request costs with 0

        request_cost_dimension_name)

    request_cost_dimension = routing.GetDimensionOrDie(request_cost_dimension_name)

pickup_index = manager.NodeToIndex(request.from_node)

    delivery_index = manager.NodeToIndex(request.to_node)

    route_start = distance_dimension.CumulVar(pickup_index)

    route_end = distance_dimension.CumulVar(delivery_index)

    route_cost = request_cost_dimension.CumulVar(delivery_index)

    solver.Add(route_cost == route_end - route_start)

    request_cost_dimension.SetCumulVarSoftUpperBound(

        delivery_index,

        request.max_route_length,

        detour_cost

    )

Depending on the model size it could be that the solver takes more time now. In my current use cases I only use this soft constraint for a small part of the requests.

Best Johannes

[Nano Byte]

Hey Johannes and All,

I am facing the same problem as you - penalizing Detour - and are also not finding a direct solution in the C++ API or Google OR Tools.

I also had the Idea of using a dummy Dimension and redirecting the detour into it.

Using one Dimension per Request and binding the CumVar is one option I want to avoid though, because of > 100 Requests.

I had SOME success actually intercepting the SlackVar, eventually enforcing the Slack of the "Detour" dimension for each Pickup Node to be equal to the detour between Pickup and Delivery.

It worked fine in a Unit Test, but did for some reason not perform in a large scale data set. It stalls when ReadAssignmentFromRoutes() with no error. (OR Tools Version 9.12)

I thus ran out of ideas to try out.

Did you have any progress on this issue since?

Best
N.