use_all_vehicles = True results in 'problem Infeasible'

[prasanik]

The below code is set up to have 4 nodes with 10 each as demand. It also has 4 vehicles with 10 capacity each. vrpy returns 4 routes as expected.. 1 node per route. But if you uncomment the line prob.use_all_vehicles, it results in error of problem infeasible. But as we have seen, when we run the code without this line, it does actually end up using all vehicles.

from networkx import DiGraph
from vrpy import VehicleRoutingProblem
import networkx as nx

def run():
    G = DiGraph()
    for v in [1, 2,3,4]:
           G.add_edge("Source", v, cost=[10, 11, 10, 10])
           G.add_edge(v, "Sink", cost=[10, 11, 10, 10])
           G.nodes[v]["demand"] = 10
    G.add_edge(1, 2, cost=[10, 11, 10, 10])
    G.add_edge(2, 3, cost=[10, 11, 10, 10])
    G.add_edge(3, 4, cost=[15, 16, 10, 10])
    
    nx.draw_networkx(G)

    prob=VehicleRoutingProblem(G, mixed_fleet=True, load_capacity=[10, 10, 10, 10])
    prob.num_vehicles = [1,1,1,1]
    #prob.use_all_vehicles=True
    prob.solve(time_limit=60)
    a = prob.best_value
    a = prob.best_routes
    a = prob.best_routes_type
    print(a)

run()

[torressa]

Thanks for the report! This is indeed a bug on our side with the way the initial routes are handled.

[torressa]

Just pushed a fix without changing the master problem formulation. It is a bit over-complicated but works for this small example. I cannot a better way of fixing it right now.