《物流系統(tǒng)分析》課件 項(xiàng)目九-任務(wù)三 （一）車輛路徑優(yōu)化模型1

項(xiàng)目九

運(yùn)輸系統(tǒng)決策哈爾濱職業(yè)技術(shù)學(xué)院車輛路徑優(yōu)化模型集裝箱空箱調(diào)度優(yōu)化模型多式聯(lián)運(yùn)優(yōu)化模型一二三項(xiàng)目九運(yùn)輸系統(tǒng)決策任務(wù)三

理解復(fù)雜運(yùn)輸系統(tǒng)決策優(yōu)化模型和方法

車輛路徑問題(vehicleroutingproblem.VRP)是指在客戶需求位置已知的情況下，確定車輛在各個(gè)客戶間的行程路線，使得運(yùn)輸路線最短或運(yùn)輸成本最低。

從配送中心(物流據(jù)點(diǎn))用多輛汽車向多個(gè)需求點(diǎn)(顧客)送貨，每個(gè)需求點(diǎn)的位置和需求量一定，每輛汽車的裝載量一定，要求合理安排汽車路線，使總運(yùn)距最短，并滿足以下條件：

(1)每條配送路徑上各需求點(diǎn)的需求量之和不超過汽車裝載量；

(2)每條配送路徑的長度不超過汽車一次配送的最大行駛距離；

(3)每個(gè)需求點(diǎn)的需求必須滿足，且只能由一輛汽車送貨。問題描述項(xiàng)目九運(yùn)輸系統(tǒng)決策——車輛路徑優(yōu)化模型任務(wù)三

理解復(fù)雜運(yùn)輸系統(tǒng)決策優(yōu)化模型和方法項(xiàng)目九運(yùn)輸系統(tǒng)決策

問題建模——車輛路徑優(yōu)化模型任務(wù)三

理解復(fù)雜運(yùn)輸系統(tǒng)決策優(yōu)化模型和方法VRP求解算法分析①起訖點(diǎn)相同的車輛路徑優(yōu)化——節(jié)約法節(jié)約法也稱為節(jié)約里程法（Clarke-Wright法,C-W法），該算法能靈活處理許多現(xiàn)實(shí)的約束條件，如能同時(shí)確定車輛數(shù)及車輛經(jīng)過各站點(diǎn)的順序。由于其簡單性和一定程度的實(shí)用性，成為廣泛使用的求解VRP模型的近似算法。

項(xiàng)目九運(yùn)輸系統(tǒng)決策基本原理是幾何學(xué)中三角形一邊之長必定小于另外兩邊之和。核心思想是依次將運(yùn)輸問題中的兩個(gè)回路合并為一個(gè)回路，每次使合并后的總運(yùn)輸距離減小的幅度最大，直到達(dá)到一輛車的裝載限制時(shí)，再進(jìn)行下一輛車的優(yōu)化。優(yōu)化過程分為并行方式和串行方式兩種?！囕v路徑優(yōu)化模型任務(wù)三

理解復(fù)雜運(yùn)輸系統(tǒng)決策優(yōu)化模型和方法

有一配送（P）具有如圖所示的配送網(wǎng)絡(luò)，其中A-J表示收貨站，（）內(nèi)數(shù)字表示發(fā)送量(噸)，路線上的數(shù)字表示道路距離（公里)。問為使行走距離盡量小，應(yīng)該如何去求配送線路？假設(shè)能夠利用的車是2噸車(即最大載重量是2噸)和4噸車兩種，并限制車輛一次運(yùn)行的初步距離是30公里問題描述解：Step1：作出最短距離矩陣，首先從配送網(wǎng)絡(luò)圖中計(jì)算出配送中心與收貨點(diǎn)之間以及收貨點(diǎn)相互之間的最短距離矩陣，見下表所示:

問題解決PABCDEFGHIJP

109788834107A

491418181314114B

51014171213158C

591510111713D

61311121815E

710121815F

681715G

21110H

911I

8J

項(xiàng)目九運(yùn)輸系統(tǒng)決策——車輛路徑優(yōu)化模型任務(wù)三

理解復(fù)雜運(yùn)輸系統(tǒng)決策優(yōu)化模型和方法

Step2：根據(jù)節(jié)約里程表中節(jié)約里程的順序，由大到小排列，編制節(jié)約里程順序表例如:計(jì)算A-B的節(jié)約里程項(xiàng)目如下:P-A的距離是:a=10P-B的距離是:b=9A-B的距離是:c=4節(jié)約里程項(xiàng)目為:a+b-c=10+9-4=15公里

問題解決ABCDEFGHIJA