TSP Spanning multiple days with start/end locations

[joshkautz]

GitHub: https://github.com/joshykautz/tsp_multiple_days/blob/feature/morning_nodes/tsp_multiple_days.py
Stack Overflow: https://stackoverflow.com/questions/65028943/google-or-tools-tsp-spanning-multiple-days-with-start-stop-times

I have a routing problem for one vehicle. I specify the starting and ending location for the vehicle (they are different locations) as well as the time window from which the vehicle must leave the starting location and the time window by which the vehicle must arrive at the ending location. I have a fairly large number of locations that I want the vehicle to try visiting in between these start and end locations during the day. There are 40 locations, but I don't expect the vehicle to be able to visit all of them, so I have allowed the locations to be droppable. Each of these locations have their own time windows to indicate availability as well.

I am trying to allow for the scheduling of locations that this vehicle visits to occur over the span of multiple days. The caveat being that the vehicle will not necessarily be starting and ending the day at the same location each day - I intend to represent the start and ending locations for each day in the matrix with the following pattern:

Number of days: 2

NUM_DAYS = 2

Matrix = [[start day 1], [end day 1], [start day 2], [end day 2], [location], [location], ... ]

# Day 1 - Start at 8:00am at "start day 1" location
# Day 1 - End at 4:00pm at "end day 1" location
# Day 2 - Start at 6:00am at "start day 2" location
# Day 2 - End at 6:00pm at "end day 2" location
Windows = [[28800, 28800], [57600, 57600], [21600, 21600], [64800, 64800], [0, 86400], [0, 86400], [0, 86400], ... ]

Number of days: 3

NUM_DAYS = 3

Matrix = [[start day 1], [end day 1], [start day 2], [end day 2], [start day 3], [end day 3], [location], [location], ... ]

# Day 1 - Start at 8:00am at "start day 1" location
# Day 1 - End at 4:00pm at "end day 1" location
# Day 2 - Start at 6:00am at "start day 2" location
# Day 2 - End at 6:00pm at "end day 2" location
# Day 3 - Start at 10:00am at "start day 3" location
# Day 3 - End at 2:00pm at "end day 3" location
Windows = [[28800, 28800], [57600, 57600], [21600, 21600], [64800, 64800], [36000, 36000], [50400, 50400], [0, 86400], [0, 86400], [0, 86400], ... ]

When I try to solve the routing problem using two days, I am able to receive a solution, but my constraints are not being followed the way that I intended them to be. For instance, the first day uses the ending location of the second day instead of the ending location of the first day; I want to ensure that each day starts and ends at its specified locations. Also, locations appear to be visited past the time window that I am using to enforce the ending location.

Output:

solution found.  Objective value is  22468
Dropped
[]
Scheduled
[0, 28800, 28800]
[28, 29216, 35021]
[20, 31277, 37082]
[21, 33510, 39315]
[19, 35787, 41592]
[8, 37197, 43002]
[6, 39278, 45083]
[4, 40829, 46634]
[5, 41386, 47191]
[9, 42037, 47842]
[26, 43496, 49301]
[10, 45818, 51623]
[11, 47690, 53495]
[32, 49169, 54974]
[31, 51530, 57335]
[24, 53621, 59426]
[25, 55790, 61595]
[15, 57982, 63787]
[13, 59251, 65056]
[14, 60366, 66171]
[12, 61559, 67364]
[17, 62886, 68691]
[16, 64245, 70050]
[18, 65428, 71233]
[3, 66607, 72412]
[2, 2334, 8139]
[35, 2530, 8335]
[36, 4568, 10373]
[40, 6609, 12414]
[37, 10906, 16711]
[23, 13016, 18821]
[22, 15163, 20968]
[27, 17473, 23278]
[7, 20179, 25984]
[39, 22710, 28515]
[38, 27042, 32847]
[42, 29446, 35251]
[41, 33593, 39398]
[43, 37551, 43356]
[30, 42217, 48022]
[34, 44789, 50594]
[29, 46839, 52644]
[33, 49177, 54982]
[1, 57600, 57600]

This has been giving me a heck of a time. Another set of eyes or any suggestions or help would be enormously appreciated. Hopefully I provided enough context here - if not, I'd be happy to clarify anything I may have omitted!

GitHub: https://github.com/joshykautz/tsp_multiple_days/blob/feature/morning_nodes/tsp_multiple_days.py
Stack Overflow: https://stackoverflow.com/questions/65028943/google-or-tools-tsp-spanning-multiple-days-with-start-stop-times

[joshkautz]

I am hoping for an output that looks something like:

Dropped
[24,25,15,13,14,12,17,16,35,36,40,37,23]
Scheduled
**[0, 28800, 28800]**
[28, 28906, 35021]
[20, 31277, 37082]
[21, 33510, 39315]
[19, 35787, 41592]
[8, 37197, 43002]
[6, 39278, 45083]
[4, 40829, 46634]
[5, 41386, 47191]
[9, 42037, 47842]
[26, 43496, 49301]
[10, 45818, 51623]
[11, 47690, 53495]
[32, 49169, 54974]
[31, 51530, 56656]
[18, 51530, 57335]
[1, 52756, 57600]

[2, 21600, 21600]
[39, 22710, 28515]
[38, 27042, 32847]
[42, 29446, 35251]
[41, 33593, 39398]
[43, 37551, 43356]
[30, 42217, 48022]
[34, 44789, 50594]
[29, 46839, 52644]
[33, 49177, 54982]
[22, 50505, 59482]
[27, 52434, 61120]
[7, 54179, 62434]
[3, 64800, 64800]

Where the day starts at the time defined by the start location window, and ends by the time window of the end location. I feel like I've exhausted all of the options that I can think for for achieving this.

[Mizux]

I'll mark it as answered
https://github.com/jmarca/tsp_multiple_days/blob/feature/command_line_parameters/tsp_multiple_days.py
or
https://github.com/Mizux/tsp_multiple_days/blob/feature/morning_nodes/40_Locations_3_days.py

[joshkautz]

I'm late to the party, but I'm happy to share the solution at which @Mizux helped me arrive.

The nature of my original question was fairly specific - my goal was to be able to assign recurring time window constraints for locations in the traveling salesperson problem for an arbitrary number of days (i.e. making a location available between 2:00pm and 4:00pm during each day over the span of days that the vehicle would be active).

The solution came down to modeling the problem in a way such that the entire span of days would be represented as one large range of time between the start of the first day and the end of the last day; all durations of unavailability (due to night time, existing events, unavailable time windows, etc) would be removed from this range. This was achieved by using SetRange and RemoveInterval.