□ 文 軍

(蘭州交通大學 交通運輸學院，甘肅 蘭州 730070)

1 引言

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

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

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

2 模型建立

2.1 問題描述

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

問題的目標是：在客戶共享的條件下，通過合理設計各運輸車輛的運輸路徑以滿足客戶需求，實現(xiàn)運輸總費用最低的目標。

2.2 符號定義

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

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

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

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

c表示車輛運輸?shù)膯挝痪嚯x成本；

c1表示早到車輛的單位時間消耗成本；

c2表示遲到車輛的單位時間懲罰成本；

c3表示車輛的固定成本；

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

Q表示車輛滿載量；

qi表示客戶i的需求量；

[Ei,Li]表示客戶i要求的服務時間窗；

ti表示對客戶i進行服務的時間；

Ti表示車輛到達客戶i的時間；

V表示車輛行駛的平均時速。

2.3 模型建立

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

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

其中，表達式的含義為：

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

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

約束條件(3)-(5)表示每個客戶只能被一輛運輸車輛配送一次；

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

約束條件(7)表示運輸車輛到達客戶j的時間；

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

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

3 算法設計

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

①將配送中心位置設置為初始中心，觀察問題中客戶的位置點分布，對位置點進行k均值聚類處理。

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

③置m的初始值為1。

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

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

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

圖1 算法流程圖

⑦隨機選擇每只搜索蟻k的初始位置，并將該位置放在與每只搜索蟻對應tabuk表中；

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

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

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

(B11)如果到達最大進化代數(shù)MAXGEN，轉(zhuǎn)(B14)，若在達到最大進化次數(shù)之前獲得的解，在最近若干次的迭代中沒有顯著改進，則調(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) 輸出各個類中的最優(yōu)解相加之和。

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

4 實例仿真

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

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

其中，標號為1-20的位置點為客戶點的相關數(shù)據(jù)，標號為Ⅰ、Ⅱ、Ⅲ的位置點為配送中心的相關數(shù)據(jù)。

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

①配送中心Ⅰ對六個客戶進行配送，客戶標號分別為：4、5、10、13、16、19；

②配送中心Ⅱ?qū)ζ邆€客戶進行配送，客戶標號分別為：2、7、9、12、15、18、20；

③配送中心Ⅲ對七個客戶進行配送，客戶標號分別為：1、3、6、8、11、14、17；

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

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

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

(a)配送車輛路線

(b)收劍曲線圖2

5 結(jié)束語

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