供應鏈運輸管理（運輸路線的選擇）

供應鏈運輸管理《智慧港航供應鏈》藍賢鋼運輸路線的選擇3運輸路線的選擇一、起、止點不同的單一路徑規(guī)劃

這類路徑規(guī)劃問題稱為最短路問題。最短路徑問題是線路優(yōu)化模型理論中最為基礎的問題之一。

問題描述：假設有一n個節(jié)點和m條弧的連通圖G（Vn,Em),并且圖中的每條?。╥,j）都有一個長度cij(或者費用cij)，則最短路徑問題為：在連通圖中找到一條從節(jié)點1到節(jié)點n距離最短（或費用最低）的路徑。

求解算法：（1）Dijkstra算法；（2）逐次逼近法；（3）Floyd算法。下面通過一個實例對該類問題進行說明。4例1：

某運輸公司簽訂了一項運輸合同，要把A市的一批貨物運送到B市，該公司根據(jù)這兩個城市之間可選擇的行車路線的地圖繪制了如圖所示的公路網絡。圖中，圓圈也稱節(jié)點，代表起點、目的地和與行車路線相交的其他城市。鏈代表兩個結點之間的公路，每一條公路都標明運輸里程。A市B市:5-1A、B兩地之間運輸路線示意圖

問題：從A市出發(fā)到達B市，可以有很多條路線可以選擇。如何選擇運輸路線，才能使總路程的長度最短？5解答：最短路的計算方法（1）找出第n個距起點最近的節(jié)點。對n=1,2,…，重復此過程，直到所找出的最近節(jié)點是終點。（2）在前面的迭代過程中找出（n-1）個距起點最近的節(jié)點，及其距起點最短的中徑和距離，這些節(jié)點和起點統(tǒng)稱為已解的節(jié)點，其余的稱為未解節(jié)點。（3）每個已解的節(jié)點和一個或多外未解的節(jié)點相連接，就可以得出一個候選點—連接距離最短的未解點。如果有多個距離相等的最短連接，則有多個候選點。（4）將每個已解節(jié)點與其候選點之間的距離累加到該已解節(jié)點與起點之間最短路徑的距離上，所得出的總距離最短的候選點就是第n個最近的節(jié)點，其最短路徑就是得出該距離的路徑（若多個候選點都得出相等的最短距離，則都是已解節(jié)點）。6步驟直接連接到未解節(jié)點的已解節(jié)點與其直接連接的未解結點相關總成本第n個最近解點最小成本最新連接11123411241-22122345114+7=114+2=6562-5312553446114+7=116+3=96+8=14495-4414453366119+1=109+4=136+8=143104-3534566610+2=129+4=136+8=146123-6最短路徑法的計算步驟表通過上表的計算可知，最短路徑為1-2-5-4-3-6，最短距離為12。最短路徑法適合利用計算機進行求解，把運輸網絡中的鏈和節(jié)點的資料都存入數(shù)據(jù)庫中，選好起點和終點后，可很快算出最短路徑。7二．多個起、止點的路徑規(guī)劃當有多個貨源和多個目的地時，就需要指定目的地的供貨地，同時要找到供貨地、目的地之間的最佳路徑。例2某公司下屬三個倉庫，供應四個客戶的需要，三個倉庫的供應量和四個客戶的需求量，以及由各倉庫到各客戶的運輸單價如下表所示。求運輸費用最少的運輸方案。

銷地客戶1客戶2客戶3客戶4供應量運價產地倉庫A311310700倉庫B1928400倉庫C74105900需求量30060050060020008表上做業(yè)法，該方法適合于對相對簡單的問題進行求解，求解過程方便直觀，而且由于計算量不大，可以用手工直接完成。利用表上作業(yè)法有兩個基本步驟：（1）確定初始調運方案最小元素法是按運價表依次挑選運費小的供-需點組合，盡量優(yōu)先安排運費最低組合的方法。3113101928734105

銷地客戶1客戶2客戶3客戶4供應量運價產地倉庫A400300700倉庫B300100400倉庫C600300900需求量300600500600表1初始調運方案9（2）初始方案的檢驗最優(yōu)方案的數(shù)字特征—檢驗數(shù)：閉回路：從理論上講，對于表上作業(yè)法的初始方案來說，從調運方案表上的一個空格出發(fā)，存在一條且僅存在一條以該空格（用xij表示）為起點，以其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉回路。這個閉回路有以下性質：每個頂點都是轉角點；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行（列）若有閉合回路的頂點，則必有兩個。只有從空格出發(fā)，其余各轉角點所對應的方格內均填寫數(shù)字時，所構成的閉合回路才是我們所說的閉回路；另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。10

銷地客戶1客戶2客戶3客戶4供應量產地倉庫A400300700倉庫B300100400倉庫C600300900需求量300600500600

表2給出了單元格（1，1）和（3，1）所形成的閉回路：（1，1）—（1,3）—(2，3)—（2，1）—（1，1）（3，1）—（2，1）—（2，3）—（1，3）—（1，4）—（3，4）—（3，1）。其他空格的閉回路與此同理。在調運方案內的每個空格所形成的閉回路上，作單位物資的運量調整，總可以計算出相應的運費是增加還是減少。把所計算出來的每條閉回路上調整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。如果檢驗數(shù)小于0，表示在該空格的閉回路上調整運量會使運費減少；相反，如果檢驗數(shù)大于0，則會使運費增加。表2初始調運方案11用閉回路法求檢驗數(shù)時，需給每一空格找一條閉回路。當產銷點很多時，這種計算很繁，可以用較為簡便的方法“位勢法”求解。設u1,u2,…,um；v1,v2,…,vn，是對應運輸問題的m+n個約束條件的對偶變量。在初始調運方案中x13,x14,x21,x23,x32,x34是基變量，這時對應的檢驗數(shù)是：基變量檢驗數(shù)x21c21-(u2+v1)=0設v1=0，并且c21=1所以u2=1x23c23-(u2+v3)=02-(u2+v3)=0x13c13-(u1+v3)=03-(u1+v3)=0x14c14-(u1+v4)=010-(u1+v4)=0x34c34-(u3+v4)=05-(u3+v4)=0x22c22-(u2+v2)=04-(u2+v2)=012通過這些方程可以求得u1=2u2=1u3=-3v1=0v2=7v3=1v4=8在初始解調運方案中增加一行一列，在列中填入ui,在行中填入vi。接下來，按σij=cij-(ui+vj)計算所有空格的檢驗數(shù)。完成后的表格見表6.6。3113101928734105

銷地客戶1客戶2客戶3客戶4ui運價產地倉庫A12002倉庫B010-11倉庫C100120-3vi0718表3檢驗數(shù)表格13（3）方案調整判定一個初始調運方案不是最優(yōu)調運方案的標準，是在檢驗數(shù)表格中出現(xiàn)負值的檢驗數(shù)。如果檢驗數(shù)的負值不止個時，一般選擇負檢驗數(shù)絕對值最大的空格作為具體調整對象。從表3可以發(fā)現(xiàn)，單元格x24的檢驗數(shù)是負數(shù)，因此對其進行調整，具體過程如表4所示。x13400+100=500x14300-100=200x23100-100=0x240+100=100表4調動方案調整表

從單元格x24開始，沿閉回路在各奇數(shù)次轉角點中挑選運量的最小數(shù)值作為調整量。在此將x23單元格的100作為調整量，將亮個數(shù)填入單元格x24內，同時調整該閉回路中其他轉角點上的運量，使各行、列保持原來的供需平衡，這樣注得到一個新的調運方案，如表5所示。143113101928734105

銷地客戶1客戶2客戶3客戶4供應量

運價產地倉庫A500200700倉庫B300100400倉庫C600300900需求量300600500600表5調整后的方案按新方案計算調運物資的運輸費用為：3×500+10×200+8×100+4×600+5×300=8500元新方案是否最優(yōu)方案，還需再進行檢驗。經計算，該新方案的所有檢驗數(shù)都是非負數(shù)，說明該方案已經是最優(yōu)方案了。15三．起點和終點相同的路徑規(guī)劃物流管理人員經常會遇到起點和終點相同的路徑規(guī)劃問題。例如，從某倉庫送貨到零售店然后返回的路線；從零售店到客戶地點配送的路線規(guī)劃。起點和終點重合的路徑問題一般被稱為“流動推銷員”問題（TSP,TravelingSalesmanProblem），是運籌學、圖論和組合優(yōu)化中的典型問題。

TSP問題一般描述如下：一個旅行者從出發(fā)地出發(fā)，經過所有要到達的城市后，返回到出發(fā)地，要求合理安排其旅行路線，使得總旅行距離（或旅行費用、旅行時間等）最短。人們已經提出不少方法來解決這類問題。如果某個問題中包含很多個點，要找到最優(yōu)路徑是不切實際的，因為許多現(xiàn)實問題的規(guī)模太大。啟發(fā)式算法是求解這類問題的好辦法。16

車輛路線安排問題（VRP,VehicleRoutingProblem）是指對物流配送的車輛進行優(yōu)化調度。該問題一般可以描述如下：對一系列裝貨點或（和）卸貨點，組織適當合理的行車路線，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量、數(shù)目限制、車輛行駛里程、時間限制等）下，達到一定的目標（如最短路程、最小費用、最短時間、最少車輛等）。該問題涉及了多輛交通工具的服務對象的選擇和路徑（服務順序）確定兩方面的問題。

VRP問題是組合優(yōu)化領域著名的NP難題之一，求解方法一般相當復雜，通常的做法是應用相關技術問題分解或者轉化為一個或多個已經研究過的基本問題（如旅行商問題、指派問題、最短路問題等），再使用相對比較成熟的基本理論和方法進行求解。車輛路線安排17運用VRP模型對實際問題進行研究時，一般需要考慮以下幾個方面的問題：（1）倉庫。倉庫的級數(shù)，每級倉庫的數(shù)量、地點和規(guī)模；（2）車輛。車輛的型號和數(shù)量，每種車輛的容積和運作費用，出發(fā)時間和返回時間，司機休息時間，最大的里程和時間限制；（3）時間窗口。由于各處的工作時間不同，每個站點每天只允許在特定的時間內取貨和/或送貨；（4）顧客。顧客需求，裝載、卸載，所處的地理位置，分離需求，優(yōu)先等級；（5）道路信息。車流密度，道路交通費用，距離或時間屬性；（6）貨物信息。貨物的種類多少，兼容性，貨物的保鮮；（7）運輸規(guī)章。工人每天的工作時間，車輛的周期維護。18（1）安排車輛負責相互距離最接近的站點的貨物運輸；（2）安排