search

Kuifje02 / vrpy

A python framework for solving the VRP and its variants with column generation.
MIT License
173 stars 42 forks source link

Issue with prob.duration #102

Closed shunana closed 3 years ago

shunana commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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.