運(yùn)輸線路決策培訓(xùn)資料

1、n第二節(jié) 運(yùn)輸線路決策在整個(gè)物流成本中，運(yùn)輸成本所占 比列為33%-67%，所以我們必須關(guān)注如 何降低運(yùn)輸成本問題，最大化地利用運(yùn) 輸設(shè)備和人員，優(yōu)化運(yùn)輸線路是降低運(yùn) 輸成本的關(guān)鍵。 （一）影響運(yùn)輸線路選擇的因素 1.成本因素 （1）運(yùn)輸成本（2）營運(yùn)成本 （3）運(yùn)輸線路建設(shè)成本和土地成本 （4）固定成本 2.非成本因素 （1）交通因素 （2）環(huán)保因素 （3）政策法規(guī)因素（二）運(yùn)輸路線決策 運(yùn)輸路線決策就是，找到運(yùn)輸網(wǎng)絡(luò)中的最 佳路線，以盡可能縮短運(yùn)輸時(shí)間或運(yùn)輸距離， 達(dá)到降低運(yùn)輸成本、改善運(yùn)輸服務(wù)的目標(biāo)。 運(yùn)輸路線決策問題有三種基本類型：一是起點(diǎn)和終點(diǎn)不同的單一路徑規(guī)劃；二是多個(gè)起點(diǎn)和終點(diǎn)的

2、路徑規(guī)劃； 三是起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃。一、起點(diǎn)和終點(diǎn)不同的單一路徑規(guī)劃 此類問題可以描述為在一個(gè)已知交通運(yùn)輸網(wǎng)絡(luò)中，尋 找從出發(fā)地到目的地的最佳路線。這里的“最佳”可以指 距離最短、時(shí)間最省或是費(fèi)用最少。 數(shù)學(xué)模型求網(wǎng)絡(luò)圖中二點(diǎn)之間的最短路問題。采用網(wǎng) 絡(luò)規(guī)劃中求最短路Dijkstra算法（標(biāo)號算法）。除了距離以外，還需要考慮通過交通網(wǎng)絡(luò)的時(shí)間長短。標(biāo)號算法1、最短路與最大流例題1例如，從上圖中找出V1與V8之間的最短路線。例題2 要把A市的一批貨物運(yùn)送到 市的一批貨物運(yùn)送到B市 例題 要把 市的一批貨物運(yùn)送到 市，根據(jù)兩個(gè)城市之間 可選擇的行車路線地圖，繪制了圖513的公路網(wǎng)絡(luò)。要 的公

3、路網(wǎng)絡(luò)。 可選擇的行車路線地圖，繪制了圖 的公路網(wǎng)絡(luò) 求尋找一條線路最短的運(yùn)輸路線。 求尋找一條線路最短的運(yùn)輸路線。解：從終點(diǎn)開始逐步逆向推算(1) 與終點(diǎn)10聯(lián)接的結(jié)點(diǎn)有兩個(gè)，即結(jié)點(diǎn)9和8； 從結(jié)點(diǎn)9到結(jié)點(diǎn)10只有一條線路，該線路為最短線路，長度100，記為：（9-10）100； 同樣，結(jié)點(diǎn)8到結(jié)點(diǎn)10的最短線路為150，記為（8-10）150； (2) 結(jié)點(diǎn)6。與6聯(lián)接的只有一個(gè)結(jié)點(diǎn)9，6至9的最短里程為200。而9至終點(diǎn)10的最短里程為 100因此6至終點(diǎn)10的最短里程為200十100300。記為：(6-9-10)300。(3)結(jié)點(diǎn)5。與5聯(lián)接的結(jié)點(diǎn)有9、8兩個(gè)。 5至9再至終點(diǎn)的最短里

4、程為400十100500， 5至8再至終點(diǎn)的最短里程為250十155400。 400500，所以5至終點(diǎn)的最短里程為400，記為：(5-8-10)400。 (4) 結(jié)點(diǎn)7。至終點(diǎn)的最短里程為125十150275， (5)結(jié)點(diǎn)4。與4聯(lián)接的結(jié)點(diǎn)有5、6、7三個(gè)。 結(jié)點(diǎn)4至6再到終點(diǎn)的最短里程為200十300=500； 結(jié)點(diǎn)4至5再到終點(diǎn)的最短里程為175十400575； 結(jié)點(diǎn)4至7再到終點(diǎn)的最短里程為275十275550。三個(gè)里程中以500為最小，所以結(jié)點(diǎn)4至l 0的最短里程記為(4 6910) 500。(6)結(jié)點(diǎn)2和3。 用同樣的方法，得到： 結(jié)點(diǎn)2到終點(diǎn)的最短里程為600。記為：(2 691

5、0)600。結(jié)點(diǎn)3到終點(diǎn)的最短里程為575。記為：(3 7810)575。(5)最后看結(jié)點(diǎn)1。結(jié)點(diǎn)1可以通過三個(gè)結(jié)點(diǎn)2、3、4連接到終點(diǎn)。 結(jié)點(diǎn)。1通過結(jié)點(diǎn)2再到終點(diǎn)的最短里程100十600700，路徑為（126910）700 結(jié)點(diǎn)1通過結(jié)點(diǎn)4再到終點(diǎn)的最短里程150十500650，路徑為（146910）650 結(jié)點(diǎn)1通過結(jié)點(diǎn)3再到終點(diǎn)的最短里程175十575750，路徑為（137810）750 以上三個(gè)里程中以650為最小，即A幣到B市的最短里程，對應(yīng)的最短路線為：146910 二、多個(gè)起點(diǎn)和多個(gè)終點(diǎn)的路徑規(guī)劃問題多個(gè)起點(diǎn)和終點(diǎn)的路徑優(yōu)化，需要確定各供求地點(diǎn)之 間的最佳供應(yīng)關(guān)系。運(yùn)用線性規(guī)劃

6、,數(shù)學(xué)模型可以描述為： 有m個(gè)產(chǎn)地 Ai，i =1，2，m，可供應(yīng)量分別為ai， i=1，2，m；有n個(gè)銷地 Bj，j=1，2，n，需要量 分別為bj，j=1，2，n；產(chǎn)銷平衡，從Ai到Bj 運(yùn)輸單位 貨物的運(yùn)價(jià)（也可以是時(shí)間或距離）為cij。問如何調(diào)運(yùn)這 些貨物，使得運(yùn)費(fèi)（或時(shí)間、噸公里數(shù)）最少？常見的解決方法有： 1、單純形法 2、圖表分析法 3、圖上作業(yè)法 4、表上作業(yè)法 5、供求不平衡運(yùn)輸模型三、起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃問題是物流配送業(yè)務(wù)中的常見問題。 由于要求車輛必須返回起點(diǎn)，問題的難度提高了。 由于要求車輛必須返回起點(diǎn)，問題的難度提高了。解決這類 問題的目標(biāo)

7、是找出途中經(jīng)過的點(diǎn)的順序，使運(yùn)輸工具依次經(jīng)過 問題的目標(biāo)是找出途中經(jīng)過的點(diǎn)的順序，使運(yùn)輸工具依次經(jīng)過 所有送貨點(diǎn)并滿足各點(diǎn)對送貨時(shí)間的要求 并滿足各點(diǎn)對送貨時(shí)間的要求， 所有送貨點(diǎn)并滿足各點(diǎn)對送貨時(shí)間的要求，且總出行時(shí)間或總 距離最短。 旅行推銷員（ NP難題 距離最短?！奥眯型其N員（TSP）”問題，屬于NP難題。 旅行推銷員 TSP） 問題，屬于NP難題。 隨著問題中包含節(jié)點(diǎn)個(gè)數(shù)和約束條件的增加， 隨著問題中包含節(jié)點(diǎn)個(gè)數(shù)和約束條件的增加，求解問題的復(fù) 雜程度增加，要找到最優(yōu)路徑非常困難。 雜程度增加，要找到最優(yōu)路徑非常困難。即使用最快的計(jì)算機(jī) 進(jìn)行計(jì)算，求最優(yōu)解的時(shí)間也非常長。 進(jìn)行計(jì)算，求

8、最優(yōu)解的時(shí)間也非常長。啟發(fā)式求解法是求解這 類問題的好方法。 類問題的好方法。 見p206頁例題3 運(yùn)輸批量越大，運(yùn)輸費(fèi)率越低。將小批量貨物合并成大批量貨物進(jìn)行運(yùn) 輸是降低運(yùn)輸成本的主要方法。 輸是降低運(yùn)輸成本的主要方法。（三）合理路線和時(shí)間安排的原則原則將相互接近的停留點(diǎn)的貨物裝在一輛車上運(yùn)送，以 便使停留點(diǎn)之間的運(yùn)行距離最小化。（a）差的串聯(lián) （b）更好的串聯(lián)原則2：將集聚在一起的停留點(diǎn)安排同一天送貨，要避免 不是同一天送貨的停留點(diǎn)在運(yùn)行線路上重疊。原則3： 合理的運(yùn)輸路線 一輛運(yùn)貨車順次途經(jīng)各停車點(diǎn)的路線要呈凸?fàn)?，或淚 點(diǎn)的路線要呈凸?fàn)睿?一輛運(yùn)貨車順次途經(jīng)各 點(diǎn)的路線要呈凸?fàn)?滴形，各

9、條線路之間是不交叉。原則4：運(yùn)行線路從倉庫最遠(yuǎn)的停留點(diǎn)開始，送貨車輛一次裝載 鄰近這個(gè)關(guān)鍵停留點(diǎn)的一些停留點(diǎn)的貨物，這輛運(yùn)貨車裝載滿 后，再安排另一輛運(yùn)貨車裝載另一個(gè)最遠(yuǎn)的停留點(diǎn)的貨物原則5 ： 有多種規(guī)格的車型，應(yīng)優(yōu)先使用載重量最大的送貨 車，將路線上所有要求運(yùn)送的貨物都裝載。原則6： 提貨應(yīng)混在送貨過程中進(jìn)行，而不要在運(yùn)行線路結(jié) 束后再運(yùn)行。原則7： 對偏離集聚停車點(diǎn)路線遠(yuǎn)的單獨(dú)的停車點(diǎn)可以使用 點(diǎn) 點(diǎn) 小載重量的車輛專門為這些停車點(diǎn)單獨(dú)送貨。另一個(gè)可供選 點(diǎn) 擇的方案是租用車輛或采用公共服務(wù)（如郵政服務(wù)）為這些 停車點(diǎn)送貨。原則8： 應(yīng)當(dāng)避免停車點(diǎn)工作時(shí)間太短的約束。2、制定車輛路徑優(yōu)化

10、方法物流配送路徑優(yōu)化常見的約束條件包括：停車點(diǎn) 的工作時(shí)間約束，車輛的類型，最大的運(yùn)行時(shí)間、 不同區(qū)段的車速限制，運(yùn)行途中的障礙物（湖泊、 山脈等、交通管制）、司機(jī)的短時(shí)間休息等。 如果問題中包含送貨點(diǎn)的個(gè)數(shù)很多，附加了許多 約束條件，問題求解就變得十分復(fù)雜。（四）運(yùn)輸路線和時(shí)刻表的制定方法 （1） 人工計(jì)算方法掃描法 人工計(jì)算方法 掃描法問題：對于若干個(gè)停車點(diǎn)（客戶）安排最優(yōu)行車路線。 第一步，將倉庫（出發(fā)點(diǎn)）和所有的停車點(diǎn)位置畫在地圖 上或坐標(biāo)圖上； 第二步，通過倉庫位置放置一直尺，然后順時(shí)針或逆時(shí)針 方向轉(zhuǎn)動，直到直尺交到一個(gè)停車點(diǎn)。詢問：累計(jì)的裝貨 量是否超過送貨的載重量或容積（首先要

11、使用最大的送貨 車輛）。如是，最后的停車點(diǎn)排除，將路線確定下來。然 后再從這個(gè)停車點(diǎn)開始繼續(xù)掃描，開始一條新的路線。這 樣掃描下去，直至全部的停留點(diǎn)都被分配到路線上。 第三步，對每條路線安排運(yùn)行順序，以求運(yùn)行距離最小化。 方案的誤差率在10%左右。例4 從各客戶點(diǎn)提貨，然后將貨物運(yùn)回倉庫。全天的提 貨量見圖5-13。送貨車每次可運(yùn)載10000件。要求確定： 需多少條路線（即多少輛送貨車）；每條路線上有哪幾個(gè) 客戶點(diǎn)；送貨車輛服務(wù)有關(guān)客戶點(diǎn)的順序。圖5-13停留點(diǎn)提貨量數(shù)據(jù) 停留點(diǎn)提貨量數(shù)據(jù)掃描法:手工計(jì)算。車的載貨量是 掃描法 手工計(jì)算。車的載貨量是10000件。需要多少條線 手工計(jì)算 件 每條線路上的站點(diǎn)如何排列