閆 凱，李愛光，郭 健，陳 冰

（1.信息工程大學(xué)， 河南 鄭州 450001）

基于時(shí)間窗的多車場(chǎng)車輛路徑問題研究

閆 凱1，李愛光1，郭 健1，陳 冰1

（1.信息工程大學(xué)， 河南 鄭州 450001）

啟發(fā)式優(yōu)化算法在解決車輛路徑問題時(shí)具有較好的收斂性，整體法在解決時(shí)間窗的多車場(chǎng)車輛路徑問題時(shí)具有較好的全局性，結(jié)合二者優(yōu)點(diǎn)，進(jìn)行了算法研究。首先采用整體法得到車輛路徑問題的全局最優(yōu)解；再采用智能優(yōu)化算法對(duì)配送點(diǎn)進(jìn)行車場(chǎng)選擇，匹配代價(jià)最小的車場(chǎng)；最后通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法在解決時(shí)間窗的多車場(chǎng)車輛路徑問題上的有效性。

智能優(yōu)化算法；整體法；時(shí)間窗；多車場(chǎng)車輛路徑

隨著現(xiàn)代物流業(yè)的發(fā)展，車輛路徑規(guī)劃在物流配送領(lǐng)域的作用日趨明顯，設(shè)計(jì)合理的配送方案，提高配送效率，降低配送成本，已成為物流企業(yè)競(jìng)爭(zhēng)的核心。車輛路徑問題（VRP）[1]，即在配送區(qū)域范圍內(nèi)，所有配送車輛都從配送中心出發(fā)，在滿足一定的約束條件（如車輛的最大容載量、貨物需求量、行駛里程約束、時(shí)間限制等）的情況下，選擇合適的配送路線來(lái)實(shí)現(xiàn)特定的目標(biāo)（如總行駛距離最短、時(shí)間最短、使用車輛數(shù)目最少、總體費(fèi)用最低等）。目前，VRP已廣泛應(yīng)用于軍事物流配送、快遞投放與取件、垃圾回收和牛奶配送等行業(yè)。

隨著現(xiàn)代商業(yè)的發(fā)展，許多大型貨運(yùn)公司在區(qū)域范圍內(nèi)建立了多個(gè)配送中心，因此多車場(chǎng)車輛路徑問題就顯得非常重要。多車場(chǎng)車輛路徑問題（MDVRP）是單車場(chǎng)VRP的一個(gè)拓展，VRP屬于完全NP問題，因此MDVRP也屬于NP問題。解決MDVRP主要有3種方法：傳統(tǒng)方式、整體法和啟發(fā)式優(yōu)化法[2-4]。傳統(tǒng)方法是首先將多車場(chǎng)問題轉(zhuǎn)換為單車場(chǎng)問題，再按照單配送問題進(jìn)行處理，常用的轉(zhuǎn)化方法有中垂線分區(qū)法、圓域分區(qū)法和客戶聚類法等；整體法主要是通過(guò)虛擬配送中心的方式來(lái)實(shí)現(xiàn)多配送中心問題，首先設(shè)置虛擬配送中心，再?gòu)奶摂M配送中心出發(fā)，選擇車場(chǎng)后完成配送任務(wù)[5]；啟發(fā)式優(yōu)化法主要是采用智能優(yōu)化方法處理多車場(chǎng)問題，常見的優(yōu)化算法有遺傳算法、蟻群算法、模擬退火算法和混合算法等[6]。傳統(tǒng)方法求解MDVRP時(shí)，在一定程度上降低了問題的復(fù)雜性，但失去了問題的整體性；整體法求解時(shí)，注重問題的整體性，但忽略了單一車輛的優(yōu)化；啟發(fā)式優(yōu)化算法通過(guò)構(gòu)造的方式對(duì)MDVRP進(jìn)行求解，注重了單一車輛，忽視了問題的整體性[7-9]。本文擬采用啟發(fā)式優(yōu)化算法和整體法求解基于時(shí)間窗的VRP，不僅考慮了VRP的整體性，還兼顧了單一車輛的優(yōu)化。

1 問題描述及數(shù)學(xué)建模

基于時(shí)間窗的MDVRP（圖1）可描述為：配送區(qū)域內(nèi)有M個(gè)車場(chǎng)，每個(gè)車場(chǎng)具有運(yùn)載能力為Q的車輛Km（m=1,2,…,M）輛，配送區(qū)域有N個(gè)客戶，每個(gè)客戶的需求量為qi(i=1,2,…,N)，且對(duì)于任意客戶i都有需求量qi

圖1 多配送中心問題

客戶編號(hào)為0,1,2,…,N；車場(chǎng)編號(hào)為N+1,N+2,…, N+M。為建模方便，定義兩個(gè)變量：

基于時(shí)間窗的MDVRP數(shù)學(xué)模型為：

其中，式（3）表示配送完所有客戶點(diǎn)所花費(fèi)的費(fèi)用最低，包括車輛啟用的固定成本、運(yùn)行過(guò)程中的油料消耗和由于時(shí)間延誤造成的懲罰費(fèi)用；式（4）表示車輛的容量限制，即一輛車所配送客戶的總需求不能超過(guò)車輛的最大容載量；式（5）表示每個(gè)車場(chǎng)完成配送任務(wù)使用的車輛數(shù)目不超過(guò)該車場(chǎng)車輛總數(shù)；式（6）表示一個(gè)客戶點(diǎn)的任務(wù)只能對(duì)應(yīng)一個(gè)車場(chǎng)中的一輛車；式（7）、（8）表示每個(gè)客戶只能被來(lái)自同一車場(chǎng)的同一輛車服務(wù)，其他車場(chǎng)的車輛不能對(duì)該客戶進(jìn)行服務(wù)；式（9）表示所有配送車輛從配送中心出發(fā)，完成配送任務(wù)后再返回配送中心；式（10）表示車輛不能從一個(gè)車場(chǎng)達(dá)到另一個(gè)車場(chǎng)；式（11）表示客戶的時(shí)間窗約束，即在規(guī)定時(shí)間內(nèi)，客戶需求得到滿足，否則車輛將增加一定的懲罰成本。

2 多車場(chǎng)問題的解決方法分析

在當(dāng)前物流配送中對(duì)車輛調(diào)度問題的研究主要集中在配送規(guī)模較大、范圍廣、客戶數(shù)量多的多配送中心模式，且在實(shí)踐中發(fā)現(xiàn)一般規(guī)模較大的物流企業(yè)都采用多配送中心車輛調(diào)度模式，因此研究多配送中心車輛調(diào)度問題具有重要的現(xiàn)實(shí)意義[10]。目前解決多配送中心車輛調(diào)度問題主要采用傳統(tǒng)方法、整體法和啟發(fā)式優(yōu)化法。

2.1 分區(qū)法求解VRP

傳統(tǒng)方法是將多配送中心車輛調(diào)度問題看作是多個(gè)單配送中心車輛調(diào)度問題的組合，先將其分離再進(jìn)行優(yōu)化[11]。傳統(tǒng)方法的研究重點(diǎn)在于如何將多配送中心車輛調(diào)度問題拆分成多個(gè)單配送中心車輛調(diào)度問題，然后在全局的基礎(chǔ)上對(duì)其解進(jìn)行優(yōu)化。拆分過(guò)程中主要按照距離最近或劃分邊界的原則確定各配送點(diǎn)與配送中心的對(duì)應(yīng)關(guān)系；實(shí)際應(yīng)用中一般以配送中心的總配送路程最短優(yōu)先，因此選取距離最近原則來(lái)劃分客戶。傳統(tǒng)方法的求解方式有圓域分區(qū)法、中垂線分區(qū)法和最近鄰域法（圖2）。傳統(tǒng)方法具有一定的可行性，但在拆分過(guò)程中失去了問題的整體性，僅在各配送中心范圍內(nèi)取得費(fèi)用最少，很難在整體上取得最優(yōu)解。

圖2 分區(qū)法解決多配送中心車輛調(diào)度問題

2.2 整體法求解VRP

與傳統(tǒng)方法的思路相反，整體法在解決多配送中心車輛調(diào)度問題時(shí)將配送過(guò)程看作一個(gè)整體，首先設(shè)置虛擬的配送中心，然后使所有配送車輛從虛擬配送中心出發(fā)，到達(dá)實(shí)際配送中心后，按照就近原則選擇要服務(wù)的客戶點(diǎn)，完成配送任務(wù)后，返回實(shí)際配送中心[12]。整體法從全局角度考慮了問題的最優(yōu)解，但是在解決時(shí)間窗的多配送中心車輛調(diào)度問題時(shí)，距離最近并不意味整體消耗最少，配送點(diǎn)的選擇不僅要考慮配送點(diǎn)之間的距離，而且要考慮配送點(diǎn)的時(shí)間窗要求（圖3）。

2.3 啟發(fā)式優(yōu)化法求解VRP

啟發(fā)式優(yōu)化法的思想是把多配送中心車輛調(diào)度問題看作是復(fù)雜的多個(gè)問題的組合，在此基礎(chǔ)上進(jìn)行優(yōu)化研究[13]。與傳統(tǒng)方法和整體法不同，啟發(fā)式優(yōu)化法是通過(guò)一系列方法來(lái)簡(jiǎn)化求解計(jì)算過(guò)程，以降低求解搜索的復(fù)雜程度。常用的啟發(fā)式優(yōu)化算法有遺傳算法、蟻群算法、模擬退火算法、禁忌搜索算法和人工神經(jīng)網(wǎng)絡(luò)算法等。啟發(fā)式優(yōu)化算法在求解VRP時(shí)，首先對(duì)路徑進(jìn)行編碼，再通過(guò)不斷更新節(jié)點(diǎn)的順序獲取VRP的最優(yōu)解。它具有較好的收斂性，求解質(zhì)量高，但過(guò)分關(guān)注求解每一輛車的最優(yōu)路徑，忽視了問題的整體性（圖4）。

圖3 整體法解決多配送中心車輛調(diào)度問題

圖4 啟發(fā)式優(yōu)化方法求解多配送中心車輛調(diào)度問題

3 混合算法設(shè)計(jì)

啟發(fā)式優(yōu)化算法在解決單車場(chǎng)問題時(shí)具有較好的收斂性，整體法在求解多車場(chǎng)問題時(shí)具有較好的全局性。鑒于此，首先設(shè)置虛擬配送中心將多配送中心車輛調(diào)度問題轉(zhuǎn)化為單車場(chǎng)VRP，然后采用啟發(fā)式優(yōu)化算法求解單車場(chǎng)VRP，最后為每個(gè)配送點(diǎn)選擇車場(chǎng)。混合算法流程如圖5所示。

混合算法的一般步驟為：

1）參數(shù)設(shè)置，主要包括選擇自適應(yīng)的交叉率和變異率，蟻群信息素的總量、螞蟻個(gè)數(shù)以及α、β；

2）確定染色體編碼方式和適應(yīng)度函數(shù)的計(jì)算方式；

3）對(duì)所有節(jié)點(diǎn)進(jìn)行染色體編碼，并計(jì)算染色體的適應(yīng)度值，選擇父代中較好的一部分染色體遺傳到下一代，子代進(jìn)行自適應(yīng)的交叉和變異過(guò)程，并產(chǎn)生新的染色體；

4）計(jì)算新染色體適應(yīng)度值，并根據(jù)適應(yīng)度值進(jìn)行折半排序；

5）計(jì)算相鄰兩代染色體適應(yīng)度值的平均值，并計(jì)算相鄰兩代染色體的進(jìn)化率，若相鄰兩代染色體的進(jìn)化率不超過(guò)3%或超過(guò)遺傳算法中設(shè)置的最大迭代次數(shù)，則將該組染色體的適應(yīng)度值轉(zhuǎn)化成蟻群算法中初始狀態(tài)下的信息素濃度，否則重新進(jìn)行選擇、交叉和變異操作；

6）將所有螞蟻隨機(jī)放置在任意一個(gè)頂點(diǎn)，螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個(gè)待訪問的節(jié)點(diǎn)，當(dāng)螞蟻選擇完所有節(jié)點(diǎn)后，形成多條訪問路徑；

圖5 混合算法設(shè)計(jì)流程圖

7）計(jì)算當(dāng)前所有路徑適應(yīng)度值，并標(biāo)記適應(yīng)度值最好的螞蟻；

8）更新當(dāng)前最優(yōu)路徑上的信息素濃度，然后更新所有路徑上的信息素濃度；

9）判斷當(dāng)前迭代次數(shù)與最大迭代次數(shù)的關(guān)系，若當(dāng)前迭代次數(shù)小于蟻群算法的最大迭代次數(shù)，則將每只螞蟻重新放置在各節(jié)點(diǎn)處，按照狀態(tài)轉(zhuǎn)移規(guī)則重新訪問所有節(jié)點(diǎn)，否則停止蟻群算法，得到當(dāng)前一組最優(yōu)路徑；

10）對(duì)于當(dāng)前每一條路徑，采用2-opt算法進(jìn)行路徑優(yōu)化，得到一組基于虛擬配送中心的車輛路徑，再對(duì)所有路徑進(jìn)行排序；

11）計(jì)算每輛車到實(shí)際配送中心的消耗，再將虛擬配送中心轉(zhuǎn)換成實(shí)際配送中心，總消耗最小的轉(zhuǎn)換結(jié)果即為當(dāng)前最優(yōu)的配送方案。

4 案例分析

為了驗(yàn)證混合算法的有效性，實(shí)驗(yàn)采用標(biāo)準(zhǔn)的MDVRPTW問題進(jìn)行實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)環(huán)境為Inter酷睿i5，內(nèi)存8 G，操作系統(tǒng)為Windows10，編程語(yǔ)言為C++，開發(fā)環(huán)境為VS2010。

標(biāo)準(zhǔn)的MDVRPTW問題是：有3個(gè)配送中心A、B、C，每個(gè)配送中心貨物充足，有15個(gè)配送點(diǎn)，每個(gè)客戶點(diǎn)具有一定的需求量，也有一定的時(shí)間窗限制，具體的車輛路徑實(shí)驗(yàn)數(shù)據(jù)如表1、2所示[14]。

為了驗(yàn)證算法的有效性，實(shí)驗(yàn)分別采用MDVRP的傳統(tǒng)方法（中垂線法）、整體法、啟發(fā)式優(yōu)化算法以及本文設(shè)計(jì)的混合算法對(duì)多車場(chǎng)的時(shí)間窗問題進(jìn)行求解。實(shí)驗(yàn)中設(shè)定車輛的單位油耗為8，車輛的啟動(dòng)成本為60，配送過(guò)程早到所產(chǎn)生的等待成本為0.5，晚到所產(chǎn)生的懲罰成本為1.5，測(cè)試結(jié)果如表3所示。

表1 客戶點(diǎn)的實(shí)驗(yàn)數(shù)據(jù)

表2 配送中心的實(shí)驗(yàn)數(shù)據(jù)

表3 測(cè)試結(jié)果統(tǒng)計(jì)

由表3可知，分區(qū)法、整體法和啟發(fā)式優(yōu)化算法在求解帶時(shí)間窗的MDVRP時(shí)，分區(qū)法的效果最差，整體法次之，啟發(fā)式優(yōu)化算法最好，而混合算法比啟發(fā)式優(yōu)化算法的平均費(fèi)用降低了85個(gè)單位。因此，采用混合算法可降低帶時(shí)間窗的MDVRP的費(fèi)用。

5 結(jié) 語(yǔ)

本文針對(duì)基于時(shí)間窗的MDVRP建立了配送方案的最小費(fèi)用模型，分析了分區(qū)法、整體法和啟發(fā)式優(yōu)化算法在解決MDVRP時(shí)的優(yōu)劣；并結(jié)合整體法和啟發(fā)式優(yōu)化算法，進(jìn)行了混合算法的設(shè)計(jì)，最后通過(guò)實(shí)驗(yàn)驗(yàn)證了混合算法在解決帶時(shí)間窗的MDVRP的有效性。

[1] 楊從平.基于蟻群算法的快遞物流配送路徑優(yōu)化[J].物流工程與管理,2014(4)：65-67

[2] 姚婷婷.車輛調(diào)度有及其遺傳算法[D].蘭州：西北師范大學(xué),2013：2-3

[3] 鄒彤,李寧,孫德寶,等.多車場(chǎng)車輛路徑問題的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2004(21)：82-83

[4] 楊元峰.多車場(chǎng)多車型車輛路徑問題的改進(jìn)遺傳算法[J].計(jì)算機(jī)與現(xiàn)代化,2008(9)：10-13

[5] 鐘石泉,賀國(guó)光.多車場(chǎng)有時(shí)間窗的多車型車輛調(diào)度及其禁忌算法研究[J].運(yùn)籌學(xué)學(xué)報(bào),2005(4)：67-73

[6] 李小花.多車場(chǎng)帶容量限制弧路徑規(guī)劃問題研究[D].重慶：重慶大學(xué),2009：23-25

[7] 戴樹貴,陳文蘭,潘蔭榮,等.多配送中心車輛路徑安排問題混合蟻群算法[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版),2008(6)：154-158 [8] 孫世權(quán).多配送中心車輛路徑優(yōu)化問題的研究[D].西安：西安電子科技大學(xué),2012：3-4

[9] 汪平.多生產(chǎn)點(diǎn)煙草企業(yè)的原材料運(yùn)輸車輛路徑問題研究[D].武漢：華中科技大學(xué),2010：12-14

[10] 高志剛.多車輛配送路徑分析及與GIS平臺(tái)的集成技術(shù)研究[D].武漢：武漢理工大學(xué),2005：10-11

[11] 王詩(shī)瑤,王文發(fā),富文軍,等.大規(guī)模單車場(chǎng)VRP問題中掃描法的改進(jìn)[J].現(xiàn)代電子技術(shù),2014(24)：34-36

[12] 高特,李莉,鐘蓮,等.烏魯木齊市社區(qū)蔬菜直銷統(tǒng)一配送路徑優(yōu)化[J].物流技術(shù),2014(11)：168-170

[13] 張立峰,趙方庚,孫江生,等.戰(zhàn)時(shí)備件配送的MDVRP問題及其遺傳算法求解[J].計(jì)算機(jī)應(yīng)用與軟件,2010(2)：194-196 [14] 鐘石泉.物流配送車輛調(diào)度智能優(yōu)化方法研究[D].天津：天津大學(xué),2004：3-5

P208

B

1672-4623（2017）05-0035-04

10.3969/j.issn.1672-4623.2017.0051.1

閆凱，碩士研究生，主要研究方向?yàn)檫\(yùn)籌地理信息系統(tǒng)。

2016-10-31。

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金資助項(xiàng)目（7130939）。