基于客戶共享的車(chē)輛路徑問(wèn)題研究

□ 文 軍

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070)

1 引言

隨著城市物流規(guī)模的逐漸擴(kuò)大，由物流運(yùn)輸車(chē)輛所帶來(lái)的道路擁堵、環(huán)境污染、噪音污染等一系列問(wèn)題日益突出，為了提升物流配送效率，加大物流企業(yè)利潤(rùn)空間，加強(qiáng)城市的社會(huì)效益，如何高效合理地安排運(yùn)輸車(chē)輛路徑問(wèn)題尤為重要。

基于客戶共享的車(chē)輛路徑問(wèn)題，其實(shí)質(zhì)是在共同配送的理念下[1]，研究關(guān)于多配送中心的車(chē)輛路徑問(wèn)題，為了提高客戶滿意度，加入軟時(shí)間窗的條件約束，構(gòu)成了帶軟時(shí)間窗的多配送中心車(chē)輛路徑問(wèn)題(Mutli-Depot Vehicle Routing Problem with Soft Time windows，MDVRPSTW)，是一個(gè)標(biāo)準(zhǔn)的NP-難問(wèn)題。

目前，相對(duì)國(guó)內(nèi)學(xué)者，國(guó)外學(xué)者對(duì)MDVRP研究比較充分。對(duì)于MDVRPSTW的研究主要集中在智能算法方面，國(guó)外Giosa[2]，Tansini[3]，Li J[4]以及Ebadati[5]采用不同智能算法求解都取得了較好的研究成果；對(duì)于MDVRP的研究主要在于模型的重構(gòu)及求解，Hong[6]和Kuo[7]分別從模糊時(shí)間旅程和裝載成本對(duì)該問(wèn)題模型重構(gòu)并取得了較好的解。雖然國(guó)內(nèi)外學(xué)者對(duì)MDVRPSTW的研究比較多，但現(xiàn)實(shí)中，該問(wèn)題屬于大規(guī)模問(wèn)題且是NP-難問(wèn)題，用不同的方法尋找更優(yōu)的解仍具有現(xiàn)實(shí)意義。

2 模型建立

2.1 問(wèn)題描述

假設(shè)某城市擁有多個(gè)物流配送中心，每個(gè)配送中心擁有相同數(shù)量的運(yùn)輸車(chē)輛，需要為該市多個(gè)客戶提供服務(wù)。已知：①貨物充足且運(yùn)輸車(chē)輛的載量相同；②任意兩點(diǎn)之間均可順利到達(dá)，且距離已知并具有對(duì)稱性；③為提高客戶滿意度，為每個(gè)客戶提供服務(wù)軟時(shí)間窗；④運(yùn)輸車(chē)輛在完成配送任務(wù)之后必須回到始發(fā)配送中心。

問(wèn)題的目標(biāo)是：在客戶共享的條件下，通過(guò)合理設(shè)計(jì)各運(yùn)輸車(chē)輛的運(yùn)輸路徑以滿足客戶需求，實(shí)現(xiàn)運(yùn)輸總費(fèi)用最低的目標(biāo)。

2.2 符號(hào)定義

P={p|1,2,3,…,P}表示配送中心個(gè)數(shù)；

G={g|1,2,3,…,g}表示客戶數(shù)量；

K={k|1,2,3,…k}表示運(yùn)輸車(chē)輛數(shù)；

dij表示任意兩點(diǎn)之間的歐式距離，?i,j∈P∪G；

c表示車(chē)輛運(yùn)輸?shù)膯挝痪嚯x成本；

c1表示早到車(chē)輛的單位時(shí)間消耗成本；

c2表示遲到車(chē)輛的單位時(shí)間懲罰成本；

c3表示車(chē)輛的固定成本；

Z表示物流配送產(chǎn)生的總成本；

Q表示車(chē)輛滿載量；

qi表示客戶i的需求量；

[Ei,Li]表示客戶i要求的服務(wù)時(shí)間窗；

ti表示對(duì)客戶i進(jìn)行服務(wù)的時(shí)間；

Ti表示車(chē)輛到達(dá)客戶i的時(shí)間；

V表示車(chē)輛行駛的平均時(shí)速。

2.3 模型建立

根據(jù)上述問(wèn)題描述和符號(hào)定義，創(chuàng)建如下帶軟時(shí)間窗的多配送中心VRP的混合整數(shù)規(guī)劃模型如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

其中，表達(dá)式的含義為：

目標(biāo)函數(shù)(1)代表最小化運(yùn)輸成本與客戶等待時(shí)間成本之和，即使物流配送總成本最小化；

約束條件(2)表示各配送中心始發(fā)的運(yùn)輸車(chē)輛總數(shù)小于擁有的車(chē)輛數(shù)；

約束條件(3)-(5)表示每個(gè)客戶只能被一輛運(yùn)輸車(chē)輛配送一次；

約束條件(6)表示每輛車(chē)服務(wù)客戶的需求總和不大于其最大負(fù)載；

約束條件(7)表示運(yùn)輸車(chē)輛到達(dá)客戶j的時(shí)間；

約束條件(8)表示完成配送任務(wù)的運(yùn)輸車(chē)輛，必須回到始發(fā)配送中心；

約束條件(9)表示決策變量的0-1約束。

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

結(jié)合趙喜貴等[8]提出的基于蟻群算法的K-Means聚類雷達(dá)信號(hào)分選算法和陳美軍等[9]提出的自適應(yīng)多態(tài)蟻群算法相關(guān)原理，將聚類的多態(tài)蟻群算法用來(lái)求解MDVRPSTW問(wèn)題，其設(shè)計(jì)步驟如下：

①將配送中心位置設(shè)置為初始中心，觀察問(wèn)題中客戶的位置點(diǎn)分布，對(duì)位置點(diǎn)進(jìn)行k均值聚類處理。

②設(shè)位置點(diǎn)可以聚成c1,c2,…，cm個(gè)類，其中m為配送中心點(diǎn)的個(gè)數(shù)，且o1,o2,…,om分別為每個(gè)類的中心點(diǎn)，把Om看成一個(gè)MDVRPSTW問(wèn)題。

③置m的初始值為1。

④初始化參數(shù)Q、C、α、β、ξ和ρ，并設(shè)置最大迭代數(shù)為MAXGEN等。

⑤根據(jù)類中的客戶點(diǎn)的數(shù)量放置不同數(shù)量的偵察蟻，每只偵察蟻以所在客戶點(diǎn)i為中心，對(duì)相應(yīng)類中其他客戶點(diǎn)進(jìn)行偵察，計(jì)算并記錄總偵察表，將結(jié)果賦予sij。

⑥在初始時(shí)設(shè)置每條路徑的信息量，并且進(jìn)化代數(shù)Nc初始值為0；

圖1 算法流程圖

⑦隨機(jī)選擇每只搜索蟻k的初始位置，并將該位置放在與每只搜索蟻對(duì)應(yīng)tabuk表中；

⑧計(jì)算每只搜索蟻k將要移動(dòng)的位置，假如要移動(dòng)的位置為j，上一個(gè)位置假設(shè)為i，則將j放在與搜索螞蟻k對(duì)應(yīng)的tabuk表中，當(dāng)每只搜索蟻完成一個(gè)循環(huán)，即相應(yīng)獲得一個(gè)解；

⑨計(jì)算各搜索蟻的目標(biāo)函數(shù)值f(Z)，并記載目前最優(yōu)解；

⑩執(zhí)行2-opt局部?jī)?yōu)化算法；

(B11)如果到達(dá)最大進(jìn)化代數(shù)MAXGEN，轉(zhuǎn)(B14)，若在達(dá)到最大進(jìn)化次數(shù)之前獲得的解，在最近若干次的迭代中沒(méi)有顯著改進(jìn)，則調(diào)整揮發(fā)系數(shù)ρ，轉(zhuǎn)(B13)，否則轉(zhuǎn)(B12)；

(B13)NC←NC+1，轉(zhuǎn)⑦；

(B14)得到類中的最優(yōu)解；

(B15)m←m+1，轉(zhuǎn)⑤；

(B16) 輸出各個(gè)類中的最優(yōu)解相加之和。

結(jié)合k-means算法的多態(tài)蟻群算法流程圖如圖1所示：

4 實(shí)例仿真

本文采用Matlab R2015a仿真軟件來(lái)求解優(yōu)化結(jié)果。設(shè)計(jì)配送中心數(shù)量為3，各配送中心擁有的車(chē)輛數(shù)為2，客戶點(diǎn)數(shù)量為20，每個(gè)節(jié)點(diǎn)分散在100*100的正方形區(qū)域，其具體數(shù)據(jù)見(jiàn)下表1：

表1 位置點(diǎn)數(shù)據(jù)

其中，標(biāo)號(hào)為1-20的位置點(diǎn)為客戶點(diǎn)的相關(guān)數(shù)據(jù)，標(biāo)號(hào)為Ⅰ、Ⅱ、Ⅲ的位置點(diǎn)為配送中心的相關(guān)數(shù)據(jù)。

根據(jù)距離的影響因素采取的k-means聚類算法，取得如下的聚類成效：

①配送中心Ⅰ對(duì)六個(gè)客戶進(jìn)行配送，客戶標(biāo)號(hào)分別為：4、5、10、13、16、19；

②配送中心Ⅱ?qū)ζ邆€(gè)客戶進(jìn)行配送，客戶標(biāo)號(hào)分別為：2、7、9、12、15、18、20；

③配送中心Ⅲ對(duì)七個(gè)客戶進(jìn)行配送，客戶標(biāo)號(hào)分別為：1、3、6、8、11、14、17；

根據(jù)上述聚類結(jié)果，結(jié)合以往經(jīng)驗(yàn)，為算法中的相關(guān)參數(shù)賦予初始值：α=1，β=2，ρ(t0)=1，N=23，Q=100，C=3，max(Pc)=10，最大迭代次數(shù)為50。模型中車(chē)輛的相關(guān)系數(shù)設(shè)定值為：?jiǎn)挝贿\(yùn)輸成本c=1，早到的消耗單位成本c1=0.2，遲到的懲罰單位成本c2=2，最大裝載量Q=6，平均時(shí)速V=40。模型求解得到的最小總成本為459.78，車(chē)輛的行駛路徑情況如下表2所示：

表2 最優(yōu)車(chē)輛配送路徑

通過(guò)軟件仿真實(shí)例所得的車(chē)輛最佳配送路線和收斂速度如圖(a)和(b)所示：

(a)配送車(chē)輛路線

(b)收劍曲線圖2

5 結(jié)束語(yǔ)

本文在基于共同配送的理念下，提出了關(guān)于客戶共享的車(chē)輛路徑問(wèn)題，其本質(zhì)是多配送中心的車(chē)輛路徑問(wèn)題，為提高客戶滿意度，加入軟時(shí)間窗的條件約束，在解決帶軟時(shí)間窗的多配送中心車(chē)輛問(wèn)題的時(shí)候，首先，應(yīng)用了一種依據(jù)歐式距離聚類客戶點(diǎn)的k-means聚類算法；其次，對(duì)通過(guò)聚類算法劃分的子問(wèn)題采用了多態(tài)蟻群算法進(jìn)行求解計(jì)算，為了進(jìn)一步提高算法的收斂速度，結(jié)合了2-opt局部?jī)?yōu)化算法；最后，構(gòu)建了一種帶聚類的多態(tài)蟻群算法，該算法適用于大規(guī)模的城市物流配送問(wèn)題。對(duì)于具有明顯的聚類特征的客戶點(diǎn)的分布，算法的優(yōu)越性也得到很好的體現(xiàn)。