第20次課 運輸調(diào)運決策（車輛行駛最短路徑）求解方法

第7章運輸決策第20次課運輸調(diào)運決策（車輛行駛最短路徑）求解方法3知識點1運輸調(diào)運決策求解方法-最小元素法、沃格爾法知識點2車輛行駛最短路徑求解方法-里程節(jié)約算法、節(jié)點掃描算法主要知識點（重難點）4問題思考學習啟示1.什么是“三段式”教學模式（方法）？2.什么是“三段式”學習模式（方法）？寫寫畫畫：進行數(shù)字計算，數(shù)字如何計算得來？（關(guān)鍵：步驟一，一通百通）2.

畫圖，畫出示意圖、位置圖。7.3運輸計劃編制

運輸計劃編制，即車輛運行路線和時間安排，是車輛運行路線選擇問題的延伸，受到的約束條件更多。

例如，(1)每個停留點規(guī)定的提貨數(shù)量和送貨數(shù)量；(2)所使用的多種類型的車輛的載重量和載貨容積；(3)車輛在路線上休息前允許的最大的行駛時間；(4)停留點規(guī)定的在一天內(nèi)可以進行的提貨的時間；(5)可能只允許送貨后再提貨的時間；(6)司機可能只能在一天的特定時間進行短時間的休息或進餐。

這些約束條件大大地使問題復(fù)雜化，甚至使人們難以去尋求最優(yōu)化的解。這里的問題是車輛是從一個倉庫出發(fā)，向多個停留點送貨，然后在同一天內(nèi)返回到該倉庫，要安排一個滿意的運行路線和時間。7.3.1制定調(diào)運方案

運輸問題

人們在從事生產(chǎn)活動中，不可避免要進行物資調(diào)運工作，如某時期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區(qū)。根據(jù)各地的生產(chǎn)量和需求量及各地之間的運輸費用，如何制定一個運輸方案，使總的運輸費用最小，這樣的問題就是運輸問題。7.3.1制定調(diào)運方案

【例7-3】如圖7-12所示的網(wǎng)絡(luò)圖，有A1，A2，A3三個產(chǎn)糧區(qū)，可供應(yīng)糧食分別為10，8，5（萬噸），現(xiàn)將糧食運往B1，B2，B3，B4四個銷糧區(qū)，其需求量分別為5，7，8，3（萬噸）。箭條旁的數(shù)字為產(chǎn)量地到需求地（銷地）的運價（元/噸），圖7-12也可以用表7-3表示，問如何安排一個運輸計劃，使總的運輸費用最少。7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

表上作業(yè)法

表上作業(yè)法求解步驟：

先用最小元素法或沃格爾法尋找初始調(diào)運方案，再通過閉合回路法或位勢法微調(diào)調(diào)運方案，直至得到最佳方案。

（1）最小元素法

最小元素法的基本思想是就近供應(yīng)，即從最小的運價開始盡量滿足供銷關(guān)系，然后從次小的運價開始，一直到給出初始基本可行解為止。

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

（2）沃格爾（Vogel）法

最小元素法的缺陷是：為了節(jié)省一處的費用，有時造成在其他處要多花幾倍的運費。沃格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次最小運費，這就是一個差額，差額越大，說明不能按最小運費調(diào)運時，運費增加越多。因而對差額最大處，就應(yīng)當采用最小運費調(diào)運。7.3.1制定調(diào)運方案

沃格爾法(Vogel'smethod)，是線性規(guī)劃中用來編制最優(yōu)計劃方案的方法。在運輸問題上，對于每個供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的運價中找出最小運價和次小運價，并稱這兩個運價之差為該供應(yīng)地或銷售地的罰數(shù)。若罰數(shù)的值不大，當不能按照最小運價安排運輸所造成的運費損失不大；反之，如果罰數(shù)的值很大，不按照最小運價組織運輸就會造成很大損失，故應(yīng)盡量按照最小運價安排運輸。

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.1制定調(diào)運方案

7.3.4

里程節(jié)約算法

節(jié)約法，用于多車輛路徑問題，能同時確定車輛數(shù)及車輛行駛路徑，其目標是使所有車量總里程最短，且使所需車輛總數(shù)最少。

節(jié)約法的基本原理是：如果將運輸問題中的兩個回路合并成一個回路，就對縮短線路總里程（即節(jié)約了距離）并減少了一輛卡車。如圖7-22所示，將兩個回路合并成一個回路后，節(jié)約的距離為ΔAB=CAO+CBO-CAB。7.3.4

里程節(jié)約算法

7.3.4

里程節(jié)約算法

7.3.5

節(jié)點掃描算法

掃描法，是一種先進行客戶分群在確定車輛最短路線的算法。求解過程分為兩步：第一步是指派車輛服務(wù)的站點或客戶點；第二步是決定每輛車的行車路線。

用掃描法確定車輛運行路線的方法十分簡單，可以通過手工計算或直接在圖紙上完成，也可以利用計算機編程求解。一般來說，它求解所得方案的誤差率在10%左右，這樣的誤差率通常是可以被接受的，因為調(diào)度員往往需要在接到最后一份訂單后一小時內(nèi)就制定出車輛運行路線。由于掃描法是分階段操作的，因此有些時間方面的問題，如路線上的總時間和停留點工作時間的約束等，難以妥善地處理。

7.3.5

節(jié)點掃描算法

掃描法的原理：先以物流中心為原點，計算出所有客戶點的極坐標，然后依角度大小以逆時針或順時針方向掃描，若滿足車輛裝載容量即劃分為一群；在劃分完的每個客戶群內(nèi)，用最短路徑算法求出車輛最佳行駛路徑。具體步驟如下：①以物流中心為原點，將所有客戶點的極坐標計算出來。②選定極坐標軸，按順時針或逆時針方向旋轉(zhuǎn)，依角度大小開始掃描。③將掃描經(jīng)過的客戶點需求量進行累加，當客戶需求總量達到一輛車的載重量限制且不超過載重量極限時，就將這些客戶劃分為一群，即由同一輛車完成送貨服務(wù)。接著，按照同樣的方法對其余客戶劃分新的客戶群，指派新的車輛。④重復(fù)步驟③，直到所有的客戶都被劃分到一個群里。⑤在每個群內(nèi)部用最短路徑方法求出車輛行駛最短路徑。7.3.5

節(jié)點掃描算法

7.3.6

運輸路線和時間安排原則

除根據(jù)定量計算的最優(yōu)路徑和調(diào)運方案外，運行路線和時間安排的決策者，如車輛調(diào)度員，在長期的實際工作經(jīng)驗中為滿意的運行路線和時間安排提煉出下列八條原則。7.3.6

運輸路線和時間安排原則

1．將相互接近的停留點的貨物裝在一輛車上運送車輛的運行路線應(yīng)將相互接近的停留點串起來，以便停留點之間的運行距離最小化，這樣也就使總的路線上的運行時間最小化。圖7-26所示的是將有關(guān)停留點的貨分配給車輛，從而將各點串起來的示意圖。其中圖7-26(a),串得不合理，車輛的運行路線長，要盡量避免，圖7-26(b)是合理的串法。7.3.6

運輸路線和時間安排原則

7.3.6

運輸路線和時間安排原則

2．將集聚在一起的停留點安排同一天送貨當停留點的送貨時間是定在一周的不同天數(shù)進行時，應(yīng)當將積聚在一起的停留點安排在同一天送貨，要避免不是同一天送貨的停留點在運行路線上重疊，這樣可有助于使所需的服務(wù)車輛數(shù)目最小化以及一周中的車輛運行時間和距離最小化。圖7-27所示的是好的集聚和差的集聚的例子。7.3.6

運輸路線和時間安排原則

7.3.6

運輸路線和時間安排原則

3．運行路線從離倉庫最遠的停留點開始合理的運行路線應(yīng)從離倉庫最遠的停留點開始將該集聚區(qū)的停留點串起來，然后返回倉庫。一旦確認了最遠的停留點之后，送貨車輛應(yīng)滿載貼鄰這個關(guān)鍵停留點的一些停留點的貨物。這輛運貨車滿載后，再選擇另一個最遠的停留點，用另一輛運貨車轉(zhuǎn)載貼鄰第二個最遠停留點的一些停留點的貨物，按此程序進行下去，直至所有停留點的貨物都分配給運貨車輛。4．一輛運貨車順次途經(jīng)各停留點的路線要成凸狀運貨車輛順序途經(jīng)各停留點的路線不應(yīng)交叉，并應(yīng)成凸狀。不過，停留點工作時間的約束和在停留點送貨后再提貨的要求往往會導致路線交叉。7.3.6

運輸路線和時間安排原則

5．最有效的運行路線通常是使用大載重量的送貨車輛最好是使用一輛載重量大到能將路線上所有停留點所要求運送的貨物都裝載的送貨車，這樣一來可將服務(wù)備停留點的總的運行距離或時間最小化。因此在多種規(guī)格車型的車隊中，應(yīng)優(yōu)先使用載重量最大的送貨車。6．提貨應(yīng)混在送貨過程中進行，而不要在運行路線結(jié)束后再進行提貨應(yīng)盡可能在送貨過程中進行，以減少交叉路程量，而在送貨結(jié)束后再進行提貨經(jīng)常會發(fā)生交叉路程。提貨混在送貨過程中進行，究竟能做到什么程度，則取決于送貨車輛的形狀、提貨量以及所提的貨物對車輛內(nèi)后續(xù)送貨通道的影響程度。7.3.6

運輸路線和時間安排原則

7．對偏離集聚停留點路線遠的單獨的停留點可應(yīng)用另一個送貨方案偏離集聚停留點遠的停留點，特別是那些送貨量小的停留點一般要花費大量的司機時間和車輛費用，因此使用小載重量的車輛專門為這些停留點送貨是經(jīng)濟的，其經(jīng)濟效益取決于該停留點的偏離度和送貨量。偏離度越大，送貨量越小，使用小載重量的車輛專門為這些停留點送貨越經(jīng)濟。另一個可供選擇的方案是租用車輛為這些停留點送貨。8．應(yīng)當避免停留點工作時間太短的約束停留點工作時間太短常會迫使途經(jīng)停留點的順序偏離理想狀態(tài)。由于停留點的工作時間約束一般不是絕對的，因此如果停留點的工作時間確實影響到合理的送貨路線，則可以與停留點商量，調(diào)整其工作時間或放寬其工作時間約束。7.3.6

運輸路線和時間安排原則

上述的原則可以很容易傳授給運作人員，從而幫助他們制定出滿意的（不一定必須是最優(yōu)的）現(xiàn)實可行的合理路線和時間安排。當然上述的原則也僅是合理路線設(shè)計的指引，運作人員面對的車輛運作的許多復(fù)雜情況并不是上述原則所能全部包容的。遇到特殊的約束條件，運作人員要根據(jù)自己的經(jīng)驗隨機處理。本課小結(jié)本課講授知識點，主要包括：知識點1