Issue with prob.duration

[shunana]

I have trying to reproduce some of the Vehicle Routing Problems, in the CVRP with resource constraints

The following is added to the graph and the model:

G.edges["Source",1]["time"] = 5
G.edges["Source",2]["time"] = 4
G.edges[1,2]["time"] = 2
G.edges[1,"Sink"]["time"] = 6
G.edges[2,"Sink"]["time"] = 1
prob.duration = 9
prob.solve()

My issue is that I get a ValueError in the feasibility check:

ValueError: Node 1 not reachable: duration of path [Source,1,Sink], 11, is larger than max duration 9

How can that be ? By having that constraint it is specified that we don't want the duration of 11. Or have I completely misunderstood what prob.duration does ?

I am using python 3.8.10 , vrpy 0.5.0 and networkx 2.5.1

I hope that somebody are able to help.

[Kuifje02]

What the error is saying is that it is not possible to service node 1, because the simplest and shortest route (source-1-sink) violates the duration constraint.

Any other route with node 1 will thus also violate the duration constraint.

So in summary, the problem is not feasible with such times.

[shunana]

Okay, but what about the solution (source - 1- 2- sink ) which has a duration of 8, even though it includes node 1 it would not violate the duration constraint.

And I would have expected that the solution (source - 1- 2- sink ) would have been found instead.

I can't really understand why that isn't the case. Also it is given as an example so somehow it should or did work..

[Kuifje02]

O yes, you are absolutely right. I was assuming the triangle inequality holds, which is not the case. My previous comment is obviously False without this assumption.

Thank you for pointing this out, will be fixed in the next release.