運(yùn)輸路線選擇PPT課件

1、本次課程項(xiàng)目2.3 任務(wù)2.3.1情境2.3.1：遠(yuǎn)大公司的汽車配件需從義烏運(yùn)至北侖，結(jié)合浙江省詳細(xì)地圖，做好運(yùn)輸路徑優(yōu)化：現(xiàn)要求你找出路程最短的運(yùn)輸路線。案例1：百勝物流降低連鎖餐飲企業(yè)運(yùn)輸成本之道任務(wù)任務(wù)1 運(yùn)用標(biāo)號(hào)法完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇運(yùn)用標(biāo)號(hào)法完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇情境2.3.2：由于時(shí)間很趕，需要你找出花費(fèi)時(shí)間最短的運(yùn)輸路線。任務(wù)任務(wù)2 運(yùn)用標(biāo)號(hào)法和軟件操作完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇運(yùn)用標(biāo)號(hào)法和軟件操作完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇情境2.3.3：這票貨物賺的不多，在時(shí)間允許的情況下，需要你找出成本最低的運(yùn)輸路線。情境2.3.4：義烏公司

2、的倉(cāng)庫(kù)有多個(gè)，現(xiàn)接到聯(lián)發(fā)的裝貨通知，義烏公司需從其各個(gè)倉(cāng)庫(kù)提貨到總公司。請(qǐng)為該業(yè)務(wù)設(shè)計(jì)運(yùn)輸路線并調(diào)度。任務(wù)任務(wù)3 運(yùn)用掃描法完成起訖點(diǎn)重合的運(yùn)輸路線優(yōu)化選擇運(yùn)用掃描法完成起訖點(diǎn)重合的運(yùn)輸路線優(yōu)化選擇第1頁(yè)/共21頁(yè)知識(shí)目標(biāo)：知識(shí)目標(biāo)： 1.了解運(yùn)輸路線的類型；2.掌握最短路（單一起訖點(diǎn)運(yùn)輸路線）的原理和計(jì)算方法3.了解起訖點(diǎn)重合運(yùn)輸路線的優(yōu)化問(wèn)題4. 了解多起訖點(diǎn)的運(yùn)輸路線優(yōu)化問(wèn)題 能力目標(biāo)：能力目標(biāo)：1.能運(yùn)用最短路方法正確制定運(yùn)輸路線選擇方案；2.能運(yùn)用計(jì)算機(jī)軟件正確制定運(yùn)輸路線選擇方案素質(zhì)目標(biāo)：素質(zhì)目標(biāo)：成本意識(shí)、優(yōu)化思維能力成本意識(shí)、優(yōu)化思維能力 、自主學(xué)習(xí)能力。、自主學(xué)習(xí)能力。第2頁(yè)

3、/共21頁(yè)案例1：百勝物流降低連鎖餐飲企業(yè)運(yùn)輸成本之道合理安排運(yùn)輸排程 運(yùn)輸排程的意義在于，盡量使車輛滿載，只要貨量許可，就應(yīng)該做相應(yīng)的調(diào)整，以減少總行駛里程. 運(yùn)輸排程的構(gòu)想最初起源于運(yùn)籌學(xué)中的路線原理，其最簡(jiǎn)單的是從起點(diǎn)A到終點(diǎn)O有多條路徑可供選擇，每條路徑的長(zhǎng)度各不相同，要求找到最短的路線。實(shí)際問(wèn)題要比這個(gè)模型復(fù)雜得多，首先，需要了解最短路線的點(diǎn)數(shù)，從幾個(gè)點(diǎn)增加到成百甚至上千個(gè)，路徑的數(shù)量也相應(yīng)增多到成千上萬(wàn)條。其次，每個(gè)點(diǎn)都有一定數(shù)量的貨物流需要配送或提取，因此要尋找的不是一條串聯(lián)所有點(diǎn)的最短路線，而是每條串聯(lián)幾個(gè)點(diǎn)的若干條路線的最優(yōu)組合。另外，還需要考慮許多限制條件，比如車輛裝載能力

4、、車輛數(shù)目、每個(gè)點(diǎn)在相應(yīng)的時(shí)間開放窗口等，問(wèn)題的復(fù)雜度隨著約束數(shù)目的增加呈幾何級(jí)數(shù)增長(zhǎng)。要解決這些問(wèn)題，需要用線性規(guī)劃、整數(shù)規(guī)劃等數(shù)學(xué)工具，目前市場(chǎng)上有一些軟件公司能夠以這些數(shù)學(xué)解題方法作為引擎，結(jié)合連鎖餐飲業(yè)的物流配送需求，做出優(yōu)化運(yùn)輸路線安排的軟件。第3頁(yè)/共21頁(yè)運(yùn)輸優(yōu)化策略運(yùn)輸優(yōu)化策略運(yùn)輸路線選擇運(yùn)輸路線選擇微課：運(yùn)輸路線和時(shí)間安排的原則情境2.3.1：遠(yuǎn)大公司的汽車配件需從義烏運(yùn)至北侖，結(jié)合浙江省詳細(xì)地圖，做好運(yùn)輸路徑優(yōu)化：現(xiàn)要求你找出路程最短的運(yùn)輸路線。任務(wù)任務(wù)1 運(yùn)用標(biāo)號(hào)法完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇運(yùn)用標(biāo)號(hào)法完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇第4頁(yè)/共21頁(yè) 寧波聯(lián)發(fā)

5、物流有限公司需要在本月底將浙江遠(yuǎn)大汽車配件從義烏運(yùn)送到北侖。該公司根據(jù)這兩個(gè)城市之間可選擇的行車路線的地圖,繪制了如圖的公路網(wǎng)絡(luò).圖中,圓圈稱為節(jié)點(diǎn),代表起點(diǎn)、目的地和與行車路線相交的其他城市，箭頭代表兩個(gè)節(jié)點(diǎn)之間的公路，每條公路都表明運(yùn)輸里程。求A市到B市的最短路？義烏5075851501401008513510015010020080607550北侖第5頁(yè)/共21頁(yè)計(jì)算步驟：0507585175160210275240315義烏5075851501401008513510015010020080607550北侖1、標(biāo)號(hào)，如下圖所示：第6頁(yè)/共21頁(yè)2、反向搜尋，過(guò)程如下：3、結(jié)論：結(jié)論：義

6、烏到北侖的的路線選擇為1（義烏）-4-5-8-10（北侖）， 最短距離為315公里。0507585175160210275240315義烏5075851501401008513510015010020080607550北侖第7頁(yè)/共21頁(yè)最短路問(wèn)題理論總結(jié)起訖點(diǎn)不同的單一運(yùn)輸問(wèn)題起訖點(diǎn)不同的單一運(yùn)輸問(wèn)題 采用方法：Dijstra算法 應(yīng)用條件：1、權(quán)非負(fù)；2、求一給定點(diǎn)到其余各點(diǎn)最短通路及其長(zhǎng)度。 標(biāo)號(hào)法 臨時(shí)標(biāo)號(hào) 固定標(biāo)量給定點(diǎn)到該點(diǎn)的最短通路的長(zhǎng)度，最后用反向搜索法可計(jì)算總長(zhǎng)度。第8頁(yè)/共21頁(yè)原理：如果U= e1, e2, e3 en 為v1到vn的最短距離,則U1= e1, e2, e

7、3 ek 是v1到vk的最短路.注： （1）有固定標(biāo)號(hào)的點(diǎn)（檢查過(guò)的大 上 表示） （2）在所有的臨時(shí)標(biāo)號(hào)中選最小的 作固定標(biāo)號(hào)，即為將被檢查的點(diǎn)； （3）邊檢查邊修改臨時(shí)標(biāo)號(hào)。第9頁(yè)/共21頁(yè)情境2.3.2：由于時(shí)間很趕，需要你找出花費(fèi)時(shí)間最短的運(yùn)輸路線。任務(wù)任務(wù)2 運(yùn)用標(biāo)號(hào)法和軟件操作完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇運(yùn)用標(biāo)號(hào)法和軟件操作完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇練習(xí)：1、標(biāo)號(hào)法完成。義烏11.512.531.52322.5132111北侖義烏到北侖的運(yùn)輸路線如下（數(shù)值代表運(yùn)輸時(shí)間：h)：2、軟件操作：見微課“最短路EXCEL操作過(guò)程”第10頁(yè)/共21頁(yè)任務(wù)任務(wù)2 運(yùn)用標(biāo)號(hào)法和

8、軟件操作完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇運(yùn)用標(biāo)號(hào)法和軟件操作完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇情境2.3.3：這票貨物賺的不多，在時(shí)間允許的情況下，需要你找出成本最低的運(yùn)輸路線。A市100150175300275200175275200300200400250125150100B義烏到北侖的運(yùn)輸路線如下（數(shù)值代表運(yùn)輸成本：元)：練習(xí)：練習(xí)：1、標(biāo)號(hào)法 2、EXCEL求解操作第11頁(yè)/共21頁(yè) 某配送中心與一個(gè)客戶之間的公路網(wǎng)絡(luò)示意圖，O起點(diǎn)為配送中心所在位置，P終點(diǎn)為客戶所在位置，其它A、B、C、D代表從O到P途中要經(jīng)過(guò)的節(jié)點(diǎn)，節(jié)點(diǎn)與節(jié)點(diǎn)之間有線路連接, 線路上標(biāo)明了兩個(gè)節(jié)點(diǎn)之間的距離，

9、以運(yùn)行時(shí)間 ( 分鐘 ) 表示（當(dāng)然也可以用距離表示）?，F(xiàn)在要在該圖找出一條從配送中心（O起點(diǎn)）到客戶（J終點(diǎn)）之間的最短路線。OPCBDA18122843217321117練習(xí)練習(xí)第12頁(yè)/共21頁(yè)理論總結(jié) 1、運(yùn)輸網(wǎng)絡(luò)圖有點(diǎn)和線組成。點(diǎn)即節(jié)點(diǎn)，線即路線；2、運(yùn)輸網(wǎng)絡(luò)圖：有向圖和無(wú)向圖；3、起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇：標(biāo)號(hào)法、excel求解。第13頁(yè)/共21頁(yè)情境2.3.4：義烏公司的倉(cāng)庫(kù)有多個(gè)，現(xiàn)接到聯(lián)發(fā)的裝貨通知，義烏公司需從其各個(gè)倉(cāng)庫(kù)提貨到總公司。請(qǐng)為該業(yè)務(wù)設(shè)計(jì)運(yùn)輸路線并調(diào)度。任務(wù)任務(wù)3 運(yùn)用掃描法完成起訖點(diǎn)重合的運(yùn)輸路線優(yōu)化選擇運(yùn)用掃描法完成起訖點(diǎn)重合的運(yùn)輸路線優(yōu)化選擇 義烏公

10、司從其所屬的倉(cāng)庫(kù)用送貨車輛到各客戶點(diǎn)提貨，然后將客戶的貨物運(yùn)回倉(cāng)庫(kù)，以便集運(yùn)成大的批量再進(jìn)行遠(yuǎn)程運(yùn)輸。全天的提貨量見下圖，提貨量以件為單位。送貨車每次可運(yùn)載1萬(wàn)件，完成一次運(yùn)行路線一般需要一天時(shí)間。該公司要求確定：需多少條路線（即多少輛送貨車）；每條路線上有哪幾個(gè)客戶點(diǎn)；送貨車輛途經(jīng)有關(guān)客戶點(diǎn)的順序。（具體內(nèi)容見下圖）第14頁(yè)/共21頁(yè)義烏總公司400010003000200010002000200020002000300020003000第15頁(yè)/共21頁(yè)總結(jié) 物流管理人員經(jīng)常遇到的一個(gè)路線選擇問(wèn)題是始發(fā)點(diǎn)就是終點(diǎn)的路線選擇，又常稱為“旅行推銷員”問(wèn)題。這類問(wèn)題通常在運(yùn)輸工具是同一部門所有的

11、情況下發(fā)生。郵遞員問(wèn)題起訖點(diǎn)重合的運(yùn)輸問(wèn)題起訖點(diǎn)重合的運(yùn)輸問(wèn)題第16頁(yè)/共21頁(yè)是是開始將所有的停留點(diǎn)位置畫在地圖上選擇最大的車輛裝載這個(gè)停留點(diǎn)的貨物然后順時(shí)針或逆時(shí)針?lè)较蜣D(zhuǎn)動(dòng)直尺，直到直尺交到一個(gè)停留點(diǎn)。通過(guò)倉(cāng)庫(kù)位置放置一直尺，直尺指向任何方向均可是否超過(guò)車輛容積或體積的限度是否掃描完所有停留點(diǎn)安排下一輛車裝載貨物，得到一條運(yùn)行線路結(jié)束繼續(xù)轉(zhuǎn)動(dòng)直尺，掃描到下一個(gè)停留點(diǎn)，分配該車輛裝載貨物優(yōu)化每條運(yùn)行路線的停留點(diǎn)順序，以求運(yùn)行距離最小化否否掃描法 第17頁(yè)/共21頁(yè)掃描法求解過(guò)程400010003000200010002000200020002000300020003000第18頁(yè)/共21頁(yè)總結(jié) 盡管路線選擇問(wèn)題種類繁多，但可以歸為三種基本類型：起迄點(diǎn)不同的單一問(wèn)題、起迄點(diǎn)重合的問(wèn)題、多起迄點(diǎn)問(wèn)題。多起迄點(diǎn)問(wèn)題：如果有多個(gè)貨源地可以服務(wù)于多個(gè)目的地時(shí)，那么我們面臨的問(wèn)題是，要指定為各目的地服務(wù)的供貨地，同時(shí)要找到供貨地、目的地之間的最佳路徑。該問(wèn)題常發(fā)生在多個(gè)供應(yīng)商、工廠或倉(cāng)庫(kù)服務(wù)于多個(gè)客戶的情況下。第19頁(yè)/共21頁(yè)作