설명
이 트래픽 할당 문제에는 수많은 사용자/도시가 연결되어 있습니다.
도로의 공유 네트워크를 통해. 각 사용자 n
그녀의 도시 n에서 도시 n++3으로 고정된 수량을 이동해야 합니다.
공유 네트워크를 통해. 각 사용자는 여러 경로를 따라 흐름을 라우팅할 수 있습니다.
그녀의 소스 및 대상 노드. 각 경로의 지연은
경로의 각 호를 따라 지연되는 반면, 각 사용자에 대한 *유효 지연*은
는 0이 아닌 흐름을 갖는 경로에 대한 최대 지연입니다. 각 사용자
선택한 흐름을 가정하여 효과적인 지연을 최소화하도록 흐름을 라우팅합니다.
다른 사용자에 의해 일정합니다.
우리는 무료 슬롯에 대해 두 가지 공식을 제공합니다. 첫 번째는 EMP를 통한 VI입니다.
두 번째는 표준 MCP입니다. MCP 제제는 다음과 같은 장점이 있습니다.
작은 무료 슬롯(도시당 하나의 변수)이지만 MCP를 정의하는 데 사용되는 함수
VI를 정의하는 데 사용되는 함수보다 읽기 쉽고 유지 관리가 어렵습니다.
추가 링크를 추가하기 위해 VI 공식을 수정하는 것이 더 쉬울 것입니다.
또는 일부 링크 흐름을 바인딩하는 반면 MCP 공식은
네트워크의 특정 형태.
MCP 공식은 다음에서 가져옵니다.
스티븐 P. 더크세(Steven P. Dirkse) 박사 논문
혼합 상보성 문제의 강력한 솔루션.
수학적 프로그래밍 기술 보고서 94-12, 1994년 8월.
ftp://ftp.cs.wisc.edu/math-prog/tech-reports/94-12.ps
3.2.4장, 페이지 63-65
무료 슬롯의 출처는 다음과 같습니다.
Bertsekas, D. P. & Gafni E. M. (1982) '변형에 대한 투영 방법
트래픽 할당 문제에 대한 적용과의 불평등',
수학적 프로그래밍 연구 17, 139-159
기고자: Steven Dirkse, 2009년 2월
소형 무료 슬롯 유형 :무료 슬롯
카테고리 : 무료 슬롯 EMP 라이브러리
메인 파일 : 무료 슬롯.gms
$title 트래픽 할당 무료 슬롯(TRAFFIC,SEQ=19)
$onText
이 트래픽 할당 문제에는 다수의 사용자/도시가 연결되어 있습니다.
도로의 공유 네트워크를 통해. 각 사용자 n
그녀의 도시 n에서 도시 n++3으로 고정된 수량을 이동해야 합니다.
공유 네트워크를 통해. 각 사용자는 여러 경로를 따라 흐름을 라우팅할 수 있습니다.
그녀의 소스 및 대상 노드. 각 경로의 지연은
경로의 각 호를 따라 지연되는 반면, 각 사용자에 대한 *유효 지연*은
는 0이 아닌 흐름을 갖는 경로에 대한 최대 지연입니다. 각 사용자
선택한 흐름을 가정하여 효과적인 지연을 최소화하도록 흐름을 라우팅합니다.
다른 사용자에 의해 일정합니다.
우리는 무료 슬롯에 대해 두 가지 공식을 제공합니다. 첫 번째는 EMP를 통한 VI입니다.
두 번째는 표준 MCP입니다. MCP 제제는 다음과 같은 장점이 있습니다.
작은 무료 슬롯(도시당 하나의 변수)이지만 MCP를 정의하는 데 사용되는 함수
VI를 정의하는 데 사용되는 함수보다 읽기 쉽고 유지 관리가 어렵습니다.
추가 링크를 추가하기 위해 VI 공식을 수정하는 것이 더 쉬울 것입니다.
또는 일부 링크 흐름을 바인딩하는 반면 MCP 공식은
네트워크의 특정 형태.
MCP 공식은 다음에서 가져옵니다.
스티븐 P. 더크세(Steven P. Dirkse) 박사 논문
혼합 상보성 문제의 강력한 솔루션.
수학적 프로그래밍 기술 보고서 94-12, 1994년 8월.
ftp://ftp.cs.wisc.edu/math-prog/tech-reports/94-12.ps
3.2.4장, 페이지 63-65
무료 슬롯의 출처는 다음과 같습니다.
Bertsekas, D. P. & Gafni E. M. (1982) '변형에 대한 투영 방법
트래픽 할당 문제에 대한 적용과의 불평등',
수학적 프로그래밍 연구 17, 139-159
기고자: Steven Dirkse, 2009년 2월
$offText
$eolCom //
세트
n '네트워크의 도시/원산지' / n1 * n5 /
'노드 유형' 입력 /
od '원점-목적지 노드'
oA, oB '외부 루프'
iA, iB '내부 루프'
/
p '경로 유형' / 내부, 외부 /
;
별칭(n,n1,n2);
별칭(일반,t1,t2);
세트
A(n1,t1,n2,t2) '(n1,t1)에서 (n2,t2)까지의 단방향 호'
paths(n,p,n1,t1,n2,t2) '경로-호 입사 행렬';
A(n1,'od',n1 ,'oA') = 예; // 외부 루프로 진입
A(n1,'oA',n1 ,'oB') = 예; // 메인 외부 호
A(n1,'oB',n1++1,'od') = 예; // 외부 루프에서 오프 램프
A(n1,'oB',n1++1,'oA') = 예; // 외부 루프 우회
A(n1,'od',n1 ,'iA') = 예; // 내부 루프로 진입
A(n1,'iA',n1 ,'iB') = 예; // 메인 내부 호
A(n1,'iB',n1--1,'od') = 예; // 내부 루프에서 오프 램프
A(n1,'iB',n1--1,'iA') = 예; // 외부 루프 우회
abort$[card(A) <> 8*card(n)] '도시당 8개의 호가 있어야 합니다.';
스칼라
w '고속도로 중량' / 10 /
감마 '결합 계수' / 0.5 /;
* 일부 링크의 지연 시간이 증가합니다.
* 감마 * 링크 병합/종료 지연
* 감마가 0, 0.5 또는 4로 설정된 경우
$onText
요구 사항은 다음 중 하나입니다.
(.1, .2, .3, .4, .5)
또는
(1, 8 1 8 1),
$offText
매개변수
수요 (n) /
n1 .1
n2 .2
n3 .3
n4 .4
n5 .5
/,
c(n,p,n1,t1,n2,t2) '지연 계수';
c(n,'외부',n, 'od',n, 'oA') = 1; // 메인 노드에서 외부 루프로
c(n,'외부',n, 'oA',n, 'oB') = w; // 외부 루프
c(n,'외부',n, 'oB',n++1,'oA') = 1; // 외부 루프 우회
c(n,'외부',n++1,'oA',n++1,'oB') = w; // 외부 루프
c(n,'외부',n++1,'oB',n++2,'oA') = 1; // 외부 루프 우회
c(n,'외부',n++2,'oA',n++2,'oB') = w; // 외부 루프
c(n,'외부',n++2,'oB',n++3,'od') = 1; // 메인 노드에 대한 외부 루프
c(n,'내부',n, 'od',n, 'iA') = 1; // 메인 노드에서 내부 루프로
c(n,'내부',n, 'iA',n, 'iB') = w; // 내부 루프
c(n,'내부',n, 'iB',n--1,'iA') = 1; // 내부 루프 우회
c(n,'내부',n--1,'iA',n--1,'iB') = w; // 내부 루프
c(n,'내부',n--1,'iB',n--2,'od') = 1; // 메인 노드에 대한 내부 루프
abort$[card(c) <> 12*card(n)] 'c에는 도시당 12개의 호가 있어야 합니다.';
경로(n,p,n1,t1,n2,t2) = c(n,p,n1,t1,n2,t2);
* 이제 경로에 없는 호로 인한 혼잡 효과에 대한 추가 지연을 추가합니다.
* 두 가지 유형의 혼잡이 고려됩니다.
* 1. 우회링크에서 트래픽과의 합류로 인한 진입로 지연
* 고속도로 진입로에서의 교통 정체로 인해 2회 지연
c(n,'외부',n--1,'oB',n ,'oA') = 감마; // 우회 트래픽으로 인해 진입 속도가 느려집니다.
c(n,'outer',n ,'oB',n++1,'od') = 2*감마; // 진입로를 벗어나는 교통으로 인해 고속도로 속도가 느려집니다.
c(n,'outer',n++1,'oB',n++2,'od') = 2*감마; // 진입로를 벗어나는 교통으로 인해 고속도로 속도가 느려집니다.
c(n,'외부',n++2,'oB',n++3,'od') =
c(n,'외부',n++2,'oB',n++3,'od') +2*감마; // 진입로를 벗어나는 교통으로 인해 고속도로 속도가 느려집니다.
c(n,'inner',n++1,'iB',n ,'iA') = 감마; // 우회 트래픽으로 인해 진입 속도가 느려집니다.
c(n,'inner',n ,'iB',n--1,'od') = 2*감마; // 진입로를 벗어나는 교통으로 인해 고속도로 속도가 느려집니다.
c(n,'내부',n--1,'iB',n--2,'od') =
c(n,'내부',n--1,'iB',n--2,'od') +2*감마; // 진입로를 벗어나는 교통으로 인해 고속도로 속도가 느려집니다.
긍정적인 변수
x(n,p) '각 경로의 흐름';
변수
f(n1,t1,n2,t2) '각 호의 흐름';
방정식
Delay(n,p) '각 경로의 지연'
fDef(n1,t1,n2,t2)
flowCon(n) '흐름은 요구 사항을 충족해야 합니다.'
;
$매크로 d(f) (1 + f + sqr(f))
지연(n,p).. 합계A, c(n,p,A)*d(f(A)) =N= 0;
fDef(A).. f(A) =e= sum경로(n,p,A), x(n,p);
flowCon(n).. sump, x(n,p) =G= 수요(n);
무료 슬롯 mVI / 지연, fDef, flowCon /;
* vi에 대한 보완 쌍을 정의
파일 myinfo / '%emp.info%' /;
putclose myinfo 'vi f 지연 x fDef flowCon';
x.l(n,p) = 0.5 * 수요(n);
f.l(A) = 합계경로(n,p,A), x.l(n,p)
EMP를 사용하여 mVI를 해결합니다.
abort$[mVI.modelstat <> %modelStat.locallyOptimal%] 'mVI에 대한 잘못된 modelstat';
abort$[mVI.solvestat <> %solveStat.normalCompletion%] 'mVI에 대한 잘못된 해석';
* 보고서 라벨의 경우 ed = 유효 지연
매개변수 보고서(n,*), 보고서2(n,p,*);
Report2(n,p,'delayVI') = sumA, c(n,p,A)*d(f.l(A));
Report2(n,p,'flowVI') = round(x.l(n,p),8);
보고서(n,'ed_calcVI') = smaxp$[x.l(n,p) > 1e-8], 보고서2(n,p,'delayVI');
보고서(n,'ed_margVI') = flowCon.m(n);
보고서(n,'ed_diffVI') = abs(report(n,'ed_calcVI')-report(n,'ed_margVI'));
보고서(n,'out-in_VI') = (report2(n,'outer','delayVI')
- 보고서2(n,'inner','delayVI')) + eps;
보고서 표시, 보고서2;
$onText
보조 변수 f와 d를 사용하지 않고도 위의 VI를 작성할 수 있습니다.
추가적인 재공식화 트릭을 사용하여 이를 VI(F,z)로 작성할 수 있습니다.
z(n)은 (더 긴) 외부 루프에서 n에서 n++3으로의 흐름입니다.
수요(n) - z(n) (더 짧은) 내부 루프의 흐름, 그리고
F(z) = 지연(외부 루프) - 지연(내부 루프)
z에 대한 실행 가능한 집합은 상자이므로 이는 단순한 MCP입니다.
$offText
양의 변수 z(n);
z.up(n) = 수요(n);
방정식 dd(n) '지연(외부) - 지연(내부), n을 n++3으로 전달' ;
dd(n) ..
* 지연(외부)
[
(1 + z(n) + 거듭제곱(z(n),2))
+ 감마 * (1 + z(n++3) + z(n++4) + 거듭제곱(z(n++3)+z(n++4),2))
+ w * (1 + z(n) + z(n++3) + z(n++4) + 거듭제곱(z(n) + z(n++3) + z(n++4),2))
+ 2 * 감마 * (1 + z(n++3) + 거듭제곱(z(n++3),2))
+ (1 + z(n) + z(n++4) + 거듭제곱(z(n) + z(n++4),2))
+ w * (1 + z(n) + z(n++1) + z(n++4) + 거듭제곱(z(n) + z(n++1) + z(n++4), 2))
+ 2 * 감마 * (1 + z(n++4) + 거듭제곱(z(n++4),2))
+ (1 + z(n) + z(n++1) + 거듭제곱(z(n)+z(n++1),2))
+ w * (1 + z(n) + z(n++1) + z(n++2) + 거듭제곱(z(n) + z(n++1) + z(n++2), 2))
+ 2 * 감마 * (1 + z(n) + 거듭제곱(z(n),2))
+ (1 + z(n) + 거듭제곱(z(n),2))
]
=n=
* 지연(내부)
[
(1 + 수요(n)-z(n) + 전력(수요(n)-z(n),2))
+ 감마 * (1 + 수요(n++1)-z(n++1) + 전력(수요(n++1)-z(n++1),2))
+ w * (1 + 수요(n)-z(n) + 수요(n++1)-z(n++1)
+ 전력(수요(n)-z(n)+수요(n++1)-z(n++1),2))
+ 2 * 감마 * (1 + 수요(n++1)-z(n++1) + 전력(수요(n++1)-z(n++1),2))
+ (1 + 수요(n)-z(n) + 전력(수요(n)-z(n),2))
+ w * (1 + 수요(n)-z(n) + 수요(n++4)-z(n++4)
+ 전력(수요(n)-z(n)+수요(n++4)-z(n++4),2))
+ 2 * 감마 * (1 + 수요(n)-z(n) + 전력(수요(n)-z(n),2))
+ (1 + 수요(n)-z(n) + 전력(수요(n)-z(n),2))
];
무료 슬롯 mMCP / dd.z /;
mcp를 사용하여 mMCP를 해결합니다.
abort$[mMCP.modelstat <> %modelStat.optimal%] 'mMCP에 대한 잘못된 modelstat';
abort$[mMCP.solvestat <> %solveStat.normalCompletion%] 'mMCP에 대한 잘못된 해석';
* MCP 솔루션의 보고서를 정리합니다.
매개변수 xp(n,p), fp(n1,t1,n2,t2);
xp(n,'외부') = z.l(n);
xp(n,'내부') = 수요(n) - xp(n,'외부');
fp(A) = 합계경로(n,p,A), xp(n,p);
Report2(n,p,'delayMCP') = sumA, c(n,p,A)*(1 + fp(A) + sqr(fp(A)));
Report2(n,p,'flowMCP') = xp(n,p);
보고서2(n,p,'flowDiff') = abs(xp(n,p) - 보고서2(n,p,'flowVI')) + eps;
보고(n,'ed_MCP') = smaxp$[xp(n,p) > 1e-8], 보고2(n,p,'delayMCP');
보고서(n,'ed_diffMCP') = abs(report(n,'ed_calcVI')-report(n,'ed_MCP')) + eps;
보고서(n,'out-in_MCP') = dd.l(n) + eps;
보고서(n,'out-in_diff') = (보고서(n,'out-in_VI')-보고서(n,'out-in_MCP')) + eps;
보고서 표시, 보고서2;
abort$[smaxn, report(n,'ed_diffMCP') > 1e-5] 'MCP와 VI의 유효 지연이 다릅니다';
abort$[smax(n,p), report2(n,p,'flowDiff') > 1e-5] 'MCP와 VI의 경로 흐름이 다릅니다';
abort$[smax(n,p), report(n,'out-in_diff') > 1e-5] 'MCP와 VI의 다른 차이점';