第六章 配送運(yùn)輸路線設(shè)計(jì)1

1、第一節(jié)第一節(jié) 配送運(yùn)輸概述配送運(yùn)輸概述 一、 配送運(yùn)輸 （一）概念 配送運(yùn)輸是指將顧客所需要的貨物通過(guò)運(yùn)輸工具從供應(yīng)點(diǎn)送至顧客手中的活動(dòng)。 特點(diǎn)：配送運(yùn)輸通常是一種短距離、小批量、高頻率的運(yùn)輸形式。如果單從運(yùn)輸?shù)慕嵌瓤?，它是?duì)干線運(yùn)輸?shù)囊环N補(bǔ)充和完善，屬于末端運(yùn)輸、支線運(yùn)輸。他以服務(wù)為目標(biāo)，以盡可能滿足客戶要求為優(yōu)先。 可能是從工廠等生產(chǎn)的倉(cāng)庫(kù)直接送至客戶；也可能通過(guò)批發(fā)商、經(jīng)銷商或由配送中心、物流中心轉(zhuǎn)送至客戶手中。 （二）影響配送運(yùn)輸?shù)囊蛩兀ǘ┯绊懪渌瓦\(yùn)輸?shù)囊蛩?動(dòng)態(tài)因素 靜態(tài)因素 （三）配送運(yùn)輸?shù)奶攸c(diǎn)（三）配送運(yùn)輸?shù)奶攸c(diǎn) 時(shí)效性 ：快速及時(shí)，即確保在客戶指定的時(shí)間內(nèi)交貨 安全性 ：貨物

2、完好無(wú)損的送到目的地 溝通性 ：通過(guò)送貨上門服務(wù)直接與客戶接觸 方便性 ：盡可能的讓顧客享受到便捷的服務(wù) 經(jīng)濟(jì)性 ：以較低的費(fèi)用，完成配送作業(yè) 車流輛變化、道路施工、配送客戶的變動(dòng)、可供調(diào)動(dòng)的車輛變動(dòng) 如配送客戶的分布區(qū)域、道路交通網(wǎng)絡(luò)、車輛運(yùn)行限制 二、配送運(yùn)輸?shù)幕咀鳂I(yè)程序二、配送運(yùn)輸?shù)幕咀鳂I(yè)程序 （一）劃分基本配送區(qū)域 （二）車輛配載 （三）暫定配送先后順序 （四）車輛安排 （五）選擇配送線路 （六）確定最終的配送順序 （七）完成車輛積載 費(fèi)用1外雇車輛2自有車輛運(yùn)輸量（t.km）車輛安排：自營(yíng)還是外包？第二節(jié)第二節(jié) 配送線路優(yōu)化技術(shù)配送線路優(yōu)化技術(shù) 一、線路優(yōu)化設(shè)計(jì)的意義一、線路優(yōu)化

3、設(shè)計(jì)的意義 配送線路設(shè)計(jì)就是整合影響配送運(yùn)輸?shù)母鞣N因素，適時(shí)適當(dāng)?shù)乩矛F(xiàn)有的運(yùn)輸工具和道路狀況，及時(shí)、安全、方便、經(jīng)濟(jì)地將客戶所需的商品準(zhǔn)確地送達(dá)客戶手中。在配送運(yùn)輸線路設(shè)計(jì)中，需根據(jù)不同客戶群的特點(diǎn)和要求，選擇不同的線路設(shè)計(jì)方法，最終達(dá)到節(jié)省時(shí)間、運(yùn)距和降低配送運(yùn)輸成本的目的第二節(jié)第二節(jié) 配送線路設(shè)計(jì)配送線路設(shè)計(jì) 二、配送線路類型二、配送線路類型 1.往復(fù)式行駛路線 供應(yīng)點(diǎn)：1個(gè) 客戶：1個(gè) 客戶需求量=可用車輛的核定載重量 2.環(huán)形式行駛路線 供應(yīng)點(diǎn)1個(gè)對(duì)應(yīng)多個(gè)客戶或客戶1個(gè)對(duì)應(yīng)多個(gè)供應(yīng)點(diǎn) 3.匯集式行駛路線供應(yīng)點(diǎn)客戶第二節(jié)第二節(jié) 配送線路設(shè)計(jì)配送線路設(shè)計(jì) 二、配送線路類型二、配送線路類型

4、 2.環(huán)形式行駛路線 供應(yīng)點(diǎn)1個(gè)對(duì)應(yīng)多個(gè)客戶或客戶1個(gè)對(duì)應(yīng)多個(gè)供應(yīng)點(diǎn) AAACABADAEAACABADAACABAACABDAEAF單環(huán)形式交叉環(huán)形式復(fù)合環(huán)形式三角環(huán)形式第二節(jié)第二節(jié) 配送線路設(shè)計(jì)配送線路設(shè)計(jì) 二、配送線路類型二、配送線路類型 3.匯集式行駛線路 BACD分送式BCD匯集式BACD分送-匯集式分送貨物收集貨物三三 配送線路設(shè)計(jì)配送線路設(shè)計(jì)1、直送式配送運(yùn)輸（1）最短路徑設(shè)計(jì)l最短線路的方法Dijkstra算法，也叫標(biāo)號(hào)法。V2 V7V6V3 47 V5 V162532 61V472直送式配送運(yùn)輸，是指由一個(gè)供應(yīng)點(diǎn)對(duì)一個(gè)客戶的專門送貨 l線路V72467V427V572V25V

5、102516362、分送式配送運(yùn)輸、分送式配送運(yùn)輸 分送式配送是指由一個(gè)供應(yīng)點(diǎn)對(duì)多個(gè)客戶的共同送貨?；緱l件：同一條線路上所有客戶的需求量總和不大于一輛車的額定載重量，送貨時(shí)，由這一輛車裝著所有客戶的貨物，沿著一條精心挑選的最佳路線依次將貨物送到各個(gè)客戶手中，這樣既保證按時(shí)按量將用戶需要的貨物及時(shí)送到，又節(jié)約了車輛，節(jié)省了費(fèi)用，緩解了交通緊張的壓力，并減少了運(yùn)輸對(duì)環(huán)境造成的污染。（一）節(jié)約法的基本規(guī)定（一）節(jié)約法的基本規(guī)定 利用里程節(jié)約法確定配送路線的主要出發(fā)點(diǎn)是，根據(jù)配送方的運(yùn)輸能力及其到客戶之間的距離和各客戶之間的相對(duì)距離來(lái)制定使配送車輛總的周轉(zhuǎn)量達(dá)到或接近最小的配送方案。（二）節(jié)約法的基

6、本思想（二）節(jié)約法的基本思想方案a）的配送路線為p0pip0pjp0,配送距離為da=d0i+d0j方案b)配送路線p0pipjp0,配送距離為db=. d0i+d0j+dij顯然，da不等于db，我們用sij表示里程節(jié)約量，即方案b)比方案a)節(jié)約的配送里程： （1）節(jié)約里程法）節(jié)約里程法 案例分析案例分析l例：某一配送中心p0向10個(gè)客戶pj(j=1,2,10)配送貨物，其配送網(wǎng)絡(luò)如圖11-9所示。圖中括號(hào)內(nèi)的數(shù)字表示客戶的需求量（T），線路上的數(shù)字表示兩節(jié)點(diǎn)之間的距離。配送中心有2t和4t兩種車輛可供使用，試制定最優(yōu)的配送方案。第一步：計(jì)算最短距離。根據(jù)配送網(wǎng)絡(luò)中的已知條件，計(jì)算配送中心

7、與客戶及客戶之間的最短距離，結(jié)果見下表。第二步：計(jì)算節(jié)約里程sij。第三步：將節(jié)約sij,進(jìn)行分類，按從大到小的順序排列，得表第四步：確定配送線路。從分類表中，按節(jié)約里程大小順序，組成線路圖（1）初始方案：對(duì)每一客戶分別單獨(dú)派車）初始方案：對(duì)每一客戶分別單獨(dú)派車送貨，結(jié)果如圖所示。送貨，結(jié)果如圖所示。修正方案修正方案4 4（2）兩階段法）兩階段法（一）先求出一個(gè)可行解，然后對(duì)現(xiàn)有可行解 進(jìn)行反復(fù)地局部擾亂，以達(dá)到較好的解；（二）利用VSP模型的特征，將一個(gè)整體優(yōu)化問(wèn)題分解成兩步進(jìn)行優(yōu)化計(jì)算。（2）兩階段法）兩階段法l先路徑后分組算法第一階段：形成包含所有需求點(diǎn)的路徑第二階段：根據(jù)一定的約束（如

8、車輛容量、距離、時(shí)間等）對(duì)它進(jìn)行劃分，形成各配送車輛的路徑。（2）兩階段法）兩階段法l先路徑后分組算法步驟 第一步：尋求對(duì)于每個(gè)節(jié)點(diǎn)通過(guò)一次且只通過(guò)一次的巡回路徑，設(shè)表達(dá)巡回路徑的序列為，(i)表示回路第i個(gè)通過(guò)的點(diǎn)，而(0)為配送中心。 第二步：按照車輛路徑上的客戶必須在上是連續(xù)的，并且滿足給定條件（如最大裝載量、最大運(yùn)輸距離等）進(jìn)行分組。 第三步：確定各組需求的訪問(wèn)順序（2）兩階段法）兩階段法l先路徑后分組算法步驟： 第三步：確定各組需求的最優(yōu)訪問(wèn)順序。 最優(yōu)訪問(wèn)順序可應(yīng)用最優(yōu)劃分法最優(yōu)劃分法求解。最優(yōu)劃分法最優(yōu)劃分法 j1ik)(;0),(,1i, 0WRjCkij的費(fèi)用，若）（路徑當(dāng)訪

9、問(wèn)所有需求點(diǎn)的巡回路徑已經(jīng)確定的條件下，最優(yōu)劃分法給出了一種不破壞巡回路徑順序的“最優(yōu)”分組方法。設(shè)巡回路徑的序列為0,(1),.,(n),令Cij為滿足裝載量約束和的按巡回路徑的順序從第i+1個(gè)需求點(diǎn)到第j個(gè)需求點(diǎn)的費(fèi)用加上兩端點(diǎn)到配送中心 費(fèi)用，在計(jì)算Cij時(shí)，還需滿足不超出最大運(yùn)輸距離或運(yùn)輸時(shí)間。最優(yōu)劃分法最優(yōu)劃分法 求解步驟：第一步：將需求點(diǎn)集合N構(gòu)筑成為每個(gè)點(diǎn)恰好通過(guò)一次的巡回路徑，設(shè)表示巡回路徑的序列為；第二步：應(yīng)用Cij確定中任意兩點(diǎn)間的距離費(fèi)用矩陣Cij第三步：以點(diǎn)0為起點(diǎn)，以點(diǎn)(n)為終點(diǎn)，求解最短路徑L;第四步:對(duì)于最短路徑L上的所有有向枝(i,j),輸出分組路徑0,(i+

10、1),.,(j),0第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度一、影響因素（一）貨物（二）車輛（三）配送中心（四）客戶（五）運(yùn)輸網(wǎng)絡(luò)（六）約束條件（七）目標(biāo)函數(shù) 60B3305020第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度二、方法（一）圖上作業(yè)法 1繪制交通圖 設(shè)有A1、A2、A3三個(gè)配送點(diǎn)分別有化肥40t、30t、30t，需送往四個(gè)客戶 點(diǎn)B1、B2、B3、B4，而且已知各配送點(diǎn)和客戶點(diǎn)的地理位置及它們之間 的道路通阻情況，可據(jù)此制出相應(yīng)的交通圖 A330B110A140B440B220A23040304050運(yùn)距運(yùn)量交通圖2將初始調(diào)運(yùn)方案反映在交通圖上 A330B110A140B440B330B220A2304

11、02030A2 B4破圈調(diào)運(yùn)圖204040凡是按順時(shí)針?lè)较蛘{(diào)運(yùn)的貨物調(diào)運(yùn)線路（如A3至B1、B1至B4、A2至B3），其調(diào)運(yùn)箭頭線都畫在圈外，稱為外圈；否則，其調(diào)運(yùn)箭頭線（A3至B3）都畫在圈內(nèi)，稱為內(nèi)圈 3檢查與調(diào)整 A330B110A140B440B330B220A230103020A3 B1破圈調(diào)運(yùn)圖圖204030首先分別計(jì)算線路的全圈長(zhǎng)、內(nèi)圈長(zhǎng)和外圈長(zhǎng)（圈長(zhǎng)即指里程數(shù)），如果內(nèi)圈長(zhǎng)和外圈長(zhǎng)都分別小于全圈長(zhǎng)的一半，則該方案即為最優(yōu)方案；否則，即為非最優(yōu)方案，需要對(duì)其進(jìn)行調(diào)整 第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度二、方法（三）基于時(shí)間窗車輛調(diào)度 1問(wèn)題的描述 設(shè)Ti為任務(wù)i裝(卸)貨所需時(shí)間，E

12、Ti為任務(wù)i的允許最早開始時(shí)間， LTi為任務(wù)i的允許最遲開始時(shí)間，即任務(wù)i的開始時(shí)間需在一定的時(shí)間范圍ETi , LTi內(nèi)。 求滿足貨運(yùn)要求的費(fèi)用最少的車輛行駛線路。稱此問(wèn)題為有時(shí)間窗的車輛優(yōu)化調(diào)度問(wèn)題。第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度1問(wèn)題的描述l 以si 表示車輛到達(dá)i點(diǎn)的時(shí)間，tij表示車輛由點(diǎn)i行駛到點(diǎn)j的時(shí)間，一般應(yīng)滿足以下關(guān)系式 s0=0 ETi si LTi式中， s0=0表示從車場(chǎng)出發(fā)，若每項(xiàng)任務(wù)必須在要求的時(shí)間范圍內(nèi)完成，即必須滿足上式，否則得到的解為不可行解，稱之為硬時(shí)間窗VSP;若某項(xiàng)任務(wù)不能在要求的時(shí)間范圍內(nèi)完成，則給予一定的懲罰，稱之為軟時(shí)間窗VSP。第三節(jié)第三節(jié) 車

13、輛調(diào)度車輛調(diào)度2模型建立 第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度2模型建立 第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度2模型建立 第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度3算法原理第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度3算法原理第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度3算法原理第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度案例第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度二、方法（四）遺傳算法 1基本思想第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度二、方法（四）遺傳算法 2基本步驟第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度二、方法（四）遺傳算法 2基本步驟第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度二、方法（四）遺傳算法 2基本步驟第三節(jié)第三節(jié) 車輛調(diào)度車輛調(diào)度二、方法（四）遺傳算法 2基本步驟第三節(jié)第三節(jié) 車

14、輛調(diào)度車輛調(diào)度二、方法（四）遺傳算法 2基本步驟比如有些危險(xiǎn)品必須減載運(yùn)送才能保證安全第四節(jié)第四節(jié) 配送車輛積載技術(shù)配送車輛積載技術(shù) 一、影響配送車輛積載因素一、影響配送車輛積載因素 貨物特性因素 貨物包裝情況 不能拼裝運(yùn)輸 由于裝載技術(shù)的原因，造成不能裝足噸位。 輕泡貨物噸位利用率降低如車廂尺寸不與貨物包裝容器的尺寸成整倍數(shù)關(guān)系，則無(wú)法裝滿車廂 二、車輛積載的原則二、車輛積載的原則 （一）輕重搭配的原則 （二）大小搭配的原則 （三）貨物性質(zhì)搭配原則 （四）到達(dá)同一地點(diǎn)的適合配裝的 貨物應(yīng)盡可能一次積載。（五）確定合理的堆碼層次及方法 將重貨置于底部，輕貨置于上部，避免重貨壓壞輕貨，并使貨物重

15、心下移 拼裝在一個(gè)車廂內(nèi)的貨物，其化學(xué)性質(zhì)、物理屬性不能互相抵觸 可根據(jù)車廂的尺寸、容積，貨物外包裝的尺寸來(lái)確定 （六）裝載時(shí)不允許超過(guò)車輛所允許的最大載重量 （七）裝載易滾動(dòng)的卷狀、桶狀貨物，要垂直擺放。（八）貨與貨之間，貨與車輛之間應(yīng)留有空隙并適當(dāng)襯墊，防止貨損。（九）裝貨完畢，應(yīng)在門端處采取適當(dāng)?shù)姆€(wěn)固措施，以防開門卸貨時(shí)， 貨物傾倒造成貨損（十）盡量做到“后送先裝” 三、提高車輛裝載效率的具體辦法三、提高車輛裝載效率的具體辦法 研究各類車廂的裝載標(biāo)準(zhǔn)，根據(jù)不同貨物和不同包裝體積的要求，合理安排裝載順序，努力提高裝載技術(shù)和操作水平，力求裝足車輛核定噸位。 根據(jù)客戶所需要的貨物品種和數(shù)量，調(diào)

16、派適宜的車型承運(yùn)，這就要求配送中心根據(jù)經(jīng)營(yíng)商品的特性，配備合適的車型結(jié)構(gòu)。 凡是可以拼裝運(yùn)輸?shù)?，盡可能拼裝運(yùn)輸，但要注意防止差錯(cuò)。 配載模型配載模型(裝載貨物的價(jià)值最大裝載貨物的價(jià)值最大)l假設(shè)配送車輛的最大載重量為G，用于運(yùn)送n種不同的物品，此n種不同物品的重量分別為W1, W2, Wn,每一種物品的價(jià)值系數(shù)（可表現(xiàn)為價(jià)值、運(yùn)費(fèi)等）用P1, P2, Pn表示。另設(shè)Xk表示第k種物品的裝入數(shù)量，則在 條件下1nkkkW XG1( )maxnkkkf xP X配載模型配載模型(考慮優(yōu)先級(jí)情況下考慮優(yōu)先級(jí)情況下)1 問(wèn)題描述配載模型配載模型(考慮優(yōu)先級(jí)情況下考慮優(yōu)先級(jí)情況下)1 建立模型客戶需求優(yōu)先系數(shù)表客戶需求優(yōu)先系數(shù)表兩階段算法思路兩階段算法思路先將裝剩余的(n一k