Variable/indeterminate and non-obligatory pause at the depot

[thiagomoretto]

Hi there!
I have a case that I am trying to model the right way, at the same time trying to figure out if it's possible to solve with one problem instance.

It's a pickup & dropoff with time-window problem. There's a case where I have a pickup a customer early morning a drop him somewhere. But, I also have to pickup this same customer several hours later, and I would like to use the same vehicle if it's available. As you can see, there's a huge time gap between the orders (several hours that the vehicle has nothing to do) in this case.

Using an huge "wait time" on time dimension I get a solution with one route, but ends up that the min and max time windows for arrival/depart from/to each node are all "useless" for the case (huge gap between them) and also can afect other routes unnecessarily. Nevertherless to say there's another problem, the final solution means the the vehicle is waiting somewhere or on the next stop. Using a small wait time, one of the orders (that later one) is dropped, even thought the vehicle is "available", once the vehicle already returned to the depot after serving the first order, it can't exit for other orders anymore.

The ideal case here is to reuse the same vehicle when possible, so, generating two routes for the same vehicle and letting it to a variable/indeterminate and non-obligatory "pause" at the depot in those simulate cases I described above.

I though checking the initial solution if the solver has dropped some orders, and if so, I would generate a new VRP problem with the remaining available time of each vehicle (they have a service time-window, I can use that to limit) and pass just the dropped orders in attempt to generate routes for them. Idk if this approach will work as expected or not, though.

So, I would like to solve using one problem instance. Are there ways to create those variable/indeterminate and non-obligatory "pause" at the depot to allow the vehicle to pause? Or which alternatives can I have to handle this case?

I think fixed time interval breaks won't work for this case. Neither modelling it as refueling.

Really thanks!

[thiagomoretto]

What I have done so far:

Since each vehicle can start and end at different locations (although start == end), I created spare/fake depots (pickup&dropoff nodes in the same location) for each vehicle and set the range of the slack var for them:

time_dimension.SlackVar(pickup).setRange(0, 1440)
time_dimension.SlackVar(dropoff).setRange(0, 1440)

where 1440 is the "end of day" (the max. time).

For regular/customer nodes, the slack var was also set individually to make sure the default max wait time of the time dimension (== 1440) is not used for them:

time_dimension.SlackVar(pickup).setRange(0, 5)
time_dimension.SlackVar(dropoff).setRange(0, 5)

I have also added a disjunction for the fake depot spot with a small penalty (= 1). Using 0 make the solver to ignore totally the fake depot nodes prefering to drop customer nodes (they have a huge penalty value). Is this right?

Also added constraints to make sure the vehicle arrives empty at the fake depot, as well as, the pickup&dropoff of are also in sequence. These constraints are working well.

One initial issue I had is that those fake stops were being "consumed" in the start of the route, not between the real nodes where I supposed to see, to fix this issue I put a constraint on those fake nodes to avoid them being visited at the start of the route. Worked for one scenario, messed other one.

The example so far:

wpt: 0 type: start ride: None time-window: {'start': 0, 'end': 11} for: None loc: None
wpt: 1 type: pickup ride: outbound time-window: {'start': 41, 'end': 52} for: None loc: {'id': 4, 'lat': 39.8187, 'lng': -104.634}
wpt: 2 type: dropoff ride: outbound time-window: {'start': 79, 'end': 90} for: None loc: {'id': 5, 'lat': 39.8929, 'lng': -104.6748}
wpt: 3 type: pickup ride: **pause** time-window: {'start': 100, 'end': 116} for: 0 loc: {'id': 0, 'lat': 39.8911, 'lng': -104.6618}
wpt: 4 type: dropoff ride: **pause** time-window: {'start': 100, 'end': 639} for: 0 loc: {'id': 0, 'lat': 39.8911, 'lng': -104.6618}
wpt: 5 type: pickup ride: **pause** time-window: {'start': 100, 'end': 639} for: 0 loc: {'id': 0, 'lat': 39.8911, 'lng': -104.6618}
wpt: 6 type: dropoff ride: **pause** time-window: {'start': 100, 'end': 639} for: 0 loc: {'id': 0, 'lat': 39.8911, 'lng': -104.6618}
wpt: 7 type: pickup ride: **pause** time-window: {'start': 100, 'end': 639} for: 0 loc: {'id': 0, 'lat': 39.8911, 'lng': -104.6618}
wpt: 8 type: dropoff ride: **pause** time-window: {'start': 100, 'end': 639} for: 0 loc: {'id': 0, 'lat': 39.8911, 'lng': -104.6618}
wpt: 9 type: pickup ride: return time-window: {'start': 600, 'end': 660} for: None loc: {'id': 5, 'lat': 39.8929, 'lng': -104.6748}
wpt: 10 type: dropoff ride: return time-window: {'start': 639, 'end': 704} for: None loc: {'id': 4, 'lat': 39.8187, 'lng': -104.634}
wpt: 11 type: end ride: None time-window: {'start': 681, 'end': 751} for: None loc: None

Since I've added 3 fake depots for each vehicle, they were all used between the regular/real nodes. Not an issue, I can collapse them.

Unfortunately, in some other cases, those stops ("pause") are appearing on the end of route as well, but this isn't really an issue right now.

That's all for now. I would like to know if I am going to the right direction to solve this problem.

[Mizux]

Did you try to add soft constraint on vehicle to "force" to use the same vehicle if possible ?
see

or-tools/ortools/constraint_solver/routing.h

Lines 588 to 592 in 554cbcc

	// Adds a soft contraint to force a set of nodes to be on the same vehicle.
	// If all nodes are not on the same vehicle, each extra vehicle used adds
	// 'cost' to the cost function.
	void AddSoftSameVehicleConstraint(const std::vector<NodeIndex>& nodes,
	int64 cost);

Warning: NOT tested

p1 = routing.NodeToIndex(pickup_1)
p2 = routing.NodeToIndex(pickup_2)
# force same vehicle or add the penalty cost
penalty_cost = 1000
routing.AddSoftSameVehicleConstraint([p1,p2], penalty_cost)

close to #979 (comment)

[thiagomoretto]

Hi @Mizux. I definetely have to see this. Looks interesting way to go.
So far, I solved in another way, I'll share some steps for others that might come here with a similar problem.

Like I said before, I've created dummy/fake nodes at the same place as the depots, some of them for each vehicle, and I also had to add a small penalty for dropping the visit, idk but without this the dummy node was totally ignored:

Ex.:

routing.AddDisjunction([routing.NodeToIndex(i)], 1)

Those dummy nodes (internally, I named them as "pause" nodes), has a custom service time (meaning the minimal time to pause/rest at the depot). I've also ajusted the slack var of these nodes allowing a very flexible pause time.

time_dimension.SlackVar(pause_node).SetRange(0,
    data.max_allowed_pause - data.service_times[node])

To force the vehicle to just visit/pause at nodes that it was designed for, I added the constraints below, where each dummy node has a vehicle index, that is used to check if the pause node is being correctly used:

vehicle_index = node.obj['vehicleIndex']
constraintActive =\
    routing.ActiveVar(routing.NodeToIndex(pause_node)) * \
    routing.ActiveVar(routing.NodeToIndex(vehicle_index))
routing.solver().Add(
    constraintActive * routing.VehicleVar(routing.NodeToIndex(pause_node)) ==
    constraintActive * routing.VehicleVar(routing.NodeToIndex(vehicle_index)))

This approach is working pretty well so far, some issues I was having are gone. But I am not so sure if this approach wil survive with the new future features I still have to add to the model.

Roughly speaking, that's it.

Many thanks! I will see this guy here routing.AddSoftSameVehicleConstraint, I didn't know about it before, it might be useful for an improved version.