use_all_vehicles not working
ossker opened this issue · 17 comments
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.
That's weird. Have you tried with the cspy=False option?
Please send some code to reproduce this issue
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.
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'] }
Please provide a minimal reproducible example. Your current code is hard to read and does not work as is:
delivery_pointsis undefinedfrom_numpy_matrixis deprecated
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.
Sorry but this is still not reproducible. Anyone must be able to copy paste the code without having to guess anything.
driversis undefineddistancesmust not be in some comment somewhere- you must show exactly which librairies you import (networkx ? vpry ? numpy ?)
- truck has no capacity ?
- truck has no fixed cost ?
Please try copy pasting exactly the code that you share and make sure it works as is.
Some comments:
- you are solving with a heuristic only, which does not guarantee that all vehicles are used.
- you have no vehicle capacity and no fixed cost. This does impact the nature of the optimal solution.
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']}
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.
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']}
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.
What solution do you propose for now? But after all, this is the most basic case..
p = nx.shortest_path(G, "Source", "Sink")yields
networkx.exception.NetworkXNoPath: No path between Source and Sink.
Check the graph
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_routesI 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']}
cspy==1.0.3