Closed ErikUGent closed 1 year ago
torressa
commented
1 year ago Please revise your time windows, as suggested in the other issue. For instance, the node 1 is unreachable as the travel time from the source is 673 but the time window is [200, 400].
We should probably have an error message indicating this.
EDIT: hang on minute, I think this is indeed a bug.
torressa
commented
1 year ago Nope, please double-check the time windows, if you set drop_penalty=1e6 in the VehicleRoutingProblem construction (I had to force this to work so you will probably not be able to see this), the solution is to drop nodes [1, 2, 4, 16, 22].
Maybe try to make every node reachable from the source (in terms of time windows).
ErikUGent
commented
1 year ago Dear,
Many thanks for your replies. However, I am using the same time windows for the larger examples, being with 32 and 40 nodes and there it works perfectly. :-(
Thanks for having a look.
Regards, Erik
ErikUGent
commented
1 year ago Dear,
Please have a look at it again. I have created a new error on https://github.com/Kuifje02/vrpy/issues/144#issue-1570605674
I have written on it what might be the issue, but I can't see why It doesn't work. I still believe this is a bug, since alle the other examples work fine and with the OR tool solution I get a correct answer.
Thanks! Erik
torressa
commented
1 year ago Could you post the code and the solution you are getting with OR-Tools?
ErikUGent
commented
1 year ago Dear,
This is the solution:
_Objective: 1928
Route for vehicle 0:
0 Time(0,0) -> 4 Time(44,60) -> 11 Time(676,692) -> 12 Time(679,695) -> 13 Time(682,698) -> 24 Time(700,700) -> 0 Time(1373,1373)
Time of the route: 1373min
Route for vehicle 1:
0 Time(0,0) -> 16 Time(223,297) -> 22 Time(226,300) -> 23 Time(650,693) -> 17 Time(653,696) -> 18 Time(654,697) -> 20 Time(657,700) -> 19 Time(800,889) -> 21 Time(807,896) -> 14 Time(809,898) -> 15 Time(900,900) -> 0 Time(1124,1124)
Time of the route: 1124min
Route for vehicle 2:
0 Time(0,0) -> 1 Time(200,400) -> 2 Time(400,600) -> 3 Time(600,897) -> 10 Time(700,899) -> 9 Time(900,900) -> 5 Time(905,905) -> 6 Time(906,906) -> 8 Time(907,907) -> 7 Time(907,907) -> 0 Time(950,950)
Time of the route: 950min
Total time of all routes: 3447min
the elapsed time:0.0509_Hereby the code:
"""Vehicles Routing Problem (VRP) with Time Windows."""
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import time
start_time = time.time()
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['time_matrix'] = [
[ 0, 45, 45, 45, 44, 44, 44, 43, 43, 46, 46, 676, 675, 674, 224, 224, 223, 224, 226, 227, 229, 225, 225, 227, 673],
[ 45, 0, 1, 1, 2, 3, 4, 4, 4, 2, 1, 631, 630, 629, 198, 198, 197, 198, 199, 201, 202, 200, 199, 201, 629],
[ 45, 1, 0, 1, 1, 2, 3, 3, 4, 3, 2, 632, 631, 630, 199, 198, 197, 199, 200, 202, 203, 201, 200, 201, 629],
[ 45, 1, 1, 0, 1, 1, 2, 3, 3, 3, 2, 632, 631, 630, 200, 199, 198, 200, 201, 202, 204, 201, 201, 202, 630],
[ 44, 2, 1, 1, 0, 1, 2, 2, 2, 4, 3, 632, 632, 631, 200, 200, 199, 200, 201, 203, 204, 202, 201, 203, 630],
[ 44, 3, 2, 1, 1, 0, 1, 1, 2, 5, 4, 633, 632, 631, 201, 200, 199, 201, 202, 204, 205, 203, 202, 203, 630],
[ 44, 4, 3, 2, 2, 1, 0, 1, 1, 6, 5, 633, 632, 632, 202, 201, 200, 202, 203, 205, 206, 204, 203, 204, 631],
[ 43, 4, 3, 3, 2, 1, 1, 0, 0, 6, 5, 634, 633, 632, 203, 202, 201, 202, 203, 205, 207, 204, 204, 205, 632],
[ 43, 4, 4, 3, 2, 2, 1, 0, 0, 6, 6, 634, 633, 633, 203, 202, 201, 203, 204, 205, 207, 204, 204, 205, 632],
[ 46, 2, 3, 3, 4, 5, 6, 6, 6, 0, 1, 630, 629, 628, 196, 196, 195, 196, 197, 199, 200, 198, 197, 199, 627],
[ 46, 1, 2, 2, 3, 4, 5, 5, 6, 1, 0, 631, 630, 629, 197, 197, 196, 197, 198, 200, 201, 199, 198, 200, 628],
[676, 631, 632, 632, 632, 633, 633, 634, 634, 630, 631, 0, 3, 6, 526, 524, 523, 522, 521, 520, 519, 527, 523, 522, 9],
[675, 630, 631, 631, 632, 632, 632, 633, 633, 629, 630, 3, 0, 3, 524, 522, 521, 520, 519, 518, 517, 525, 522, 521, 5],
[674, 629, 630, 630, 631, 631, 632, 632, 633, 628, 629, 6, 3, 0, 522, 521, 520, 519, 518, 517, 515, 523, 520, 519, 2],
[224, 198, 199, 200, 200, 201, 202, 203, 203, 196, 197, 526, 524, 522, 0, 2, 4, 4, 5, 6, 7, 2, 2, 4, 521],
[224, 198, 198, 199, 200, 200, 201, 202, 202, 196, 197, 524, 522, 521, 2, 0, 2, 2, 3, 5, 6, 4, 2, 3, 520],
[223, 197, 197, 198, 199, 199, 200, 201, 201, 195, 196, 523, 521, 520, 4, 2, 0, 2, 3, 4, 6, 6, 3, 4, 518],
[224, 198, 199, 200, 200, 201, 202, 202, 203, 196, 197, 522, 520, 519, 4, 2, 2, 0, 1, 3, 5, 6, 3, 3, 517],
[226, 199, 200, 201, 201, 202, 203, 203, 204, 197, 198, 521, 519, 518, 5, 3, 3, 1, 0, 2, 3, 6, 3, 2, 516],
[227, 201, 202, 202, 203, 204, 205, 205, 205, 199, 200, 520, 518, 517, 6, 5, 4, 3, 2, 0, 2, 7, 4, 3, 515],
[229, 202, 203, 204, 204, 205, 206, 207, 207, 200, 201, 519, 517, 515, 7, 6, 6, 5, 3, 2, 0, 8, 5, 4, 514],
[225, 200, 201, 201, 202, 203, 204, 204, 204, 198, 199, 527, 525, 523, 2, 4, 6, 6, 6, 7, 8, 0, 4, 5, 522],
[225, 199, 200, 201, 201, 202, 203, 204, 204, 197, 198, 523, 522, 520, 2, 2, 3, 3, 3, 4, 5, 4, 0, 1, 519],
[227, 201, 201, 202, 203, 203, 204, 205, 205, 199, 200, 522, 521, 519, 4, 3, 4, 3, 2, 3, 4, 5, 1, 0, 518],
[673, 629, 629, 630, 630, 630, 631, 632, 632, 627, 628, 9, 5, 2, 521, 520, 518, 517, 516, 515, 514, 522, 519, 518, 0],
]
data['time_windows'] = [
(0, 1000), # depot
(200, 400), # 1
(400, 600), # 2
(600, 900), # 3
(0, 500), # 4
(680, 1200), # 5
(900, 1000), # 6
(900, 1200), # 7
(780, 1400), # 8
(900, 1000), # 9
(700, 1000), # 10
(0, 1000), # 11
(200, 1500), # 12
(0, 800), # 13
(600, 900), # 14
(900, 1200), # 15
(200, 350), # 16
(0, 900), # 17
(0, 1000), # 18
(800, 1000), # 19
(600, 700), # 20
(500, 900), # 21
(200, 300), # 22
(650, 800), # 23
(700, 1000), # 24
]
data['num_vehicles'] = 5
data['depot'] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
time_dimension = routing.GetDimensionOrDie('Time')
total_time = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += '{0} Time({1},{2}) -> '.format(
manager.IndexToNode(index), solution.Min(time_var),
solution.Max(time_var))
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index),
solution.Min(time_var),
solution.Max(time_var))
plan_output += 'Time of the route: {}min\n'.format(
solution.Min(time_var))
print(plan_output)
total_time += solution.Min(time_var)
print('Total time of all routes: {}min'.format(total_time))
def main():
"""Solve the VRP with time windows."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def time_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 data['time_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Time Windows constraint.
time = 'Time'
routing.AddDimension(
transit_callback_index,
9999, # allow waiting time at the customer
9999, # maximum time per vehicle --- > When you want less vehicles
False, # Don't force start cumul to zero.
time)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data['time_windows']):
if location_idx == data['depot']:
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.
depot_idx = data['depot']
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data['time_windows'][depot_idx][0],
data['time_windows'][depot_idx][1])
# Instantiate route start and end times to produce feasible times.
for i in range(data['num_vehicles']):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i)))
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
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_solution(data, manager, routing, solution)
if __name__ == '__main__':
main()
print('the elapsed time:%s'% (round(time.time() - start_time, 4)))`I still think this is an issue with your data, you need a source and a sink node. The source will have the same row as the matrix in your snippet above (the depot) plus a 0 at the end, the sink should have all zeros. You can find an example in our docs: https://vrpy.readthedocs.io/en/latest/examples.html#vrp-with-time-windows
The distance/cost matrix will have an entry in the first position with the value 0 and an entry in the last position with the value that is currently in the first position. In your case, you seem to have moved the last row to the beginning (as well as doing the above).
If I make these changes to obtain the following matrix we seem to converge to the correct solution but this now takes a long time.
[
[0, 45, 45, 45, 44, 44, 44, 43, 43, 46, 46, 676, 675, 674, 224, 224, 223, 224, 226, 227, 229, 225, 225, 227, 673, 0]
[0, 0, 1, 1, 2, 3, 4, 4, 4, 2, 1, 631, 630, 629, 198, 198, 197, 198, 199, 201, 202, 200, 199, 201, 629, 45]
[0, 1, 0, 1, 1, 2, 3, 3, 4, 3, 2, 632, 631, 630, 199, 198, 197, 199, 200, 202, 203, 201, 200, 201, 629, 45]
[0, 1, 1, 0, 1, 1, 2, 3, 3, 3, 2, 632, 631, 630, 200, 199, 198, 200, 201, 202, 204, 201, 201, 202, 630, 45]
[0, 2, 1, 1, 0, 1, 2, 2, 2, 4, 3, 632, 632, 631, 200, 200, 199, 200, 201, 203, 204, 202, 201, 203, 630, 44]
[0, 3, 2, 1, 1, 0, 1, 1, 2, 5, 4, 633, 632, 631, 201, 200, 199, 201, 202, 204, 205, 203, 202, 203, 630, 44]
[0, 4, 3, 2, 2, 1, 0, 1, 1, 6, 5, 633, 632, 632, 202, 201, 200, 202, 203, 205, 206, 204, 203, 204, 631, 44]
[0, 4, 3, 3, 2, 1, 1, 0, 0, 6, 5, 634, 633, 632, 203, 202, 201, 202, 203, 205, 207, 204, 204, 205, 632, 43]
[0, 4, 4, 3, 2, 2, 1, 0, 0, 6, 6, 634, 633, 633, 203, 202, 201, 203, 204, 205, 207, 204, 204, 205, 632, 43]
[0, 2, 3, 3, 4, 5, 6, 6, 6, 0, 1, 630, 629, 628, 196, 196, 195, 196, 197, 199, 200, 198, 197, 199, 627, 46]
[0, 1, 2, 2, 3, 4, 5, 5, 6, 1, 0, 631, 630, 629, 197, 197, 196, 197, 198, 200, 201, 199, 198, 200, 628, 46]
[0, 631, 632, 632, 632, 633, 633, 634, 634, 630, 631, 0, 3, 6, 526, 524, 523, 522, 521, 520, 519, 527, 523, 522, 9, 676]
[0, 630, 631, 631, 632, 632, 632, 633, 633, 629, 630, 3, 0, 3, 524, 522, 521, 520, 519, 518, 517, 525, 522, 521, 5, 675]
[0, 629, 630, 630, 631, 631, 632, 632, 633, 628, 629, 6, 3, 0, 522, 521, 520, 519, 518, 517, 515, 523, 520, 519, 2, 674]
[0, 198, 199, 200, 200, 201, 202, 203, 203, 196, 197, 526, 524, 522, 0, 2, 4, 4, 5, 6, 7, 2, 2, 4, 521, 224]
[0, 198, 198, 199, 200, 200, 201, 202, 202, 196, 197, 524, 522, 521, 2, 0, 2, 2, 3, 5, 6, 4, 2, 3, 520, 224]
[0, 197, 197, 198, 199, 199, 200, 201, 201, 195, 196, 523, 521, 520, 4, 2, 0, 2, 3, 4, 6, 6, 3, 4, 518, 223]
[0, 198, 199, 200, 200, 201, 202, 202, 203, 196, 197, 522, 520, 519, 4, 2, 2, 0, 1, 3, 5, 6, 3, 3, 517, 224]
[0, 199, 200, 201, 201, 202, 203, 203, 204, 197, 198, 521, 519, 518, 5, 3, 3, 1, 0, 2, 3, 6, 3, 2, 516, 226]
[0, 201, 202, 202, 203, 204, 205, 205, 205, 199, 200, 520, 518, 517, 6, 5, 4, 3, 2, 0, 2, 7, 4, 3, 515, 227]
[0, 202, 203, 204, 204, 205, 206, 207, 207, 200, 201, 519, 517, 515, 7, 6, 6, 5, 3, 2, 0, 8, 5, 4, 514, 229]
[0, 200, 201, 201, 202, 203, 204, 204, 204, 198, 199, 527, 525, 523, 2, 4, 6, 6, 6, 7, 8, 0, 4, 5, 522, 225]
[0, 199, 200, 201, 201, 202, 203, 204, 204, 197, 198, 523, 522, 520, 2, 2, 3, 3, 3, 4, 5, 4, 0, 1, 519, 225]
[0, 201, 201, 202, 203, 203, 204, 205, 205, 199, 200, 522, 521, 519, 4, 3, 4, 3, 2, 3, 4, 5, 1, 0, 518, 227]
[0, 629, 629, 630, 630, 630, 631, 632, 632, 627, 628, 9, 5, 2, 521, 520, 518, 517, 516, 515, 514, 522, 519, 518, 0, 673]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
Archief.zip Dear,
I have added two files to solve the vehicle routing problem with time windows. The one with 16 hubs leads to a correct solution, the second one with 24 hubs gives a Key Error. I have been staring myself blind on the issue, but cannot see why it doesn't work. Thanks and kind regards, Erik