Vrpy not accomplish the Time Windows Constraints

[tomatoes-prog]

I am trying to solve a CVRPTW on a graph with 54 nodes and 353 edges, as you can see it is a little size problem, and all the edges have a time window, a demand and a service time as the next image:

However, when I try to solve the problem with the exact algorithm the best routes are not satisfying the time windows constraint, as an example (even when this happens with many nodes) the previous node 36 has the time window [8 , 14] and when I look at the prob.arrival_time attribute the arrival time at the node is 15.3 (out of the TW) as shown in the next image

You can reproduce the problem with the next graph in the zip and this code:

from networkx import read_gpickle
import vrpy
G = read_gpickle('graph_vrpy,test')
len(G.nodes)
prob = vrpy.VehicleRoutingProblem(G, load_capacity=80)
#prob = VehicleRoutingProblem(G, load_capacity=100)
prob.time_windows = True
prob.solve(exact=True)

prob.best_routes
prob.arrival_time
G.nodes['36']

graph_vrpy.zip

[tomatoes-prog]

Taking a look at the problem it seems to be a problem at the SubProblem algorithm, at the subproblem_cspy.py module y tried changing the direction of the Bidirectional algorithm from 'both' to 'forward' it seems to generate a different solution where the solution seems to be feasible. Obviously I think this solution is not good because it comes with a several decrease on the subproblem performance.

[torressa]

Hey @tomatoes-prog! Hmm.. I can reproduce the error, I've tried solving the problem with LP instead to compare solutions but it's too slow even with Gurobi. I'll have a look into this...

[tomatoes-prog]

Yeah, I also tried the LP solving but I think the reason might be the size of the Time windows, but no sure to be honest.

[torressa]

Hmm.. There's something weird about this, I think it's to do with the arrival/departure time conversion. As I wasn't sure if it was cspy or not, I've checked using the Solomon instance with the LP. It seems that the departure/arrival times conversions violate the TW. Just pushed the test to dev

[Kuifje02]

I am still getting the error for nodes 58, 150, 108, 13, 222. But all the solomon tests are passing...needs a little investigation !

[torressa]

Can confirm, only for arrival times though... I've just added another condition there

[Kuifje02]

Hmm, I'm doubting now. I am not 100% sure this is right : https://github.com/Kuifje02/vrpy/blob/f01b147a81bb8852386e9d59b76c3160615c785d/vrpy/vrp.py#L365-L370

I feel like we are kind of cheating with the outer min, in the sense that if we have to use the min, it means the route is not feasible. I need to think it through, we might need a different strategy to compute departure and arrival times, maybe we need to compute them simultaneously with something like departure(head) = arrival(head) + service time(head) arrival(head) = max(lower,departure(tail)+travel_time)

[torressa]

Yeh I think you're right here. I think I'm confused... If you try to enforce time-windows both at arrival and departure, you get an infeasible subproblem as lower + service_time > upper in some cases (for example in the Solomon instance). So we can check time windows for arrival times (or self.t in the subprblem_lp) but if we check the departure time, it will not satisfy the time-windows as this is not being considered in the subproblem.

Not sure if this is correct, but if is, the previous version of arrival_time was fine

[torressa]

And.. Going back to the beginning, @tomatoes-prog is correct. With the previous arrival_time version, without the min, cspy works with direction="forward" and not with "both". Performance-wise "forward" seems to be faster so it's not really a problem, I just need to double check the backward REF.

PS. Sorry for committing to master

[Kuifje02]

@torressa does this mean we should always use direction="forward" when time windows are enforced ?

[torressa]

Will look into this as well along with #15 Not sure why bidirectional sometimes fails (probs a bug in the callback), but the performance difference is normal and comes from the bounds of the primary resource (mono/load here) which determines the halfway point. If the bounds are loose, forward is the same or outperforms, if they are tight both is the same or outperforms.

[ugirumurera]

@torressa, does this mean solutions vrp with time windows are incorrect or is just that the arrival/departure times are incorrect?

[torressa]

@ugirumurera With the current release actually kind off both. The arrival/departure times contain the fudge mentioned above. The solutions, using cspy=False are definitely correct, with cspy=True may be incorrect. As we were using direction="both" and for some reason that doesn't always work. Until I figure out why this is, I've set the labelling to "forward" which works https://github.com/Kuifje02/vrpy/blob/65c13ab3c1ba91b2f0d77d8b7a9d90e3d31d33f2/vrpy/subproblem_cspy.py#L233

Will be all fixed in the next release.