基于車輛共享的多配送中心車輛路徑問題研究

□ 文 軍

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

1 引言

據中國物流與采購聯合會統計顯示，2017年中國社會物流總費用為12.1萬億元，其中運輸費用為6.6萬億元，占比高達54.5%。因此，在物流系統優化過程中，怎樣經濟高效地選擇車輛配送路徑依然是一個極其重要的問題。

基于車輛共享的多配送中心車輛路徑問題其實質就是開放式車輛路徑問題，它是1981年由Schrage[1]首次提出的一類經典NP難問題。為提高客戶滿意度，本文還添加了軟時間窗的限制，其相當于帶軟時間窗的多配送中心開放式車輛路徑問題(Multi-Depot Open Vehicle Routing Problem with Soft Time Windows，MDOVRPSTW)，因此對其求解更加困難。

目前，國內外學者對VRP研究充分，但在MDOVRPSTW問題的研究上，還相對缺乏。對該問題的研究主要集中在智能算法方面，如遺傳算法[2][3]、禁忌搜索算法[4]、蟻群算法[5-7]等。但多態蟻群算法在MDVRPSTW中的應用中，仍存在著許多未解決的問題。為此，本文設計了一種結合2-opt局部優化算法的自適應多態蟻群算法進行求解，采用實例驗證該算法在求解MDOVRPSTW問題中的可行性和有效性。

2 構造模型

2.1 闡述問題

假設在某市存在著若干個物流配送中心，每個配送中心擁有數量相等的運輸車輛，需要為本市多個客戶承擔貨物配送任務。已知：①每個配送中心的貨物充足且配送車輛的載量相同；②客戶之間、客戶與各配送中心之間均可順利到達，且距離已知并具有對稱性；③為提高客戶的滿意度，為每個客戶提供服務軟時間窗；④配送車輛在完成配送任務之后無須返回原配送中心，可根據就近原則，停靠在就近配送中心。

問題的目標是：在配送車輛有限的情況下，如何合理地設計各配送車輛的運輸路徑，以滿足客戶需求的前提下，達到運輸總成本最小的目標。

2.2 符號定義

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

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

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

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

c表示車輛運輸的單位距離成本；

c1表示早到車輛的單位時間等待成本；

c2表示晚到車輛的單位時間罰金成本；

Z表示運輸車輛配送時產生的總成本；

Q表示運輸車輛最大裝載量；

qi表示客戶i的所需貨物量；

[Ei,Li]表示客戶i限制的提供配送服務時間窗；

ti表示對客戶i提供物流配送服務的時間；

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

xijk表示運輸車輛順利從點i到達點J時為1，未順利到達則為0，?i,j∈G；

yijk表示車輛從配送中心i到客戶j或者從客戶i到配送中心j時為1，否則為0，?i,j∈P∪G；

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

2.3 模型建立

根據以上的問題闡述和符號定義，構造如下帶軟時間窗的多配送中心開放式VRP的混合整數規劃模型如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

?i∈G,?j∈P,?k∈Kor?i∈P,?j∈G,?k∈K

(10)

其中，表達式的含義為：

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

約束條件(2)表示每個客戶只能被一輛運輸車輛進行配送服務一次；

約束條件(3)表示為客戶j提供配送服務的車輛數在到發方面保持一致；

約束條件(4)表示運輸車輛服務客戶的需求量之和不大于其最大裝載量；

約束條件(5)表示運輸車輛抵達客戶j的時刻點；

約束條件(6)表示運輸車輛在完成相應的物流配送服務后，可選擇任一配送中心停靠；

約束條件(7)和(8)表示運輸車輛在完成相應的物流配送服務后，一定得選擇一個配送中心停靠；

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

3 算法設計

3.1 算法設計的總體思路

本文基于傳統的TSP蟻群算法，結合具有軟時間窗的多配送中心開放式車倆路徑問題的具體約束條件，適當改進了選擇、更新以及協調等機制，同時添加了自適應的轉移策略和信息素更新策略。由蟻群具有多樣社會分工的特性，使偵察螞蟻在偵測過程帶有特定的約束；讓搜索螞蟻來完成搜索滿足目標函數可行解的任務。通過不同種類螞蟻的分工協作，最后將信息素自適應策略與多態蟻群算法相結合，改進的算法有效地加快了基礎蟻群算法收斂速度，克服了早熟現象的發生。

3.2 自適應多態蟻群算法步驟

根據陳美軍等提出的自適應多態蟻群算法相關原理[8]，本文加入2-opt局部優化算法，將其應用于解決本文構建的帶軟時間窗的多配送中心開放式車輛路徑模型上，其求解步驟如下：

①初始時刻，設置參數Q、C、α、β、ξ和ρ，并設置最大迭代數為MAXGEN等。

②在N個客戶點放置N只偵察蟻，把所在客戶點i看作相應偵察蟻的中心，對其他N-1個客戶點進行偵察，計算并記錄總偵察表，將結果賦予Sij。

③在初始時設置每條路徑上的信息量。

④設置進化代數NC初值為0。

⑤將搜索蟻k的初始位置定為虛擬配送中心點，并將該位置放在與搜索蟻k相對應的禁忌表tabuk中。

⑥搜索蟻k用輪盤賭方法挑選下一個訪問的客戶點，相應的禁忌表tabuk加入該客戶點。

⑦對還沒有訪問到的客戶點集合進行刷新，并再次計算可選客戶點的集合。

⑧若還有客戶點沒有訪問到而這些客戶點都是不可選的，則說明雖然還有沒提供配送服務的客戶點，但是這些客戶點都不符合約束條件。此時搜索蟻k返回虛擬配送中心點，相應的在禁忌表tabuk的末尾加入該點，構成以虛擬配送中心為始末位置的一條閉環路線。返回步驟⑤，直到還沒用訪問到的客戶點的集合為空，轉入下一步。

⑨計算每條路徑中第一個和最后一個客戶與實際配送中心之間的距離，用合適的實際配送中心代替虛擬配送中心，連接第一個客戶的首端和最后一個客戶末端，形成完整的路徑。

⑩計算每只搜索蟻的目標函數值f(Z)，并記錄當前最佳解。

結合2-opt局部優化算法的自適應多態蟻群算法的流程圖見圖1。

4 實例仿真

本文采用Matlab R2015a仿真軟件來計算優化結果。設計3個配送中心位置點，各配送中心擁有的車輛最大數是3，20個客戶位置點，每個位置點分散在一個100*100的正方形區域。其具體數據見表1。

圖1 算法流程圖

表1 位置點數據

其中，標號為1-3的位置點為配送中心的相關數據，標號為4-23的位置點為客戶的相關數據。

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

表2 最優車輛配送路徑

通過實驗所得的配送車輛路徑最佳圖和最優解收斂曲線圖如圖2(a)和(b)所示：

圖2(a)配送車輛路徑圖

圖2(b)收斂曲線圖

5 結束語

根據城市物流實際配送中遇到的多配送中心、多任務車輛調度優化問題，為降低整個配送過程中配送所產生的物流成本，提高城市的社會物流效益，本文從運輸、時間等方面出發構建了一個基于物流配送車輛共享的開放式車輛路徑問題數學模型。對于該模型，使用自適應多態蟻群算法來優化求解，并且將2-opt算法用于局部優化以加速算法的收斂。最后，該算法由Matlab R2015a仿真軟件實現，并通過實例驗證了自適應多態蟻群算法在處理基于車輛共享的開放式車輛路徑問題是有效且可取的。