설명
이 문제는 다음을 충족하는 열차 장치의 최소 비용 슬롯 무료체험을 찾습니다. 모든 시간표에 대한 1등석 및 2등석 승객 수요 요건 여행. 단일 열차 유형의 경우 MIP 모델은 항상 루트에서 해결합니다. 두 개 이상의 열차 유형의 경우 어려운 MIP 모델입니다.
대형 모델 유형 :MIP
카테고리 : 슬롯 무료체험 모델 라이브러리
메인 파일 : 슬롯 무료체험gms
$title 철도 재고의 최소 순환(railcirc,SEQ=220)
$onText
이 문제는 다음을 충족하는 열차 단위의 최소 비용 순환을 찾습니다.
모든 시간표에 대한 1등석 및 2등석 승객 수요 요건
여행. 단일 열차 유형의 경우 MIP 모델은 항상 루트에서 해결합니다.
두 개 이상의 열차 유형에 대해서는 어려운 MIP 모델입니다.
Schrijver, A, 철도 재고의 최소 순환. CWI 분기별 3
(1993), 205-217.
키워드: 혼합 정수 선형 계획법, 최소 순환, 철도 재고,
네덜란드 철도
$offText
$eolCom //
$inlineCom /* */
세트
z '시간표에 있는 열차' / z1*z36 /
t '오늘의 모든 분' / 0000*0059, 0100*0159, 0200*0259, 0300*0359
0400*0459, 0500*0559, 0600*0659, 0700*0759
0800*0859, 0900*0959, 1000*1059, 1100*1159
1200*1259, 1300*1359, 1400*1459, 1500*1559
1600*1659, 1700*1759, 1800*1859, 1900*1959
2000*2059, 2100*2159, 2200*2259, 2300*2359 /
s '역'/ Asd '암스테르담'
Rtd '로테르담'
Rsd '루센달'
Vl '블리싱겐' /
슬롯 무료체험 'trainunit 유형' / tu1*tu2 /
c '서비스 클래스' / 첫 번째, 두 번째 /;
테이블 trainunitdata (슬롯 무료체험,*) '열차 단위 유형 데이터'
첫 번째 두 번째 숫자자동차 비용
투1 38 163 3 4
투2 65 218 4 5;
Scalar maxcars '트랙의 최대 차량 수' / 15 /;
테이블 타임테이블(z,s,t,s,t,*)
/* 출발 도착 */ 첫 번째 두 번째
z1 .Rtd.0700.Rsd.0740 4 58
z1 .Rsd.0743.Vl .0838 14 328
z2 .Asd.0648.Rtd.0755 47 340
z2 .Rtd.0801.Rsd.0841 35 272
z2 .Rsd.0843.Vl .0938 19 181
z3 .Asd.0755.Rtd.0858 100 616
z3 .Rtd.0902.Rsd.0941 52 396
z3 .Rsd.0943.Vl .1038 27 270
z4 .Asd.0856.Rtd.0958 61 407
z4 .Rtd.1003.Rsd.1043 41 364
z4 .Rsd.1045.Vl .1138 26 237
z5 .Asd.0956.Rtd.1058 41 336
z5 .Rtd.1102.Rsd.1141 26 240
z5 .Rsd.1143.Vl .1238 24 208
z6 .Asd.1056.Rtd.1158 31 282
z6 .Rtd.1203.Rsd.1241 25 221
z6 .Rsd.1243.Vl .1338 32 188
z7 .Asd.1156.Rtd.1258 46 287
z7 .Rtd.1302.Rsd.1341 27 252
z7 .Rsd.1343.Vl .1438 15 180
z8 .Asd.1256.Rtd.1358 42 297
z8 .Rtd.1402.Rsd.1441 27 267
z8 .Rsd.1443.Vl .1538 21 195
z9 .Asd.1356.Rtd.1458 33 292
z9 .Rtd.1502.Rsd.1541 28 287
z9 .Rsd.1543.Vl .1638 23 290
z10.Asd.1456.Rtd.1558 39 378
z10.Rtd.1600.Rsd.1643 52 497
z10.Rsd.1645.Vl .1740 41 388
z11.Asd.1556.Rtd.1658 84 527
z11.Rtd.1701.Rsd.1743 113 749
z11.Rsd.1745.Vl .1840 76 504
z12.Asd.1656.Rtd.1758 109 616
z12.Rtd.1801.Rsd.1842 98 594
z12.Rsd.1844.Vl .1939 67 381
z13.Asd.1756.Rtd.1858 78 563
z13.Rtd.1902.Rsd.1941 51 395
z13.Rsd.1943.Vl .2038 43 276
z14.Asd.1856.Rtd.1958 44 320
z14.Rtd.2002.Rsd.2041 29 254
z14.Rsd.2043.Vl .2138 20 187
z15.Asd.1956.Rtd.2058 28 184
z15.Rtd.2102.Rsd.2141 22 165
z15.Rsd.2143.Vl .2238 15 136
z16.Asd.2056.Rtd.2158 21 161
z16.Rtd.2202.Rsd.2241 13 130
z17.Asd.2156.Rtd.2258 28 190
z17.Rtd.2302.Rsd.2354 8 77
z18.Asd.2256.Rtd.2358 10 123
z19.Rtd.0531.Asd.0639 7 61
z20.Rsd.0529.Rtd.0628 16 167
z20.Rtd.0629.Asd.0738 26 230
z21.Vl .0530.Rsd.0635 28 138
z21.Rsd.0643.Rtd.0726 88 449
z21.Rtd.0732.Asd.0838 106 586
z22.Vl .0654.Rsd.0748 100 448
z22.Rsd.0752.Rtd.0832 134 628
z22.Rtd.0835.Asd.0940 105 545
z23.Vl .0756.Rsd.0850 48 449
z23.Rsd.0853.Rtd.0932 57 397
z23.Rtd.0934.Asd.1038 56 427
z24.Vl .0856.Rsd.0950 57 436
z24.Rsd.0953.Rtd.1032 71 521
z24.Rtd.1034.Asd.1138 75 512
z25.Vl .0956.Rsd.1050 24 224
z25.Rsd.1053.Rtd.1132 34 281
z25.Rtd.1134.Asd.1238 47 344
z26.Vl .1056.Rsd.1150 19 177
z26.Rsd.1153.Rtd.1232 26 214
z26.Rtd.1234.Asd.1338 36 303
z27.Vl .1156.Rsd.1250 19 184
z27.Rsd.1253.Rtd.1332 22 218
z27.Rtd.1335.Asd.1438 32 283
z28.Vl .1256.Rsd.1350 17 181
z28.Rsd.1353.Rtd.1432 21 174
z28.Rtd.1435.Asd.1538 34 330
z29.Vl .1356.Rsd.1450 19 165
z29.Rsd.1453.Rtd.1532 25 206
z29.Rtd.1534.Asd.1640 39 338
z30.Vl .1456.Rsd.1550 22 225
z30.Rsd.1553.Rtd.1632 35 298
z30.Rtd.1634.Asd.1738 67 518
z31.Vl .1556.Rsd.1650 39 332
z31.Rsd.1653.Rtd.1733 51 422
z31.Rtd.1735.Asd.1838 74 606
z32.Vl .1656.Rsd.1750 30 309
z32.Rsd.1753.Rtd.1832 32 313
z32.Rtd.1834.Asd.1938 37 327
z33.Vl .1756.Rsd.1850 19 164
z33.Rsd.1853.Rtd.1932 20 156
z33.Rtd.1934.Asd.2038 23 169
z34.Vl .1856.Rsd.1950 15 142
z34.Rsd.1953.Rtd.2032 14 155
z34.Rtd.2035.Asd.2138 18 157
z35.Vl .1955.Rsd.2049 11 121
z35.Rsd.2052.Rtd.2130 14 130
z35.Rtd.2132.Asd.2238 17 154
z36.Rsd.2153.Rtd.2232 7 64
z36.Rtd.2234.Asd.2338 11 143;
세트
g(s,t,s,t) '시간표 그래프'
is(s,t,s,t) '서비스 중인 아크'
on(s,t,s,t) '밤새 호'
ste(s,t) '역 시간표 이벤트'
first_ste(s,t) '오늘의 첫 번째 역 시간표 이벤트'
last_ste(s,t) '오늘의 마지막 역 시간표 이벤트'
tup(슬롯 무료체험) '모델에 있는 열차 단위의 하위 집합';
별칭 (t,tt), (s,ss);
* 시간표 그래프 구성
루프((z,s,t,ss,tt)$sum(c,timetable(z,s,t,ss,tt,c)),
ste(s,t) = 예; // 역 시간표 이벤트
ste(ss,tt) = 예; // 역 시간표 이벤트
is(s,t,ss,tt) = 예; // 서비스 중인 아크
g(s,t,ss,tt) = 예;
);
루프(들,
* 오늘의 첫 번째 역 시간 이벤트
first_ste(ss,tt) = 아니오;
loop(ste(s,t)$(카드가 아님(first_ste)), first_ste(ste) = yes);
* 모든 인접 스테이션 시간 이벤트는 스테이션 내 호입니다.
last_ste(first_ste) = 예;
loop(ste(s,t)$(first_ste(ste)가 아님),
g(last_ste(s,tt),ste) = 예;
last_ste(ss,tt) = 아니오;
last_ste(ste) = 예;
);
* 밤새 아크를 잊지 마세요
on(last_ste,first_ste) = 예;
g(온) = 예;
);
변수
f(슬롯 무료체험s,t,s,t) '열차 단위의 흐름'
obj '객관 변수';
정수변수 f;
방정식
순환(슬롯 무료체험s,t) '각 노드에서 유입은 유출과 동일합니다.'
수요(s,t,s,t,c) '1등석과 2등석 수요'
defmaxcars(s,t,s,t) '서비스 중인 아크의 최대 차량 수'
defobj '목적 함수';
순환(tup,ste(s,t))..
sum(g(ss,tt,ste), f(tup,g)) =e= sum(g(ste,ss,tt), f(tup,g));
수요(is,c)..
sum(z, timetable(z,is,c)) =l= sum(tup, f(tup,is)*trainunitdata(tup,c));
데프맥스카(이다)..
maxcars =g= sum(tup, f(tup,is)*trainunitdata(tup,'NumberCars'));
디포브..
obj =e= sum((tup,on), f(tup,on)*trainunitdata(tup,'Cost'));
모델 nscirc / all /;
옵션 optCr = 0;
* 한 번에 한 가지 유형의 훈련 단위를 수행하면 수요 방정식을 더 엄격하게 만들 수 있습니다.
f.lo(슬롯 무료체험is) = smax(c,ceil(sum(z, timetable(z,is,c)/trainunitdata(슬롯 무료체험c))));
매개변수 담당자 '솔루션 보고서';
* 이제 trainunit tu1
tup('tu1') = 예;
tup('tu2') = 아니요;
obj를 최소화하는 mip를 사용하여 nscirc를 해결합니다.
rep('tu1 only',tup) = sum(on, f.l(tup,on));
rep('tu1 only','총 비용') = obj.l;
rep('tu1 only','maxcars') = maxcars;
* 이제 trainunit tu2
tup('tu1') = 아니요;
tup('tu2') = 예;
* Rtd.1701에서 Rsd.1743으로의 서비스 때문에 maxcars를 16으로 재설정해야 합니다.
* tu2 유형의 열차 4대가 필요하므로 차량 16대가 필요합니다.
최대 자동차 = 16;
obj를 최소화하는 mip를 사용하여 nscirc를 해결합니다.
rep('tu2 only',tup) = sum(on, f.l(tup,on));
rep('tu2 only','maxcars') = maxcars;
rep('tu2 only','총 비용') = obj.l;
* 이제 두 열차 단위 모두
tup('tu1') = 예;
tup('tu2') = 예;
* 조임을 취소하고 원래의 맥스카로 돌아갑니다.
최대자동차 = 15;
f.lo(슬롯 무료체험is) = 0;
* 'tu1 전용' 단일 trainunit 솔루션을 시작으로 사용
f.l("tu2",g) = 0.0;
nscirc.tryint = 0.1;
obj를 최소화하는 mip를 사용하여 nscirc를 해결합니다. // 이것은 실제 MIP입니다.
rep('tu1+tu2',tup) = sum(on, f.l(tup,on));
rep('tu1+tu2','maxcars') = 최대자동차;
rep('tu1+tu2','총 비용') = obj.l;
디스플레이 담당자;