第12章貨物運輸的優化求解

Chapter12FreightageOptimization主要內容：產銷運輸問題，分配運輸問題，網絡流問題，送貨集貨問題的模型建立、求解過程。重點掌握：產銷運輸問題，分配運輸問題，網絡流問題，送貨集貨問題模型建立、最優解求取。7/23/20231貨物運輸的優化求解：第一節產銷運輸問題第二節分配運輸問題第三節網絡流問題第四節送貨集貨問題7/23/20232現代物流學12.1產銷運輸問題

12.1ProductionandSaleTransportationProblem12.1.1產銷平衡的運輸問題12.1.1.1模型分析某種物資有m個產地A1,A2,…,Am，其供應量分為a1,a2,…,am；有n個銷地B1,B2,…,Bn，其銷量分為b1,b2,…,bn；產地物資供應量總和等于銷地物資銷量（需求量）總和；從產地Ai到銷地Bj的物資量和單位物資運價分別為xij,cij，求此時調運物資最佳方案。7/23/20233現代物流學對此問題可有下述線性規劃模型：7/23/20234現代物流學12.1.1.2表上作業法求解根據上述模型的特殊結構而建立的表上作業法比起用單純形法要簡單得多。其思路為：由初始運輸方案開始，通過檢驗、改進，最后獲得最優運輸方案。設有兩個煤礦供應三個城市用煤，煤礦A1和A2的日產量分別為a1=200t；a2=250t。三城市（B1,B2,B3）的日銷量分別為b1=100t，b2=150t，b3=200t。假定每t貨物的社會運輸費與出行公里線性有關，取cij代表煤礦i至城市j的最短距離。已知c11=90km，c12=70km，c13=100km，c21=80km，c22=65km，c23=80km。問如何安排運輸時運輸費用最省？例7/23/20235現代物流學解：設xij為煤礦i運往城市j的煤量，根據每個煤礦產煤總量和城市的用煤總量，xij(i=1,2;j=1,2,3)必須滿足下列條件：x11+x12+x13=200x21+x22+x23=250x11+x21=100x12+x22=150x13+x23=200目標函數為：minz=90x11+70x12+100x13+80x21+65x22+80x23。7/23/20236現代物流學1、列運輸平衡表列表時要求表內供銷平衡，并將運費標入表內空格。需供B1B2B3供應量A1x1190x1270x13100200A2x2180x2265x2380250需求量1001502004507/23/20237現代物流學

2、建立初始調運方案采用最小元素法，即在平衡表中挑取運價最小或較小的供需點格子盡量優先分配的調運方法。需供B1B2B3供應量A109070200100200A2100801506580250需求量1001502004507/23/20238現代物流學

3、方案的檢驗和調整（1）閉回路。從調運方案的任意空格出發，沿水平方向或垂直方向前進，而遇到填有數字的方格，折轉90o前進，當然可以直接穿過數字格和空格，但只能遇有數字的格才能折轉，只能水平、垂直方向前進，不能對角線移動，這樣經過多次折轉直到回到原來出發的空格，形成一條閉回路。（2）位勢法檢驗①由方案表列出檢驗表。表中行列數與方案表一樣，運價在每一格的右上角，原方案表中的空格填寫檢驗數，原方案表中的數字格為檢驗表的空格，原方案表中的供應量、需求量寫行與列的位勢，稱為行或列位勢格。7/23/20239現代物流學需供B1B2B3uiA10907020010090A210080150658080vj0-1510位勢表

③求檢驗數。若空格位于第i行第j列，則其檢驗數σij按下式求出：σij=cij-ui-vj②求位勢。記第i行位勢為ui，第j列位勢為vj，通常可任選一格填0作為該格的位勢。而其他格位勢可由則可求得：cij=ui+vj。7/23/202310現代物流學需供B1B2B3uiA190-57010090A28065-108080vj0-1510檢驗數表由上表可知，存在負的檢驗數，表明不是最優的，需要進行調整。7/23/202311現代物流學（3）調整運輸方案①確定閉回路。在需調整的運輸方案表上選取對應的檢驗數為負的且絕對值最大的格為檢驗格，從檢驗格出發在運輸方案表上作閉回路。需供B1B2B3供應量A109070200100200A2100801506580250需求量100150200450閉回路表7/23/202312現代物流學②在閉回路上做運輸量最大的調整，得出新的運輸方案。從空格開始，沿閉回路在格偶數格中挑選運量最小的作為調整量，調整閉回路各點的運輸量。需供B1B2B3供應量A11009070100100200A2801506510080250需求量100150200450新運輸方案1表7/23/202313現代物流學由于上表中有負檢驗數，故需繼續進行調整，得新運輸方案表。需供B1B2B3供應量A11009010070100200A280506520080250需求量100150200450新運輸方案2表7/23/202314現代物流學對新運輸方案表進行檢驗。需供B1B2B3uiA190701510090A2-580658085vj0-20-5新運輸方案2檢驗表7/23/202315現代物流學繼續進行調整。需供B1B2B3供應量A1509015070100200A250806520080250需求量100150200450新運輸方案3表7/23/202316現代物流學此時，檢驗數全是正數，因此運輸方案3表中的運輸方案為最優方案。需供B1B2B3uiA190701010090A2805658080vj0-200新運輸方案3檢驗表7/23/202317現代物流學12.1.2產銷不平衡時的運輸問題

2、銷大于產的運輸問題對于銷量大于產量，即的運輸問題，必然有一些銷地不能得到滿足，發生缺貨，此時引入虛擬供應點，并設其相應運價為0。這樣，就可以用產銷平衡的表上作業法求解銷大于產的運輸問題。1、產大于銷的運輸問題對于產量大于銷量，即的運輸問題，必然有些產地的產品不能安排運輸，此時引入虛擬需求點，令其需量等于總供量與總需量之差，并設其相應運價為0。這樣，就可以用表上作業法求解產大于銷的運輸問題。7/23/202318現代物流學12.2分配運輸問題

12.2AssignmentTransportationProblem

12.2.1

模型分析某材料廠有B1、B2、B3三臺叉車可分配給A1、A2、A3三個倉庫進行搬運作業，其中任一叉車都可以再任一倉庫進行搬運工作，只是搬運作業費不同，各臺叉車相應作業費cij，如表所示，要求一臺叉車只分配給一個倉庫使用，試求搬運作業費用最小的分配方案。7/23/202319現代物流學效率矩陣表171922B3242015B2353125B1A3A2A1倉庫cij叉車根據問題引入變量xij，并按以下規定取值：其中，i=1,2,…,n；j=1,2,…,n。7/23/202320現代物流學當問題要求極小時，有數學模型：7/23/202321現代物流學

12.2.2匈牙利算法匈牙利算法的主要依據：在效率矩陣的任何行或列中，加上或減去同一常數，并不改變最優分配。利用此性質，可使原效率矩陣變換為含有很多0元素的新效率矩陣，找出在其中的位于不同行、列的n個獨立的0元素，將其取值為1，其他元素取值為0，即的原分配問題的最優解。7/23/202322現代物流學效率矩陣為：例題第一步：變換效率舉陣，使其每一行和每一列都至少有一個0元素。7/23/202323現代物流學第二步：試求最優分配方案。從1行開始，依次檢查各行，找出只有一個未標記的0元素的行，并講該元素用“”表示，與該元素同行同列的其他0元素則用“Φ”表示。對應的任務僅由所對應的單位去完成，此單位不再去完成其他任務，這項任務也不再由其他單位完成。依次檢查各列，找出只有一個未標記的0元素的列，并講該元素用“”表示，與該元素同行同列的其他0元素則用“Φ”表示。重復上述步驟，直到效率矩陣中沒有未標記的0元素。7/23/202324現代物流學0第三步：繼續調整效率矩陣。對每一個元素畫一條水平線或垂直線，使這些線覆蓋所有0元素。在直線不穿過的所有元素中找到最小元素。在沒有水平線的各行減去此最小元素，有垂直線的各列加上此最小元素，得到新的效率矩陣。-1-17/23/202325現代物流學已經得3個0元素，故得最優分配方案為：A1→B1，A2→B2，A3→B3則，根據原效率矩陣，3叉車總搬運作業費為：25+20+17=60（元）第四步：回第二步，直到求出最優分配方案。7/23/202326現代物流學12.2.3巡回運輸問題（旅行商問題）在單網點配送中，物流網點向所屬用戶送貨，各用戶的需求量bi（i=1,2,3,…,n），貨車載重量為Q，若滿足，則該網點只需一輛貨車即可。顯然，這種情況下使費用最省的方案是合理安排貨車訪問各用戶的順序，使貨車的巡回路線的總距離最短，這也就是旅行商問題。7/23/202327現代物流學已知5用戶間距離如表，其中d(i,j)=∞表示從第i個用戶到第j個用戶是沒有意義的，用戶1為物流網點所在位置，如果只考慮將每個用戶都當作一個達到用戶，則對每個出發用戶都要選擇一個到達用戶，爾每個到達用戶只能有一個出發用戶到達該地，將問題變成了一個分配問題，可用匈牙利算法求解。到達出發1234512345∞21171∞65576∞44432∞53416∞用戶間距表例題7/23/202328現代物流學解:

第一步：令d(i,i)=∞，不存在通路的也記為∞，的距離陣，通常d(i,j)與d(j,i)不一定相同，即矩陣不一定對稱。

第二步：對距離矩陣用匈牙利法求解，若得到無環路的路線，則就是最優路線；如路線有環路，就不是最優路線，但所走總距離給出了旅行商問題總距離的下界。7/23/202329現代物流學得不考慮環路下的最優方案：1→2，2→4，4→1，3→5，5→3則，所走總距離為：1+3+1+1+4=10可以看出上述路線存在環路，不是原問題的最優路線，但給出了原問題的下界10。7/23/202330現代物流學

第三步：出現環路時，打開節點個數最少的環路。即在此環路上考慮某段路線不通的各種情況，分別用匈牙利法求解，其中距離最短又無環路的路線即為最優路線。本例中，出現兩個環路，1→2→4→1和3→5→3，打開節點數少的環路，分別令d(3,5)=∞和d(5,3)=∞求解。7/23/202331現代物流學（1）當d(3,5)=∞時，用匈牙利法求解。可得無環路的最優方案：5→3→4→1→2→5則，所走總距離為：1+4+2+1+4=12。7/23/202332現代物流學（2）當d(5,3)=∞時，用匈牙利法求解。可得無環路的最優方案：1→2,2→1,3→5,4→3,5→4則，所走總距離為：1+2+1+4+5=13。7/23/202333現代物流學可以看到，上述方案出現環路1→2→1和3→5→4→3，如果打開環路求解，其總距離一定不小于13，而已經得到總距離為12的路線，故不必再作計算。因此得上述旅行上的最優路線為：5→3→4→1→2→5；總距離為：12。7/23/202334現代物流學12.2.4旅行商問題的神經網絡求解1、連續Hopfield神經網絡模型（a）Hopfield神經元7/23/202335現代物流學（b）Hopfield神經網絡7/23/202336現代物流學設有n個神經元互連，則可用下述非線性微分方程描述：上式可以定義系統的能量函數為：7/23/202337現代物流學可以證明，對于該能量函數，恒有，即當，網絡達到穩定。應用網絡的這一特性，可以進行優化問題的求解。求解時，只需將優化問題的目標函數轉化成能量函數的形式，然后應用上述微分方程運算到網絡收斂即可。通常在用Hopfield神經網絡求解實際問題時，一般忽略能量式中得積分項，將能量函數簡化為下式，以便目標函數的映射。

7/23/202338現代物流學12.3網絡流問題

12.3NetworkFlowProblem12.3.1網絡最大流問題1、問題的提出已知連接產地V1與銷地Vn的交通網，每一弧（Vi,Vj）代表從Vi到Vj的運輸線，產品經由Vi輸送到Vj，弧旁括號外的數字cij為弧的容量，括號內的數字xij為Vi到Vj的貨運量，要求合理安排xij，使V1到Vn的貨運量最大。7/23/202339現代物流學2、尋求最大流的標號法對于包含n個頂點V1,V2,…,Vn的網絡流，V1為發點，Vn為收點，各段弧（Vi,Vj）上容量為cij，設是一個可行流，判斷它是否最大流及對它進行調整，關鍵在于求出其增廣鏈，標號法就是基于此來尋求最大流的。3、最小費用最大流問題解最小費用最大流問題的基本思想是，通過已知的由V1到收點Vn的最小費用流x，尋求其對應的最小費用增廣鏈，沿此增廣鏈去調整x，實現最大流。7/23/202340現代物流學

第三步：重復第二步，直到所有的頂點都標號為止，每個頂點標號內的第二個數字即為V1到該頂點得最短距離，運用反向追蹤可找出此最短路徑。4、最短路徑問題Dijkstra算法如下：第一步：給發點V1以標號（1,0），L11=0。第二步：從以標號頂點出發，找出與這些頂點Vi相鄰所有頂點，若，則對Vj標號為（i,L1j）7/23/202341現代物流學12.4送貨集貨問題

12.4ProblemofGoodsDeliveringandCollection

12.4.1模型分析送貨問題，是指在中心倉庫中，需要向幾個分倉庫送貨，每個分倉庫對貨物由一定的需求，運送貨物的車輛在中心倉庫裝滿貨后發出，把貨送到各分倉庫卸貨，完成任務后返回中心倉庫，求滿足貨運需求的費用最小的車輛行駛路線。7/23/202342現代物流學其中，7/23/202343現代物流學12.4.2掃描法求解（1）在地圖或方格圖中確定所有分倉庫的位置。（2）自中心倉庫始沿任一方向向外劃一條直線。（3）沿順時針或逆時針方向旋轉該直線直到與某分倉庫相交，相交時考慮在線路上增加該分倉庫運貨任務時，是否會超過車輛的載貨容量（顯示雍容量最大的車輛），如果不會，線路增加該分倉庫，并繼續旋轉直線到下一分倉庫。否則執行步驟（4）。（4）構成一條送貨線路。7/23/202344現代物流學（5）從不包含在上一條線路中的分倉庫開始，繼續旋轉直線，繼續步驟（3），直到所有得分倉庫的送貨任務都已安排在不同線路中。（6）應用TSP問題的求解算法，排定各線路中分倉庫的先后順序，使各線路的路徑最短。7/23/202345現代物流學

12.4.3節約法求解在對多個分倉庫進行送貨時，將其中能取得最大“節約里程”的兩個分倉庫合并在一條線路上，進行巡回送貨，能夠獲得最大的里程節約。同時，在不超過運輸車輛載貨容量的條件下，設法使這條選定的巡回路線，盡可能將其他分倉庫按其所能取得“節約里程”的打下納入這條線路中，則能獲得更大的里程節約效果。7/2