ECLiPSe CLP - 随时间变化的 TSP WIndow。我如何计算成本？

Question

我正在研究 TSP 的变体，其中每个节点都有一个时间 Window，但我在计算成本函数时遇到了一些问题。我使用的是后继模型，所以我有一个列表，其中每个变量代表下一个目的地，Xi = j 是从节点 i 到节点 j 的 link。

我的代码如下所示：

:-lib(ic).
:-lib(branch_and_bound).
:-lib(propia).
:-[nodes].

tsp(Next, Cost):-
  Cost::1..10000,
  Next::1..10000,

  %Constraints
  alldifferent(Next),
  different_from_index(Next),
  circuit(Next),
  create_objective(Next, Cost),
  minimize(labeling(Next), Cost).

其中 different_from_index 是 Next 变量的索引与其值之间的约束：Next[i] != i，而create_objective是定义objective函数的谓词。首先，create_objective 谓词创建了一个 link 的成本列表，因此使用简单的 sumlist 谓词很容易获得成本。但是我需要为每个节点定义一个时间window，我想是这样的：

time_window([], _, _, 0).
time_window([HCost | TCost], Next, Start, Cost):-
  element(Start, Next, Destination),
  time_window(TCost, Next, Destination, Cost1),
  Cost #= Cost1 + HCost,
  node(Destination, Min, Max) infers most,
  Cost #>= Min, Cost #=< Max.

[HCost | TCost] 是之前提到的成本列表，但经过排序和反转（因此我将第一个 link 作为列表的第 n 个元素，第二个为 n-1，依此类推）。此外，node 谓词包含在开头加载的序言文件中。不幸的是，这似乎不起作用：它不是 return false 也不是错误的解决方案。经过一段时间的计算后，我收到此消息：

[eclipse 2]: tsp(Next, Cost).
bb_min: search did not instantiate cost variable
Aborting execution ...
Abort

我明白这个错误，但我不知道如何解决。我使用更简单的模型和类似的 time_window 谓词成功地做到了，但在这种情况下似乎不合适。

谁能帮帮我？谢谢指教。

Answer 1

让我们从以下基本的 TSP 程序开始。它以一个距离矩阵 Dist 作为输入，并维护一个后继数组 Next 和一个距离数组 Legs，其中包含从每个节点到其后继节点的行进距离。我们最小化 Cost，这是总行驶距离。

:- lib(ic).
:- lib(branch_and_bound).

tsp(Dist, Next, Cost) :-
    dim(Dist, [N,N]),       % get distance matrix size

    dim(Next, [N]),         % successor variables
    Next #:: 1..N,
    circuit(Next),          % they must form a circuit

    dim(Legs, [N]),         % Legs[I] is distance I->Next[I]
    ( for(I,1,N), param(Dist,Next,Legs) do
        element(I, Next, J),
        element(J, Dist[I], DistIJ),
        element(I, Legs, DistIJ)
    ),
    Cost #= sum(Legs),

    % search and minimize
    minimize(search(Legs,0,smallest,indomain_min,complete,[]), Cost).

要启用时间 window 处理，添加一个数组 Time 给出每个节点的到达时间，然后可以根据需要对其进行约束。节点 I 的后继节点的到达时间可以计算为 I 的到达时间加上从 I 到其后继节点的旅行时间（为简单起见，假设距离 = 时间，并且我们开始在时间 0 的节点 1）。这导致

tsp(Dist, Next, Time, Cost) :-
    dim(Dist, [N,N]),       % get distance matrix size

    dim(Next, [N]),         % successor variables
    Next #:: 1..N,
    circuit(Next),          % they must form a circuit

    dim(Legs, [N]),         % Legs[I] is distance I->Next[I]
    dim(Time, [N]),         % Time[I] is arrival time at I
    ( for(I,1,N), param(Dist,Next,Legs,Time) do
        element(I, Next, J),
        element(J, Dist[I], DistIJ),
        element(I, Legs, DistIJ),

        ( I==1 -> TimeAtI = 0 ; element(I, Time, TimeAtI) ),
        element(J, Time, TimeAtJ),
        TimeAtJ #= TimeAtI + DistIJ
    ),
    Cost #= sum(Legs),  % total distance travelled

    % search and minimize
    minimize(search(Legs,0,smallest,indomain_min,complete,[]), Cost).

样本运行:

?- data(b6, Dist), tsp(Dist, Next, Time, Cost).
Found a solution with cost 2495
Found a solution with cost 2441
Found a solution with cost 2336
Found no solution with cost 1525.0 .. 2335.0

Dist = []([](0, 153, 510, 706, 966, 581),
          [](153, 0, 422, 664, 997, 598),
          [](510, 422, 0, 289, 744, 390),
          [](706, 664, 289, 0, 491, 265),
          [](966, 997, 744, 491, 0, 400),
          [](581, 598, 390, 265, 400, 0))
Next = [](2, 3, 4, 5, 6, 1)
Time = [](2336, 153, 575, 864, 1355, 1755)
Cost = 2336
Yes (0.00s cpu)

ECLiPSe CLP - 随时间变化的 TSP WIndow。我如何计算成本？

ECLiPSe CLP - TSP with Time WIndow. How do i calculate the cost?

prolog

traveling-salesman

constraint-programming

clpfd

eclipse-clp