Google OR-Tools TSP spanning multiple days with start/stop times

You may have something like that:

python plop.py
Objective: 93780
droped: []
Route for vehicle 0:
0 [21600;21600] -> 38 [21902;57722] -> 33 [23897;59717] -> 34 [25935;61755] -> 28 [28562;64382] -> 41 [31374;67194] -> 39 [33520;69340] -> 40 [35840;71660] -> 36 [38315;74135] -> 37 [40745;76565] -> 5 [44115;79935] -> 25 [46810;82630] -> 20 [49163;84983] -> 21 [51370;790+1day] -> 35 [53471;2891+1day] -> 26 [55707;5127+1day] -> 18 [57768;7188+1day] -> 19 [60001;9421+1day] -> 17 [62278;11698+1day] -> 6 [64588;14008+1day] -> 4 [67569;16989+1day] -> 2 [70020;19440+1day] -> 3 [72377;21797+1day] -> 7 [74828;24248+1day] -> 24 [77187;26607+1day] -> 8 [79509;28929+1day] -> 9 [82281;31701+1day] -> 30 [84660;34080+1day] -> 31 [778+1day;36598+1day] -> 32 [3163+1day;38983+1day] -> 27 [5213+1day;41033+1day] -> 22 [7579+1day;43399+1day] -> 29 [9715+1day;45535+1day] -> 23 [11863+1day;47683+1day] -> 13 [14055+1day;49875+1day] -> 11 [16224+1day;52044+1day] -> 12 [18239+1day;54059+1day] -> 10 [20332+1day;56152+1day] -> 15 [22559+1day;58379+1day] -> 14 [24818+1day;60638+1day] -> 16 [26901+1day;62721+1day] -> 1 [64800+1day;64800+1day]

%diff -u plop.py plop_final.py 
--- plop.py 2020-12-01 17:48:15.187255138 +0100
+++ plop_final.py   2020-12-01 17:47:41.033692899 +0100
@@ -7,6 +7,7 @@
 Penalties = [576460752303423487, 576460752303423487, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000]
 Slack_Max = 86400
 Capacity = 86400
+OneDay = 86400
 
 # The inputs to RoutingIndexManager are:
 #   1. The number of rows of the time matrix, which is the number of locations (including the depot).
@@ -36,7 +37,7 @@
 routing.AddDimension(
     transit_callback_index,
     Slack_Max,  # An upper bound for slack (the wait times at the locations).
-    Capacity,  # An upper bound for the total time over each vehicle's route.
+    2*Capacity,  # 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')
@@ -50,13 +51,14 @@
   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])
+  time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]+OneDay)
+  time_dimension.CumulVar(index).RemoveInterval(time_window[1], time_window[0]+OneDay)
 
 # Add time window constraints for each vehicle start node.
 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])
+time_dimension.CumulVar(index).SetRange(Windows[1][0]+OneDay,Windows[1][1]+OneDay)
 
 # Instantiate route start and end times to produce feasible times.
 routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(0)))
@@ -73,28 +75,24 @@
 
 # Solve the problem.
 solution = routing.SolveWithParameters(search_parameters)
-
-# Print the results
-result = {
-  'Dropped': [],
-  'Scheduled': []
-}
+print(f"Objective: {solution.ObjectiveValue()}")
 
 # Return the dropped locations
+dropped = []
 for node in range(routing.Size()):
   if routing.IsStart(node) or routing.IsEnd(node):
     continue
   if solution.Value(routing.NextVar(node)) == node:
-    result['Dropped'].append(manager.IndexToNode(node))
+    dropped.append(manager.IndexToNode(node))
+print(f"droped: {dropped}")
 
 # Return the scheduled locations
-time = 0
 index = routing.Start(0)
+plan_output = 'Route for vehicle 0:\n'
 while not routing.IsEnd(index):
   time = time_dimension.CumulVar(index)
-  result['Scheduled'].append([manager.IndexToNode(index), solution.Min(time),solution.Max(time)])
+  tw_min = solution.Min(time)
+  if tw_min > OneDay:
+      tw_min = f"{tw_min%OneDay}+1day"
+  tw_max = solution.Max(time)
+  if tw_max > OneDay:
+      tw_max = f"{tw_max%OneDay}+1day"
+
+  plan_output += f'{manager.IndexToNode(index)} [{tw_min};{tw_max}] -> '
   index = solution.Value(routing.NextVar(index))
 time = time_dimension.CumulVar(index)
-result['Scheduled'].append([manager.IndexToNode(index), solution.Min(time),solution.Max(time)])
-
-print(result)
+tw_min = solution.Min(time)
+tw_max = solution.Max(time)
+if tw_min > OneDay:
+    tw_min = f"{tw_min%OneDay}+1day"
+tw_max = solution.Max(time)
+if tw_max > OneDay:
+    tw_max = f"{tw_max%OneDay}+1day"
+plan_output += f'{manager.IndexToNode(index)} [{tw_min};{tw_max}]'
+print(plan_output)

My changes:

• Add const OneDay = 86400

• Change Vehicle horizon to two day i.e. Capacity+OneDay

• You can remove a range of value using RemoveInterval() method.
  ref: https://github.com/google/or-tools/blob/84c35244c9bdd635609af703bbf3053c16c487c0/ortools/constraint_solver/constraint_solver.h#L3980-L3988
  So the idea is SetRange to [FirstTW start; LastTW end] then remove [FirstTW end; LastTW start]

• Then I rewrite the output part (cleaner to me by removing your "unused struct result for this snippet")

ps: If you have question, please join our or-tools discord (link in the README on github) ;)

Step 2

Currently:

• your TW for location is [0;86400] while your vehicle is working from 21600 to 64800.
• Your end TW is [64800, 64800] instead I would use [21600;64800] i.e. finish ASAP instead of dispatching visit until 6pm ?

So let's hack your TW data as follow:

Windows = [[21600, 21600], [21600, 64800], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400]]

Then you'll get the following result:

python plop_final.py
Objective: 93780
droped: []
Route for vehicle 0:
0 [21600;21600] -> 38 [21902;23641] -> 33 [23897;25636] -> 34 [25935;27674] -> 28 [28562;30301] -> 41 [31374;33113] -> 39 [33520;35259] -> 40 [35840;37579] -> 36 [38315;40054] -> 37 [40745;42484] -> 5 [44115;45854] -> 25 [46810;48549] -> 20 [49163;50902] -> 21 [51370;53109] -> 35 [53471;55210] -> 26 [55707;57446] -> 18 [57768;59507] -> 19 [60001;61740] -> 17 [62278;64017] -> 6 [64588;66327] -> 4 [67569;69308] -> 2 [70020;71759] -> 3 [72377;74116] -> 7 [74828;76567] -> 24 [77187;78926] -> 8 [79509;81248] -> 9 [82281;84020] -> 30 [84660;86399] -> 31 [21601+1day;21601+1day] -> 32 [23986+1day;23986+1day] -> 27 [26036+1day;26036+1day] -> 22 [28402+1day;28402+1day] -> 29 [30538+1day;30538+1day] -> 23 [32686+1day;32686+1day] -> 13 [34878+1day;34878+1day] -> 11 [37047+1day;37047+1day] -> 12 [39062+1day;39062+1day] -> 10 [41155+1day;41155+1day] -> 15 [43382+1day;43382+1day] -> 14 [45641+1day;45641+1day] -> 16 [47724+1day;47724+1day] -> 1 [49803+1day;49803+1day]

note: You can find my fork here: https://github.com/Mizux/tsp_multiple_days