I have a working Vehicle Routing Problem solution implemented using Google's OR-Tools in Python. I have a time matrix of 16 locations, time windows for each location, and penalties for dropping each location. All values are in units of seconds. I am intentionally solving this with just one vehicle (essentially solving a Traveling Salesperson Problem). I am allowing the vehicle to wait at any location for as long as is needed. I have set the drop penalty extremely high for some locations because I do not want them to ever be dropped.
Each location that is represented in the Time Matrix will have a time window, which indicates the time since the beginning of the day (28800 is the equivalent of 8:00am, and 64800 is the equivalent of 6:00pm, etc.) I set the upper bound maximum value as 64800 because there I want the vehicle to be done by 6:00pm.
I have designated the the first location in the matrix as the start location.
Now, I want the second location in the matrix to be the end location.
I have referenced the OR-Tools documentation for this, but have not found success. I have also found a similar question posted on Stack Overflow, but did not find any particularly helpful responses.
Below is my source code - it runs successfully, but does use the second location in the matrix as the end location in the solution it creates.
Source
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
Matrix = [
[0, 0, 550, 743, 790, 606, 810, 684, 1500, 101, 1001, 722, 533, 574, 1126, 713],
[0, 0, 550, 743, 790, 606, 810, 684, 1500, 101, 1001, 722, 533, 574, 1126, 713],
[530, 530, 0, 609, 953, 620, 676, 550, 1544, 598, 875, 443, 489, 737, 1114, 914],
[622, 622, 475, 0, 962, 570, 453, 144, 1695, 585, 1073, 641, 738, 745, 966, 922],
[760, 760, 1014, 1147, 0, 1018, 1208, 1088, 1029, 780, 1375, 1180, 976, 609, 1293, 450],
[629, 629, 621, 716, 989, 0, 715, 706, 1654, 516, 1219, 787, 734, 728, 1247, 650],
[867, 867, 720, 567, 1109, 653, 0, 392, 1330, 830, 1318, 886, 983, 990, 731, 1092],
[671, 671, 524, 213, 1011, 619, 395, 0, 1724, 634, 1122, 690, 788, 795, 867, 971],
[1372, 1372, 1549, 1758, 1030, 1593, 1358, 1731, 0, 1392, 1987, 1714, 1588, 1221, 1443, 1101],
[132, 132, 615, 764, 688, 545, 830, 704, 1398, 0, 990, 787, 547, 472, 1126, 612],
[930, 930, 960, 1198, 1318, 1209, 1265, 1138, 2028, 1031, 0, 526, 866, 1078, 1703, 1272],
[759, 759, 549, 786, 1130, 797, 853, 727, 1721, 718, 556, 0, 579, 914, 1291, 1091],
[437, 437, 541, 836, 887, 764, 902, 776, 1597, 538, 877, 576, 0, 671, 1340, 811],
[621, 621, 880, 1013, 486, 926, 1079, 953, 1196, 640, 1005, 1046, 837, 0, 1259, 441],
[1608, 1608, 1517, 1654, 1547, 1562, 1088, 1480, 1610, 1484, 2115, 1683, 1794, 1556, 0, 1436],
[515, 515, 769, 902, 373, 773, 969, 842, 1078, 534, 1130, 935, 731, 364, 1140, 0]
]
Windows = [[28800, 28800], [64800, 64800], [43200, 43200], [50400, 50400], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200]]
Durations = [0, 0, 1800, 3600, 3600, 7200, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800]
Penalties = [100000, 100000, 576460752303423487, 576460752303423487, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000]
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, 0)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def transit_callback(from_index, to_index):
# Returns the travel time between the two nodes.
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return Matrix[from_node][to_node] + Durations[from_node]
transit_callback_index = routing.RegisterTransitCallback(transit_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Time Windows constraint.
routing.AddDimension(
transit_callback_index,
64800, # An upper bound for slack (the wait times at the locations).
64800, # An upper bound for the total time over each vehicle's route.
False, # Determine whether the cumulative variable is set to zero at the start of the vehicle's route.
'Time')
time_dimension = routing.GetDimensionOrDie('Time')
# Allow to drop nodes.
for node in range(1, len(Matrix)):
routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(Windows):
if location_idx == 0:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
index = routing.Start(0)
time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
# Instantiate route start and end times to produce feasible times.
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(0)))
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(0)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Setting local search metaheuristics:
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 5
search_parameters.log_search = False
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
result = {
'Dropped': None,
'Schedule': None
}
# Display dropped nodes.
dropped = []
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if solution.Value(routing.NextVar(node)) == node:
dropped.append(manager.IndexToNode(node))
result['Dropped'] = dropped
# Return the solution the problem.
schedule = []
time = 0
index = routing.Start(0)
while not routing.IsEnd(index):
time = time_dimension.CumulVar(index)
schedule.append([manager.IndexToNode(index), solution.Min(time),solution.Max(time)])
index = solution.Value(routing.NextVar(index))
time = time_dimension.CumulVar(index)
schedule.append([manager.IndexToNode(index), solution.Min(time),solution.Max(time)])
result['Schedule'] = schedule
print(result)
Output
{'Dropped': [4, 5], 'Schedule': [[0, 28800, 28800], [9, 28901, 29249], [13, 31173, 31521], [15, 33414, 33762], [8, 36292, 36640], [14, 39535, 39883], [2, 43200, 43200], [6, 45676, 46195], [7, 47868, 48387], [3, 50400, 50400], [11, 54641, 57541], [10, 56997, 59897], [12, 59663, 62563], [1, 64800, 64800], [0, 64800, 64800]]}
My understanding is that the main changes need to be made with the RoutingIndexManager.
Like the Google OR-Tools documentation seemed to indicate, I have tried the follow change:
manager = pywrapcp.RoutingIndexManager(len(Matrix),1,0)
to
manager = pywrapcp.RoutingIndexManager(len(Matrix),1,[0],[1])
but this causes an error:
WARNING: Logging before InitGoogleLogging() is written to STDERR
F0820 15:13:16.748222 62401984 routing.cc:1433] Check failed: kUnassigned != indices[i] (-1 vs. -1)
*** Check failure stack trace: ***
Are there any blatant errors in my usage of OR Tools? I'm happy to answer any questions. Any help will be very appreciate! Thank you!
I received an answer for this question in the OR-Tools Google Groups forums.
First, properly change the manager constructor code.
# Create the routing index manager.
[-] manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, 0)
[+] manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, [0], [1])
Second, you cannot specify a start or an end node in a disjunction:
# Allow to drop nodes.
[-] for node in range(1, len(Matrix)):
[+] for node in range(2, len(Matrix)):
routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])
Third, you cannot use NodeToIndex(node_index) on start or end nodes, since it is not always a bijection.
# Add time window constraints for each location except start and end location.
for location_idx, time_window in enumerate(Windows):
[-] if location_idx == 0:
[+] if location_idx == 0 or location_idx == 1:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
Finally, be sure to set a time window on the end location:
index = routing.Start(0)
time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
[+] index = routing.End(0)
[+] time_dimension.CumulVar(index).SetRange(Windows[1][0],Windows[1][1])