I'm trying to solve TSP problem with additional constraint - time windows.
All the standard assumptions apply:
- We start and end at given city.
- Each city is visited only once.
- We try to find the optimal path in terms of travel cost (here travel time).
Additionally each city has its own time window in format , which limits when a city can be visited:
- We cannot visit a city after its closing time.
- We can arrive at any city before it's opening time and wait for it to open. If we do so, waiting time is added to overall time passed, but it is not added to time spent travelling. So time_spent_travelling and total_time_passed are two distinct things we need to keep track of.
I managed to write constraints that find optimal solution in terms of total_time_passed, but I need to find optimal time_spent_travelling.
Here is my logic:
% THE TRAVELING SALESMAN WITH TIME WINDOWS
% DESC ------------------------------------------------------------------------------------
% visited(city, arrive_step)
% travel(dest_city, depart_step)
% location(city, arrive_step, when_visited (summary travel time))
% place(name, opening_time, closing_time)
% path(from, to, travel_cost)
% Warunki ----------------------------------------------------------------------------------
% Start and end must be in the same city
:- not location(Place, t, _), location(Place, 0, _).
% Paths are symmetrical
path(A, B, COST) :- path(B, A, COST).
% In each step, there can be only one travel from one city to another
{ travel(Place, T) : place(Place, _, _) } 1 :- T = 0..t-1.
% If there was a travel to a city, that city has been visited (this way starting city is not visited at the beginning)
visited(Place, T) :- travel(Place, T).
% We cannot visit a city, we've been to before
:- travel(Place, T1), visited(Place, T2), T1 > T2.
% We cannot travel to city, we are staying right now
:- travel(Place, T), location(Place, T, _).
% We cannot go to somewhere, to where leads no path
:- travel(To, T), location(From, T, _), not path(From, To, _).
% We cannot travel to city if we arrive after it's closing time
:- travel(TO, T), location(From, T, TOTAL_TIME), path(From, TO, TRAVEL_TIME), place(TO, OPENED_FROM, OPENED_TO), TOTAL_TIME + TRAVEL_TIME > OPENED_TO.
% If we started travel to city A at step T, we must have reached it at step T + 1
% City might me not opened yet, so our travel time is MAX of (CITY_OPENED_TIME, ARRIVAL_TIME)
% max = ((a+b)+|a-b|)/2
% min = ((a+b)-|a-b|)/2
location(To, T + 1, ((ARRIVAL+OPENED_FROM)+|ARRIVAL-OPENED_FROM|)/2) :- travel(To, T), location(From, T, C1) , path(From, To, C2), place(To, OPENED_FROM, _), ARRIVAL = C1+C2.
% There isn't a single city, we haven't visited
:- place(Place, _, _), not visited(Place, _).
% Find minimal travel time (Arrival time at starting city)
result(C) :- location(_, t, C).
#minimize{C : result(C)}.
#show location/3.
And here sample data (Running it with clingo takes ~ 30s):
% Cities count
#const t=21.
% Starting point
location(city_0, 0, 0).
% City list in format (name, opening_time, closing_time)
place(city_0, 0, 408).
place(city_1, 62, 68).
place(city_2, 181, 205).
place(city_3, 306, 324).
place(city_4, 214, 217).
place(city_5, 51, 61).
place(city_6, 102, 129).
place(city_7, 175, 186).
place(city_8, 250, 263).
place(city_9, 3, 23).
place(city_10, 21, 49).
place(city_11, 79, 90).
place(city_12, 78, 96).
place(city_13, 140, 154).
place(city_14, 354, 386).
place(city_15, 42, 63).
place(city_16, 2, 13).
place(city_17, 24, 42).
place(city_18, 20, 33).
place(city_19, 9, 21).
place(city_20, 275, 300).
% Distance between cities (from, to, travel_cost)
path(city_0, city_1, 19).
path(city_0, city_2, 17).
path(city_0, city_3, 34).
path(city_0, city_4, 7).
path(city_0, city_5, 20).
path(city_0, city_6, 10).
path(city_0, city_7, 17).
path(city_0, city_8, 28).
path(city_0, city_9, 15).
path(city_0, city_10, 23).
path(city_0, city_11, 29).
path(city_0, city_12, 23).
path(city_0, city_13, 29).
path(city_0, city_14, 21).
path(city_0, city_15, 20).
path(city_0, city_16, 9).
path(city_0, city_17, 16).
path(city_0, city_18, 21).
path(city_0, city_19, 13).
path(city_0, city_20, 12).
path(city_1, city_2, 10).
path(city_1, city_3, 41).
path(city_1, city_4, 26).
path(city_1, city_5, 3).
path(city_1, city_6, 27).
path(city_1, city_7, 25).
path(city_1, city_8, 15).
path(city_1, city_9, 17).
path(city_1, city_10, 17).
path(city_1, city_11, 14).
path(city_1, city_12, 18).
path(city_1, city_13, 48).
path(city_1, city_14, 17).
path(city_1, city_15, 6).
path(city_1, city_16, 21).
path(city_1, city_17, 14).
path(city_1, city_18, 17).
path(city_1, city_19, 13).
path(city_1, city_20, 31).
path(city_2, city_3, 47).
path(city_2, city_4, 23).
path(city_2, city_5, 13).
path(city_2, city_6, 26).
path(city_2, city_7, 15).
path(city_2, city_8, 25).
path(city_2, city_9, 22).
path(city_2, city_10, 26).
path(city_2, city_11, 24).
path(city_2, city_12, 27).
path(city_2, city_13, 44).
path(city_2, city_14, 7).
path(city_2, city_15, 5).
path(city_2, city_16, 23).
path(city_2, city_17, 21).
path(city_2, city_18, 25).
path(city_2, city_19, 18).
path(city_2, city_20, 29).
path(city_3, city_4, 36).
path(city_3, city_5, 39).
path(city_3, city_6, 25).
path(city_3, city_7, 51).
path(city_3, city_8, 36).
path(city_3, city_9, 24).
path(city_3, city_10, 27).
path(city_3, city_11, 38).
path(city_3, city_12, 25).
path(city_3, city_13, 44).
path(city_3, city_14, 54).
path(city_3, city_15, 45).
path(city_3, city_16, 25).
path(city_3, city_17, 28).
path(city_3, city_18, 26).
path(city_3, city_19, 28).
path(city_3, city_20, 27).
path(city_4, city_5, 27).
path(city_4, city_6, 11).
path(city_4, city_7, 17).
path(city_4, city_8, 35).
path(city_4, city_9, 22).
path(city_4, city_10, 30).
path(city_4, city_11, 36).
path(city_4, city_12, 30).
path(city_4, city_13, 22).
path(city_4, city_14, 25).
path(city_4, city_15, 26).
path(city_4, city_16, 14).
path(city_4, city_17, 23).
path(city_4, city_18, 28).
path(city_4, city_19, 20).
path(city_4, city_20, 10).
path(city_5, city_6, 26).
path(city_5, city_7, 27).
path(city_5, city_8, 12).
path(city_5, city_9, 15).
path(city_5, city_10, 14).
path(city_5, city_11, 11).
path(city_5, city_12, 15).
path(city_5, city_13, 49).
path(city_5, city_14, 20).
path(city_5, city_15, 9).
path(city_5, city_16, 20).
path(city_5, city_17, 11).
path(city_5, city_18, 14).
path(city_5, city_19, 11).
path(city_5, city_20, 30).
path(city_6, city_7, 26).
path(city_6, city_8, 31).
path(city_6, city_9, 14).
path(city_6, city_10, 23).
path(city_6, city_11, 32).
path(city_6, city_12, 22).
path(city_6, city_13, 25).
path(city_6, city_14, 31).
path(city_6, city_15, 28).
path(city_6, city_16, 6).
path(city_6, city_17, 17).
path(city_6, city_18, 21).
path(city_6, city_19, 15).
path(city_6, city_20, 4).
path(city_7, city_8, 39).
path(city_7, city_9, 31).
path(city_7, city_10, 38).
path(city_7, city_11, 38).
path(city_7, city_12, 38).
path(city_7, city_13, 34).
path(city_7, city_14, 13).
path(city_7, city_15, 20).
path(city_7, city_16, 26).
path(city_7, city_17, 31).
path(city_7, city_18, 36).
path(city_7, city_19, 28).
path(city_7, city_20, 27).
path(city_8, city_9, 17).
path(city_8, city_10, 9).
path(city_8, city_11, 2).
path(city_8, city_12, 11).
path(city_8, city_13, 56).
path(city_8, city_14, 32).
path(city_8, city_15, 21).
path(city_8, city_16, 24).
path(city_8, city_17, 13).
path(city_8, city_18, 11).
path(city_8, city_19, 15).
path(city_8, city_20, 35).
path(city_9, city_10, 9).
path(city_9, city_11, 18).
path(city_9, city_12, 8).
path(city_9, city_13, 39).
path(city_9, city_14, 29).
path(city_9, city_15, 21).
path(city_9, city_16, 8).
path(city_9, city_17, 4).
path(city_9, city_18, 7).
path(city_9, city_19, 4).
path(city_9, city_20, 18).
path(city_10, city_11, 11).
path(city_10, city_12, 2).
path(city_10, city_13, 48).
path(city_10, city_14, 33).
path(city_10, city_15, 23).
path(city_10, city_16, 17).
path(city_10, city_17, 7).
path(city_10, city_18, 2).
path(city_10, city_19, 10).
path(city_10, city_20, 27).
path(city_11, city_12, 13).
path(city_11, city_13, 57).
path(city_11, city_14, 31).
path(city_11, city_15, 20).
path(city_11, city_16, 25).
path(city_11, city_17, 14).
path(city_11, city_18, 13).
path(city_11, city_19, 17).
path(city_11, city_20, 36).
path(city_12, city_13, 47).
path(city_12, city_14, 34).
path(city_12, city_15, 24).
path(city_12, city_16, 16).
path(city_12, city_17, 7).
path(city_12, city_18, 2).
path(city_12, city_19, 10).
path(city_12, city_20, 26).
path(city_13, city_14, 46).
path(city_13, city_15, 48).
path(city_13, city_16, 31).
path(city_13, city_17, 42).
path(city_13, city_18, 46).
path(city_13, city_19, 40).
path(city_13, city_20, 21).
path(city_14, city_15, 11).
path(city_14, city_16, 29).
path(city_14, city_17, 28).
path(city_14, city_18, 32).
path(city_14, city_19, 25).
path(city_14, city_20, 33).
path(city_15, city_16, 23).
path(city_15, city_17, 19).
path(city_15, city_18, 22).
path(city_15, city_19, 17).
path(city_15, city_20, 32).
path(city_16, city_17, 11).
path(city_16, city_18, 15).
path(city_16, city_19, 9).
path(city_16, city_20, 10).
path(city_17, city_18, 5).
path(city_17, city_19, 3).
path(city_17, city_20, 21).
path(city_18, city_19, 8).
path(city_18, city_20, 25).
path(city_19, city_20, 19).
I used MAX function to calculate arrival time at given cities by choosing from real arrival time or city's opening time - whichever happened to be later. It worked nicely, so my first thought was to add additional field to location fact changing this line as follows:
%Before:
location(To, T + 1, ((ARRIVAL+OPENED_FROM)+|ARRIVAL-OPENED_FROM|)/2) :- travel(To, T), location(From, T, C1) , path(From, To, C2), place(To, OPENED_FROM, _), ARRIVAL = C1+C2.
%After:
location(To, T + 1, ((ARRIVAL+OPENED_FROM)+|ARRIVAL-OPENED_FROM|)/2, TRAVEL_TIME + C2) :- travel(To, T), location(From, T, C1, TRAVEL_TIME) , path(From, To, C2), place(To, OPENED_FROM, _), ARRIVAL = C1+C2.
This way location hold information about both time_spent_travelling and total_time_passed. While this works fine for 5 cities, with 20 cities it keeps calculating too long (I gave up after 15 minutes) - I expected the program to run roughly the same time at both situations, but apparently there is something I don't understand here.
I also tried to store waiting times as separate facts, but it seemed to affect computing time the same way and introduced another issue of taking it into consideration in #minimize function which I couldn't menage to solve.
So here are my questions:
- What can I do to calculate optimal value of time_spent_travelling, yet correctly considering waiting time?
- Why a small change in code, I've described above, has such a high computational impact on the solving process?
I've started using clingo recently and there is a good chance I don't see a simple solution to this problem. It's kind of hard to change the way you write your program, being so used to declarative programming.
The code I've provided can be simple run with clingo:
clingo logic data
My output:
Solving...
Answer: 1
location(city_0,0,0) location(city_16,1,9) location(city_9,2,17) location(city_19,3,21) location(city_17,4,24) location(city_10,5,31) location(city_18,6,33) location(city_5,7,51) location(city_15,8,60) location(city_1,9,66) location(city_11,10,80) location(city_12,11,93) location(city_6,12,115) location(city_13,13,140) location(city_7,14,175) location(city_2,15,190) location(city_4,16,214) location(city_8,17,250) location(city_20,18,285) location(city_3,19,312) location(city_14,20,366) location(city_0,21,387)
Optimization: 387
OPTIMUM FOUND
Models : 1
Optimum : yes
Optimization : 387
Calls : 1
Time : 27.654s (Solving: 0.10s 1st Model: 0.04s Unsat: 0.06s)
CPU Time : 27.651s
(base) igor@i:~/projects/transInfo/TSPTW/src$ clingo dane logika
clingo version 5.4.0
Reading from dane ...
Solving...
Answer: 1
location(city_0,0,0) location(city_16,1,9) location(city_9,2,17) location(city_19,3,21) location(city_17,4,24) location(city_10,5,31) location(city_18,6,33) location(city_5,7,51) location(city_15,8,60) location(city_1,9,66) location(city_11,10,80) location(city_12,11,93) location(city_6,12,115) location(city_13,13,140) location(city_7,14,175) location(city_2,15,190) location(city_4,16,214) location(city_8,17,250) location(city_20,18,285) location(city_3,19,312) location(city_14,20,366) location(city_0,21,387)
Optimization: 387
OPTIMUM FOUND
Models : 1
Optimum : yes
Optimization : 387
Calls : 1
Time : 29.682s (Solving: 0.09s 1st Model: 0.03s Unsat: 0.06s)
CPU Time : 29.680s
Here the result takes into consideration waiting time, which in this particular example is 9. (378 is time spent only on travelling).
I've managed to solve the problem. Simple change in last lines did the trick: