兩級車輛路徑問題的離散差分進化算法

彭鵬+李彬哲+付雪薇+汪恭書

A Discrete Differential Evolution Algorithm for Two-echelon Vehicle Routing Problem

PENG Peng， LI Bin-zhe， FU Xue-wei， WANG Gong-shu

摘 要：針對廣泛存在于現代物流配送過程中的兩級車輛路徑問題，在考慮配送服務耦合性特征的基礎上建立了以總成本最小為目標函數的整數規劃模型，并提出了求解問題的離散差分進化算法。在離散差分進化算法框架中，采用貪婪算法產生初始解，對一級和二級網絡分別進行編碼，然后進行變異和交叉操作，并在二級網絡求解的基礎上求解一級網絡。文章采用隨機產生的算例對算法求解效果進行驗證。結果顯示，所建的模型和算法正確有效，在求解大規模問題時也能夠獲得相對較好的優化結果。

關鍵詞：兩級車輛路徑問題；混合整數規劃；離散差分進化

中圖分類號：U116.2 文獻標識碼：A

Abstract： This paper studies a two-echelon vehicle routing problem that is widely existed in the distribution process of the modern logistics system. By considering the coupling characteristics of distribution service， the problem is formulated as an integer programming model with the objective of minimizing total distribution cost， and a discrete differential evolution algorithm is proposed to solve the model. In the framework of discrete differential evolution algorithm， we encode the first and second network individually， then use greedy algorithm to get the initial solution. The next step is variation and cross. The solution to the first network is based on the second. The proposed algorithm is tested by a random example. The results show that the proposed model and algorithm are correct， and can obtain high-quality solutions.

Key words： two-echelon vehicle routing problem； integer programming； discrete differential evolution algorithm

0 引 言

經典的車輛路徑問題大多假設單級配送，即由配送中心直接向顧客配送物資。但是由于政府部門對大型車輛的管制，從配送中心必須先到達各個中轉站，然后再送給各個顧客，這樣就形成了兩級車輛路徑問題（2E—VRP）。在文獻[1]中首次提出了2E-VRP問題的數學模型，應用分支—割平面算法求解；文獻[2]采用特殊的分支—割平面算法求解2E—VRP，取得了較好成果；文獻[3]采用了自適應大規模鄰域搜索算法改進了初始解，平衡了結果的質量和求解時間。本文采用離散差分進化算法對此問題進行求解，實驗結果表明，該算法能夠獲得高質量的解。

1 問題描述和數學模型

兩級車輛路徑問題結構如圖1所示，在兩級配送網絡中，第一級為從配送中心運送貨物至中轉站，然后再從中轉站運送到顧客。因此，在車輛路徑問題中，已知配送中心、中轉站的位置和容量、顧客的位置和需要的貨物，需要確定各個顧客分別由哪個中轉站服務、每個中轉站由哪個配送中心供貨，并設計相應的車輛行駛路徑，使車輛行駛成本之和為最低。

下面我們給出兩級車輛路徑問題參數和變量的定義[4]：配送中心集合N■，中轉站集合N■，顧客集合N■，顧客i的需求量q■i∈N■，m■j∈N■表示配送中心j擁有的車輛數量，m■k∈N■表示中轉站k擁有的車輛數量，B■表示中轉站k的容量，M■表示經過配送中心j的一級路徑集合，R■表示經過中轉站k的二級路徑集合，c■表示二級路徑l的費用，c■表示一級路徑l的花費。定義x■和y■為0-1決策變量，對l∈R■， k∈N■，x■=1表示二級路徑l被選擇，否則x■=0，對l∈M■， j∈N■，y■=1表示一級路徑l被選擇，否則y■=0。基于上述定義，兩級車輛路徑問題可以表示為以下整數規劃模型：

minz=■■c■x■+■■c■x■ （1）

s.t.

■■x■=1， i∈N■ （2）

■x■≤m■， k∈N■ （3）

■■q■x■≤B■， k∈N■ （4）

■y■≤m■， j∈N■ （5）

■q■=■■q■x■， j∈N■， k∈N■ （6）

式（1）為目標函數，目標為兩級物流網絡成本最小，式（2）表示顧客i能且只能被訪問一次，式（3）表示中轉站k使用的車輛不能超過其所擁有的數量，式（4）表示中轉站k運輸的貨物總量不能超過其容量，式（5）表示配送中心j使用的車輛不能超過其所擁有的數量，式（6）表示中轉站運入的貨物總量等于其運出的貨物總量。

2 差分進化算法

本文提出了離散差分進化算法對兩級車輛—路徑問題進行求解。差分進化算法（DE）是一種用于最佳化問題的后設啟發式算法。本質上說，它是一種基于實數編碼的具有保優思想的貪婪遺傳算法。

離散差分進化算法采用自下向上的求解過程，在每一次迭代過程中首先對二級配送網絡中配送路徑進行求解，然后根據二級配送網絡求解結果，求解一級配送網絡的配送路徑。

2.1 編 碼

由于2E—VRP包含多個子問題，并且本文提出的離散差分進化算法采用自下向上的求解過程，因此在解編碼方式選擇上，本文將一級配送網絡與二級配送網絡分別用相同的方式進行編碼來表示解向量。

本文采用的是實數編碼方式，以二級配送網絡為例。對每一個中轉站分別進行編碼，該編碼包含有編號為1，2，…，c的c個需求點以及若干個0表示路徑分割。圖2為某一中轉站的編碼示意圖。

該網絡編碼可轉換為3條路徑：

路徑1：某中轉站→22→8→7→27→該中轉站

路徑2：某中轉站→16→19→6→24→14→該中轉站

路徑3：某中轉站→20→28→該中轉站

2.2 算法步驟

初始化：

在初始化過程中需要生成兩級配送網絡初始解，本文采用貪婪算法生成初始解。

第一階段利用貪婪算法搜索構造第二級配送網絡解向量，第二階段根據上一階段生成的第二級配送網絡解向量，采用相同的方法構造第一級配送網絡解方案。

以二級配送網絡為例，貪婪隨機初始化具體步驟如下。

步驟1：將需求點分配給距離其最近的備選中轉站。

步驟2：根據需求點分配結果，檢查所有中轉站服務的需求點是否超過該中轉站的容量。

步驟3：若有中轉站服務的需求點超過其容量，將最后一個分配到該中轉站的需求點分配到距離其次近的中轉站。

步驟4：根據需求點分配結果，檢查所有中轉站的服務的需求點是否超過該中轉站的容量。如果都沒有超過，則初始化結束。否則返回步驟3。

變異：

利用隨機數產生變異的位置，例如對圖3進行變異操作，假設隨機產生的交換的兩個位置是3和4，變異過程如圖3所示。

交叉：

步驟1：隨機選擇切點c■，c■。

步驟2：交換中間部分。

步驟3：從第二個切點c■后，第一個基因起列出原順序，去掉已有基因（注意0的個數）。

步驟4：從第二個切點c■后，第一個位置起，將獲得的無重復順序填入。

我們將上面的原個體和變異個體進行交叉操作，假設我們隨機產生的c■、c■為4和6，交叉操作如圖4所示。

3 實驗分析

本文采用隨機生成的2E—VRP算例來對離散差分進化算法進行求解驗證。算法在Intel（R）Core（TM）i7—4720HQ CPU、4GB RAM、Windows10操作系統環境下，使用MATLAB編譯運行。該算例需求點數量為50，需求量為1，中轉站10個，容量10，每個擁有的車數量3輛，車的容量為5，配送中心3個，容量為30，每個擁有的車數量3輛，車的容量為10。離散差分進化算法框架部分所含參數包括：最大進化代數，變異概率，交叉概率，種群規模，在這里分別設置為100，0.5，0.9，200。求解結果如圖5所示。

4 結 論

針對兩級車輛路徑問題，建立了以一級、二級配送網絡總成本最小為目標函數的混合整數規劃數學模型，考慮了一級配送中心、二級中轉站容量約束，一級、二級配送車輛容量約束。并提出了離散差分進（下轉第13頁）