Infeasible problem with time limit, num_vehicles=1 and drop_penalty

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 ?

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!

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):

vrpy/tests/test_toy.py

Lines 296 to 303 in 96cc550

    
           def test_drop_nodes(self): 
        
               prob = VehicleRoutingProblem(self.G, 
        
                                            num_stops=3, 
        
                                            num_vehicles=1, 
        
                                            drop_penalty=100) 
        
               prob.solve() 
        
               assert prob.best_value == 240 
        
               assert prob.best_routes == {1: ["Source", 1, 2, 3, "Sink"]}

@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.

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

	def test_drop_nodes(self):
	prob = VehicleRoutingProblem(self.G,
	num_stops=3,
	num_vehicles=1,
	drop_penalty=100)
	prob.solve()
	assert prob.best_value == 240
	assert prob.best_routes == {1: ["Source", 1, 2, 3, "Sink"]}