1

我打算进行优化，我想最大化系统中的流量受到一些时间限制和一些“必须满足这些路线”的限制。第一个时间限制规定每辆车不得超过 24 小时的工作量（以分钟为单位）。第二个时间约束是一个子旅游消除约束，它还指出在车辆有时间行驶之前不能激活“访问”节点的开始时间等。约束3描述了K1和N1之间的道路必须使用不超过9次，使用任何车辆 k。最后一个约束条件是来自特定节点的所有车辆必须在一天结束时返回。

 maximize maxamount: sum{i in V, j in V, k in K} x[i,j,k];

 subject to TimeConstraint {k in K}: 
     sum{i in V, j in V} traveltime[i,j]*x[i,j,k] <= 1440; 

 subject to StartTime{i in V,j in V, k in K}:
     starttime[i] + servicetime[i] +traveltime[i,j] - 1300 * (1 - x[i,j,k]) <= starttime[j];

 subject to Constraint3:
     sum{k in K} x["K1","N1",k] <= 9;

 subject to EndNode{k in K}: 
     sum{i in V}x[i,"K1",k] - sum{j in V} x["K1",j,k]= 0;

Constraint3 和 EndNode 具有多个相同类型的约束（只是与其他“预定义位置”，例如 K1 和 N2 之间的道路不能超过 4 次访问等等）。

我的问题是我得到了错误 Impossible deduced bounds x[K1,K1,1] has lower bound = 0 and upper bound = -76 我理解这源于冲突的约束。然而，我的问题是：如何？几乎完全使用二进制变量，我看不出上面的代码为什么不起作用。我是否误解了我在模型中实际所做的事情？

我注意到编译器只在 i=j 时抱怨，所以我检查了我的 .dat 文件并注意到当 i=j 时 i 和 j 之间的旅行时间非常大（所以程序不会选择那些路线）。但是，自动编辑该 .dat 文件以不再超过 TimeConstraints 限制仍然给我同样的错误（虽然更小，现在上限是 -1 而不是 -76）。

我希望有人可以对此有所了解

提前致谢

4

1 回答 1

2

i 和 j 之间的旅行时间，当 i=j 非常大时（因此程序不会选择那些路线）

If traveltime[i,j]= M(very big) then StartTimefor i=jreads

servicetime[i] + M - 1300 * (1 - x[i,j,k]) <= 0     <=>
1300 * x[i,j,k] <= 1300 - servicetime[i] - M

因此，无论何时M > 1300 - servicetime[i]，问题都是不可行的。

我建议用或（如果问题是对称的）用定义X所有对的变量。(i,j)i<>ji < j

从评论跟进

插入AMPL 在线编辑器时，以下代码段运行良好：

param n := 10;
set N:= 1..n;
set V := {i in N, j in N: i <> j};
display V;

输出：

set V :=
(1,2)    (2,3)    (3,4)    (4,5)    (5,6)    (6,7)    (7,8)    (8,9)    (9,10)
(1,3)    (2,4)    (3,5)    (4,6)    (5,7)    (6,8)    (7,9)    (8,10)   (10,1)
(1,4)    (2,5)    (3,6)    (4,7)    (5,8)    (6,9)    (7,10)   (9,1)    (10,2)
(1,5)    (2,6)    (3,7)    (4,8)    (5,9)    (6,10)   (8,1)    (9,2)    (10,3)
(1,6)    (2,7)    (3,8)    (4,9)    (5,10)   (7,1)    (8,2)    (9,3)    (10,4)
(1,7)    (2,8)    (3,9)    (4,10)   (6,1)    (7,2)    (8,3)    (9,4)    (10,5)
(1,8)    (2,9)    (3,10)   (5,1)    (6,2)    (7,3)    (8,4)    (9,5)    (10,6)
(1,9)    (2,10)   (4,1)    (5,2)    (6,3)    (7,4)    (8,5)    (9,6)    (10,7)
(1,10)   (3,1)    (4,2)    (5,3)    (6,4)    (7,5)    (8,6)    (9,7)    (10,8)
(2,1)    (3,2)    (4,3)    (5,4)    (6,5)    (7,6)    (8,7)    (9,8)    (10,9);
== 1 ==========================

将您的代码段更改为

set N = {'K1', 'K2','K3','K4'};
set V := {i in N, j in N: i != j};
display V

试一试。我得到：

set V :=
(K1,K2)   (K1,K4)   (K2,K3)   (K3,K1)   (K3,K4)   (K4,K2)
(K1,K3)   (K2,K1)   (K2,K4)   (K3,K2)   (K4,K1)   (K4,K3);
== 1 ==========================

我希望这有帮助！

于 2014-09-24T15:17:55.340 回答