我正在尝试通过其他限制条件-时间窗口来解决TSP问题。
所有标准假设均适用：
- 我们从给定的城市开始和结束。
- 每个城市只能访问一次。
- 我们尝试根据旅行成本（此处为旅行时间）找到最佳路径。
此外，每个城市都有自己的格式的时间窗口 ，它限制了何时可以访问城市：
- 封闭时间结束后，我们将无法访问城市。
- 我们可以在开放时间之前到达任何城市，然后等待它开放。如果这样做，等待时间将添加到经过的总时间中，但不会添加到花费的旅行时间中。因此，time_spent_travelling和total_time_passed是我们需要跟踪的两个不同的事物。
我设法编写了一些约束，这些约束可以根据total_time_passed找到最佳解决方案，但是我需要找到最佳time_spent_travelling。
这是我的逻辑：
% 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.
这是示例数据（使用clingo运行它大约需要30秒）：
% 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
这里的结果考虑了等待时间，在这个特定示例中为9。（378是仅花费在旅行上的时间）。
查看更多
