pythongraphor-toolsvehicle-routing

No solution found OR-Tools VRP


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. 

Solution

  • you cannot have multiple pickups or deliveries on the same node. Only 1 action per node.