周 迅，張惠珍

（上海理工大學(xué)管理學(xué)院，上海 200093）

0 引言

設(shè)施選址與車輛路徑是供應(yīng)鏈網(wǎng)絡(luò)中的兩個(gè)關(guān)鍵問題，對(duì)公司運(yùn)營(yíng)和盈利有著重大影響。因此，設(shè)施選址問題［1］（Facility Location Problem，F(xiàn)LP）與車輛路徑問題［2］（Vehicle Routing Problem，VRP）引起了眾多研究者關(guān)注。隨著物流系統(tǒng)的日益復(fù)雜，選址和運(yùn)輸之間的耦合越來越高，儲(chǔ)運(yùn)之間關(guān)系日益密切。在解決許多實(shí)際問題時(shí)，應(yīng)綜合考慮兩者關(guān)系進(jìn)行決策，從而實(shí)現(xiàn)整體優(yōu)化，由此形成具有容量的設(shè)施選址問題（Capacitated Location Routing Problem，CLRP）［3］，該問題是當(dāng)前物流研究熱點(diǎn)。近年來，越來越多的企業(yè)將主要精力投入到核心業(yè)務(wù)中以獲得競(jìng)爭(zhēng)優(yōu)勢(shì)，同時(shí)將企業(yè)物流活動(dòng)外包給第三方物流供應(yīng)商。通常服務(wù)車輛由第三方物流公司擁有，在完成客戶服務(wù)之后，這些車輛返回到第三方物流公司，而不是企業(yè)配送中心或倉(cāng)庫(kù)，因此帶來由第三方物流配送的開放式選址路徑問題（Open Capacitated Location Routing Problem，OCLRP）［4］。CLRP 與相應(yīng)OCLRP 區(qū)別如圖1 所示。圖中實(shí)線部分給出了OCLRP 問題解決方案，每輛車在為最后一個(gè)客戶結(jié)束服務(wù)后無需回到倉(cāng)庫(kù)；圖中實(shí)線和虛線整體構(gòu)成了相應(yīng)CL?RP 解決問題的方案，車輛在為最后一個(gè)客戶結(jié)束服務(wù)后需返回倉(cāng)庫(kù)。從圖1 可以看出，CLRP 與OCLRP 的主要區(qū)別為OCLRP 中的每條路徑都是哈密頓路徑，而CLRP 中的每條路徑都是哈密頓回路。

Fig.1 The difference between CLRP and corresponding OCLRP圖1 CLRP 與相應(yīng)OCLRP 之間的區(qū)別

在實(shí)際配送中，OCLRP 會(huì)面臨各種限制條件。比如，很多客戶對(duì)交貨期都有一定要求。配送服務(wù)最好提前在約定的時(shí)間窗口內(nèi)完成，否則會(huì)因違反時(shí)間窗口約束而受到處罰。此外，在很多情況下，車輛不僅需要為客戶進(jìn)行送貨服務(wù)，還有可能在客戶所在位置進(jìn)行取貨，將貨物運(yùn)回收貨點(diǎn)或第三方公司車輛中心。因此，本文將OCLRP 與同時(shí)取送貨及軟時(shí)間窗［5］相結(jié)合，提出了帶軟時(shí)間窗的同時(shí)取送貨［6］開放式選址路徑問題（Open Capacitated Loca?tion Routing Problem with Soft Time Windows and Simultane?ous Pickup-Delivery，OCLRP-STWSPD）。OCLRP-STWSPD問題集FLP 和VRP 兩個(gè)NP-hard 問題為一體，并結(jié)合物流配送的實(shí)際情況增加了軟時(shí)間窗和同時(shí)取送貨限制，不僅復(fù)雜度更高，且更貼近現(xiàn)實(shí)。

當(dāng)采用精確算法求解大規(guī)模組合優(yōu)化NP-hard 問題時(shí)，通常難以得到最優(yōu)解，且求解效率不高，而智能優(yōu)化算法具有在較短的時(shí)間內(nèi)對(duì)大規(guī)模優(yōu)化問題提供近似最優(yōu)解的優(yōu)點(diǎn)。智能優(yōu)化算法常被用來求解此類問題，如蟻群算法［7］、遺傳算法［8］、模擬退火算法［9］、粒子群算法［10］等。煙花算法［11］（Fireworks Algorithm，F(xiàn)WA）是2010 年Tan &Zhu 受煙花爆炸產(chǎn)生火花這一自然現(xiàn)象啟發(fā)而提出的一種新型智能優(yōu)化算法，具有尋優(yōu)效果好、穩(wěn)定性強(qiáng)、效率高的優(yōu)點(diǎn)。近年來，很多改進(jìn)的FWA 算法已被提出，如反向煙花算法［12］、混沌煙花算法［13］、二進(jìn)制煙花算法［14］等，同時(shí)FWA 也被廣泛應(yīng)用于云計(jì)算［15］、WEB 服務(wù)［16］、置換流水車間［17］等多個(gè)領(lǐng)域。鑒于OCLRP-STWSPD 問題的復(fù)雜性及FWA 良好的優(yōu)化性能，本文對(duì)FWA 加以改進(jìn)并用于求解OCLRP-STWSPD 問題。

本文根據(jù)OCLRP-STWSPD 問題特征，提出新的解表示方法，并對(duì)標(biāo)準(zhǔn)的FWA 加以改進(jìn)，提出求解OCLRP-ST?WSPD 的離散煙花算法。實(shí)驗(yàn)證明該算法可有效解決目前第三方物流配送中同時(shí)取送貨和配送時(shí)間約束問題，對(duì)節(jié)約企業(yè)配送成本、提高客戶滿意度具有重要意義，同時(shí)又可進(jìn)一步拓展煙花算法應(yīng)用領(lǐng)域。

1 帶軟時(shí)間窗同時(shí)取送貨開放式選址路徑問題

1.1 問題描述

OCLRP-STWSPD 是在傳統(tǒng)OCLRP 問題上加入同時(shí)取送貨和軟時(shí)間窗限制，車輛需在客戶能夠接受的時(shí)間內(nèi)進(jìn)行配送或取貨，否則將產(chǎn)生懲罰成本。OCLRP-STWSPD 依據(jù)客戶點(diǎn)和候選倉(cāng)庫(kù)點(diǎn)空間位置與服務(wù)需求關(guān)系，確定開放倉(cāng)庫(kù)與配送路徑，由開放倉(cāng)庫(kù)派出車輛為客戶提供配送和取貨服務(wù)，使物流系統(tǒng)總成本達(dá)到最小，并要求：①車輛對(duì)客戶除了提供配送服務(wù)，還可能從客戶處取走貨物（客戶貨物量已知）；②在配送過程中每位客戶有且僅能被1 輛車訪問1 次，且客戶配送需求或取貨需求需得到滿足，車輛在配送過程中任意時(shí)刻的裝載量不能超過車輛最大裝載量；③分配給任一開放倉(cāng)庫(kù)的客戶總需求不能大于該倉(cāng)庫(kù)容量；④每輛車為最后1 個(gè)客戶完成服務(wù)后不返回倉(cāng)庫(kù)，而是返回收貨點(diǎn)或第三方公司車輛中心；⑤在配送過程中，每個(gè)客戶有自己接受服務(wù)的時(shí)間窗限制，車輛可在客戶預(yù)先給定的服務(wù)時(shí)間之外為其服務(wù)，即車輛可早到或晚到，但違反時(shí)間窗的服務(wù)會(huì)產(chǎn)生一定的懲罰成本；⑥若一位客戶同時(shí)具有配送和取貨需求，則服務(wù)順序應(yīng)該為先卸貨后取貨。

1.2 數(shù)學(xué)模型

模型主要參數(shù)設(shè)置包括：Vp為第三方物流公司的停車場(chǎng)集合；Vd為候選倉(cāng)庫(kù)集合，Vd={1,23,…,m}，其中m為候選倉(cāng)庫(kù)數(shù)量；Vc為客戶點(diǎn)集合，Vc={m+1,m+2,…,m+n}，其中n為客戶數(shù)量；V為停車場(chǎng)、候選倉(cāng)庫(kù)和客戶點(diǎn)集合，V=Vp∪Vd∪Vc；K為配送車輛集合；Oi為倉(cāng)庫(kù)i開放成本；di為客戶i配送量；bi為客戶i取貨量；Qi為倉(cāng)庫(kù)i容量；P為每一輛車最大裝載量，假設(shè)所有配送車輛相同；cij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離；e為單位距離的運(yùn)輸成本；w為每輛車固定使用成本；ETi為客戶i接受服務(wù)的最早開始時(shí)間；LTi為客戶i接受服務(wù)的最晚開始時(shí)間；Ti為配送車輛到達(dá)節(jié)點(diǎn)i的時(shí)間；si為客戶i的服務(wù)時(shí)間；tij為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的時(shí)間；pe為提前到達(dá)的單位時(shí)間懲罰成本；pl為延遲服務(wù)的單位時(shí)間懲罰成本；aik為車輛k在離開節(jié)點(diǎn)i時(shí)的裝載量。

決策變量設(shè)置如下：

ujk=用于消除第k條配送路線中子回路的輔助變量

在上述參數(shù)和決策變量設(shè)置基礎(chǔ)上，OCLRP-STWSPD數(shù)學(xué)模型可構(gòu)建為：

其中，目標(biāo)函數(shù)（1）表示最小化總成本，包括倉(cāng)庫(kù)開放成本、車輛的固定啟用成本、行駛成本和懲罰成本；約束（2）確保每個(gè)客戶只由1 輛車提供1 次服務(wù)；約束條件（3）表示車輛在任何時(shí)刻的載重量都不超過其最大裝載量；約束條件（4）表示車輛在離開倉(cāng)庫(kù)時(shí)的載重量，即配送路線上所有客戶配送量之和；式（5）為車輛在離開各個(gè)客戶時(shí)的裝載量的等式約束；約束條件（6）表示分配給倉(cāng)庫(kù)的客戶總需求不能超過倉(cāng)庫(kù)的總?cè)萘?；約束（7）保證每條配送路線連續(xù)性；約束（8）表明任意兩個(gè)倉(cāng)庫(kù)之間沒有連接；約束（9）確保配送車輛為最后1 位客戶完成服務(wù)后不返回倉(cāng)庫(kù)；約束（10）說明每個(gè)客戶都必須被一個(gè)開放的倉(cāng)庫(kù)提供服務(wù)；約束（11）表示兩個(gè)決策變量之間的關(guān)系；約束（12）表示車輛在行駛過程中的時(shí)間窗約束；約束（13）用于消除子回路；約束（14）-（16）表示3 組不同的0-1 決策變量；約束（17）為消除子回路所用的輔助變量。

2 OCLRP-STWSPD 離散煙花算法求解

2.1 傳統(tǒng)煙花算法

煙花算法［11］是一種受煙花爆炸現(xiàn)象啟發(fā)，通過模擬煙花爆炸過程實(shí)現(xiàn)的群體智能優(yōu)化算法。為了保持種群多樣性，煙花算法設(shè)計(jì)了兩個(gè)爆炸搜索過程。煙花算法將每一個(gè)煙花和煙花爆炸產(chǎn)生的每一個(gè)火花視為一個(gè)可行解，每一次煙花在不同爆炸半徑內(nèi)產(chǎn)生不同數(shù)量的火花。通過調(diào)整爆炸半徑和火花數(shù)量，實(shí)現(xiàn)全局搜索與局部搜索平衡。該算法由爆炸算子、變異算子和選擇策略3 部分組成。

2.1.1 爆炸算子

假設(shè)研究問題是最小化目標(biāo)函數(shù)f(x)，F(xiàn)為解的可行域。首先在可行域F上初始化生成N個(gè)煙花Xi(i=1,2,3,…,N)，并評(píng)估初始煙花函數(shù)f(Xi)。煙花Xi通過爆炸算子在半徑Ai上產(chǎn)生Si個(gè)火花，每個(gè)煙花爆炸半徑Ai與產(chǎn)生的爆炸火花數(shù)Si的計(jì)算公式分別為：

其中，ymin為當(dāng)前煙花種群對(duì)應(yīng)的目標(biāo)函數(shù)最小值，ymax為目標(biāo)函數(shù)最大值；ε 是一個(gè)很小的常數(shù)，以防止分母為0。A0和M0為常數(shù)，分別用以調(diào)整每個(gè)煙花爆炸產(chǎn)生的半徑大小和爆炸火花總數(shù)量。為了區(qū)分煙花優(yōu)劣，函數(shù)值越小的煙花在小半徑內(nèi)產(chǎn)生的火花越多，相應(yīng)局部搜索能力越強(qiáng)［15］；相反，函數(shù)值較高的煙花在較大范圍內(nèi)產(chǎn)生相對(duì)較少的火花，具有一定的全局搜索能力。

為控制火花數(shù)量過多或過少，引入式（18）所示的機(jī)制控制每個(gè)煙花產(chǎn)生的火花數(shù)量Si。

其中，a和b為兩個(gè)常數(shù)，round為四舍五入函數(shù)。

2.1.2 變異算子

在變異算子中，通常采用高斯變異產(chǎn)生變異火花加強(qiáng)煙花種群多樣性。高斯變異火花產(chǎn)生過程為：首先，在煙花種群中隨機(jī)選擇1 個(gè)煙花Xi;然后，隨機(jī)選擇Xi中的若干分量，并按照公式（19）進(jìn)行變異操作［10］，重復(fù)M1次，即可產(chǎn)生M1個(gè)變異火花。

其中，r為服從均值和標(biāo)準(zhǔn)差均為1的高斯分布隨機(jī)數(shù)。

2.1.3 選擇策略

為了將當(dāng)前煙花種群中的優(yōu)秀信息傳遞到下一代種群中，煙花算法會(huì)在候選種群H中選擇N個(gè)個(gè)體作為下一代煙花。其中，候選種群H由煙花、爆炸火花和高斯變異火花組成［10］。選擇過程為：首先，采用精英策略保留最優(yōu)秀的煙花，即函數(shù)值最小解；其次，使用輪盤賭策略從候選集合中選擇N-1 個(gè)個(gè)體。其中每個(gè)個(gè)體被選中的概率為：

2.2 離散煙花算法

傳統(tǒng)煙花算法最初用于連續(xù)域函數(shù)優(yōu)化，算法步驟中的爆炸算子和變異算子僅適用于連續(xù)域空間搜索。由于離散優(yōu)化問題與連續(xù)優(yōu)化問題的區(qū)別，傳統(tǒng)煙花算法不能直接應(yīng)用于OCLRP-STWSPD 和其他離散優(yōu)化問題求解。因此，本文依據(jù)OCLRP-STWSPD 問題特征和煙花算法搜索機(jī)制，對(duì)爆炸算子和變異算子重新定義，并針對(duì)OCLRPSTWSPD 提出新的解表示方法，在算法搜索過程中加入自適應(yīng)策略，進(jìn)而提出求解OCLRP-STWSPD 問題的離散煙花算法（Discrete Fireworks Algorithm，DFWA）。

2.2.1 初始解構(gòu)建

（1）編碼方式。假設(shè)有m個(gè)候選倉(cāng)庫(kù)和n個(gè)客戶，則初始解由Vd={1,2,3,…,m}集合內(nèi)的元素和Vc={m+1,m+2,…,m+n}中的元素以及一些輔助數(shù)字0 組成。其中，輔助數(shù)字0 用來分割路徑，輔助數(shù)字0 的數(shù)量應(yīng)該等于或小于表示大于或等于x的最小整數(shù)）。分配給每個(gè)倉(cāng)庫(kù)的客戶位于它與下一個(gè)不同的倉(cāng)庫(kù)之間，如果在一個(gè)倉(cāng)庫(kù)之后沒有客戶，則表示該候選倉(cāng)庫(kù)沒有開放。

圖2 給出1 個(gè)10 位客戶和3 個(gè)備選倉(cāng)庫(kù)的例子。如圖2 所示，倉(cāng)庫(kù)3 未開放，倉(cāng)庫(kù)1、2 開放。其中，從倉(cāng)庫(kù)1 出發(fā)的兩條配送路線為1 →9 →10→13 和1 →12→4；從倉(cāng)庫(kù)2 出發(fā)的兩條配送路線為2→8 →11→5 和2 →6→7。

Fig.2 Solution representation圖2 解的表示

（2）種群初始化。為了產(chǎn)生好的初始種群，本文采用基于貪婪思想的策略構(gòu)建初始解。

步驟1：設(shè)Per為Vd中m個(gè)倉(cāng)庫(kù)的隨機(jī)排列。將Per中的第i個(gè)元素表示為Peri，令i=1。

步驟2：設(shè)Cus為未被分配客戶的集合，C(Peri)表示未被分配客戶中需求不超過倉(cāng)庫(kù)Peri剩余能力的客戶集合。首先，對(duì)未分配的客戶進(jìn)行分配，并從Peri倉(cāng)庫(kù)開始一條新的路線，將C(Peri)中距離Peri倉(cāng)庫(kù)最近的客戶分配給Peri倉(cāng)庫(kù)；其次，將C(Peri)中距離上一個(gè)已分配客戶最近的客戶分配到當(dāng)前路線中，如果該客戶需求量大于車輛剩余容量，則將該客戶從該路線中刪除，并繼續(xù)從C(Peri)中尋找距離上一個(gè)客戶最近且需求量滿足車輛剩余容量的客戶。若不存在客戶滿足條件，則從Peri開始一條新的路線，并重復(fù)上述操作，直到Peri倉(cāng)庫(kù)剩余容量無法服務(wù)任何新客戶為止。

步驟3：如果Cus不為空，則令i=i+1，并重復(fù)步驟2。否則，將使用2.1.1 中的編碼方式對(duì)當(dāng)前序列進(jìn)行編碼作為一個(gè)初始解。

步驟4：如果初始解的個(gè)數(shù)小于預(yù)先設(shè)定的煙花種群大小N，返回步驟1；否則，輸出初始種群。

2.2.2 爆炸算子

針對(duì)OCLRP-STWSPD 離散特征，本文采用交換操作實(shí)現(xiàn)爆炸算子［5］，并將爆炸半徑Ai定義為交換次數(shù)。具體操作為對(duì)煙花Xi，隨機(jī)選取Xi上的Ai對(duì)客戶，并對(duì)選中位置上的元素進(jìn)行交換，得到新的序列。

圖3 為爆炸算子具體操作。如圖3 所示，當(dāng)煙花Xi爆炸半徑Ai為2 時(shí)，對(duì)煙花序列Xi選擇兩對(duì)客戶進(jìn)行交換操作，選擇5 和7、10 和12 進(jìn)行交換操作形成新序列。

Fig.3 Illustration of generating a spark with Ai=2圖3 為2 時(shí)的爆炸算子操作

2.2.3 變異算子

（1）變異算子實(shí)現(xiàn)。DFWA 變異算子是通過插入和逆轉(zhuǎn)兩種搜索機(jī)制［5］實(shí)現(xiàn)的。變異火花通過這兩種操作產(chǎn)生，兩種操作概率均為0.5。

生成隨機(jī)數(shù)rand，若rand小于0.5，則使用插入操作：隨機(jī)選取Xi的兩個(gè)位置a、b，將b位置上的元素插入到a位置元素的前面；若rand大于等于0.5，則使用逆轉(zhuǎn)操作：隨機(jī)選取Xi的兩個(gè)位置a、b，逆轉(zhuǎn)a、b之間的元素排列。

圖4 和圖5 分別給出了變異算子的兩種實(shí)現(xiàn)方法。圖4 為插入操作，將元素9 插入到元素7 前面產(chǎn)生一個(gè)新的序列；圖5 為逆轉(zhuǎn)操作，將元素5 和元素13 之間的所有元素逆轉(zhuǎn)其排列順序生成1 個(gè)新的序列。

Fig.4 Illustration of the insertion move圖4 插入操作

Fig.5 Illustration of the inverse move圖5 逆轉(zhuǎn)操作

（2）自適應(yīng)策略?；舅枷霝椋喝绻?dāng)前代搜索到更優(yōu)解，則認(rèn)為當(dāng)前煙花種群具有較強(qiáng)的尋優(yōu)能力；否則，說明可能已經(jīng)陷入局部最優(yōu)?；谠撍枷?，算法利用變異算子中的參數(shù)q改變種群尋優(yōu)能力。若當(dāng)前代搜索到更優(yōu)解，則減小q以加強(qiáng)局部搜索；若當(dāng)前最優(yōu)解沒有得到改進(jìn)，則增大q以提高接受較差解的概率，以便更快跳出局部最優(yōu)解。

在離散優(yōu)化過程中，往往很難在1 次迭代中得到較好的解。因此，當(dāng)煙花種群落入局部極值時(shí)，往往需多次迭代才能跳出局部收斂。鑒于此，本文設(shè)定如果連續(xù)10 代不改進(jìn)最優(yōu)值，則增大q值。公式（22）-（23）分別用來增大和減小q值。其中，r和h均為常數(shù)，分別為增長(zhǎng)因子和衰退因子。

2.3 算法步驟

基于上述操作，求解OCLRP-STWSPD 的DFWA 具體步驟為（見圖6）：

步驟1：初始化。首先，初始化煙花種群大小N、爆炸因子A0、爆炸火花數(shù)M0、變異火花數(shù)M1、控制參數(shù)q、增長(zhǎng)因子r、衰退因子h、最大迭代次數(shù)T；然后使用貪婪策略初始化煙花種群。

步驟2：對(duì)煙花種群進(jìn)行爆炸算子和變異算子操作，產(chǎn)生新的爆炸火花和變異火花。

步驟3：從候選種群（煙花，爆炸火花，變異火花）中選擇N個(gè)煙花作為下一代種群。

步驟4：若當(dāng)前代搜索過程產(chǎn)生更優(yōu)解，則減小q；若當(dāng)前代解連續(xù)10 代沒有得到改進(jìn)，則增大q值。

步驟5：重復(fù)步驟2、3、4、5，直到達(dá)到最佳迭代次數(shù)T，輸出最優(yōu)解。

Fig.6 The flow of DFWA algorithm圖6 DFWA 算法流程

2.4 時(shí)間復(fù)雜度分析

假設(shè)初始煙花種群大小為N，n名客戶和m個(gè)倉(cāng)庫(kù)，爆炸算子產(chǎn)生M0個(gè)爆炸火花，變異算子產(chǎn)生M1個(gè)變異火花。DFWA 在構(gòu)建初始解階段需生成N個(gè)初始解，且對(duì)每個(gè)倉(cāng)庫(kù)進(jìn)行客戶分配排序，其時(shí)間復(fù)雜度為O(N×m×n)；在爆炸算子階段，N個(gè)煙花產(chǎn)生M0個(gè)爆炸火花，其時(shí)間復(fù)雜度為O(N×M0)；在變異算子階段產(chǎn)生了個(gè)M1變異火花，其時(shí)間復(fù)雜度為O(M1)。在選擇階段需從候選種群中保留最優(yōu)個(gè)體，涉及到所有候選種群個(gè)體排序，其時(shí)間復(fù)雜度為O((N+M0+M1)log2(N+M0+M1))。綜合各個(gè)步驟，DF?WA 時(shí)間復(fù)雜度為O(N×m×n)+O(N×M0) +O(M1)+O((N+M0+M1)log2(N+M0+M1))=O(N×m×n)+O(N×M0) +O((N+M0+M1)log2(N+M0+M1))。

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

3.1 參數(shù)設(shè)置與靈敏度分析

參數(shù)設(shè)置可能影響DFWA 性能。因此，本文進(jìn)行靈敏度分析以確定最佳參數(shù)設(shè)置。實(shí)驗(yàn)在Windows10 系統(tǒng)下的MATLAB R2016a 環(huán)境進(jìn)行。測(cè)試參數(shù)值設(shè)置如下：

每種參數(shù)組合獨(dú)立運(yùn)行10 次，并使用平均目標(biāo)函數(shù)值與平均運(yùn)行時(shí)間為評(píng)價(jià)指標(biāo)。當(dāng)研究其中一個(gè)參數(shù)與算法性能之間關(guān)系時(shí)，其他參數(shù)保持不變。

3.1.1 煙花種群大小N

如圖7 所示，實(shí)線與虛線曲線分別表示在不同參數(shù)N下的目標(biāo)函數(shù)值和計(jì)算時(shí)間。隨著N的增大，解空間也隨之變大，因此得到優(yōu)秀解的概率也會(huì)增加。從圖1 可以看出，N對(duì)DFWA 的影響較大，當(dāng)N增大時(shí)，目標(biāo)值會(huì)不斷減小，計(jì)算時(shí)間也會(huì)相應(yīng)提高。當(dāng)N提高到1.25（n+m）后，解的質(zhì)量提升速度明顯下降，而計(jì)算時(shí)間依然會(huì)增加，因此綜合解質(zhì)量和計(jì)算時(shí)間，本文選取N=1.25()n+m作為煙花種群大小。

Fig.7 Sensitivity analysis of parameter N圖7 參數(shù)N 的靈敏度分析

3.1.2 爆炸因子A0

在DFWA 中，A0用于調(diào)整爆炸半徑，以控制產(chǎn)生每個(gè)火花所需交換次數(shù)。當(dāng)A0較小時(shí)，交換次數(shù)較小，交換產(chǎn)生的火花不能得到充分改善；但是當(dāng)A0較大時(shí)，也可能陷入無意義迭代，增加計(jì)算時(shí)間。如圖8 所示，當(dāng)A0=2N時(shí)，計(jì)算結(jié)果較好，相應(yīng)計(jì)算時(shí)間也相對(duì)合理。

Fig.8 Sensitivity analysis of parameter A0圖8 參數(shù)A0的靈敏度分析

3.1.3 爆炸火花數(shù)M0

爆炸火花數(shù)M0越少，對(duì)鄰域搜索力度越小，得到最優(yōu)解的可能性越小。但是，較多的爆炸火花可能與窮舉法非常相似，會(huì)大幅增加計(jì)算時(shí)間。如圖9 所示，當(dāng)M0=(n+m)時(shí)，DFWA 尋優(yōu)效果和計(jì)算時(shí)間較為合理。因此，本文將爆炸火花數(shù)量設(shè)置為M0=(n+m)。

Fig.9 Sensitivity analysis of parameter M0圖9 參數(shù)M0的靈敏度分析

3.1.4 變異火花數(shù)M1

變異火花數(shù)M1和爆炸火花數(shù)M0效果相似。變異火花可提高種群多樣性，可有效防止算法陷入局部最優(yōu)解。M1值越小，其搜索范圍越??；M1值越大，其搜索范圍越大，種群多樣性也越高，但M1取值較大時(shí)，相應(yīng)計(jì)算時(shí)間也越高。如圖10 所示，當(dāng)M1=(n+m)時(shí)，可較好平衡解質(zhì)量和計(jì)算時(shí)間。

Fig.10 Sensitivity analysis of parameter M1圖10 參數(shù)M1的靈敏度分析

3.1.5 控制參數(shù)q

在DFWA 中，參數(shù)q用來調(diào)節(jié)接受較差解的概率。當(dāng)q較小時(shí)，接受差解的概率也較小，可加速收斂速度，同時(shí)也可降低種群多樣性，加大陷入局部最優(yōu)解的可能性；當(dāng)q較大時(shí)，接受差解的概率較大，種群多樣性提高的同時(shí)也降低了收斂速度。圖11 給出了在不同q值大小下DFWA 的表現(xiàn)，可以看到當(dāng)q值較小或較大時(shí)，DFWA 尋優(yōu)效果并不理想。當(dāng)q=1 時(shí)，DFWA 可較好平衡收斂速度與尋優(yōu)效果。

Fig.11 Sensitivity analysis of parameter q圖11 參數(shù)q 的靈敏度分析

3.2 算例分析與結(jié)果比較

目前尚未有標(biāo)準(zhǔn)的實(shí)驗(yàn)數(shù)據(jù)，為了驗(yàn)證本文OCLRPSTWSPD 模型與DFWA 算法有效性與可行性，對(duì)文獻(xiàn)［19］和［20］給出的CLRP 算例加以改造進(jìn)行實(shí)驗(yàn)。算例中各節(jié)點(diǎn)坐標(biāo)、倉(cāng)庫(kù)費(fèi)用和容量、車輛最大容量、客戶配送量以及各項(xiàng)固定成本費(fèi)用均采用文獻(xiàn)［19］、［20］所給算例原始數(shù)據(jù)，客戶取貨量采用均勻分布的方式生成，均勻分布上下限為對(duì)應(yīng)算例中配送量最小值和最大值，而客戶時(shí)間窗上下限ETi和LTi同樣采用均勻分布的方式生成，均勻分布區(qū)間分別為［0，10］和［ETi+30,ETi+60]。DFWA 參數(shù)設(shè)置為參數(shù)設(shè)置與靈敏度分析中找到的最優(yōu)參數(shù)，此外，增長(zhǎng)因子r=1.1、衰退因子h=0.98、最大迭代次數(shù)T=500。

第一組數(shù)據(jù)客戶數(shù)為20 或50，候選倉(cāng)庫(kù)數(shù)均為5，單位運(yùn)輸成本為100，每輛車固定租賃成本為1 000，單位懲罰成本Pe和Pl分別為50 和80，車輛行駛速度為3；第二組數(shù)據(jù)客戶數(shù)量范圍從8 到50，候選倉(cāng)庫(kù)數(shù)為2 或5，單位運(yùn)輸成本為1，單位懲罰成本Pe和Pl分別設(shè)置為5 和8，車輛行駛速度為5。表1 和表2 分別給出了DFWA 對(duì)第一組算例中每個(gè)算例獨(dú)立求解10 次的結(jié)果，包括最小成本值、最小成本值出現(xiàn)次數(shù)、平均成本值、平均運(yùn)行時(shí)間以評(píng)估算法性能。如表1 所示，算法求解20-5 的算例時(shí)，均可達(dá)到最小成本值，平均運(yùn)行時(shí)間最長(zhǎng)達(dá)10.33s。對(duì)于50-5 的算例，算法可在10 次運(yùn)行中至少2 次達(dá)到最小成本值，平均運(yùn)行時(shí)間最長(zhǎng)達(dá)32.93s。表2 給出了DFWA 對(duì)第二組算例中每個(gè)算例獨(dú)立求解10 次的結(jié)果。對(duì)于第二組算例，算法在10 次運(yùn)行中至少3 次可達(dá)到最小成本值，且計(jì)算時(shí)間不高于31.63s。

為了更進(jìn)一步驗(yàn)證DFWA 性能，本文選擇文獻(xiàn)［18］中的OCLRP 算例進(jìn)行直接計(jì)算并與文獻(xiàn)［18］中的算法進(jìn)行比較，使用DFWA 運(yùn)行每組算例10 次后取其中最優(yōu)值，其比較結(jié)果如表3 所示。

表3 提供了CPLEX 優(yōu)化器、SA［18］、DFWA 在18 組算例上的表現(xiàn)。從求解結(jié)果方面看，CPLEX 求解器可以在16 組算例上達(dá)到最優(yōu)值，而SA（模擬退火算法）和DFWA 均可以在17 組算例上取得最優(yōu)值；從求解效率上來看，CPLEX 優(yōu)化器在小規(guī)模且客戶數(shù)不多于22 的算例上效率更高，甚至在一些算例上可以在1s 以內(nèi)得到優(yōu)化結(jié)果。但在大規(guī)模的算例上，CPLEX 求解效率較低，某些大規(guī)模算例在4 小時(shí)內(nèi)仍未求得最優(yōu)解。而SA 和DFWA 在大規(guī)模算例上的求解效率明顯更高，從時(shí)間上來看，DFWA 在13 組算例上的計(jì)算時(shí)間少于SA，且計(jì)算時(shí)間大幅度下降。綜合來看，DF?WA 在求解此類問題時(shí)，能夠在較短時(shí)間內(nèi)求解出令人滿意的解，且具有尋優(yōu)效果好、求解效率高的優(yōu)點(diǎn)。

Table 1 The OCLRP-STWSPD results of the first set of data表1 第一組數(shù)據(jù)的OCLRP-STWSPD 結(jié)果

Table 2 The OCLRP-STWSPD results of the second set of data表2 第二組數(shù)據(jù)的OCLRP-STWSPD 結(jié)果

3.3 OCLRP-STWSPD 與CLRP-STWSPD 比較

為證明OCLRP-STWSPD 模型在現(xiàn)實(shí)生活中的適用性，本部分對(duì)上述數(shù)據(jù)集在相同時(shí)間窗和相同參數(shù)設(shè)置下，進(jìn)行帶軟時(shí)間窗的同時(shí)取送貨有容量選址路徑問題（Capacitated Location Routing Problem with Soft Time Win?dows and Simultaneous Pickup-Delivery，CLRP-STWSPD）實(shí)驗(yàn)，并將CLRP-STWSPD 運(yùn)行結(jié)果與上述OCLRP-STWSPD結(jié)果進(jìn)行對(duì)比。

表4 給出了運(yùn)用DFWA 對(duì)OCLRP-STWSPD 和OCL?RP-STWSPD 在所給算例上的求解結(jié)果、差值（差值=CL?RP-STWSPD－ OCLRP-STWSPD）和Gap值（Gap=。

Table 3 Comparison of DFWA and other algorithms表3 DFWA 與其他算法的比較結(jié)果

Table 4 Comparison of solution results of OCLRP-STWSPD and CLRP-STWSPD表4 OCLRP-STWSPD 與CLRP-STWSPD 求解結(jié)果對(duì)比

從表4 可知，在相同時(shí)間窗下，OCLRP-STWSPD 成本值遠(yuǎn)小于CLRPSTW-STWSPD，最大Gap達(dá)到30.20%，可節(jié)省高達(dá)15 270 單位的成本。這是由于OCLRP-STWSPD 物流系統(tǒng)外包給第三方公司，為所有客戶完成服務(wù)后的車輛無需返回倉(cāng)庫(kù)以節(jié)省開支。這些結(jié)果進(jìn)一步證明了OCL?RP-STWSPD 在現(xiàn)實(shí)生活中的適用性，同時(shí)也表明如果公司將配送活動(dòng)外包給第三方，可節(jié)省大量配送成本。

4 結(jié)語

本文提出了一個(gè)應(yīng)用背景更符合實(shí)際的帶軟時(shí)間窗同時(shí)取送貨開放式選址路徑問題，并以最小化倉(cāng)庫(kù)開放成本、配送成本、固定車輛車本、懲罰成本之和為目標(biāo)建立數(shù)學(xué)模型。針對(duì)傳統(tǒng)煙花算法求解離散問題的局限性，基于交叉逆轉(zhuǎn)等操作重新定義爆炸算子與變異算子以維持種群多樣性，并加入自適應(yīng)策略避免過早陷入局部最優(yōu)解，提高算法搜索能力。同時(shí)，在算法中加入新的解表示方式分割求解路徑。最后通過算例求解與結(jié)果比較，證明了DFWA 在求解OCLRP-STWSPD 問題上有效性和可行性，可很好地解決目前第三方物流配送中面臨的現(xiàn)實(shí)問題，對(duì)企業(yè)節(jié)約配送成本與提高客戶滿意度具有重要意義。下一步將集中從3 個(gè)方面開展更深入研究：①考慮更多的約束條件，比如考慮交通路況的OCLRP、帶模糊需求的OCLRP、多目標(biāo)的OCLRP；②設(shè)計(jì)其他啟發(fā)式算法解決OCLRP 問題；③采用DFWA 解決FLP 與VRP 其他變體。