설명
이 모델은 제한된 용량의 차량을 위한 최적의 경로를 찾으려고 시도합니다. 일련의 고객 요구를 충족시키면서 총 이동 거리를 최소화함으로써. 이 모델은 경로에서 하위 투어를 제거하기 위해 두 가지 방법, 즉 i) miller-tucker-zemlin, 슬롯 커뮤니티) 단치히-풀커슨-존슨. 데이터는 VRPLIB에서 가져온 것이며 임베디드 코드 Python을 사용하여 데이터를 읽습니다. Augerat 1995 - 세트 A | a-n32-k05,http://www.vrp-rep.org/datasets/item/2014-0000.html
대형 모델 유형 :MIP
카테고리 : 슬롯 커뮤니티 모델 라이브러리
메인 파일 : 슬롯 커뮤니티gms 포함: a-n32-k05.xml
$title 정전된 차량 경로 문제(CVRP,SEQ=435)
$onText
이 모델은 제한된 용량의 차량을 위한 최적의 경로를 찾으려고 시도합니다.
일련의 고객 요구를 충족시키면서 총 이동 거리를 최소화함으로써.
이 모델은 경로에서 하위 투어를 제거하기 위해 두 가지 방법, 즉 i) miller-tucker-zemlin,
ii) 단치히-풀커슨-존슨. 데이터는 VRPLIB에서 가져온 것이며 임베디드 코드 Python을 사용하여 데이터를 읽습니다.
Augerat 1995 - 세트 A | a-n32-k05, http://www.vrp-rep.org/datasets/item/2014-0000.html
이 공식은 다음에 자세히 설명되어 있습니다.
G. B. Dantzig, J. H. Ramser, (1959) 트럭 파견 문제. 경영과학 6(1):80-91.
키워드: 혼합 정수 선형 계획법, 용량성 차량 경로 문제,
밀러-터커-젬린, 단치그-풀커슨-존슨
$offText
$eolCom !!
$설정되지 않은 경우 TOURELIMINATE $set TOURELIMINATE mtz !! 하위 순회 제거 방법 [mtz, dfj]
$설정되지 않은 경우 TIMELIMIT $set TIMELIMIT 10 !! 총 시간 제한
$설정되지 않은 경우 DEBUG $set DEBUG 0 !! DEBUG=1은 추가 출력을 활성화합니다.
* 차량 흐름 공식
고객 노드의 세트 ii 상위 집합
i(ii) 고객 노드의 하위 집합
kk 차량 슈퍼세트
k(kk) 차량의 하위 집합
저장소(ii) 저장소 노드
ijk(ii,ii,kk)는 차량에 호를 허용했습니다.
별칭 (ii,jj),(i,i2,j);
매개변수
수요(ii) 노드에서 소비자의 수요
distance(ii,jj) 노드 사이의 거리
용량(kk<) 각 차량의 용량;
* xml 파일에서 데이터 읽기
$onEmbeddedCode 파이썬:
팬더를 PD로 가져오기
수학 가져오기 dist, ceil에서
노드 = pd.read_xml('a-n32-k05.xml', xpath='./network/nodes/*', 파서='etree')
nodeId = 노드['id'].values
depotId = 노드[nodes['type']== 0]['id'].values
용량 = pd.read_xml('a-n32-k05.xml', xpath='./fleet/vehicle_profile', 파서='etree')["capacity"].values[0]
DemandFrame = pd.read_xml('a-n32-k05.xml', xpath='./requests/request', 파서='etree')
수요 = 수요프레임[['노드', '수량']].값
nvehicle = ceil(demandFrame.Quantity.sum()/capacity)
distArray = 노드[['cx', 'cy']].to_numpy()
df = 목록()
범위(len(distArray))에 있는 i의 경우:
범위(len(distArray))의 j에 대해:
df.append(('n'+str(i+1) ,'n'+str(j+1), dist(distArray[i], distArray[j])))
ii = [('n'+str(i)) for i in nodeId]
kk = [('k'+str(i)) for i in range(1, nvehicle+1)]
depot = [('n'+str(i)) for i in depotId]
수요 = [('n'+str(int(i[0])), i[1]) for i 수요]
용량 = [('k'+str(i), float(capacity)) for i in range(1, nvehicle+1)]
슬롯 커뮤니티set('ii', ii)
슬롯 커뮤니티set('수요', 수요)
슬롯 커뮤니티set('거리', df)
슬롯 커뮤니티set('depot', 디포)
슬롯 커뮤니티set('용량', 용량)
$offEmbeddedCode ii, 수요, 거리, 창고, 용량
* 32개의 노드 중 16개만 사용하면 전체 문제가 계산적으로 어려워집니다.
i(ii)$[ord(ii) <= 16] = 예; !! 저장소를 포함하여 처음 16개 노드 선택(n1)
k(kk)$[ord(kk) <= 3] = 예; !! 차량 5대 중 첫 3대 선택
바이너리 변수
X(ii,jj,kk) '노드 i에서 노드 j까지의 호는 차량 k에 의해 사용됩니다.';
자유변수
TOTDIST '총 거리';
방정식
eq_tot_dist '목적 함수'
eq_node_balance(ii,kk) '모든 차량은 일단 진입하면 노드를 떠나야 합니다'
eq_enter_once(ii) '한 노드는 한 번만 방문할 수 있습니다.'
eq_leave_depot(kk,ii) '모든 차량은 차고지를 떠나야 합니다'
eq_capacity(kk) '각 차량의 수용능력 제한을 충족해야 합니다.';
eq_tot_dist.. TOTDIST =e= sum(ijk(i,j,k), distance(i,j)*X(i,j,k));
eq_node_balance(j,k).. sum(i$ijk(i,j,k), X(i,j,k)) =E= sum(i$ijk(j,i,k), X(j,i,k));
eq_enter_once(j)$(depot(j) 아님).. sum((i,k)$ijk(i,j,k), X(i,j,k)) =E= 1;
eq_leave_depot(k,i)$depot(i).. sum(j$(depot(j) 및 ijk(i,j,k)가 아님), X(i,j,k)) =E= 1;
eq_capacity(k).. sum((i,j)$(depot(j) 및 ijk(i,j,k)가 아님), Demand(j)*X(i,j,k)) =L= 용량(k);
옵션 limrow=0, limcol=0, solprint=off,solvlink=5;
$ifE %DEBUG%>1 옵션 limrow=1e6, limcol=1e6, solprint=on;
* 허용되는 호를 채우고 루프는 허용되지 않습니다.
ijk(i,j,k)$[not sameas(i,j)] = 예;
$ifThenI.TOURELIMINATE %TOURELIMINATE%==mtz
!! 밀러 - 터커 - Zemlin 서브투어 제거
양의 변수 P(ii) '여행의 순서를 결정하고 현재 부하에 한계를 두는 MTZ 변수';
!! MTZ 변수 P의 경계
P.fx(ii)$depot(ii) = 0;
P.up(ii) = 카드(jj)-1;
방정식 eq_MTZ(ii,jj) 'Miller, Tucker 및 Zemlin 하위 투어 제거';
eq_MTZ(i,j)$[동일하지 않음(i,j)].. P(i) - P(j) =l= 카드(j) - 카드(j)*sum(k$ijk(i,j,k), X(i,j,k)) - 1 + 카드(j)$(depot(j));
모델 vrp_mtz 'Miller - Tucker - Zemlin 하위 투어 제거' /all/;
vrp_mtz.reslim = %TIMELIMIT%;
vrp_mtz min을 해결하세요. TOTDIST는 MIP를 사용합니다.
디스플레이 x.l;
$elseIfI.TOURELIMINATE %TOURELIMINATE%==dfj
!! Dantzig - Fulkerson - Johnson 하위 투어 제거
stCut 가능한 하위 투어 제거 컷 설정 /c1*c1000/
a(stCut) 활성 컷
투어(ii,jj,kk) 하위 투어 가능
sn(jj,kk) 서브투어가 방문한 노드;
싱글톤 세트
cur(stCut) 현재 컷 /c1/;
매개변수
cc(stCut,ii,jj) 절단 계수
rhs(stCut);
Equation eq_defdfj(stCut,kk) '컷을 정의하는 방정식. 하위 투어를 정의하는 노드 S의 하위 집합의 경우 해당 노드 사이의 호 수는 <= 카드(S)-1'이어야 합니다.
eq_defdfj(a,k).. sum((i,j)$ijk(i,j,k), cc(a,i,j)*X(i,j,k)) =L= rhs(a);
모델 vrp_dfj / 모두 /;
vrp_dfj.reslim = %TIMELIMIT%;
a(stCut) = 아니오;
cc(a,i,j) = 0;
rhs(a) = 0;
스칼라 발견최적 / 0 /;
싱글톤 세트 last(ii,kk);
반복
vrp_dfj min TOTDIST 해결 MIP 사용;
abort$(vrp_dfj.modelStat <> %modelStat.optimal% 및 vrp_dfj.modelStat <> %modelStat.integerSolution% ) 'MIP 솔버 관련 문제';
X.l(i,j,k) = round(X.l(i,j,k));
!! 다음 블록은 현재 솔루션의 모든 투어를 조사합니다.
!! 불법적인 하위 투어가 있는 경우 다음 해결을 위해 컷을 추가하세요.
투어(i,j,k) = 아니오;
sn(i, k) = 저장소(i); !!기지에서 건물 투어 시작
동안(카드(sn),
발견최적 = 1; !! 최적이라고 가정합니다(그러나 불법 하위 투어를 감지하면 0으로 재설정).
루프(k$(합(sn(i,k), 1)),
last(sn(i,k)) = 1;
while(sum((i,j)$last(i,k), X.l(i,j,k)), !! sn에 있는 노드 i의 차량 k에 대한 솔루션에 아크가 있는 동안
loop((i,j)$(last(i,k) and X.l(i,j,k)), !! 해당 호를 반복합니다.
투어(i,j,k) = 예; !! 차량 k의 투어에 호 추가
X.l(i,j,k) = 0; !! 솔루션에서 호 제거
sn(j, k) = 예; !! sn을 설정하기 위해 ark의 대상 노드 j를 추가합니다.
last(j,k) = 예;
);
);
!! sn(*,k)에 저장소가 포함되어 있지 않으면 sn(*,k)의 노드는 잘못된 하위 투어를 형성합니다.
if(not sum(sn(depot,k),1), !! 저장소가 sn에 없는 경우
발견최적 = 0;
$$ifThenE %DEBUG%>=1
put_utility$%DEBUG% '로그' / '!!!!!! 차량 ' k.tl:0 '에 대한 ' (sum(sn(j,k), 1)):0 ' 노드가 있는 불법 하위 투어가 감지됨';
put_utility$%DEBUG% '로그' / '!!!!!! k = 'k.tl:0;
put_utility$%DEBUG% '로그' / '!!!!!! sn(j,k) = ';
loop(sn(j,k), put_utility$%DEBUG% 'log' / '!!!!!! ' j.tl:0;);
$$endIf
a(cur) = 예; !! 현재 컷 활성화
rhs(cur) = sum(sn(j,k), 1) - 1; !! rhs를 카드(S)-1로 계산
cc(cur,i,j)$(sn(i,k) 및 sn(j,k)) = 1; !! 컷 계수를 1로 설정
현재(stCut+1) = 현재(stCut); !! 현재 컷을 컷 세트의 다음 컷으로 진행
abort$(card(cur)=0) '하위 컷이 부족하여 stCut 세트를 확대합니다.';
);
sn(j, k) = 아니오;
loop((i,j)$(sum(sn(i2,k),1) = 0 및 x.l(i,j,k)), sn(i, k) = yes); !! 하위 투어 감지에서 아직 방문하지 않은 k 투어의 노드를 찾습니다.
);
);
최적이 발견되거나 TimeElapsed > %TIMELIMIT%까지;
X.l(투어) = 1; !! 최종 솔루션 복원
디스플레이 X.1;
$else.TOURELIMINATE
$$abort --TOURELIMINATE의 값이 잘못되었습니다. 허용되는 것은 'mtz' 및 'dfj'입니다.
$endIf.TOURELIMINATE