GUSEK 中的 TSP 时间 windows

Question

我正在尝试做一个程序，我有 9 个地方可以参观，每个地方都有时间 window 参观，程序中 [a,b]。每个城市的时间是 p，我有一笔押金，我从一辆车开始，我也需要完成押金。我不需要在同一天访问所有城市。到时候这就是我所拥有的，但是程序说 "p" 没有定义。也许你可以帮助我并告诉我一些关于如何做的提示。

param n, integer, >= 3;
/* number of nodes */

param MAX_TIME := 600;
param MAX_X :=20;
param maxspeed;

set CITIES := 1..n;
/* set of nodes */


set ARCS, within CITIES cross CITIES;
/* set of arcs */

param DIST{(i,j) in ARCS};
/* distance from node i to node j */
param NEXTC, integer, >= 0;
/* Next city after i in the solution */
var x{(i,j) in ARCS}, binary;
/* x[i,j] = 1 means that the salesman goes from node i to node j */


param bigM := 5000;
var tar{CITIES};         /*arrival */
var tlv{CITIES};         /* departure */
var tea{CITIES} >= 0;    /* early arrival (arrival before the designated   time window) */
var tla{CITIES} >= 0;    /* late arrival (arrival after the designated time window) */
var ted{CITIES} >= 0;    /* early departure (departure before the designated time window) */
var tld{CITIES} >= 0;    /* late departure (departure after the designated time window) */

s.t. t1 {i in CITIES} : tlv[i] >= tar[i]; 
s.t. t2 {i in CITIES, j in CITIES} : tar[j] >= tlv[i] + p[i] +   DIST[i,j]/maxspeed - bigM*(1-x[i,j]);
s.t. t3 {i in CITIES} : tea[i] >= a[i] - tar[i];   /* early arrival */
s.t. t4 {i in CITIES} : tla[i] >= tar[i] - b[i];   /* late arrival */
s.t. t5 {i in CITIES} : ted[i] >= a[i] - tlv[i];   /* early departure */
s.t. t6 {i in CITIES} : tld[i] >= tlv[i] - b[i];   /* late departure */

set days := 1..5;
param root := 1;



var y{(i,j) in ARCS}, >= 0;
/* y[i,j] is a flow through arc (i,j) */


minimize total: sum{(i,j) in ARCS} DIST[i,j] * x[i,j];


solve;

printf "Optimal tour has length %d\n",
sum{(i,j) in ARCS} DIST[i,j] * x[i,j];
printf("From node   To node   Distance\n");
printf{(i,j) in ARCS: x[i,j]} "      %3d       %3d   %8g\n",
i, j, DIST[i,j];
data;

param n := 9;

param : ARCS : DIST :=
1  2   21
1  3   8
1  4   6
1  5   10
1  6   2
1  7   4
1  8   5
1  9   5
2  1   21
2  3   18
2  4   21
2  5   23
2  6   22
2  7   20
2  8   22
2  9   25
3  1   7
3  2   16
3  4   3
3  5   9
3  6   8
3  7   4
3  8   7
3  9   9
4  1   8
4  2   18
4  3   3
4  5   10
4  6   9
4  7   6
4  8   9
4  9   11
5  1   9
5  2   25
5  3   11
5  4   9
5  6   11
5  7   8
5  8   11
5  9   13
6  1   4
6  2   23
6  3   8
6  4   7
6  5   11
6  7   5
6  8   7
6  9   8
7  1   3
7  2   20
7  3   6
7  4   5
7  5   8
7  6   4
7  8   3
7  9   8
8  1   3
8  2   20
8  3   5
8  4   4
8  5   8
8  6   5
8  7   4
8  9   7
9  1   7
9  2   24
9  3   10
9  4   8
9  5   13
9  6   7
9  7   7
9  8   6;

param : a :=
  1  705
  2  420
  3  420
  4  420
  5  420
  6  420
  7  420
  8  420
  9  420;

param : b :=
  1  785
  2  795
  3  725
  4  500
  5  785
  6  785
  7  430
  8  785
  9  785;

param : p :=
  1  65
  2  55
  3  125
  4  65
  5  65
  6  65
  7  65
  8  65
  9  65;

end;

谢谢。

Answer 1

在约束 t2 中使用 p[i]:

tar[j] >= tlv[i] + p[i] + DIST[i,j]/maxspeed - bigM*(1-x[i,j]);

但 p 未声明。您应该根据它是输入数据还是优化过程中需要确定的东西来声明它是参数还是变量。例如：

param p{CITIES};

GUSEK 中的 TSP 时间 windows

TSP time windows in GUSEK

ampl

glpk