兩級(jí)車(chē)輛路徑問(wèn)題的離散差分進(jìn)化算法

彭鵬+李彬哲+付雪薇+汪恭書(shū)

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

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

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

關(guān)鍵詞：兩級(jí)車(chē)輛路徑問(wèn)題；混合整數(shù)規(guī)劃；離散差分進(jìn)化

中圖分類(lèi)號(hào)：U116.2 文獻(xiàn)標(biāo)識(shí)碼：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 引 言

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

1 問(wèn)題描述和數(shù)學(xué)模型

兩級(jí)車(chē)輛路徑問(wèn)題結(jié)構(gòu)如圖1所示，在兩級(jí)配送網(wǎng)絡(luò)中，第一級(jí)為從配送中心運(yùn)送貨物至中轉(zhuǎn)站，然后再?gòu)闹修D(zhuǎn)站運(yùn)送到顧客。因此，在車(chē)輛路徑問(wèn)題中，已知配送中心、中轉(zhuǎn)站的位置和容量、顧客的位置和需要的貨物，需要確定各個(gè)顧客分別由哪個(gè)中轉(zhuǎn)站服務(wù)、每個(gè)中轉(zhuǎn)站由哪個(gè)配送中心供貨，并設(shè)計(jì)相應(yīng)的車(chē)輛行駛路徑，使車(chē)輛行駛成本之和為最低。

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

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）為目標(biāo)函數(shù)，目標(biāo)為兩級(jí)物流網(wǎng)絡(luò)成本最小，式（2）表示顧客i能且只能被訪問(wèn)一次，式（3）表示中轉(zhuǎn)站k使用的車(chē)輛不能超過(guò)其所擁有的數(shù)量，式（4）表示中轉(zhuǎn)站k運(yùn)輸?shù)呢浳锟偭坎荒艹^(guò)其容量，式（5）表示配送中心j使用的車(chē)輛不能超過(guò)其所擁有的數(shù)量，式（6）表示中轉(zhuǎn)站運(yùn)入的貨物總量等于其運(yùn)出的貨物總量。

2 差分進(jìn)化算法

本文提出了離散差分進(jìn)化算法對(duì)兩級(jí)車(chē)輛—路徑問(wèn)題進(jìn)行求解。差分進(jìn)化算法（DE）是一種用于最佳化問(wèn)題的后設(shè)啟發(fā)式算法。本質(zhì)上說(shuō)，它是一種基于實(shí)數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法。

離散差分進(jìn)化算法采用自下向上的求解過(guò)程，在每一次迭代過(guò)程中首先對(duì)二級(jí)配送網(wǎng)絡(luò)中配送路徑進(jìn)行求解，然后根據(jù)二級(jí)配送網(wǎng)絡(luò)求解結(jié)果，求解一級(jí)配送網(wǎng)絡(luò)的配送路徑。

2.1 編 碼

由于2E—VRP包含多個(gè)子問(wèn)題，并且本文提出的離散差分進(jìn)化算法采用自下向上的求解過(guò)程，因此在解編碼方式選擇上，本文將一級(jí)配送網(wǎng)絡(luò)與二級(jí)配送網(wǎng)絡(luò)分別用相同的方式進(jìn)行編碼來(lái)表示解向量。

本文采用的是實(shí)數(shù)編碼方式，以二級(jí)配送網(wǎng)絡(luò)為例。對(duì)每一個(gè)中轉(zhuǎn)站分別進(jìn)行編碼，該編碼包含有編號(hào)為1，2，…，c的c個(gè)需求點(diǎn)以及若干個(gè)0表示路徑分割。圖2為某一中轉(zhuǎn)站的編碼示意圖。

該網(wǎng)絡(luò)編碼可轉(zhuǎn)換為3條路徑：

路徑1：某中轉(zhuǎn)站→22→8→7→27→該中轉(zhuǎn)站

路徑2：某中轉(zhuǎn)站→16→19→6→24→14→該中轉(zhuǎn)站

路徑3：某中轉(zhuǎn)站→20→28→該中轉(zhuǎn)站

2.2 算法步驟

初始化：

在初始化過(guò)程中需要生成兩級(jí)配送網(wǎng)絡(luò)初始解，本文采用貪婪算法生成初始解。

第一階段利用貪婪算法搜索構(gòu)造第二級(jí)配送網(wǎng)絡(luò)解向量，第二階段根據(jù)上一階段生成的第二級(jí)配送網(wǎng)絡(luò)解向量，采用相同的方法構(gòu)造第一級(jí)配送網(wǎng)絡(luò)解方案。

以二級(jí)配送網(wǎng)絡(luò)為例，貪婪隨機(jī)初始化具體步驟如下。

步驟1：將需求點(diǎn)分配給距離其最近的備選中轉(zhuǎn)站。

步驟2：根據(jù)需求點(diǎn)分配結(jié)果，檢查所有中轉(zhuǎn)站服務(wù)的需求點(diǎn)是否超過(guò)該中轉(zhuǎn)站的容量。

步驟3：若有中轉(zhuǎn)站服務(wù)的需求點(diǎn)超過(guò)其容量，將最后一個(gè)分配到該中轉(zhuǎn)站的需求點(diǎn)分配到距離其次近的中轉(zhuǎn)站。

步驟4：根據(jù)需求點(diǎn)分配結(jié)果，檢查所有中轉(zhuǎn)站的服務(wù)的需求點(diǎn)是否超過(guò)該中轉(zhuǎn)站的容量。如果都沒(méi)有超過(guò)，則初始化結(jié)束。否則返回步驟3。

變異：

利用隨機(jī)數(shù)產(chǎn)生變異的位置，例如對(duì)圖3進(jìn)行變異操作，假設(shè)隨機(jī)產(chǎn)生的交換的兩個(gè)位置是3和4，變異過(guò)程如圖3所示。

交叉：

步驟1：隨機(jī)選擇切點(diǎn)c■，c■。

步驟2：交換中間部分。

步驟3：從第二個(gè)切點(diǎn)c■后，第一個(gè)基因起列出原順序，去掉已有基因（注意0的個(gè)數(shù)）。

步驟4：從第二個(gè)切點(diǎn)c■后，第一個(gè)位置起，將獲得的無(wú)重復(fù)順序填入。

我們將上面的原個(gè)體和變異個(gè)體進(jìn)行交叉操作，假設(shè)我們隨機(jī)產(chǎn)生的c■、c■為4和6，交叉操作如圖4所示。

3 實(shí)驗(yàn)分析

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

4 結(jié) 論

針對(duì)兩級(jí)車(chē)輛路徑問(wèn)題，建立了以一級(jí)、二級(jí)配送網(wǎng)絡(luò)總成本最小為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃數(shù)學(xué)模型，考慮了一級(jí)配送中心、二級(jí)中轉(zhuǎn)站容量約束，一級(jí)、二級(jí)配送車(chē)輛容量約束。并提出了離散差分進(jìn)（下轉(zhuǎn)第13頁(yè)）