運(yùn)輸及配送系統(tǒng)規(guī)劃

1、.,1,第六章 運(yùn)輸及配送系統(tǒng)規(guī)劃,第一節(jié) 運(yùn)輸方式的選擇 第二節(jié) 物資運(yùn)輸調(diào)配決策 第三節(jié) 單一車輛配送路線的優(yōu)化 第四節(jié) 多車輛配送路線的優(yōu)化,.,2,重點(diǎn)、難點(diǎn),1）運(yùn)輸方式的定量選擇方法； 2）單車輛路線優(yōu)化方法； 3）多車輛路線優(yōu)化方法 （掃描法和節(jié)約法,.,3,第一節(jié) 運(yùn)輸方式的選擇,一、運(yùn)輸方式選擇的原則 成本、速度、可靠性、安全性 （一）安全性原則 （二）及時(shí)性原則 （三）準(zhǔn)確性原則 （四）經(jīng)濟(jì)性原則,.,4,二、運(yùn)輸服務(wù)方式選擇的定性方法,即根據(jù)各種運(yùn)輸方式的經(jīng)濟(jì)和服務(wù)特征進(jìn)行判斷： 運(yùn)輸成本：成本如何確定？ 速度（運(yùn)輸時(shí)間）： 可靠性（運(yùn)輸時(shí)間的波動）：,.,5,三、運(yùn)輸方

2、式的定量分析法,1、成本比較法的基本思想 （運(yùn)輸成本與庫存成本的總成本） 使該運(yùn)輸服務(wù)的成本與該運(yùn)輸服務(wù)水平以及相關(guān)庫存成本之間達(dá)到平衡的運(yùn)輸服務(wù)就是最佳服務(wù)。 即：既能滿足客戶需求，又使總成本最低的服務(wù)。,成本比較法,.,6,2、計(jì)算過程示例說明,某公司欲將產(chǎn)品從位置A的工廠運(yùn)往位置B的公司自有倉庫，年運(yùn)量D=700 000件，產(chǎn)品單價(jià)C=30元，年存貨成本I=產(chǎn)品價(jià)格的30。公司希望選擇使總成本最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫存成本可以減少1。,.,7,各種運(yùn)輸服務(wù)的有關(guān)參數(shù)：,方式 費(fèi)率R(元/件) 時(shí)間T(天) 年運(yùn)送批次 平均存貨量Q/2 鐵路 0.1 21 10

3、100 000 馱背 0.15 14 20 46 500 公路 0.2 5 20 42 000 航空 1.4 2 40 20 250,選擇哪種運(yùn)輸方式最滿意？,.,8,選擇依據(jù),總成本=運(yùn)輸成本+庫存成本 運(yùn)輸成本= 運(yùn)輸量費(fèi)率 庫存成本=在途庫存成本+工廠存貨成本+ 倉庫存貨成本,庫存量庫存費(fèi)率物資價(jià)格,.,9,庫存成本=在途庫存成本+工廠存貨成本+ 倉庫存貨成本,在途庫存費(fèi)用= I C D T/365 工廠存貨成本= I C Q/2 倉庫存貨成本= I （C+R） Q/2,年運(yùn)量D=700 000件， 產(chǎn)品單價(jià)C=30元， 存貨費(fèi)率I=30%,.,10,各種運(yùn)輸方式成本計(jì)算：,年運(yùn)量D=7

4、00 000件，產(chǎn)品單價(jià)C=30元， 存貨費(fèi)率I=30%,.,11,各種運(yùn)輸方式成本計(jì)算結(jié)果：,總成本最低的是公路運(yùn)輸方式，其次是馱背運(yùn)輸，成本最高的是鐵路運(yùn)輸。,.,12,結(jié)果討論,1）存儲費(fèi)率改變，對選擇有什么影響？ 降低存儲費(fèi)率，結(jié)果會怎樣？ 2）運(yùn)輸費(fèi)率和運(yùn)輸時(shí)間，對于選擇結(jié)果有何影響？,.,13,第二節(jié) 物資運(yùn)輸調(diào)配決策,指在多個(gè)供應(yīng)地和多個(gè)需求地之間如何合理調(diào)配貨物，在滿足需求前提下，使總運(yùn)輸成本最低。,.,14,第二節(jié) 物資運(yùn)輸調(diào)配決策,問題特征：兩點(diǎn)間的運(yùn)輸線路固定，運(yùn)輸距離的影響反映在單位運(yùn)費(fèi)中，運(yùn)輸總成本由運(yùn)輸量決定。 不涉及運(yùn)輸路線如何優(yōu)化。,.,15,問題分類,一、多起

5、迄點(diǎn)間的直達(dá)運(yùn)輸 （一）產(chǎn)銷平衡的運(yùn)輸問題 （二）產(chǎn)銷不平衡的運(yùn)輸問題 二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配,.,16,一、多起迄點(diǎn)間的直達(dá)運(yùn)輸,.,17,運(yùn)輸問題,多個(gè)貨源可服務(wù)于多個(gè)市場地，怎么指定各目的市場的供貨地？在有多個(gè)供應(yīng)商、工廠、倉庫服務(wù)于多個(gè)客戶的情況下，這是運(yùn)輸組織中常見的問題。若供求不平衡呢？更復(fù)雜。 請看下面幾種情況： (1)某企業(yè)要將濟(jì)南、鄭州、蘭州三個(gè)工廠生產(chǎn)的鋼材運(yùn)輸?shù)奖本?、上海、西安、杭州，?yīng)該如何組織運(yùn)輸使運(yùn)費(fèi)最小? (2)某大零售商有3個(gè)大型配送中心在北京、上海、廣州，給它在天津、杭州、武漢、南寧四個(gè)城市的超市連鎖店配貨，應(yīng)該如何組織運(yùn)輸使運(yùn)費(fèi)最小?,.,18,（一）產(chǎn)

6、銷平衡的運(yùn)輸問題,從每一供應(yīng)地運(yùn)送多少物資到各需求地，總運(yùn)費(fèi)最低？,完成練習(xí)題4,.,19,（一）產(chǎn)銷平衡的運(yùn)輸問題,從每一供應(yīng)地運(yùn)送多少物資到各需求地，總運(yùn)費(fèi)最低？,.,20,求解方法,運(yùn)輸問題的表上作業(yè)法、單純形法,最佳方案： A客戶1：400； B客戶1：200； B客戶2：200； B客戶3：300； C客戶2：300 完成練習(xí)題4,.,21,（二）產(chǎn)銷不平衡的運(yùn)輸問題,1總產(chǎn)量大于總銷量 2總銷量大于總產(chǎn)量 （略）,.,22,二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配,（一）問題描述,.,23,（一）問題描述,某物流系統(tǒng)中有f個(gè)供應(yīng)地，m個(gè)中轉(zhuǎn)站，n個(gè)需求地。工廠Ak的生產(chǎn)能力為ak（k=1，f），

7、流通中心Ti的配送能力為ti（i=1，m），零售店Bj的需求量為bj（j=1，2，n）。由Ak經(jīng)Ti運(yùn)到Bj的單位運(yùn)價(jià)為Ckij。 求：在設(shè)施點(diǎn)能力限制的條件下，滿足零售店需求量的最優(yōu)運(yùn)輸方案。,.,24,（二）數(shù)學(xué)模型,決策變量Xkij由產(chǎn)地Ak經(jīng)Ti運(yùn)到零售店Bj的物資量 目標(biāo)函數(shù)：,約束條件： （1）配送量生產(chǎn)能力的限制： （2）流通中心發(fā)送能力的限制： （3）滿足零售店需求量 （4）變量非負(fù)：,.,25,（三）求解方法 （1）一般的線性規(guī)劃方法求解 （2）運(yùn)輸問題表上作業(yè)法 方法（2）的思路： 補(bǔ)充一些虛擬的產(chǎn)地或需求地，將有中轉(zhuǎn)的運(yùn)輸問題轉(zhuǎn)化為無中轉(zhuǎn)的直達(dá)運(yùn)輸問題； 進(jìn)一步轉(zhuǎn)化為供需

8、平衡的運(yùn)輸問題； 運(yùn)用表上作業(yè)法求解。,.,26,存在中間轉(zhuǎn)運(yùn)的物資調(diào)配：算例 題目條件：,中轉(zhuǎn)能力不限,.,27,存在中間轉(zhuǎn)運(yùn)的物資調(diào)配：算例 運(yùn)輸問題表：,.,28,運(yùn)輸問題表中需求和供應(yīng)量確定準(zhǔn)則 ：,.,29,存在中間轉(zhuǎn)運(yùn)的物資調(diào)配：算例 最終運(yùn)輸表：,.,30,第三節(jié) 單一車輛配送路線的優(yōu)化,兩類問題： 從O點(diǎn)送貨到T點(diǎn)； 從A點(diǎn)出發(fā)最后回到A點(diǎn)。,.,31,問題及方法分類,一、起迄點(diǎn)不同的單一路線優(yōu)化 （一）動態(tài)規(guī)劃法 （二）Dijkstra方法 二、起迄點(diǎn)重合的單一路線優(yōu)化 （一）旅行商問題TSP模型 （二）中國郵遞員問題,.,32,一、起迄點(diǎn)不同的單一路線問題,1、應(yīng)用問題 從

9、一個(gè)發(fā)貨點(diǎn)運(yùn)輸?shù)揭粋€(gè)不同的收貨點(diǎn)，例如有一批貨需要從A城市運(yùn)送到E城市，根據(jù)從A城市到E城市的公路路網(wǎng)，用點(diǎn)表示經(jīng)過的縣市，線(鏈)表示兩市之間的運(yùn)輸代價(jià)：時(shí)間、或距離、或時(shí)間和距離的加權(quán)平均。 要確定：從A市到終點(diǎn)的最佳運(yùn)輸路線。 /最短路徑問題,.,33,2,問題的不同條件,沿著眼前(局部)的最短路走下去，可能找不到最佳路線！,.,34,（一）最短路徑的動態(tài)規(guī)劃法,要點(diǎn)：,適用于什么場合？ 如何求解？ 逆序、標(biāo)號法,19,在節(jié)點(diǎn)旁標(biāo)出該點(diǎn)到終點(diǎn)的最短距離,.,35,（一）最短路徑的動態(tài)規(guī)劃法,要點(diǎn)：,最佳路徑是：,19,AB2C2D1E,.,36,思路：若點(diǎn)序列 Vs,V1,V2,Vn-1

10、,Vn 是從Vs到Vn的最短路，則 Vs,V1,V2,Vn-1 必定是從Vs到Vn-1的最短路。 定義： P(Vi)=Vi到Vs的最短距離；lij兩點(diǎn)間距離,（二）最短路徑的網(wǎng)絡(luò)圖法Dijkstra方法,O,A,B,C,D,E,T,2,2,5,4,1,7,4,4,3,1,7,5,起點(diǎn),終點(diǎn),.,37,次序n 舊節(jié)點(diǎn) 新節(jié)點(diǎn) 總距離 第n個(gè)最近的節(jié)點(diǎn)，最短距離，連接 1 O A 2 A 2 OA 2 O C 4 C 4 OC A B 2+2=4 B 4 AB 3 A D 2+7=9 B E 4+3=7 E 7 BE C E 4+4=8 4 A D 2+7=9 B D 4+4=8 D 8 BD E

11、 D 7+1=8 D 8 ED 5 D T 8+5=13 T 13 DT E T 7+7=14,求解過程,起點(diǎn),終點(diǎn),.,38,二、起迄點(diǎn)重合的運(yùn)輸路線規(guī)劃,應(yīng)用問題,貨車運(yùn)輸時(shí)碰到的普遍問題: 從某倉庫（或配送中心）送貨到零售點(diǎn)然后返回； 從零售店到客戶地配送的路線設(shè)計(jì)； 垃圾收運(yùn)車（或送餐車）的路線設(shè)計(jì)。,.,39,二、起迄點(diǎn)重合的運(yùn)輸路線規(guī)劃,應(yīng)用問題,原則： 既經(jīng)過所有點(diǎn)或街道，又要求時(shí)間最短或總距離最短。 問題復(fù)雜性： 可行方案很多，優(yōu)化上的“組合爆炸”，,.,40,(一)旅行商問題TSP模型 （Traveling Salesman Problem） 經(jīng)過網(wǎng)絡(luò)中的各頂點(diǎn),問題及方法的

12、分類,（二）中國郵遞員問題,.,41,（二）中國郵遞員問題 郵遞員從郵局出發(fā)，走遍他所負(fù)責(zé)的街道，完成投遞后返回郵局，怎樣走才使總路程最短？ 城市配送中心為分布在各街道的便民連鎖店配送完貨物后再返回配送中心； 流動推銷員從銷售中心出發(fā)，沿著街道推銷商品，最后再返回銷售中心，也屬于這類問題。,問題及方法的分類,.,42,（一）單回路運(yùn)輸TSP模型,單一車輛的路徑安排 要求：,不可遺漏：訪問所有節(jié)點(diǎn)(或客戶) 只有一個(gè)回路，各點(diǎn)只能被訪問一次,例如：從A出發(fā)送貨到B、C、D個(gè)小配送站。任意兩點(diǎn)間距離已知(或可求) 求：最佳行程？,.,43,TSP的數(shù)學(xué)模型：0-1模型,Xij=0 從i到j(luò)無通路

13、Xij=1 從i到j(luò)有通路,.,44,組合爆炸,可行方案共 (n-1)! 個(gè),送貨順序：C3 C1C2C4 總路長d=d31+ d12+ d24+ d43 dijCiCj之間的距離,.,45,TSP問題的求解算法,整數(shù)規(guī)劃（小規(guī)模問題） 啟發(fā)式算法： 貪婪算法 （參見例題解法） 最近插入法(nearest insertion) 現(xiàn)代優(yōu)化方法： Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化 GA遺傳算法,.,46,（二）中國郵遞員問題及其解法,圖論要點(diǎn)復(fù)習(xí)： 偶點(diǎn)與奇點(diǎn) “一筆畫”問題 “一筆畫”的條件 圖論之“奇偶點(diǎn)圖上作業(yè)” 奇點(diǎn)之間的邊重復(fù),.,47,求解過程：,確定初始可行方案 判斷方案的最優(yōu)性,行走方

14、案B,方案A,判斷標(biāo)準(zhǔn)： 每一邊上最多有一條重復(fù)邊； 圖中每個(gè)圈上重復(fù)邊的總權(quán)不大于該圈總權(quán)的一半。,.,48,郵遞員問題及其解法,最優(yōu)行走方案：,方法局限： 圖形復(fù)雜后，可行方案太多。 圈過多。,.,49,第四節(jié) 多車輛配送路線的優(yōu)化車輛路徑問題VRP（Vehicle Routing Problem）,.,50,第四節(jié) 多車輛配送路線的優(yōu)化,.,51,一、問題描述,某物流中心要為q個(gè)客戶提供服務(wù)。己知每個(gè)客戶點(diǎn)的地理位置及其貨運(yùn)需求量，物流中心需要調(diào)用多輛貨車來滿足這些客戶的服務(wù)需求，每輛車載重量一定。如何指派車輛？行車路徑？,.,52,（一）模型假設(shè),（1）單一物流中心，多部車輛配送。 （

15、2）每個(gè)需求點(diǎn)由一輛車服務(wù)，每個(gè)客戶點(diǎn)貨物需求量不超過車輛的載重容量。 （3）車輛為單一車種，相同載重量，且容量有限。 （4）無時(shí)窗限制的配送問題。 （5）客戶的位置和需求量均為已知。 （6）配送的貨物視為同一種商品，便于裝載。,.,53,（二）多車輛配送路線優(yōu)化數(shù)學(xué)模型（了解）,1、變量 2、目標(biāo)：,xijk車輛k是否直接從節(jié)點(diǎn)i到節(jié)點(diǎn)j； yik車輛k是否訪問節(jié)點(diǎn)i。,.,54,（二）多車輛配送路線優(yōu)化數(shù)學(xué)模型,3、約束條件：,（1）每個(gè)客戶點(diǎn)只能被一輛車訪問： （2）車輛的載重能力約束： （3）進(jìn)入和離開某個(gè)客戶的是同一輛車： （4）消除子回環(huán)： （5）參數(shù)的取值范圍： （6） 所需最少

16、車輛數(shù)：,.,55,（三）多車輛路徑問題求解方法概述,1精確優(yōu)化方法 2人工智能方法 3模擬方法 4啟發(fā)式方法,掃描法 節(jié)約法,.,56,二、掃描法（sweep method)*,算法原理,按照角度大小以逆時(shí)鐘或順時(shí)鐘方向掃描所有客戶點(diǎn)，若滿足車輛裝載量即劃分為一群； 掃描完畢，在每個(gè)群內(nèi)部用最短路徑算法求出車輛行駛路徑。,二階段法,.,57,二、掃描法,例8-5,載重量為10噸的車若干輛,.,58,例題各點(diǎn)位置的圖形顯示,.,59,二、掃描法,算法步驟,以物流中心為原點(diǎn)，計(jì)算客戶點(diǎn)的極坐標(biāo),按一定方向掃描所有客戶點(diǎn),客戶點(diǎn)需求量進(jìn)行累加,.,60,在極坐標(biāo)系顯示各點(diǎn)位置，標(biāo)出相應(yīng)貨運(yùn)量,.,

17、61,例,.,62,例,.,63,課堂練習(xí)： 客戶的取貨量（單位：件），車輛載重10000件貨物。,W,3000,2000,3000,4000,1000,3000,2000,1000,2000,2000,2000,2000,.,64,三、節(jié)約法（savings method）,1、基本思想： 如果將運(yùn)輸問題中的兩個(gè)回路合并成一個(gè)回路，就可縮短線路總里程（即節(jié)約了距離），并減少了一輛卡車。,節(jié)約的里程=?,.,65,2、節(jié)約法步驟,例8-6,配送中心共有4輛載重量為200件的卡車,如何分配客戶？ 如何確定車輛行駛路徑？,.,66,2、節(jié)約法步驟,算法的關(guān)鍵問題,怎樣確定初始可行方案？ 怎樣對現(xiàn)有

18、方案中的回路進(jìn)行合并？,每個(gè)客戶由一輛車送貨 先對節(jié)約量最大的兩客戶（回路）進(jìn)行合并,.,67,2、節(jié)約法步驟,（1）確定距離方陣； （2）確定節(jié)約方陣； （3）將客戶劃歸由不同的卡車提供服務(wù)； （4）確定每輛車的行車線路。,.,68,2、節(jié)約法步驟,（1）確定距離方陣，表8-13,.,69,2、節(jié)約法步驟,（2）確定節(jié)約方陣， 表8-14,“配送中心-客戶A- 配送中心”,“配送中心-客戶B- 配送中心”,“配送中心-客戶A-客戶B-配送中心”,節(jié)約距離：(A，B)=AB=CAO+CBO-CAB,.,70,2、節(jié)約法步驟,（2）節(jié)約方陣， 表8-14,.,71,（3）將客戶劃歸由不同的卡車提供服務(wù)（現(xiàn)有線路的合并）*,合并原則：,保證兩條線路的合并是可行的，即運(yùn)輸總量不超過卡車載重量； 使節(jié)約最大的兩條線路合并成一條新的可行線路。,