運(yùn)輸及配送路線(xiàn)的優(yōu)化

運(yùn)輸及配送路線(xiàn)的優(yōu)化第一頁(yè)，共十九頁(yè)，編輯于2023年，星期二第一節(jié)運(yùn)輸方式的選擇

一、運(yùn)輸方式選擇的原則（一）安全性原則（二）及時(shí)性原則（三）準(zhǔn)確性原則（四）經(jīng)濟(jì)性原則第二頁(yè)，共十九頁(yè)，編輯于2023年，星期二二、運(yùn)輸方式選擇的定量分析法

基于運(yùn)輸成本與庫(kù)存成本的總成本分析方法例8-1

某公司欲將產(chǎn)品從位置A的工廠(chǎng)運(yùn)往位置B的公司自有倉(cāng)庫(kù)，年運(yùn)量D=700000件，產(chǎn)品單價(jià)C=30元，年存貨成本I=產(chǎn)品價(jià)格的30％。公司希望選擇使總成本最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫(kù)存成本可以減少1％。各種運(yùn)輸服務(wù)方式的有關(guān)參數(shù)見(jiàn)表8-1：第三頁(yè)，共十九頁(yè)，編輯于2023年，星期二二、運(yùn)輸方式選擇的定量分析法

表8-1運(yùn)輸方式費(fèi)率R(元/件)時(shí)間T(天)年運(yùn)送批次平均存貨量Q/2鐵路0.12110100000馱背0路0.252042000航空1.424020250第四頁(yè)，共十九頁(yè)，編輯于2023年，星期二二、運(yùn)輸方式選擇的定量分析法解：以年總成本最低為原則來(lái)選擇合適的運(yùn)輸方式。這里，總成本=運(yùn)輸費(fèi)用+庫(kù)存成本；其中，運(yùn)輸費(fèi)用=運(yùn)輸量費(fèi)率庫(kù)存成本=在途運(yùn)輸庫(kù)存成本+工廠(chǎng)存貨成本+倉(cāng)庫(kù)存貨成本在途運(yùn)輸庫(kù)存費(fèi)用=ICDT/365工廠(chǎng)存貨成本=ICQ/2倉(cāng)庫(kù)存貨成本=I（C+R）Q/2代入各種運(yùn)輸方式的基本數(shù)據(jù)信息，將相應(yīng)的成本計(jì)算結(jié)果列入表8-2。第五頁(yè)，共十九頁(yè)，編輯于2023年，星期二二、運(yùn)輸方式選擇的定量分析法表8-2各種運(yùn)輸方式成本計(jì)算結(jié)果由表中結(jié)果可知，總成本最低的是公路運(yùn)輸方式，總成本為984821元，其次是馱背運(yùn)輸，成本最高的是鐵路運(yùn)輸。按照總成本最低的原則，適合選擇公路運(yùn)輸方式。

成本類(lèi)型計(jì)算公式鐵路運(yùn)輸馱背運(yùn)輸公路運(yùn)輸航空運(yùn)輸運(yùn)輸成本RD70000105000140000980000在途庫(kù)存ICDT/3653452052416448630134521工廠(chǎng)存貨ICQ/2900000416500378000182250倉(cāng)庫(kù)存貨I(C+R)Q/2903000420593380520190755總成本

221820511857379848211387526第六頁(yè)，共十九頁(yè)，編輯于2023年，星期二第三節(jié)物資運(yùn)輸調(diào)配決策

一、多起迄點(diǎn)間的直達(dá)運(yùn)輸

設(shè)某物資有m個(gè)產(chǎn)地A1，A2，…，Am；供應(yīng)n個(gè)銷(xiāo)售地B1，B2，…，Bn；已知Ai的產(chǎn)量為ai（i=1，2，…，m），Bj的需求量為bj（j=1，2，…，n）。由Ai到Bj的單位運(yùn)價(jià)為Cij。用Xij表示由產(chǎn)地Ai運(yùn)輸?shù)戒N(xiāo)地Bj的物資量（i＝1，2，…，m；j=1，2，…，n），如圖8-1所示。圖8-1多點(diǎn)之間的物資運(yùn)輸調(diào)撥問(wèn)題示意圖第七頁(yè)，共十九頁(yè)，編輯于2023年，星期二第三節(jié)物資運(yùn)輸調(diào)配決策

（一）產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題1．產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題數(shù)學(xué)模型（8-1）約束條件為：

（8-2）（8-3）

i＝1，2，…，m；j=1，2，…，n

且第八頁(yè)，共十九頁(yè)，編輯于2023年，星期二第三節(jié)物資運(yùn)輸調(diào)配決策

（二）產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題1．總產(chǎn)量大于總銷(xiāo)量即：，則增加一個(gè)假想的銷(xiāo)地Bn+1，其銷(xiāo)量為：（8-4）從產(chǎn)地Ai運(yùn)往假想銷(xiāo)地Bn+1的物資數(shù)量實(shí)際上是停留在原產(chǎn)地沒(méi)有運(yùn)出的物資，因此，相應(yīng)的運(yùn)價(jià)為0，這樣就將不平衡運(yùn)輸問(wèn)題轉(zhuǎn)化為平衡運(yùn)輸問(wèn)題。第九頁(yè)，共十九頁(yè)，編輯于2023年，星期二第三節(jié)物資運(yùn)輸調(diào)配決策2．總銷(xiāo)量大于總產(chǎn)量即：，可增加一個(gè)假想的產(chǎn)地Am+1，其產(chǎn)量為：（8-5）

由于假想的產(chǎn)地并不存在，其產(chǎn)量也不可能存在，由假想產(chǎn)地運(yùn)往某個(gè)銷(xiāo)地的物資數(shù)量實(shí)際上就是該銷(xiāo)地不能滿(mǎn)足的需求量，因此相應(yīng)的運(yùn)價(jià)為0，這樣就將不平衡運(yùn)輸問(wèn)題轉(zhuǎn)化為平衡運(yùn)輸問(wèn)題。第十頁(yè)，共十九頁(yè)，編輯于2023年，星期二第三節(jié)物資運(yùn)輸調(diào)配決策二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配（一）問(wèn)題描述如圖8-2所示，某物流系統(tǒng)中有f個(gè)工廠(chǎng)（供應(yīng)地），m個(gè)流通中心（中轉(zhuǎn)站），n個(gè)零售商店（需求地）。已知工廠(chǎng)Ak的生產(chǎn)能力為ak（k=1，2，…，f），流通中心Ti的配送能力為ti（i=1，2，…，m），零售店Bj的需求量為bj（j=1，2，…，n）。由Ak經(jīng)Ti運(yùn)到Bj的單位運(yùn)價(jià)為Ckij。求：在工廠(chǎng)生產(chǎn)能力一定，流通中心配送能力限制的條件下，滿(mǎn)足零售店需求量的最優(yōu)運(yùn)輸方案。圖8-2有中間轉(zhuǎn)運(yùn)的物資運(yùn)輸調(diào)撥問(wèn)題第十一頁(yè)，共十九頁(yè)，編輯于2023年，星期二第三節(jié)物資運(yùn)輸調(diào)配決策（二）數(shù)學(xué)模型用Xkij表示由產(chǎn)地Ak經(jīng)流通中心Ti運(yùn)輸?shù)搅闶鄣闎j的物資量（k=1，2，…，f；i＝1，2，…，m；j=1，2，…，n），這就是問(wèn)題的決策變量。其目標(biāo)函數(shù)為：（8-6）約束條件為：（1）配送量生產(chǎn)能力的限制：

k=1，2，…，f；

（8-7）（2）流通中心發(fā)送能力的限制：

i＝1，2，…，m；

（8-8）第十二頁(yè)，共十九頁(yè)，編輯于2023年，星期二第三節(jié)物資運(yùn)輸調(diào)配決策（3）滿(mǎn)足零售店需求量：

j=1，2，…，n；（8-9）（4）變量非負(fù)：（8-10）

（三）求解方法求解上述問(wèn)題有兩種方法。一種是運(yùn)用一般的線(xiàn)性規(guī)劃方法求解，但由于該問(wèn)題的變量數(shù)多、約束方程多，求解過(guò)程十分復(fù)雜、計(jì)算量特別大。另一種方法就是運(yùn)用運(yùn)輸問(wèn)題表上作業(yè)法，其基本思路是：補(bǔ)充一些虛擬的產(chǎn)地或需求地，將有中轉(zhuǎn)的運(yùn)輸問(wèn)題轉(zhuǎn)化為無(wú)中轉(zhuǎn)的直達(dá)運(yùn)輸問(wèn)題；再進(jìn)一步轉(zhuǎn)化為供需平衡的運(yùn)輸問(wèn)題；然后，再運(yùn)用表上作業(yè)法求解。下面通過(guò)例題說(shuō)明第二種方法的應(yīng)用。第十三頁(yè)，共十九頁(yè)，編輯于2023年，星期二第四節(jié)單一車(chē)輛配送路線(xiàn)的優(yōu)化

一、起迄點(diǎn)不同的單一路線(xiàn)優(yōu)化（一）動(dòng)態(tài)規(guī)劃法

首先，根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)特征將整個(gè)線(xiàn)路網(wǎng)絡(luò)劃分成多個(gè)階段；其次，對(duì)每個(gè)階段的決策問(wèn)題求解；最后對(duì)于每一階段，以初始狀態(tài)為基礎(chǔ)確定下一階段的可選狀態(tài)，并計(jì)算各狀態(tài)的代價(jià)，然后從中選擇代價(jià)最小的狀態(tài)。

（二）Dijkstra方法此方法主要用來(lái)解決圖論中的最短路徑問(wèn)題。廣義上，“最短路徑”不單指“純距離”意義上的最短路徑，它可以是“經(jīng)濟(jì)距離”意義上的最短路徑，“時(shí)間”意義上的最短路徑，“網(wǎng)絡(luò)”意義上的最短路徑等。第十四頁(yè)，共十九頁(yè)，編輯于2023年，星期二第四節(jié)單一車(chē)輛配送路線(xiàn)的優(yōu)化二、起迄點(diǎn)重合的單一路線(xiàn)優(yōu)化（一）旅行商問(wèn)題TSP模型（TravelingSalesmanProblem）TSP模型可描述如下：在一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的網(wǎng)絡(luò)中，要求找出一個(gè)包括所有頂點(diǎn)的具有最小耗費(fèi)（例如最短距離、或最小時(shí)間代價(jià)）的環(huán)路。一個(gè)環(huán)路也就是一個(gè)回路，既然回路是包含了所有頂點(diǎn)的一個(gè)循環(huán)，所以，可以將任何一個(gè)點(diǎn)作為起點(diǎn)和終點(diǎn)。（二）中國(guó)郵遞員問(wèn)題郵遞員從郵局出發(fā)，走遍他所負(fù)責(zé)的街道，完成投遞后返回郵局，怎樣走才使總路程最短？城市配送中心為分布在各街道的便民連鎖店配送完貨物后再返回配送中心；流動(dòng)推銷(xiāo)員從銷(xiāo)售中心出發(fā)，沿著街道推銷(xiāo)商品，最后再返回銷(xiāo)售中心，也屬于這類(lèi)問(wèn)題。由于該類(lèi)問(wèn)題是我國(guó)學(xué)者管梅谷在1962年首先提出的，國(guó)際上通稱(chēng)這類(lèi)問(wèn)題為中國(guó)郵遞員問(wèn)題。第十五頁(yè)，共十九頁(yè)，編輯于2023年，星期二第五節(jié)多車(chē)輛配送路線(xiàn)的優(yōu)化

一、問(wèn)題概述（一）多車(chē)輛路徑問(wèn)題VRP（VehicleRoutingProblem）多車(chē)輛路徑問(wèn)題在現(xiàn)實(shí)中普遍存在。例如，一家大型物流中心要為成百上千的客戶(hù)提供送貨或取貨的服務(wù)，就需要對(duì)運(yùn)輸車(chē)輛的數(shù)量及其行駛路線(xiàn)進(jìn)行規(guī)劃。（二）多車(chē)輛路徑問(wèn)題數(shù)學(xué)模型模型假設(shè)：（1）單一物流中心，多部車(chē)輛配送。（2）每個(gè)需求點(diǎn)由一輛車(chē)服務(wù)，每個(gè)客戶(hù)點(diǎn)貨物需求量不超過(guò)車(chē)輛的載重容量。（3）車(chē)輛為單一車(chē)種，即視為相同的載重量，且有容量限制。（4）無(wú)時(shí)窗限制的配送問(wèn)題。（5）客戶(hù)的位置和需求量均為已知。（6）配送的貨物視為同一種商品，便于裝載。

（三）多車(chē)輛路徑問(wèn)題求解方法概述求解上述VRP模型，可以應(yīng)用精確優(yōu)化算法、智能優(yōu)化算法、模擬方法、啟發(fā)式方法等。第十六頁(yè)，共十九頁(yè)，編輯于2023年，星期二第五節(jié)多車(chē)輛配送路線(xiàn)的優(yōu)化

二、掃描法

描述：掃描法在VRP求解方法中是一種先分群再尋找最佳路線(xiàn)的算法。求解過(guò)程分為兩步：第一步是分派車(chē)輛服務(wù)的站點(diǎn)或客戶(hù)點(diǎn)；第二步是決定每輛車(chē)的行車(chē)路線(xiàn)。掃描法的原理是：先以物流中心為原點(diǎn)，將所有需求點(diǎn)的極坐標(biāo)算出，然后依角度大小以逆時(shí)鐘或順時(shí)鐘方向掃描，若滿(mǎn)足車(chē)輛裝載容量即劃分為一群，將所有點(diǎn)掃描完畢后在每個(gè)群內(nèi)部用最短路徑算法求出車(chē)輛行駛路徑。第十七頁(yè)，共十九頁(yè)，編輯于2023年，星期二第五節(jié)多車(chē)輛配送路線(xiàn)的優(yōu)化掃描法步驟：

1．以物流中心為原點(diǎn)，將所有客戶(hù)需求點(diǎn)的極坐標(biāo)計(jì)算出來(lái)。

2．以零角度為極坐標(biāo)軸，按順時(shí)針或逆時(shí)針?lè)较?，依角度大小開(kāi)始掃描。

3．將掃描經(jīng)過(guò)的客戶(hù)點(diǎn)需求量進(jìn)行累加，當(dāng)客戶(hù)需求總量達(dá)到一輛車(chē)的載重量限制且不超過(guò)載重量極限時(shí)，就將這些客戶(hù)劃分為一群，即由同一輛車(chē)完成送貨服務(wù)。接著，按照同樣的方法對(duì)其余客戶(hù)劃分新的客戶(hù)群，指派新的車(chē)輛。

4．重復(fù)步驟3，直到所有的客戶(hù)都被劃分