多點(diǎn)物流配送車輛路徑問(wèn)題（VRP）優(yōu)化與實(shí)證分析

摘要：本文應(yīng)用掃描算法對(duì)多點(diǎn)物流配送車輛路徑問(wèn)題進(jìn)行優(yōu)化，借助計(jì)算機(jī)編程實(shí)現(xiàn)多目標(biāo)、動(dòng)態(tài)車輛調(diào)度和線路優(yōu)化。以河北快運(yùn)為例進(jìn)行實(shí)證分析，結(jié)合實(shí)例進(jìn)行測(cè)試和結(jié)果分析，證明其可行性，使該算法設(shè)計(jì)更好地適應(yīng)實(shí)際的需要。

關(guān)鍵詞：多點(diǎn)物流配送；車輛路徑問(wèn)題；優(yōu)化

基金項(xiàng)目：廣東省高等教育教學(xué)研究和改革項(xiàng)目：物流專業(yè)產(chǎn)教融合協(xié)同育人平臺(tái)建設(shè)研究

在配送線路優(yōu)化設(shè)計(jì)中，通常有兩類問(wèn)題：一類是尋求兩點(diǎn)之間最短路徑，此類問(wèn)題一般采用圖論中求解最短路問(wèn)題最好的算法Dijkatra算法進(jìn)行優(yōu)化。另一類是尋求從某一點(diǎn)到其余各點(diǎn)的最短路徑，即物流配送網(wǎng)絡(luò)中有一個(gè)配送中心和n個(gè)節(jié)點(diǎn)，車輛由配送中心出發(fā)，服務(wù)完n個(gè)節(jié)點(diǎn)再返回配送中心。這類問(wèn)題就是多點(diǎn)物流配送車輛路徑問(wèn)題。該問(wèn)題的研究目標(biāo)就是對(duì)一系列客戶需求點(diǎn)設(shè)計(jì)適當(dāng)?shù)呐渌途€路，并在滿足一定約束條件（如供應(yīng)量、需求量、車載限制、時(shí)間限制等）的基礎(chǔ)上，實(shí)現(xiàn)優(yōu)化目標(biāo)（如里程最短、費(fèi)用最省、時(shí)間最少等）。本文筆者重點(diǎn)討論由一個(gè)配送中心向多個(gè)客戶進(jìn)行共同配送的車輛路徑問(wèn)題。

1.模型的建立

多點(diǎn)物流配送車輛路徑問(wèn)題（Vehicle Routing Problem ，VRP）最早是由Dantzig和Ramser于1959年首次提出的，后被證明屬于NP難題行列。

一般車輛路徑問(wèn)題描述為：某配送中心有[M]輛車，需對(duì)[N]個(gè)節(jié)點(diǎn)（客戶）進(jìn)行運(yùn)輸配送，每個(gè)節(jié)點(diǎn)的需求量為[gi]（[i=1，2，...，N]），每輛配送車輛的最大載重量為[q]。設(shè)[cij]表示節(jié)點(diǎn)[i]到節(jié)點(diǎn)[j]的運(yùn)輸成本，如時(shí)間、費(fèi)用等。為構(gòu)建數(shù)學(xué)模型的方便，將配送起點(diǎn)編號(hào)為0，各個(gè)配送任務(wù)節(jié)點(diǎn)標(biāo)號(hào)為1，2，… N，配送中心以及貨運(yùn)節(jié)點(diǎn)統(tǒng)一用點(diǎn)i（i=0，1，2，…N）來(lái)表示。變量定義如下：

[yki=1 節(jié)點(diǎn)i的任務(wù)由車輛k完成0 否則xijk=1 車輛k從節(jié)點(diǎn)i行駛至節(jié)點(diǎn)j0 否則]

建立VRP數(shù)學(xué)模型：

[minz=ijkcijxijkigiyki≤q ?k式（1）kyki=1M i=1，2，…，Ni=0式（2）ixijk=ykj j=1，…，N；?k式（3）jxijk=yki i=0，1，…，N；?k式（4）]

其中，式（1）為車載容量約束；式（2）保證每個(gè)節(jié)點(diǎn)的運(yùn)輸任務(wù)僅由1輛成完成，且所有任務(wù)則由M輛車協(xié)同完成；式（3）和式（4）限制到達(dá)和離開(kāi)某一客戶的車輛僅有1輛。

2 .模型的求解思路 （用VRP 掃描法）

2.1 VRP 掃描算法基本思想

掃描法（Sweep Algorithm） 目的在于求解車輛調(diào)度問(wèn)題，并針對(duì)幾個(gè)求解相似問(wèn)題的算法進(jìn)行比較，證明該算法所求得的解較優(yōu)于其他的方法，此方法屬于先分群再排路線的方法，此方法分為兩階段：

第一階段：用坐標(biāo)表示各需求點(diǎn)的區(qū)位，然后任取一需求點(diǎn)為起點(diǎn)，以車輛容量為分群的約束，再以該需求點(diǎn)為零度按順時(shí)針或逆時(shí)針的方向，進(jìn)行顧客的掃描分群；

第二階段：依據(jù)求解旅行商問(wèn)題（TSP）的算法，求解各顧客群的排程。

2.2 VRP掃描算法求解步驟

2.2.1確定配送中心和各個(gè)節(jié)點(diǎn)的位置和需求量；

2.2.2以配送中心為原點(diǎn)，確定一尚未使用車輛，從最小角度且尚未指派的節(jié)點(diǎn)開(kāi)始，沿著順時(shí)針或逆時(shí)針?lè)较驋呙瑁?dāng)該車輛容量超限時(shí)，結(jié)束該條線路；

2.2.3重復(fù)上述步驟，生成新的線路，直至所有節(jié)點(diǎn)都被排入線路；

2.2.4依據(jù)TSP算法，求解出各站點(diǎn)在各線路上排定的順序，使行駛路線最短，成本最低。

3.算例分析

3.1問(wèn)題描述

本文以“邯運(yùn)杯”全國(guó)大學(xué)生物流設(shè)計(jì)大賽案例中的河北快運(yùn)公司為例進(jìn)行分析研究，本文中的數(shù)據(jù)都來(lái)源于大賽案例。河北快運(yùn)下設(shè)四個(gè)子公司分別為天恒、天昊、天誠(chéng)以及天信。河北快運(yùn)的總分撥點(diǎn)設(shè)在廊坊。河北快運(yùn)2006年及2007年業(yè)務(wù)量如圖1和圖2所示。

由圖1和圖2知，河北快運(yùn)下設(shè)的四個(gè)貨運(yùn)子公司每年貨運(yùn)量差距大，每月總貨運(yùn)周轉(zhuǎn)波動(dòng)幅度大，且各子公司之間存在著相互競(jìng)爭(zhēng)的局勢(shì)，不利于創(chuàng)造雙贏。從中總結(jié)得出河北快運(yùn)需在車輛調(diào)度和配送線路選擇方面進(jìn)行綜合優(yōu)化。

3.2問(wèn)題求解

為了研究的需要，對(duì)模型進(jìn)行一些假設(shè)：①河北快運(yùn)子公司間的競(jìng)爭(zhēng)可協(xié)調(diào)，實(shí)現(xiàn)資源的統(tǒng)一調(diào)配；②假設(shè)所有車輛具有相同容量，車載限額40噸；③暫不考慮貨物的缺失成本。④利用計(jì)算機(jī)進(jìn)行求解，詳細(xì)計(jì)算過(guò)程略，直接得出優(yōu)化結(jié)果。

具體步驟：

①利用VB編程，創(chuàng)建運(yùn)輸配套程序窗口（與總公司的SQL數(shù)據(jù)庫(kù)相連），結(jié)合算法構(gòu)建一個(gè)比較完善的運(yùn)輸調(diào)度系統(tǒng)。

②通過(guò)運(yùn)輸配套程序窗口，獲取多目標(biāo)配送相關(guān)的信息，其中包括貨物種類、數(shù)量、所需到達(dá)時(shí)間及回程貨源等信息。

③在相關(guān)約束條件下，執(zhí)行VRP掃描法，得出最終配送優(yōu)化線路和確定調(diào)配車輛數(shù)。

結(jié)束語(yǔ)

本文針對(duì)多點(diǎn)物流配送車輛路徑問(wèn)題，建立數(shù)學(xué)模型，根據(jù)企業(yè)實(shí)際數(shù)據(jù)、借助計(jì)算機(jī)軟件進(jìn)行算例分析，為企業(yè)的車輛路徑問(wèn)題進(jìn)行優(yōu)化。本文借助計(jì)算機(jī)編程實(shí)現(xiàn)快捷、動(dòng)態(tài)的多點(diǎn)物流配送車輛路徑問(wèn)題優(yōu)化，具有一定的理論價(jià)值和實(shí)際應(yīng)用價(jià)值。在實(shí)際應(yīng)用中，多點(diǎn)物流配送車輛路徑問(wèn)題的優(yōu)化需要考慮的因素很多，為了求解的方便，筆者在求解過(guò)程中作出一些假設(shè)，使本文的算法的應(yīng)用具有一定的差距。所以，如何尋找一種綜合考慮多因素影響的模型和算法，是今后還需進(jìn)一步努力研究的方向。另外，VRP屬于NP難題行列，所以VRP目前仍是一個(gè)困難的組合優(yōu)化問(wèn)題，理論上，僅能保證一些相對(duì)小規(guī)模的VRP可求得最優(yōu)解。

參考文獻(xiàn)：

[1]方金城，張岐山.物流配送車輛路徑問(wèn)題（VRP）算法研究[J].徐州工程學(xué)院學(xué)報(bào)，2007，22（2）：84-88.

[2]洪江濤，陳誠(chéng).物流企業(yè)車輛調(diào)度的優(yōu)化模型研究[J].軟科學(xué)，2011，25（3）：126-129.

作者簡(jiǎn)介：

王榮花（1977- ），女，山西臨汾，碩士研究生，講師，研究方向：物流管理。