城市物流配送方案優(yōu)化設計K

接著我們以XX地區(qū)為例來進行最短路程求解根據(jù)上面我們得出的某一區(qū)域中的數(shù)個卸貨點卸貨點的位置坐標，我們假定實際的卸貨點位于距離理想卸貨點最近的公路節(jié)點。(具體代碼見附錄)由此可得到每個實際卸貨點以及附近的道路信息如圖：R=[472471827467134473458]R(i)表示實際卸貨點為L中的第R(i)個道路節(jié)點求解卸貨點間的最短路徑，首先我們需要得到記錄連接節(jié)點的道路權值的鄰接矩陣A。由于該區(qū)域內(nèi)公路節(jié)點繁多，道路連接復雜。我們首先給出該區(qū)域內(nèi)所有公路節(jié)點的經(jīng)緯度矩陣L，L(i,1)表示第i個節(jié)點經(jīng)度，L(i,1)表示第i個節(jié)點緯度；公路信息矩陣X，X(i,1)表示第i條公路節(jié)點1經(jīng)度，X(i,2)表示緯度，X(i,3)表示節(jié)點2經(jīng)度，X(i,4)表示節(jié)點3緯度，X(i,5)表示公路權值，近似等于兩節(jié)點距離。對于每個節(jié)點，在區(qū)域內(nèi)節(jié)點并不多且經(jīng)度有效數(shù)字足夠多的情況下，我們認為經(jīng)度與節(jié)點一一對應，即可用該節(jié)點經(jīng)度檢索此節(jié)點。確定A（i，j）權值時，先由L(i,:)確定節(jié)點i經(jīng)緯度，篩選出X中節(jié)點1經(jīng)緯度相等的行，再由L(j,:)確定節(jié)點j經(jīng)緯度，從前面篩選出的行中再篩選出連接兩節(jié)點的道路，令A（i，j）等于其距離。由于可能存在j為節(jié)點1，i為節(jié)點2的情況，將i，j調(diào)換，重復上述步驟。最后將未找到符合道路的A（i，j）置為∞，A（i,i）置為0，得到最終結(jié)果，具體代碼見附錄。A的部分數(shù)值如圖其中100000表示無道路直接相連。計算卸貨點間的最短距離，我們最初采用狄克斯特拉算法，但發(fā)現(xiàn)必須對數(shù)百個公路節(jié)點由起始點開始由近及遠進行排序，無法計算出結(jié)果。于是我們改用弗洛伊德算法。弗洛伊德算法又稱為插點法，是一種用于尋找給定的加權圖中多源點之間最短路徑的算法。我們先選定一節(jié)點k，然后尋找與k直接相連的節(jié)點i，j，若D(i，j)>A(i,k)+A(k,j),則令D(i，j)=A(i,k)+A(k,j)。如此往復，k、i、j均由1到n遍歷一遍，得到任意兩節(jié)點間的最短路徑矩陣D。D的部分數(shù)值如圖接著我們通過卸貨點標號向量R從D中篩選出我們需要的卸貨點間最短路徑矩陣d確定貨車前往各個卸貨點并返回的最短路徑顯然，貨車需要從起點出發(fā)經(jīng)過且只經(jīng)過一次各個卸貨點并返回，構(gòu)成一個回路，求解它的最短路徑。我們采用最短哈密頓回路方法。哈密頓圖是一個無向圖，由指定的起點前往指定的終點，途中經(jīng)過所有其他節(jié)點且只經(jīng)過一次。在圖論中是指含有哈密頓回路的圖，閉合的哈密頓路徑稱作哈密頓回路。通過哈密頓回路來求解回路最短路的方法稱為最短哈密頓回路法。任取初始回路C=[12345…n1],對所有1<i+1<j<n，若w(i,j)+w(i+1,j+1)<w(i,j+1)+W(j,j+1),其中w(i,j)表示i點與j點間的距離，則在中刪去邊(i,i+1)和(j,j+1)而插入新邊(i,j)和(i+1,j+1),形成新的哈密頓圈,即C=[12…ij…i+1j+1…n1],對C重復這一步驟，直到條件不滿足為止，由此可以求出往復一周的最段路徑（具體代碼見附錄）。各卸貨點按在d中的順序標記為1-7，選定初始回路C=[12345671],經(jīng)過計算，最短回路為C=[15742631]，最短路徑sum=31.952632216316580。改變初始點，重復七次可得到最短路徑C=[65127436]，sum(min)=17.965393230597410。根據(jù)以上方法，便可得出所有分區(qū)的最短路徑。附錄：Matlab代碼%A（i,j）表示i節(jié)點到j節(jié)點的道路距離，100000表示兩點不直接連接%L為分區(qū)內(nèi)所有節(jié)點坐標%X為所有道路信息%求解鄰接矩陣AA=[];n=length(L(:,1));m=length(X(:,1));fori=1:nforj=i+1:np=[];fork=1:mifX(k,1)==L(i,1)p=[pk];end;end;fork=1:length(p)ifX(p(k),3)==L(j,1)A(j,i)=X(p(k),5);A(i,j)=X(p(k),5);end;end;p=[];fork=1:mifX(k,3)==L(i,1)p=[pk];end;end;fork=1:length(p)ifX(p(k),1)==L(j,1)A(j,i)=X(p(k),5);A(i,j)=X(p(k),5);end;end;end;end;fori=1:nforj=1:nifi~=j&&A(i,j)==0A(i,j)=100000;end;end;end;%S理想卸貨點坐標%R中存放實際卸貨點標號min=1000000;m=length(S(:,1));R=1:1:m;fori=1:mforj=1:length(L(:,1))La=(L(j,1)-S(i,1))^2+(L(j,2)-S(i,2))^2;ifLa<minmin=La;R(i)=j;end;end;min=1000000;end;%求解任意節(jié)點間的最短路（弗洛伊德算法）D=[];fori=1:nforj=1:nD(i,j)=10000;endendfork=1:nfori=1:nforj=1:nifA(i,k)+A(k,j)<D(i,j)D(i,j)=A(i,k)+A(k,j);endendendendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);endendendendd=[];%存放所需的用作卸貨點的節(jié)點的數(shù)據(jù)fori=1:7forj=1:7d(i,j)=D(R(i),R(j));endend%哈密頓圈算法求出最短回路C=[12345671];La=length(C);min=10000;fori=1:7F=C;F(1)=i;F(7)=i;F(i)=1;f=1;whilef>0f=0;form=1:La-3forn=m+2:La-1ifd(F(m),F(n))+d(F(m+1),F(n+1))<d(F(m),F(m+1))+d(F(n),F(n+1))f=1;