Infeasible problem with time limit, num_vehicles=1 and drop_penalty

[mdubil15]

graphe_vrp.zip

Hello, here is the graph and the issue related. Thanks for your help ;)

With this graph (20 nodes all related to each other and to the source and sink, service_time on each node, and cost=time on each edge) ,

prob = VehicleRoutingProblem(graphe_l, num_vehicles = 1, drop_penalty=100, duration = 420)
prob.solve()

gives the exception "problem infeasible" though it should show the best routing that one vehicle can operate in less than 420 time units ?

[Kuifje02]

Hi @mdubil15 ! Thanks for reaching out :)

I am able to reproduce the error. This is very strange. It seems to be related to the solver. The error that is thrown is different if I use CPLEX (prob.solve(solver="cplex")), and the error differs if I change the solving parameters withing cplex: I get 'optimal with unscaled infeasibilities'.

This needs a little investigation. I think the problem comes from the combination of imposing a unique vehicle, and allowing dropping nodes. This creates artificial variables behind the curtains, with high coefficients. Will get back to you as soon as I can!

[Kuifje02]

I am investigating and am pretty sure this is a scaling issue.

The concept of using both options num_vehicles=1 and drop_penalty=100 is perfectly valid. In fact, one of the unit tests tests this (and does not fail):

https://github.com/Kuifje02/vrpy/blob/96cc5501d05c341cc50f4377d15f27fbf422584a/tests/test_toy.py#L296-L303

[Kuifje02]

@mdubil15 Ok, quick fix:

Add this to your code before solving (add some fictitious demand):

for v in G.nodes():
    G.nodes[v]["demand"] = 1

This fixes the problem here. Can you check if this works for you?

@Kuifje02 need to understand why drop variables are not created without this.

[Kuifje02]

In the next release, the code will work without having to add fictitious demand. Closing for now.