pythonor-toolsvehicle-routing

Nonsensical OR-tools VRP solution


I'm new to OR-tools and am trying to solve a basic VRP. I've solved it with other solvers (and so the distance matrix calculation and such are correct), but I'd like to eventually add some custom constraints and such with OR-tools.

Here's the basic VRP code I have. It is taken mostly from the VRP example on the OR-tools site. There are n houses and a single depot. Three vehicles start at this depot, and complete the maximum number of possible houses in under an hour each. Each house takes 90 seconds to service. The distance matrix, houses, depot, etc. are created correctly and all the units are aligned correctly.

# Depot and houses are created correctly
points = [depot] + houses

manager = pywrapcp.RoutingIndexManager(
            len(points), 3, 0
        )

routing = pywrapcp.RoutingModel(manager)

def time_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)

    # Distance matrix is created correctly
    return distance_matrix[from_node][to_node] / WALKING_M_PER_S

    # Create the time callback.
    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Time constraint.
    time_dimension_name = "Time"
    routing.AddDimension(
        transit_callback_index,
        90,  # time at each node
        3600,  # vehicle maximum travel distance
        True,  # start cumul to zero
        time_dimension_name,
    )
    time_dimension = routing.GetDimensionOrDie(time_dimension_name)
    time_dimension.SetGlobalSpanCostCoefficient(100)

    # Allow to drop nodes
    penalty = 1
    for node in range(1, 4):
        routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    # Add verbose logging
    search_parameters.log_search = True

    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print("Objective: {}".format(solution.ObjectiveValue()))
        # Inspect solution.
        routes = []
        for vehicle_id in range(3):
            index = routing.Start(vehicle_id)
            route = []
            while not routing.IsEnd(index):
                node_index = manager.IndexToNode(index)
                route.append(node_index)
                index = solution.Value(routing.NextVar(index))
            routes.append(route)
            print(route)
        return routes
    else:
        print("No solution found.")
        return None

The output is as follows:

WARNING: All log messages before absl::InitializeLog() is called are written to STDERR
I0000 00:00:1699732434.288710   66746 routing.cc:2525] All Unperformed Solution (283, time = 12 ms, memory used = 263.57 MB)
I0000 00:00:1699732434.289000   66746 search.cc:276] Start search (memory used = 263.57 MB)
I0000 00:00:1699732434.289640   66746 search.cc:276] Root node processed (time = 0 ms, constraints = 2585, memory used = 263.57 MB)
I0000 00:00:1699732434.444527   66746 search.cc:276] Solution #0 (0, time = 155 ms, branches = 34, failures = 0, depth = 33, memory used = 273.32 MB)
I0000 00:00:1699732434.444631   66746 search.cc:276] Finished search tree (time = 155 ms, branches = 34, failures = 34, memory used = 273.32 MB)
I0000 00:00:1699732434.444888   66746 search.cc:276] End search (time = 155 ms, branches = 34, failures = 34, memory used = 273.32 MB, speed = 219 branches/s)
Objective: 0
[0]
[0]
[0, 283, 282, 281, 280, 279, 278, 277, 276, 275, 274, 273, 272, 271, 270, 269, 268, 267, 266, 265, 264, 263, 262, 261, 260, 259, 258, 257, 256, 255, 254, 253, 252, 251, 250, 249, 248, 247, 246, 245, 244, 243, 242, 241, 240, 239, 238, 237, 236, 235, 234, 233, 232, 231, 230, 229, 228, 227, 226, 225, 224, 223, 222, 221, 220, 219, 218, 217, 216, 215, 214, 213, 212, 211, 210, 209, 208, 207, 206, 205, 204, 203, 202, 201, 200, 199, 198, 197, 196, 195, 194, 193, 192, 191, 190, 189, 188, 187, 186, 185, 184, 183, 182, 181, 180, 179, 178, 177, 176, 175, 174, 173, 172, 171, 170, 169, 168, 167, 166, 165, 164, 163, 162, 161, 160, 159, 158, 157, 156, 155, 154, 153, 152, 151, 150, 149, 148, 147, 146, 145, 144, 143, 142, 141, 140, 139, 138, 137, 136, 135, 134, 133, 132, 131, 130, 129, 128, 127, 126, 125, 124, 123, 122, 121, 120, 119, 118, 117, 116, 115, 114, 113, 112, 111, 110, 109, 108, 107, 106, 105, 104, 103, 102, 101, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Thanks!


Solution

    1. the solver is integral. Any floating point distance will be silently converted to int by python

    2. make sure you enable some local search. Otherwise, you will only see the result of the first solution heuristics.