search

Kuifje02 / vrpy

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

use_all_vehicles not working #148

Open ossker opened 10 months ago

ossker commented 10 months ago

Solving just with e.g. num_vehicles = 2 and use_all_vehicles = True returns the one right route and empty route with "Source" and "Sink" only.

torressa commented 9 months ago

That's weird. Have you tried with the cspy=False option?

Please send some code to reproduce this issue

ossker commented 8 months ago

distances = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1.2985, 1.2482, 5.2122, 4.9306, 6.2494, 6.2058, 9.004, 9.861, 15.492899999999999, 8.8781, 8.2786, 14.6372, 11.8448, 22.6371, 10.192, 10.421299999999999, 13.4786, 10.412700000000001, 0], [0, 1.2985, 0, 0.1134, 3.9137, 3.6321, 6.6036, 7.5151, 10.8489, 10.5069, 15.0114, 8.3965, 7.7971, 14.155700000000001, 10.546299999999999, 21.3386, 9.7104, 9.9397, 12.180200000000001, 11.7219, 0], [0, 1.2482, 0.1134, 0, 4.1, 3.8184, 6.79, 7.7014, 11.035200000000001, 10.4267, 14.9312, 8.3163, 7.7169, 14.0755, 10.732700000000001, 21.524900000000002, 9.6302, 9.8596, 12.3665, 11.908299999999999, 0], [0, 5.2122, 3.9137, 4.1, 0, 4.2374, 7.030600000000001, 7.942, 11.275799999999998, 13.386299999999999, 18.3352, 9.2698, 11.120899999999999, 12.5063, 7.8361, 18.6283, 10.243799999999998, 13.2635, 12.7854, 12.1489, 0], [0, 4.9306, 3.6321, 3.8184, 4.2374, 0, 4.5556, 8.4625, 11.7964, 13.9069, 18.744, 12.1292, 11.5297, 17.8883, 9.2726, 20.0649, 13.458200000000001, 13.6724, 8.9764, 11.753200000000001, 0], [0, 6.2494, 6.6036, 6.79, 7.030600000000001, 4.5556, 0, 3.8208, 7.3036, 9.414, 17.3826, 13.302299999999999, 10.7219, 19.0625, 13.3766, 24.1688, 14.8401, 14.8466, 7.7801, 7.3006, 0], [0, 6.2058, 7.5151, 7.7014, 7.942, 8.4625, 3.8208, 0, 3.8921, 6.0026, 15.108799999999999, 12.762, 11.103399999999999, 18.5222, 14.6314, 25.4237, 14.925600000000001, 14.3062, 10.5224, 4.6093, 0], [0, 9.004, 10.8489, 11.035200000000001, 11.275799999999998, 11.7964, 7.3036, 3.8921, 0, 3.1823, 13.6768, 15.0603, 13.4018, 20.8206, 18.6539, 31.119400000000002, 18.0915, 16.604599999999998, 15.680200000000001, 6.6335, 0], [0, 9.861, 10.5069, 10.4267, 13.386299999999999, 13.9069, 9.414, 6.0026, 3.1823, 0, 11.7369, 14.872399999999999, 13.213799999999999, 20.6326, 20.1202, 30.9314, 17.2536, 16.4166, 16.147299999999998, 9.1615, 0], [0, 15.492899999999999, 15.0114, 14.9312, 18.3352, 18.744, 17.3826, 15.108799999999999, 13.6768, 11.7369, 0, 12.2313, 8.782, 17.9915, 31.271, 28.2904, 21.7546, 13.7756, 29.0397, 22.056, 0], [0, 8.8781, 8.3965, 8.3163, 9.2698, 12.1292, 13.302299999999999, 12.762, 15.0603, 14.872399999999999, 12.2313, 0, 4.7759, 8.744, 14.556899999999999, 19.042900000000003, 9.302200000000001, 4.525399999999999, 32.4338, 25.4501, 0], [0, 8.2786, 7.7971, 7.7169, 11.120899999999999, 11.5297, 10.7219, 11.103399999999999, 13.4018, 13.213799999999999, 8.782, 4.7759, 0, 10.6784, 16.6447, 20.9773, 14.4415, 6.4625, 30.490599999999997, 23.5069, 0], [0, 14.6372, 14.155700000000001, 14.0755, 12.5063, 17.8883, 19.0625, 18.5222, 20.8206, 20.6326, 17.9915, 8.744, 10.6784, 0, 15.803600000000001, 12.822899999999999, 5.8137, 4.4834, 37.716, 30.7323, 0], [0, 11.8448, 10.546299999999999, 10.732700000000001, 7.8361, 9.2726, 13.3766, 14.6314, 18.6539, 20.1202, 31.271, 14.556899999999999, 16.6447, 15.803600000000001, 0, 11.6985, 10.100299999999999, 18.1687, 16.232200000000002, 18.254, 0], [0, 22.6371, 21.3386, 21.524900000000002, 18.6283, 20.0649, 24.1688, 25.4237, 31.119400000000002, 30.9314, 28.2904, 19.042900000000003, 20.9773, 12.822899999999999, 11.6985, 0, 9.318200000000001, 15.7501, 26.9857, 29.0165, 0], [0, 10.192, 9.7104, 9.6302, 10.243799999999998, 13.458200000000001, 14.8401, 14.925600000000001, 18.0915, 17.2536, 21.7546, 9.302200000000001, 14.4415, 5.8137, 10.100299999999999, 9.318200000000001, 0, 5.5317, 25.2895, 19.028, 0], [0, 10.421299999999999, 9.9397, 9.8596, 13.2635, 13.6724, 14.8466, 14.3062, 16.604599999999998, 16.4166, 13.7756, 4.525399999999999, 6.4625, 4.4834, 18.1687, 15.7501, 5.5317, 0, 33.7303, 26.746599999999997, 0], [0, 13.4786, 12.180200000000001, 12.3665, 12.7854, 8.9764, 7.7801, 10.5224, 15.680200000000001, 16.147299999999998, 29.0397, 32.4338, 30.490599999999997, 37.716, 16.232200000000002, 26.9857, 25.2895, 33.7303, 0, 9.594, 0], [0, 10.412700000000001, 11.7219, 11.908299999999999, 12.1489, 11.753200000000001, 7.3006, 4.6093, 6.6335, 9.1615, 22.056, 25.4501, 23.5069, 30.7323, 18.254, 29.0165, 19.028, 26.746599999999997, 9.594, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] A = array(distances, dtype=[("cost", int)]) G = from_numpy_matrix(A, create_using=DiGraph()) G = relabel_nodes(G, {0: "Source", len(delivery_points) - 1: "Sink"}) prob = VehicleRoutingProblem(G)

Having prob.num_vehicles = 3 and prob.use_all_vehicles = True, it returns 4 routes.

Ervez commented 8 months ago

for prob.solve i tried cspy=False as you suggested and result was also 4 best_routes for 3 vehicles/drivers

{ 0: ['Source', 5, 3, 1, 2, 4, 14, 'Sink'], 1: ['Source', 11, 12, 10, 'Sink'], 2: ['Source', 18, 6, 7, 8, 9, 19, 'Sink'], 3: ['Source', 15, 16, 13, 17, 'Sink'] }

Kuifje02 commented 8 months ago

Please provide a minimal reproducible example. Your current code is hard to read and does not work as is:

Ervez commented 8 months ago

Thanks for response. In your documentation, from_numpy_matrix appears as an example of a conversion to DiGraph. That's why we used it in our code.

delivery_points is passed to the method in which the code we described is located - that's why we didn't mention it because it's obvious

len(delivery_points) = 19

A = array(distances, dtype=[("cost", int)])
  G = from_numpy_matrix(A, create_using=DiGraph())
  G = relabel_nodes(G, {0: "Source", len(delivery_points) - 1: "Sink"})
  prob = VehicleRoutingProblem(G)
  prob.num_vehicles = len(drivers)

  if use_all_vehicles:
      prob.use_all_vehicles = True
  try:
      prob.solve(time_limit=60, heuristic_only=use_heuristic_only)
  except Exception:
      raise Http404("An unsolvable problem.")

distances are in the comments here

For distances and the code we described, prob is not using the right number of drivers/vehicles. It seems to do it in some way 'randomly' , and the result is giving best_routes = 4 for 3 drivers.

If you need more code or anything let me know.

Kuifje02 commented 8 months ago

Sorry but this is still not reproducible. Anyone must be able to copy paste the code without having to guess anything.

Please try copy pasting exactly the code that you share and make sure it works as is.

Kuifje02 commented 8 months ago

Some comments:

Ervez commented 8 months ago 
from vrpy import VehicleRoutingProblem
from networkx import DiGraph, from_numpy_matrix, relabel_nodes
from numpy import array

use_all_vehicles = True
use_heuristic_only = True
delivery_points = 21
drivers = 3

distances = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1.2985, 1.2482, 5.2122, 4.9306, 6.2494, 6.2058, 9.004, 9.861, 15.492899999999999, 8.8781, 8.2786, 14.6372, 11.8448, 22.6371, 10.192, 10.421299999999999, 13.4786, 10.412700000000001, 0], [0, 1.2985, 0, 0.1134, 3.9137, 3.6321, 6.6036, 7.5151, 10.8489, 10.5069, 15.0114, 8.3965, 7.7971, 14.155700000000001, 10.546299999999999, 21.3386, 9.7104, 9.9397, 12.180200000000001, 11.7219, 0], [0, 1.2482, 0.1134, 0, 4.1, 3.8184, 6.79, 7.7014, 11.035200000000001, 10.4267, 14.9312, 8.3163, 7.7169, 14.0755, 10.732700000000001, 21.524900000000002, 9.6302, 9.8596, 12.3665, 11.908299999999999, 0], [0, 5.2122, 3.9137, 4.1, 0, 4.2374, 7.030600000000001, 7.942, 11.275799999999998, 13.386299999999999, 18.3352, 9.2698, 11.120899999999999, 12.5063, 7.8361, 18.6283, 10.243799999999998, 13.2635, 12.7854, 12.1489, 0], [0, 4.9306, 3.6321, 3.8184, 4.2374, 0, 4.5556, 8.4625, 11.7964, 13.9069, 18.744, 12.1292, 11.5297, 17.8883, 9.2726, 20.0649, 13.458200000000001, 13.6724, 8.9764, 11.753200000000001, 0], [0, 6.2494, 6.6036, 6.79, 7.030600000000001, 4.5556, 0, 3.8208, 7.3036, 9.414, 17.3826, 13.302299999999999, 10.7219, 19.0625, 13.3766, 24.1688, 14.8401, 14.8466, 7.7801, 7.3006, 0], [0, 6.2058, 7.5151, 7.7014, 7.942, 8.4625, 3.8208, 0, 3.8921, 6.0026, 15.108799999999999, 12.762, 11.103399999999999, 18.5222, 14.6314, 25.4237, 14.925600000000001, 14.3062, 10.5224, 4.6093, 0], [0, 9.004, 10.8489, 11.035200000000001, 11.275799999999998, 11.7964, 7.3036, 3.8921, 0, 3.1823, 13.6768, 15.0603, 13.4018, 20.8206, 18.6539, 31.119400000000002, 18.0915, 16.604599999999998, 15.680200000000001, 6.6335, 0], [0, 9.861, 10.5069, 10.4267, 13.386299999999999, 13.9069, 9.414, 6.0026, 3.1823, 0, 11.7369, 14.872399999999999, 13.213799999999999, 20.6326, 20.1202, 30.9314, 17.2536, 16.4166, 16.147299999999998, 9.1615, 0], [0, 15.492899999999999, 15.0114, 14.9312, 18.3352, 18.744, 17.3826, 15.108799999999999, 13.6768, 11.7369, 0, 12.2313, 8.782, 17.9915, 31.271, 28.2904, 21.7546, 13.7756, 29.0397, 22.056, 0], [0, 8.8781, 8.3965, 8.3163, 9.2698, 12.1292, 13.302299999999999, 12.762, 15.0603, 14.872399999999999, 12.2313, 0, 4.7759, 8.744, 14.556899999999999, 19.042900000000003, 9.302200000000001, 4.525399999999999, 32.4338, 25.4501, 0], [0, 8.2786, 7.7971, 7.7169, 11.120899999999999, 11.5297, 10.7219, 11.103399999999999, 13.4018, 13.213799999999999, 8.782, 4.7759, 0, 10.6784, 16.6447, 20.9773, 14.4415, 6.4625, 30.490599999999997, 23.5069, 0], [0, 14.6372, 14.155700000000001, 14.0755, 12.5063, 17.8883, 19.0625, 18.5222, 20.8206, 20.6326, 17.9915, 8.744, 10.6784, 0, 15.803600000000001, 12.822899999999999, 5.8137, 4.4834, 37.716, 30.7323, 0], [0, 11.8448, 10.546299999999999, 10.732700000000001, 7.8361, 9.2726, 13.3766, 14.6314, 18.6539, 20.1202, 31.271, 14.556899999999999, 16.6447, 15.803600000000001, 0, 11.6985, 10.100299999999999, 18.1687, 16.232200000000002, 18.254, 0], [0, 22.6371, 21.3386, 21.524900000000002, 18.6283, 20.0649, 24.1688, 25.4237, 31.119400000000002, 30.9314, 28.2904, 19.042900000000003, 20.9773, 12.822899999999999, 11.6985, 0, 9.318200000000001, 15.7501, 26.9857, 29.0165, 0], [0, 10.192, 9.7104, 9.6302, 10.243799999999998, 13.458200000000001, 14.8401, 14.925600000000001, 18.0915, 17.2536, 21.7546, 9.302200000000001, 14.4415, 5.8137, 10.100299999999999, 9.318200000000001, 0, 5.5317, 25.2895, 19.028, 0], [0, 10.421299999999999, 9.9397, 9.8596, 13.2635, 13.6724, 14.8466, 14.3062, 16.604599999999998, 16.4166, 13.7756, 4.525399999999999, 6.4625, 4.4834, 18.1687, 15.7501, 5.5317, 0, 33.7303, 26.746599999999997, 0], [0, 13.4786, 12.180200000000001, 12.3665, 12.7854, 8.9764, 7.7801, 10.5224, 15.680200000000001, 16.147299999999998, 29.0397, 32.4338, 30.490599999999997, 37.716, 16.232200000000002, 26.9857, 25.2895, 33.7303, 0, 9.594, 0], [0, 10.412700000000001, 11.7219, 11.908299999999999, 12.1489, 11.753200000000001, 7.3006, 4.6093, 6.6335, 9.1615, 22.056, 25.4501, 23.5069, 30.7323, 18.254, 29.0165, 19.028, 26.746599999999997, 9.594, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

A = array(distances, dtype=[("cost", int)])
G = from_numpy_matrix(A, create_using=DiGraph())
G = relabel_nodes(G, {0: "Source", delivery_points - 1: "Sink"})
prob = VehicleRoutingProblem(G)
prob.num_vehicles = drivers

if use_all_vehicles:
    prob.use_all_vehicles = True

prob.solve(time_limit=60, heuristic_only=use_heuristic_only)

best_routes: dict = prob.best_routes

print('len(drivers)')
print(prob.num_vehicles)
print('----------')
print('best_routes')
print(best_routes)

result:

len(drivers)
[3]
----------
best_routes
{0: ['Source', 18, 6, 7, 8, 9, 19, 'Sink'], 1: ['Source', 11, 12, 10, 'Sink'], 2: ['Source', 5, 3, 1, 2, 4, 14, 'Sink'], 3: ['Source', 15, 16, 13, 17, 'Sink']}
Kuifje02 commented 8 months ago

Ok, this looks good :) Now we can start working. As I mentioned above, I believe the issue is that you are computing a solution only with a heuristic, which does not includ the use_all_vehicles feature. This, indeed, should be more clear in the docs.

Ervez commented 8 months ago

result for: prob.solve(time_limit=60) [without heuristic_only = TRUE]

len(drivers)
[3]
----------
best_routes
{1: ['Source', 1, 2, 4, 3, 5, 6, 7, 8, 9, 19, 18, 14, 16, 13, 17, 11, 12, 10, 15, 'Sink'], 2: ['Source', 'Sink'], 3: ['Source', 'Sink']}
Kuifje02 commented 8 months ago

I guess the solver is unable to find a better solution than that. This looks like an issue that needs some work, we need to force the solver to forbid empty routes 2 and 3.

ossker commented 8 months ago

What solution do you propose for now? But after all, this is the most basic case..

torressa commented 8 months ago

This is probably similar to #147

torressa commented 8 months ago 
p = nx.shortest_path(G, "Source", "Sink")

yields

networkx.exception.NetworkXNoPath: No path between Source and Sink.

Check the graph

ossker commented 8 months ago

The code example from your documentation (copy & paste) does return exactly the same wrong solution: {1: ['Source', 'Sink'], 2: ['Source', 'Sink'], 3: ['Source', 5, 8, 6, 2, 10, 16, 14, 9, 'Sink'], 4: ['Source', 7, 1, 4, 3, 15, 11, 12, 13, 'Sink']}

Code:

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

DISTANCES = [
    [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662, 0],  # from Source
    [0, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210, 548],
    [0, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754, 776],
    [0, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358, 696],
    [0, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244, 582],
    [0, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708, 274],
    [0, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480, 502],
    [0, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856, 194],
    [0, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514, 308],
    [0, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468, 194],
    [0, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354, 536],
    [0, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844, 502],
    [0, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730, 388],
    [0, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536, 354],
    [0, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194, 468],
    [0, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798, 776],
    [0, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0, 662],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # from Sink
]

DEMAND = {1: 1, 2: 1, 3: 2, 4: 4, 5: 2, 6: 4, 7: 8, 8: 8, 9: 1, 10: 2, 11: 1, 12: 2, 13: 4, 14: 4, 15: 8, 16: 8}

A = array(DISTANCES, dtype=[("cost", int)])
G = from_numpy_matrix(A, create_using=DiGraph())

set_node_attributes(G, values=DEMAND, name="demand")

G = relabel_nodes(G, {0: "Source", 17: "Sink"})
prob = VehicleRoutingProblem(G, num_vehicles=4, use_all_vehicles=True)

prob.solve(time_limit=60)

best_routes: dict = prob.best_routes
torressa commented 8 months ago

I cannot replicate this. What version of cspy have you got? I'm getting:

# cspy=False
INFO:vrpy.vrp:time up !
INFO:vrpy.master_solve_pulp:total cost = 6004.0
{1: ['Source', 9, 10, 2, 6, 8, 'Sink'], 2: ['Source', 12, 11, 15, 3, 4, 1, 7, 'Sink'], 3: ['Source', 14, 16, 13, 'Sink'], 4: ['Source', 5, 'Sink']}
# cspy=True
INFO:vrpy.master_solve_pulp:total cost = 5480.0
{1: ['Source', 5, 'Sink'], 2: ['Source', 7, 'Sink'], 3: ['Source', 1, 4, 3, 15, 11, 12, 13, 'Sink'], 4: ['Source', 8, 6, 2, 10, 16, 14, 9, 'Sink']}
ossker commented 8 months ago

cspy==1.0.3