설명
이것은 일련의 여행 세일즈맨 중 다섯 번째 문제입니다. 문제. 여기서는 하위 투어가 없는 컴팩트한 공식을 사용합니다. Miller, Tucker 및 Zemlin 덕분입니다. 제한된 시간 동안 MTZ를 운영하거나 또는 2개 옵션 개선 교환으로 탐욕스러운 경험적 방법을 적용하고 이를 사용하십시오. 하위 투어 제거 시간이 부족할 경우를 대비한 백업 솔루션입니다. 더욱이, 우리는 훨씬 더 강한 것을 사용하여 동적 하위 투어 제거를 사용합니다. 이전 모델보다 컷이 더 커졌습니다. 또한 슬롯 게임 프로그래밍이 더 좋습니다. 이전 예보다 컴팩트합니다.
대형 모델 유형 :MIP
카테고리 : 슬롯 게임 모델 라이브러리
$title 여행하는 외판원 문제 - 5개(TSP5,SEQ=345)
$onText
이것은 여행하는 세일즈맨 시리즈의 다섯 번째 문제입니다.
문제. 여기서는 하위 투어가 없는 컴팩트한 공식을 사용합니다.
Miller, Tucker 및 Zemlin 덕분입니다. 제한된 시간 동안 MTZ를 운영하거나
또는 2개 옵션 개선 교환으로 탐욕스러운 경험적 방법을 적용하고 이를 사용하십시오.
하위 투어 제거 시간이 부족할 경우를 대비한 백업 솔루션입니다.
더욱이, 우리는 훨씬 더 강한 것을 사용하여 동적 하위 투어 제거를 사용합니다.
이전 모델보다 컷이 더 커졌습니다. 또한 슬롯 게임 프로그래밍이 더 좋습니다.
이전 예보다 컴팩트합니다.
Miller, C E, Tucker, AW 및 Zemlin, RA, 정수 프로그래밍
여행하는 세일즈맨 문제의 공식화. J. ACM 7, 4 (1960),
326-329.
키워드: 혼합 정수 선형 계획법, 여행하는 세일즈맨 문제, Miller-
Tucker-Zemlin 하위 순회 제거, 2-opt 휴리스틱, 반복 하위 순회 제거
$offText
$includebr17.inc
세트
Quicktour(ii,jj) 'MTZ 모델로 찾은 투어 또는 2-opt 투어'
i(ii) / #ii /;
$설정되지 않은 경우 BACKUP $set BACKUP 2-opt
$ifThen "%BACKUP%"=="2-opt"
임베디드코드 파이썬:
슬롯 게임transfer를 gt로 가져오기
numpy를 np로 가져오기
데프 스왑(p,i,j):
tmp = p[i]
p[i] = p[j]
p[j] = 시간
m = gt.Container(슬롯 게임db, system_directory=r"%슬롯 게임sysdir% ".rstrip())
n = len(슬롯 게임db['ii'])
c = m.data['c'].toDense()
# 빠른 욕심쟁이 투어
p = np.zeros(n, dtype=int) # 순열 벡터
다음 = 0
범위(n-1)에 있는 i의 경우:
c[:,next] = np.nan
다음 = np.nanargmin(c[다음])
p[i+1] = 다음
# 2옵션 스왑
c = m.data['c'].toDense()
tlen = sum(c[p[i],p[(i+1) % n]] for i in range(n))
슬롯 게임printLog(f'Greedy 투어 길이: tlen:.2f')
n스왑 = 1
nswap>0인 동안:
n스왑 = 0
범위(n)에 있는 i의 경우:
범위(i+1,n)의 j에 대해:
스왑(p,i,j)
newlen = sum(c[p[i],p[(i+1) % n]] for i in range(n))
newlen < tlen인 경우:
슬롯 게임printLog(f'Swap of p[j] 및 p[i]는 tlen-newlen:.2f에 의한 둘러보기를 개선했습니다. 새 길이: newlen:.2f')
tlen = 뉴렌
nswap = nswap + 1
그 외:
swap(p,i,j) # 다시 교체
슬롯 게임set('quicktour', [ (int(p[i]+1), int(p[(i+1) % n]+1)) for i in range(n)])
endEmbeddedCode 둘러보기
$else
* 컴팩트한 TSP 모델 구축
양수 변수 p(ii) '투어에서의 위치';
방정식 defMTZ(ii,jj) '밀러, 터커 및 젬린 하위 순회 제거';
defMTZ(i,j).. p(i) - p(j) =l= 카드(j) - 카드(j)*x(i,j) - 1 + 카드(j)$(ord(j) = 1);
모델 MTZ / 모두 /;
p.fx(j)$(ord(j) = 1) = 0;
p.up(j) = 카드(j) - 1;
MTZ.resLim = 30;
mip를 사용하여 MTZ min z를 해결합니다.
if (MTZ.modelStat= %modelStat.optimal% 또는 MTZ.modelStat = %modelStat.integerSolution%,
Quicktour(i,j) = round(x.l(i,j));
);
$endIf
* 동적 하위 투어 제거
세트
ste '가능한 하위 투어 제거 컷' / c1*c1000 /
a(ste) '활성 컷'
Tour(ii,jj) '가능한 하위 투어'
n(jj) '하위 투어로 방문한 노드';
싱글톤 세트
cur(ste) '현재 컷' /c1/;
매개변수
cc(ste,ii,jj) '계수 절단'
rhs(ste) '컷의 오른쪽';
방정식 defste(ste) '하위 투어 제거 컷';
defste(a).. sum((i,j), cc(a,i,j)*x(i,j)) =l= rhs(a);
모델 DSE / rowsum, colsum, 목적, defste /;
a(ste) = 아니오;
cc(a,i,j) = 0;
rhs(a) = 0;
옵션 limRow = 0, limCol = 0, solPrint = 자동,solvLink = 5;
반복하다
mip를 사용하여 DSE min z를 해결합니다.
abort$(DSE.modelStat <> %modelStat.optimal% 및 DSE.modelStat <> %modelStat.integerSolution% ) 'MIP 솔버 관련 문제';
x.l(i,j) = round(x.l(i,j));
* 하위 투어 확인
투어(i,j) = 아니오;
n(i) = ord(i)=1;
동안(카드(n),
* 단일 하위 투어를 구성하고 해당 가장자리에 대해 x.l=0을 설정하여 제거합니다.
while(sum((n,j), x.l(n,j)),
루프((i,j)$(n(i) 및 x.l(i,j)),
투어(i,j) = 예;
x.l(i,j) = 0;
n(j) = 그렇습니다;
);
);
* 서브투어
if(카드(n) < 카드(j),
a(cur) = 예;
rhs(cur) = 카드(n) - 1;
cc(cur,i,j)$(n(i) 및 n(j)) = 1;
cur(ste+1) = cur(ste);
abort$(card(cur)=0) '하위 컷이 부족하여 세트 섹션을 확대합니다';
그렇지 않으면
* 최적
휴식 2;
);
n(j) = 아니오;
loop((i,j)$(card(n) = 0 및 x.l(i,j)), n(i) = yes);
);
put_utility 'log' / 'Added' (card(a)-card(defste)):0:0 ' 하위 투어 컷'
시간이 경과될 때까지>30;
if(카드(n) = 카드(j),
옵션 둘러보기:0:0:1;
'최적의 투어 발견' 표시, 투어;
put_utility 'log' / '최적의 둘러보기';
그렇지 않으면
put_utility 'log' / '시간 초과';
put_utility$card(quicktour) 'log' / '휴리스틱 투어 보고(2-opt 또는 시간 제한 MTZ)';
투어(i,j) = 퀵투어(i,j);
);
put_utility$card(tour) 'log' / '투어 길이 = ' (sum(tour(i,j), c(i,j))):0 ':';
n(i) = ord(i)=1;
동안(1,
루프(투어(i,j)$n(i),
put_utility 'log' / i.te(i) ' --> ' j.te(j) ' (' c(i,j):6:2 ')';
n(i) = 아니오;
n(j) = 그렇습니다;
break$(ord(j)=1) 2;
);
);