[AMPL 24432] Train scheduling in AMPL

Google Group Mirror
1

Hi,
I am trying to solve a train timetable optimization problem using AMPL. I am new to it. The code is returning an incorrect answer. There are a few issues in this code

  1. Constraint #MustDepart becomes infeasible for i > D[n] but if I don’t inlclude it it results in zero for all trains.
  2. PB should be integer but then it doesn’t run saying that it is non-linear problem and the demo cannot solve more than 300 variables and constraint. I am not sure how does it become a nonlinear problem.
  3. D[n] for each n must have the optimal value but that’s not the case. It gives values such that the difference of D[n] is equal to minimum headway. I have included an >= costrain so it should work. if the reduce the minimum headway to 4 minutes, D[n] becomes 18 and the waiting time increase which is not the optimal solution.
    I would really appreciate some help!

#Sets
set N ordered; #No. of trains
set A ordered; #No. of upcoming trains
set LS ordered; #No. of loading stations
set US ordered; #No. of unloading stations

#Parameters
param T = 1; #Size of time interval in miuntes
param C = 1500; # Total Capacity of each train
param I >=0; #No. of intervals
param PE{i in 1…I,s in LS}; #No. of Passengers entering station s at interval i
param PA{i in 1…I,s in US}; #No. of Passengers alighting from train n at station s

#Independent Variables
var D {n in N} >=0 , integer;#Departure time of train n
var X {n in N,i in 1…I}, binary; #Varible for max time step for train n
var PB {n in N,i in 1…I,s in LS} >=0; #Ratio of boarding passengers to arriving passengers

#Dependent Variables
var Y {n in N,i in 1…I,s in LS} = X[n,i]*PE[i,s]; #Passenegers arriving at station s, in interval i, assigned to service n
var AC{n in N,s in LS} = if s = 1 then C else min(C,AC[n,s-1]+ sum{i in 1…I}(X[n,i]*PA[i,s]) - sum{i in 1…I}PB[n,i,s-1]); #Available capacity of service n at station s before the passengers board
var PL {n in N,i in 1…I,s in LS}= Y[n,i,s]-PB[n,i,s]; #No. of passengers left after service n departs

var W {n in N,i in 1…I,s in LS} = (Y[n,i,s](D[n]-(i-0.5)) + if n = 1 then 0 else PL[n-1,i,s](D[n]-D[n-1]))*T ; #Waiting time of p passengers, at station n and interval i, for train n

#Objective function
maximize TotalWaitingTime: #Total waiting time of all passengers
sum {n in N,i in 1…I,s in LS}W[n,i,s];

#Constraints

subject to MustDepart{n in N,i in 1…I}: #Train always departs
D[n] -(i-0.5) >= 0.5 ;

subject to MinHeadway{n in A}: #To maintain minimum headway between two trains
D[n+1] - D[n] >=6;

subject to MaxHeadway{n in A}: #To maintain minimum headway between two trains
D[n+1] - D[n] <=15;

subject to LastDeparture{i in 1…I,n in N}: #Every train must departs within the time horizon
D[n]<= I;

subject to Imin_Imax{n in N,i in 1…I}: #To update the no. of passengers arriving after train n from departs station s
X[n,i] = if n = 1 then (if i <= D[n] then 1 else 0) else if i > D[n-1] and i <= D[n] then 1 else 0;

subject to C2{n in N,i in 1…I,s in LS}: # No. of passengers boarding service n at station s should not exceed its available capacity
PB[n,i,s] = min(Y[n,i,s],(if s = 1 then C else AC[n,s])/(D[n] - if n=1 then 0 else D[n-1]));

subject to C6: # Total of passengers boarding should not exceed total passengers arriving
sum{n in N, i in 1…I, s in LS}PB[n,i,s] = sum{i in 1…I, s in LS}PE[i,s];

subject to C3 {n in N,s in LS}: # non-negativity
AC[n,s] >=0;

subject to C4 {n in N,s in LS}: # non-negativity
AC[n,s] <=C;

subject to C5{n in N,i in 1…I,s in LS}: # non negativity
W[n,i,s] >= 0;

set N:=1,2,3,4,5,6,7;
set A:= 1,2,3,4,5,6;
set LS:=1,2,3,4,5,6,7,8,9,10,11;
set US:=2,3,4,5,6,7,8,9,10,11,12;

param I:= 42;

param PE: 1 2 3 4 5 6 7 8 9 10 11:=
1 0 210 123 63 54 0 0 108 54 40 40
2 0 210 123 63 54 0 0 108 54 40 40
3 0 210 123 63 54 0 0 108 54 40 40
4 0 210 123 63 54 0 0 108 54 40 40
5 0 210 123 63 54 0 0 108 54 40 40
6 0 210 123 63 54 0 0 108 54 40 40
7 0 210 123 63 63 0 0 108 54 40 40
8 0 210 123 63 63 0 0 108 54 45 58
9 0 161 123 63 63 0 0 108 54 45 58
10 0 161 123 63 63 0 0 108 54 45 58
11 0 161 143 63 63 0 0 123 87 45 58
12 0 161 143 63 63 0 0 123 87 45 58
13 0 161 143 63 63 0 0 123 87 45 58
14 0 161 143 78 63 0 0 123 87 45 58
15 0 161 143 78 63 0 0 123 87 45 58
16 0 161 143 78 54 0 0 123 87 45 58
17 0 161 143 78 54 0 0 123 87 45 58
18 0 161 143 78 54 0 0 123 87 45 58
19 0 172 143 78 54 0 0 123 87 45 58
20 0 172 143 78 54 0 0 123 87 45 58
21 0 172 136 78 54 0 0 112 87 45 58
22 0 172 136 78 54 0 0 112 87 45 58
23 0 172 136 78 63 0 0 112 87 45 58
24 0 172 136 78 63 0 0 112 87 45 58
25 0 172 136 78 63 0 0 112 87 45 58
26 0 172 136 78 63 0 0 112 87 45 58
27 0 172 136 78 63 0 0 112 87 45 58
28 0 172 136 78 63 0 0 112 87 45 58
29 0 172 136 78 63 0 0 112 87 45 58
30 0 172 136 78 63 0 0 112 87 45 58
31 0 172 136 78 63 0 0 112 87 45 58
32 0 172 136 78 63 0 0 112 87 45 58
33 0 172 136 78 63 0 0 112 87 45 58
34 0 172 136 78 63 0 0 112 87 45 58
35 0 172 136 78 63 0 0 112 87 45 58
36 0 172 136 78 63 0 0 112 87 45 58
37 0 172 136 78 63 0 0 112 87 45 58
38 0 172 136 78 63 0 0 112 87 45 58
39 0 172 136 78 63 0 0 112 87 45 58
40 0 172 136 78 63 0 0 112 87 45 58
41 0 172 136 78 63 0 0 112 87 45 58
42 0 172 136 78 63 0 0 112 87 45 58
;

param PA: 2 3 4 5 6 7 8 9 10 11 12:=
1 0 36 71 117 125 0 0 71 74 73 125
2 0 36 71 117 125 0 0 71 74 73 125
3 0 36 71 117 125 0 0 71 74 73 125
4 0 36 71 117 125 0 0 71 74 73 125
5 0 36 71 117 125 0 0 71 74 73 125
6 0 36 71 117 125 0 0 71 74 73 125
7 0 36 71 117 134 0 0 71 74 73 125
8 0 36 71 125 141 0 0 71 74 74 132
9 0 26 62 125 132 0 0 62 69 76 123
10 0 26 62 125 132 0 0 62 69 76 123
11 0 26 72 139 149 0 0 62 74 90 131
12 0 26 72 139 149 0 0 62 74 90 131
13 0 26 72 139 149 0 0 62 74 90 131
14 0 26 72 144 154 0 0 62 74 90 136
15 0 26 72 144 154 0 0 62 74 90 136
16 0 26 72 144 145 0 0 62 74 90 136
17 0 26 72 144 145 0 0 62 74 90 136
18 0 26 72 144 145 0 0 62 74 90 136
19 0 26 62 144 154 0 0 62 73 103 136
20 0 26 62 144 154 0 0 62 73 103 136
21 0 26 43 149 145 0 0 72 80 100 127
22 0 26 43 149 145 0 0 72 80 100 127
23 0 26 43 149 154 0 0 72 80 100 127
24 0 26 43 149 154 0 0 72 80 100 127
25 0 26 43 149 154 0 0 72 80 100 127
26 0 26 43 149 154 0 0 72 80 100 127
27 0 26 43 149 154 0 0 72 80 100 127
28 0 26 43 149 154 0 0 72 80 100 127
29 0 26 43 149 154 0 0 72 80 100 127
30 0 26 43 149 154 0 0 72 80 100 127
31 0 26 43 149 154 0 0 72 80 100 127
32 0 26 43 149 154 0 0 72 80 100 127
33 0 26 43 149 154 0 0 72 80 100 127
34 0 26 43 149 154 0 0 72 80 100 127
35 0 26 43 149 154 0 0 72 80 100 127
36 0 26 43 149 154 0 0 72 80 100 127
37 0 26 43 149 154 0 0 72 80 100 127
38 0 26 43 149 154 0 0 72 80 100 127
39 0 26 43 149 154 0 0 72 80 100 127
40 0 26 43 149 154 0 0 72 80 100 127
41 0 26 43 149 154 0 0 72 80 100 127
42 0 26 43 149 154 0 0 72 80 100 127
;

2

Your MustDepart constraint is

subject to MustDepart {n in N, i in 1..I}:  #Train always departs
   D[n] - (i-0.5) >= 0.5 ;

This is the same as D[n] >= 0.5 + (i-0.5), or D[n] >= i. So you are saying that for every n in N and every i from 1 up to I, D[n] is >= i. So for each n you have D[n] >= 1, D[n] >= 2, and so forth up to D[n] >= I, which does not seem right since D[n] >= I implies all of the others. You can check that this analysis is correct by looking at the output from the AMPL command “expand MustDepart;” which lists all of the MustDepart constraints that are being generated; the listing starts with

subject to MustDepart[1,1]:
	D[1] >= 1;
subject to MustDepart[1,2]:
	D[1] >= 2;
subject to MustDepart[1,3]:
	D[1] >= 3;

and goes up to

subject to MustDepart[1,42]:
	D[1] >= 42;

and then continues with the same for other values of n. You will need to decide what constraints you really want to have here, and then if you cannot figure out how to write them in AMPL, you can post an example a description or (better yet) an example. After you fix these constraints, you can solve again to see if there are still problems with other constraints.

Your formulation has a nonlinearity where it applies the min function to an expression involving variables, and where it uses the / operator to divide by an expression involving variables. However, some solvers can automatically linearize these nonlinear expressions; try the latest download of gurobi, for example.