I am having an issue with no solution found for an instance of the OR-Tools VRP.
I am new to OR-Tools. After consulting the docs, my understanding if no first solution is found then no solution at all will be found. To help this, I should somehow loosen constraints of finding the first solution. However, I have tried making the vehicle-level distance constraints massive without any luck.
Here is the code I am using
def solve_or_tools_routing(self, data):
"""
Solves an OR tools routing problem. Documentation here: https://developers.google.com/optimization/routing/pickup_delivery
"""
def print_solution(data, manager, routing, solution):
"""HELPER FUNC. Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
print(f"data in print solution {data}")
total_distance = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
distance = routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
route_distance += distance
plan_output += f"{manager.IndexToNode(index)}\n"
plan_output += f"Distance of the route: {route_distance}m\n"
print(plan_output)
total_distance += route_distance
print(f"Total Distance of all routes: {total_distance}m")
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data["distance_matrix"]), data["num_vehicles"], data["depot"])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Define cost of each arc.
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["distance_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Distance constraint.
dimension_name = "Distance"
routing.AddDimension(
transit_callback_index,
1000, # no slack
50000, # max vehicle distance travelled
True, # start cumul to zero
dimension_name,
)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
# Define Transportation Requests.
print(f'PRINTING NUMBER OF PICKUPS/DELIVERIES: {(data["pickups_deliveries"])}')
for request in data["pickups_deliveries"]:
pickup_index = manager.NodeToIndex(request[0])
delivery_index = manager.NodeToIndex(request[1])
routing.AddPickupAndDelivery(pickup_index, delivery_index)
routing.solver().Add(
routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index)
)
routing.solver().Add(
distance_dimension.CumulVar(pickup_index)
<= distance_dimension.CumulVar(delivery_index)
)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION
)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
else:
print(f'no solution found...')```
An example data dict that I can't find a solution for would be:
{'distance_matrix':
[[0, 4877, 243, 2774, 1998, 10539, 8731, 4408, 2324, 2219, 541, 2349, 2371, 2114, 5102, 2258, 2404, 2616, 2703, 9823, 7404, 1784, 3341, 12120, 1614, 2924, 7042], [4635, 0, 4684, 4252, 6362, 10603, 7595, 755, 3153, 3050, 5177, 2812, 3008, 2814, 4454, 2864, 2717, 2536, 2623, 10770, 6615, 4557, 4241, 12184, 3759, 2205, 5961], [252, 4782, 0, 2531, 2250, 10308, 8488, 4168, 2340, 2235, 584, 2255, 2279, 2020, 4859, 2097, 2244, 2385, 2472, 9801, 7161, 2032, 3098, 11889, 1371, 2681, 6799], [2649, 4239, 2397, 0, 4064, 8234, 7752, 3521, 4712, 4607, 2309, 4275, 4577, 3869, 2615, 3762, 3618, 3473, 3560, 7826, 4801, 4314, 857, 9815, 1599, 2034, 6063], [2350, 6602, 2181, 3991, 0, 11036, 10669, 6134, 3960, 3913, 1798, 4075, 4097, 3840, 5970, 3983, 4130, 4342, 4429, 9974, 8066, 2473, 4258, 12617, 3552, 4863, 8980], [10198, 10465, 9945, 8114, 10905, 0, 7581, 10465, 12261, 12155, 9830, 11823, 12126, 11418, 6172, 11400, 11256, 11144, 11231, 2189, 4110, 11835, 7402, 1607, 9399, 9270, 6013], [8735, 7626, 8639, 7751, 10733, 7539, 0, 7750, 10516, 10413, 9012, 10094, 10371, 9690, 6008, 9439, 9293, 9145, 9232, 9407, 5693, 10287, 7739, 7721, 7529, 6599, 1706], [4080, 755, 4129, 3534, 5807, 10603, 7719, 0, 2783, 2680, 4622, 2441, 2637, 2204, 4578, 2163, 2016, 1818, 1906, 10511, 6739, 4002, 3523, 12184, 3041, 1487, 6085], [2215, 3155, 2331, 4857, 3899, 12634, 10487, 2799, 0, 105, 2756, 450, 145, 856, 7185, 1107, 1253, 1401, 1488, 12038, 9487, 1907, 5424, 14215, 3276, 3987, 8853], [2109, 3050, 2226, 4752, 3836, 12529, 10383, 2695, 105, 0, 2651, 345, 251, 750, 7080, 1002, 1148, 1295, 1383, 11933, 9382, 1868, 5319, 14110, 3171, 3881, 8748], [1109, 5361, 937, 2239, 1798, 9997, 9269, 4893, 2808, 2703, 0, 2833, 2856, 2598, 4567, 2742, 2889, 3101, 3188, 9281, 6869, 2004, 2807, 11578, 2154, 3462, 7580], [2111, 2812, 2160, 4409, 3838, 12186, 10067, 2456, 450, 346, 2653, 0, 304, 405, 6737, 657, 803, 950, 1038, 11772, 9039, 2033, 4976, 13767, 2826, 3536, 8433], [2187, 3009, 2236, 4712, 3914, 12489, 10341, 2653, 145, 251, 2729, 304, 0, 710, 7040, 961, 1107, 1255, 1342, 12011, 9342, 2053, 5279, 14070, 3130, 3841, 8707], [1876, 2817, 1925, 4003, 3603, 11780, 9661, 2349, 856, 750, 2418, 405, 710, 0, 6331, 251, 397, 750, 837, 11366, 8633, 1797, 4570, 13361, 2420, 3130, 8027], [5062, 4491, 4809, 2616, 6046, 6280, 6041, 4615, 7124, 7019, 4720, 6687, 6989, 6281, 0, 6264, 6119, 6008, 6095, 6658, 2351, 6725, 1760, 7861, 4148, 3427, 4352], [1969, 2864, 2018, 3752, 3696, 11529, 9410, 2308, 1107, 1002, 2511, 657, 962, 251, 6080, 0, 146, 709, 796, 11115, 8382, 1891, 4319, 13110, 2169, 2879, 7776], [2116, 2717, 2165, 3608, 3843, 11385, 9266, 2161, 1253, 1148, 2657, 803, 1107, 397, 5936, 146, 0, 562, 649, 10971, 8238, 2037, 4175, 12966, 2025, 2735, 7632], [2318, 2535, 2367, 3462, 4045, 11239, 9119, 1818, 1400, 1295, 2859, 950, 1254, 594, 5790, 502, 356, 0, 87, 10825, 8092, 2239, 4029, 12820, 1877, 2588, 7485], [2405, 2623, 2454, 3549, 4132, 11326, 9206, 1905, 1487, 1383, 2947, 1038, 1342, 681, 5877, 589, 443, 87, 0, 10912, 8179, 2327, 4116, 12907, 1964, 2675, 7572], [9966, 10663, 9713, 7944, 10136, 2200, 9406, 10564, 12046, 11940, 9330, 11608, 11911, 11202, 6659, 11185, 11041, 10929, 11016, 0, 4753, 11335, 7485, 2816, 9184, 9369, 7690], [7364, 6716, 7111, 4856, 8091, 4118, 5693, 6840, 9426, 9321, 7017, 8989, 9291, 8583, 2351, 8529, 8384, 8236, 8323, 4744, 0, 9021, 4062, 5699, 6373, 5652, 3977], [1984, 4611, 2227, 4301, 2443, 12059, 10434, 4143, 1936, 1887, 2061, 2084, 2082, 1849, 6629, 1993, 2139, 2351, 2438, 11343, 8931, 0, 4868, 13640, 3183, 3896, 8799], [3301, 4242, 3048, 858, 4287, 7532, 7733, 3524, 5364, 5258, 2960, 4927, 5229, 4521, 1760, 4503, 4359, 4247, 4334, 7292, 4062, 4965, 0, 9113, 2447, 2037, 6044], [11687, 11954, 11434, 9603, 12394, 1488, 7664, 11954, 13750, 13644, 11319, 13312, 13615, 12907, 7661, 12889, 12745, 12633, 12720, 2919, 5599, 13324, 8891, 0, 10888, 10759, 7502], [1437, 3544, 1393, 1600, 3436, 9545, 7502, 2826, 3263, 3158, 1974, 2820, 3125, 2414, 4096, 2163, 2019, 1874, 1961, 9131, 6331, 2987, 2335, 11126, 0, 1339, 5813], [2755, 2205, 2711, 2047, 4754, 9377, 6599, 1487, 3978, 3875, 3235, 3535, 3832, 3131, 3391, 2879, 2734, 2586, 2673, 9185, 5552, 3705, 2036, 10958, 1555, 0, 4965], [7028, 5991, 6932, 6044, 9026, 6015, 1717, 6115, 8882, 8779, 7305, 8460, 8736, 8056, 4302, 7805, 7659, 7511, 7598, 7701, 3987, 8652, 6033, 7596, 5822, 4965, 0]],
'pickups_deliveries': [[0, 1], [2, 1], [3, 4], [5, 4], [0, 6], [7, 6], [0, 8], [5, 8], [0, 9], [7, 9], [10, 11], [0, 11], [0, 12], [3, 12], [2, 13], [14, 13], [0, 13], [10, 13], [5, 15], [3, 15], [0, 16], [7, 16], [10, 16], [3, 17], [0, 17], [3, 18], [14, 18], [10, 18], [0, 19], [0, 20], [3, 20], [5, 21], [10, 21], [0, 22], [2, 22], [5, 23], [14, 23], [0, 24], [7, 24], [10, 25], [0, 25]],
'num_vehicles': 10,
'depot': 26}
Tried setting num vehicles differently. Tried setting distance limit per vehicle much higher. Tried different depots, different distance matrixes. Tried lower amounts of pickups and deliveries.
you cannot have multiple pickups or deliveries on the same node. Only 1 action per node.