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

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

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

基于運輸成本與庫存成本的總成本分析方法例8-1

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

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

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

成本類型計算公式鐵路運輸馱背運輸公路運輸航空運輸運輸成本R

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

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

一、多起迄點間的直達運輸

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

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

（8-2）（8-3）

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

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

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

由于假想的產(chǎn)地并不存在，其產(chǎn)量也不可能存在，由假想產(chǎn)地運往某個銷地的物資數(shù)量實際上就是該銷地不能滿足的需求量，因此相應(yīng)的運價為0，這樣就將不平衡運輸問題轉(zhuǎn)化為平衡運輸問題。第10頁,共19頁，2024年2月25日，星期天第三節(jié)物資運輸調(diào)配決策二、存在中間轉(zhuǎn)運的物資調(diào)配（一）問題描述如圖8-2所示，某物流系統(tǒng)中有f個工廠（供應(yīng)地），m個流通中心（中轉(zhuǎn)站），n個零售商店（需求地）。已知工廠Ak的生產(chǎn)能力為ak（k=1，2，…，f），流通中心Ti的配送能力為ti（i=1，2，…，m），零售店Bj的需求量為bj（j=1，2，…，n）。由Ak經(jīng)Ti運到Bj的單位運價為Ckij。求：在工廠生產(chǎn)能力一定，流通中心配送能力限制的條件下，滿足零售店需求量的最優(yōu)運輸方案。圖8-2有中間轉(zhuǎn)運的物資運輸調(diào)撥問題第11頁,共19頁，2024年2月25日，星期天第三節(jié)物資運輸調(diào)配決策（二）數(shù)學(xué)模型用Xkij表示由產(chǎn)地Ak經(jīng)流通中心Ti運輸?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é)物資運輸調(diào)配決策（3）滿足零售店需求量：

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

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

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

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

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

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

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

二、掃描法

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

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

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

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

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

5．在