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!
the solver is integral. Any floating point distance will be silently converted to int by python
make sure you enable some local search. Otherwise, you will only see the result of the first solution heuristics.