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

運(yùn)輸及配送路線的優(yōu)化第一節(jié)運(yùn)輸方式的選擇

一、運(yùn)輸方式選擇的原則（一）安全性原則（二）及時(shí)性原則（三）準(zhǔn)確性原則（四）經(jīng)濟(jì)性原則第2頁,共19頁，2024年2月25日，星期天二、運(yùn)輸方式選擇的定量分析法

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

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

表8-1運(yùn)輸方式費(fèi)率R(元/件)時(shí)間T(天)年運(yùn)送批次平均存貨量Q/2鐵路0.12110100000馱背0路0.252042000航空1.424020250第4頁,共19頁，2024年2月25日，星期天二、運(yùn)輸方式選擇的定量分析法解：以年總成本最低為原則來選擇合適的運(yùn)輸方式。這里，總成本=運(yùn)輸費(fèi)用+庫存成本；其中，運(yùn)輸費(fèi)用=運(yùn)輸量

費(fèi)率庫存成本=在途運(yùn)輸庫存成本+工廠存貨成本+倉庫存貨成本在途運(yùn)輸庫存費(fèi)用=ICDT/365工廠存貨成本=ICQ/2倉庫存貨成本=I（C+R）Q/2代入各種運(yùn)輸方式的基本數(shù)據(jù)信息，將相應(yīng)的成本計(jì)算結(jié)果列入表8-2。第5頁,共19頁，2024年2月25日，星期天二、運(yùn)輸方式選擇的定量分析法表8-2各種運(yùn)輸方式成本計(jì)算結(jié)果由表中結(jié)果可知，總成本最低的是公路運(yùn)輸方式，總成本為984821元，其次是馱背運(yùn)輸，成本最高的是鐵路運(yùn)輸。按照總成本最低的原則，適合選擇公路運(yùn)輸方式。

成本類型計(jì)算公式鐵路運(yùn)輸馱背運(yùn)輸公路運(yùn)輸航空運(yùn)輸運(yùn)輸成本R

D70000105000140000980000在途庫存ICDT/3653452052416448630134521工廠存貨ICQ/2900000416500378000182250倉庫存貨I(C+R)Q/2903000420593380520190755總成本

221820511857379848211387526第6頁,共19頁，2024年2月25日，星期天第三節(jié)物資運(yùn)輸調(diào)配決策

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

設(shè)某物資有m個(gè)產(chǎn)地A1，A2，…，Am；供應(yīng)n個(gè)銷售地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地Bj的物資量（i＝1，2，…，m；j=1，2，…，n），如圖8-1所示。圖8-1多點(diǎn)之間的物資運(yùn)輸調(diào)撥問題示意圖第7頁,共19頁，2024年2月25日，星期天第三節(jié)物資運(yùn)輸調(diào)配決策

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

（8-2）（8-3）

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

且第8頁,共19頁，2024年2月25日，星期天第三節(jié)物資運(yùn)輸調(diào)配決策

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

由于假想的產(chǎn)地并不存在，其產(chǎn)量也不可能存在，由假想產(chǎn)地運(yùn)往某個(gè)銷地的物資數(shù)量實(shí)際上就是該銷地不能滿足的需求量，因此相應(yīng)的運(yùn)價(jià)為0，這樣就將不平衡運(yùn)輸問題轉(zhuǎn)化為平衡運(yùn)輸問題。第10頁,共19頁，2024年2月25日，星期天第三節(jié)物資運(yùn)輸調(diào)配決策二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配（一）問題描述如圖8-2所示，某物流系統(tǒng)中有f個(gè)工廠（供應(yīng)地），m個(gè)流通中心（中轉(zhuǎn)站），n個(gè)零售商店（需求地）。已知工廠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ǎn)能力一定，流通中心配送能力限制的條件下，滿足零售店需求量的最優(yōu)運(yùn)輸方案。圖8-2有中間轉(zhuǎn)運(yùn)的物資運(yùn)輸調(diào)撥問題第11頁,共19頁，2024年2月25日，星期天第三節(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），這就是問題的決策變量。其目標(biāo)函數(shù)為：（8-6）約束條件為：（1）配送量

生產(chǎn)能力的限制：

k=1，2，…，f；

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

i＝1，2，…，m；

（8-8）第12頁,共19頁，2024年2月25日，星期天第三節(jié)物資運(yùn)輸調(diào)配決策（3）滿足零售店需求量：

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

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

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

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

（二）Dijkstra方法此方法主要用來解決圖論中的最短路徑問題。廣義上，“最短路徑”不單指“純距離”意義上的最短路徑，它可以是“經(jīng)濟(jì)距離”意義上的最短路徑，“時(shí)間”意義上的最短路徑，“網(wǎng)絡(luò)”意義上的最短路徑等。第14頁,共19頁，2024年2月25日，星期天第四節(jié)單一車輛配送路線的優(yōu)化二、起迄點(diǎn)重合的單一路線優(yōu)化（一）旅行商問題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)。（二）中國郵遞員問題郵遞員從郵局出發(fā)，走遍他所負(fù)責(zé)的街道，完成投遞后返回郵局，怎樣走才使總路程最短？城市配送中心為分布在各街道的便民連鎖店配送完貨物后再返回配送中心；流動(dòng)推銷員從銷售中心出發(fā)，沿著街道推銷商品，最后再返回銷售中心，也屬于這類問題。由于該類問題是我國學(xué)者管梅谷在1962年首先提出的，國際上通稱這類問題為中國郵遞員問題。第15頁,共19頁，2024年2月25日，星期天第五節(jié)多車輛配送路線的優(yōu)化

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

（三）多車輛路徑問題求解方法概述求解上述VRP模型，可以應(yīng)用精確優(yōu)化算法、智能優(yōu)化算法、模擬方法、啟發(fā)式方法等。第16頁,共19頁，2024年2月25日，星期天第五節(jié)多車輛配送路線的優(yōu)化

二、掃描法

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

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

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

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

4．重復(fù)步驟3，直到所有的客戶都被劃分到一個(gè)群中。

5．在