運(yùn)輸路線選擇（起訖點(diǎn)不同的單一運(yùn)輸路線問題）

1、運(yùn)輸調(diào)度管理運(yùn)輸調(diào)度管理運(yùn)輸路線選擇運(yùn)輸路線選擇本次課程本次課程項(xiàng)目項(xiàng)目2.3 任務(wù)任務(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)號法完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇運(yùn)用標(biāo)號法完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇情境2.3.2：由于時間很趕，需要你找出花費(fèi)時間最短的運(yùn)輸路線。任務(wù)任務(wù)2 運(yùn)用標(biāo)號法和軟件操作完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇運(yùn)用標(biāo)號法和軟件操作完成起訖點(diǎn)不同的單一運(yùn)輸路線優(yōu)化選擇情境2.3.3：這票貨物賺的不多，在時間允許

2、的情況下，需要你找出成本最低的運(yùn)輸路線。知識目標(biāo)：知識目標(biāo)： 1.了解運(yùn)輸路線的類型；了解運(yùn)輸路線的類型；2.掌握最短路（單一起訖點(diǎn)運(yùn)輸路線）的原理和計算方法掌握最短路（單一起訖點(diǎn)運(yùn)輸路線）的原理和計算方法3.了解起訖點(diǎn)重合運(yùn)輸路線的優(yōu)化問題了解起訖點(diǎn)重合運(yùn)輸路線的優(yōu)化問題4. 了解多起訖點(diǎn)的運(yùn)輸路線優(yōu)化問題了解多起訖點(diǎn)的運(yùn)輸路線優(yōu)化問題 能力目標(biāo)：能力目標(biāo)：1.能運(yùn)用最短路方法正確制定運(yùn)輸路線選擇方案；能運(yùn)用最短路方法正確制定運(yùn)輸路線選擇方案；2.能運(yùn)用計算機(jī)軟件正確制定運(yùn)輸路線選擇方案能運(yùn)用計算機(jī)軟件正確制定運(yùn)輸路線選擇方案素質(zhì)目標(biāo)：素質(zhì)目標(biāo)：成本意識、優(yōu)化思維能力成本意識、優(yōu)化思維能力

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

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

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

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

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

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