Load_capacity constraint breaches

[egh312]

Think the library is a great idea!

Have come across a minor issue with load_capacity breaches.

[Kuifje02]

Thank you for your feedback. I assume A is the distance/cost matrix ? Can you just provide the demands for each node so that I can replicate the error ? I assume its either 1 or 2.

[Kuifje02]

When I run the following code, it seems ok :

from networkx import from_numpy_matrix, set_node_attributes, relabel_nodes, DiGraph
from numpy import matrix
from vrpy import VehicleRoutingProblem

DISTANCES = [
    [0, 407, 13916, 189591, 190473, 0],
    [0, 0, 13805, 189480, 190361, 407],
    [0, 0, 13805, 189480, 190361, 407],
    [0, 189098, 176331, 0, 1943, 189328],
    [0, 189515, 176749, 1943, 0, 189746],
    [0, 0, 0, 0, 0, 0],
]
DEMANDS = {1: 1, 2: 2, 3: 1, 4: 2}

# Transform distance matrix to DiGraph
A = matrix(DISTANCES, dtype=[("cost", int)])
G = from_numpy_matrix(A, create_using=DiGraph())

# Set demands
set_node_attributes(G, values=DEMANDS, name="demand")

# Relabel depot
G = relabel_nodes(G, {0: "Source", 5: "Sink"})


if __name__ == "__main__":

    print(A)
    prob = VehicleRoutingProblem(G, load_capacity=2)
    prob.solve(pricing_strategy="PrunePaths")
    print(prob.best_value)
    print(prob.best_routes)
    print(prob.best_routes_load)

This is the output :

[[(     0,) (   407,) ( 13916,) (189591,) (190473,) (     0,)]
 [(     0,) (     0,) ( 13805,) (189480,) (190361,) (   407,)]
 [(     0,) (     0,) ( 13805,) (189480,) (190361,) (   407,)]
 [(     0,) (189098,) (176331,) (     0,) (  1943,) (189328,)]
 [(     0,) (189515,) (176749,) (  1943,) (     0,) (189746,)]
 [(     0,) (     0,) (     0,) (     0,) (     0,) (     0,)]]
INFO:vrpy.main:new upper bound : max num stops = 4
INFO:vrpy.main:Initial solution found with value 773638
INFO:vrpy.main:iteration 0, 773638.0
INFO:vrpy.main:iteration 1, 773638.0
INFO:vrpy.main:iteration 2, 773638.0
INFO:vrpy.main:MIP solution
INFO:vrpy.master_solve_pulp:total cost = 773638.0
773638.0
{1: ['Source', 3, 1, 'Sink'], 2: ['Source', 2, 'Sink'], 3: ['Source', 4, 'Sink']}
{1: 2, 2: 2, 3: 2}

@egh312 Please let me know how to change the data (the demands) to have the exact same problem as you.

[egh312]

Apologies, I see my mistake now - i'd given the Sink node a demand

Seems to rightly fail when i increase any demand node above 1

[Kuifje02]

This being said, you have still pointed out something interesting, it might be a good idea to raise an error if the Sink's demand is not 0.
And If you need really a demand at the sink, you can split the Sink into two vertices dummy_node, and Sink with a cost=0 between the two, and the demand at the dummy_node.