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

2、劃； 三是起點和終點相同的路徑規(guī)劃。,一、起點和終點不同的單一路徑規(guī)劃 此類問題可以描述為在一個已知交通運輸網(wǎng)絡(luò)中，尋找從出發(fā)地到目的地的最佳路線。這里的“最佳”可以指距離最短、時間最省或是費用最少。 數(shù)學(xué)模型求網(wǎng)絡(luò)圖中二點之間的最短路問題。采用網(wǎng)絡(luò)規(guī)劃中求最短路Dijkstra算法（標(biāo)號算法）。 除了距離以外，還需要考慮通過交通網(wǎng)絡(luò)的時間長短。,V5,例如，從上圖中找出V1與V8之間的最短路線。,V2,V1,V4,V6,V7,V9,V8,V3,1,6,3,1,2,2,6,2,6,3,4,10,2,4,3,1、最短路與最大流,起點,終點,例題1,標(biāo)號算法,例題2 要把A市的一批貨物運送到B市，

3、根據(jù)兩個城市之間可選擇的行車路線地圖，繪制了圖513的公路網(wǎng)絡(luò)。要求尋找一條線路最短的運輸路線。,圖中 為結(jié)點，代表起點、目的地和與行車路線相交的其他城市，其中的數(shù)字為結(jié)點編號。 箭頭為分支，代表兩個結(jié)點之間的公路，箭頭上標(biāo)明的數(shù)字為運輸里程。,公路網(wǎng)絡(luò),1,解：從終點開始逐步逆向推算。 (1)與終點10聯(lián)接的結(jié)點有兩個，即結(jié)點9和8； 從結(jié)點9到結(jié)點10只有一條線路，該線路為最短線路，長度100，記為：（9-10）100； 同樣，結(jié)點8到結(jié)點10的最短線路為150，記為（8-10）150； (2)結(jié)點6。與6聯(lián)接的只有一個結(jié)點9，6至9的最短里程為200。而9至終點10的最短里程為100因此

4、6至終點10的最短里程為200十100300。記為：(6-9-10)300。 (3)結(jié)點5。與5聯(lián)接的結(jié)點有9、8兩個。 5至9再至終點的最短里程為400十100500， 5至8再至終點的最短里程為250十155400。 400500，所以5至終點的最短里程為400，記為：(5-8-10)400。 (4) 結(jié)點7。至終點的最短里程為125十150275，記為：(7-8-10) 275。,300,(5)結(jié)點4。與4聯(lián)接的結(jié)點有5、6、7三個。 結(jié)點4至6再到終點的最短里程為200十300=500； 結(jié)點4至5再到終點的最短里程為175十400575； 結(jié)點4至7再到終點的最短里程為275十275

5、550。 三個里程中以500為最小，所以結(jié)點4至l 0的最短里程記為(46910) 500。 (6)結(jié)點2和3。 用同樣的方法，得到： 結(jié)點2到終點的最短里程為600。記為：(26910)600。 結(jié)點3到終點的最短里程為575。記為：(37810)575。 (5)最后看結(jié)點1。結(jié)點1可以通過三個結(jié)點2、3、4連接到終點。 結(jié)點1通過結(jié)點2再到終點的最短里程100十600700，路徑為（126910）700； 結(jié)點1通過結(jié)點4再到終點的最短里程150十500650，路徑為（146910）650； 結(jié)點1通過結(jié)點3再到終點的最短里程175十575750，路徑為（137810）750。 以上三個里

6、程中以650為最小，即A幣到B市的最短里程，對應(yīng)的最短路線為：146910。,二、多個起點和多個終點的路徑規(guī)劃問題 多個起點和終點的路徑優(yōu)化，需要確定各供求地點之間的最佳供應(yīng)關(guān)系。運用線性規(guī)劃,數(shù)學(xué)模型可以描述為： 有m個產(chǎn)地 Ai，i =1，2，m，可供應(yīng)量分別為ai，i=1，2，m；有n個銷地 Bj，j=1，2，n，需要量分別為bj，j=1，2，n；產(chǎn)銷平衡，從Ai到Bj 運輸單位貨物的運價（也可以是時間或距離）為cij。問如何調(diào)運這些貨物，使得運費（或時間、噸公里數(shù)）最少？,1、單純形法,2、圖表分析法,4、表上作業(yè)法,5、供求不平衡運輸模型,3、圖上作業(yè)法,常見的解決方法有：,起點和終

7、點相同的路徑規(guī)劃問題是物流配送業(yè)務(wù)中的常見問題。 由于要求車輛必須返回起點，問題的難度提高了。解決這類問題的目標(biāo)是找出途中經(jīng)過的點的順序，使運輸工具依次經(jīng)過所有送貨點并滿足各點對送貨時間的要求，且總出行時間或總距離最短。“旅行推銷員（TSP）”問題，屬于NP難題。 隨著問題中包含節(jié)點個數(shù)和約束條件的增加，求解問題的復(fù)雜程度增加，要找到最優(yōu)路徑非常困難。即使用最快的計算機進(jìn)行計算，求最優(yōu)解的時間也非常長。啟發(fā)式求解法是求解這類問題的好方法。,三、起點和終點相同的路徑規(guī)劃,見p206頁例題3,運輸批量越大，運輸費率越低。 將小批量貨物合并成大批量貨物進(jìn)行運輸是降低運輸成本的主要方法。,原則. 將相

8、互接近的停留點的貨物裝在一輛車上運送，以便使停留點之間的運行距離最小化。,（b）更好的串聯(lián),（a）差的串聯(lián),（三）合理路線和時間安排的原則,原則4：運行線路從倉庫最遠(yuǎn)的停留點開始，送貨車輛一次裝載鄰近這個關(guān)鍵停留點的一些停留點的貨物，這輛運貨車裝載滿后，再安排另一輛運貨車裝載另一個最遠(yuǎn)的停留點的貨物,原則5：有多種規(guī)格的車型，應(yīng)優(yōu)先使用載重量最大的送貨車，將路線上所有要求運送的貨物都裝載。 原則6： 提貨應(yīng)混在送貨過程中進(jìn)行，而不要在運行線路結(jié)束后再運行。 原則7： 對偏離集聚停車點路線遠(yuǎn)的單獨的停車點可以使用小載重量的車輛專門為這些停車點單獨送貨。另一個可供選擇的方案是租用車輛或采用公共服務(wù)

9、（如郵政服務(wù)）為這些停車點送貨。 原則8： 應(yīng)當(dāng)避免停車點工作時間太短的約束。,物流配送路徑優(yōu)化常見的約束條件包括：停車點的工作時間約束，車輛的類型，最大的運行時間、不同區(qū)段的車速限制，運行途中的障礙物（湖泊、山脈等、交通管制）、司機的短時間休息等。 如果問題中包含送貨點的個數(shù)很多，附加了許多約束條件，問題求解就變得十分復(fù)雜。,2、制定車輛路徑優(yōu)化方法,（四）運輸路線和時刻表的制定方法 （1）人工計算方法掃描法 問題：對于若干個停車點（客戶）安排最優(yōu)行車路線。 第一步，將倉庫（出發(fā)點）和所有的停車點位置畫在地圖上或坐標(biāo)圖上； 第二步，通過倉庫位置放置一直尺，然后順時針或逆時針方向轉(zhuǎn)動，直到直尺交到一個停車點。詢問：累計的裝貨量是否超過送貨的載重量或容積（首先要使用最大的送貨車輛）。如是，最后的停車點排除，將路線確定下來。然后再從這個停車點開始繼續(xù)掃描，開始一條新的路線。這樣掃描下去，直至全部的停留點都被分配到路線上。 第三步，對每條路線安排運行順序，以求運行距離最小化。 方案的誤差率在10%左右。,例4 從各客戶點提貨，然后將貨物運回倉庫。全天的提貨量見圖5-13。送貨車每次可運載10000件。要求確定：需多少條路線（即多少輛送貨車）；每條路線上有哪幾個客戶點；送貨車輛服務(wù)有關(guān)