帶時(shí)間窗同時(shí)送取貨選址路徑問(wèn)題及其煙花算法求解

劉亞平，張惠珍，張莉，劉優(yōu)優(yōu)

帶時(shí)間窗同時(shí)送取貨選址路徑問(wèn)題及其煙花算法求解

劉亞平，張惠珍*，張莉，劉優(yōu)優(yōu)

（上海理工大學(xué) 管理學(xué)院，上海 200093）（ ? 通信作者電子郵箱zhzzywz@163.com）

隨著電子商務(wù)的飛速發(fā)展以及互聯(lián)網(wǎng)的普及，退換貨更加便捷，因此客戶對(duì)商品的需求呈現(xiàn)出時(shí)效性、多品種、小批量、退換貨等特點(diǎn)。針對(duì)有容量的同時(shí)送取貨選址路徑問(wèn)題（LRPSPD），同時(shí)考慮客戶多樣性需求的特點(diǎn)，建立了帶時(shí)間窗的同時(shí)送取貨選址路徑問(wèn)題（LRPSPDTW）的數(shù)學(xué)模型。使用改進(jìn)煙花算法（IFWA）對(duì)模型進(jìn)行求解，對(duì)煙花爆炸和變異進(jìn)行相應(yīng)的鄰域操作，并用一些基準(zhǔn)LRPSPD算例來(lái)評(píng)估煙花算法的性能。通過(guò)大量的數(shù)值實(shí)驗(yàn)驗(yàn)證了所提模型和算法的正確性和有效性。實(shí)驗(yàn)結(jié)果表明，相較于分支切割算法（B&C），IFWA得到的結(jié)果與標(biāo)準(zhǔn)解的平均誤差縮小了0.33個(gè)百分點(diǎn)。所提算法縮短了尋求最優(yōu)解的時(shí)間，為解決選址路徑相關(guān)問(wèn)題提供了一種新的解決思路。

時(shí)間窗；同時(shí)送取貨；選址路徑；煙花算法；鄰域操作

0 引言

選址路徑問(wèn)題（Location-Routing Problem， LRP）是選址分配問(wèn)題（Location Allocating Problem， LAP）和車(chē)輛路徑問(wèn)題（Vehicle Routing Problem， VRP）的集成優(yōu)化問(wèn)題，單獨(dú)的選址和車(chē)輛路徑問(wèn)題的研究文獻(xiàn)已經(jīng)非常多并且相對(duì)成熟，根據(jù)效益悖反原理，單獨(dú)地考慮某一個(gè)問(wèn)題容易達(dá)到局部最優(yōu)并不是整體最優(yōu)效果，而企業(yè)的運(yùn)轉(zhuǎn)更多著眼于整個(gè)供應(yīng)鏈、系統(tǒng)化以及集成化的研究；另外，互聯(lián)網(wǎng)的普及以及電商的迅猛發(fā)展，退換貨更加便捷，客戶對(duì)商品交易的時(shí)間要求更高，商品種類(lèi)也更豐富。因此，研究?jī)烧叩慕M合問(wèn)題對(duì)增強(qiáng)企業(yè)自身實(shí)力和提升企業(yè)競(jìng)爭(zhēng)優(yōu)勢(shì)方面具有更加實(shí)質(zhì)性的幫助。

已經(jīng)有大量學(xué)者對(duì)選址路徑及其擴(kuò)展問(wèn)題進(jìn)行了不同程度的研究。Benotmane等［1］對(duì)經(jīng)典的LRP進(jìn)行了研究；Fazayeli等［2］因?yàn)榭蛻粜枨蟪尸F(xiàn)隨機(jī)性和動(dòng)態(tài)性，研究了客戶需求不確定性的LRP；Zhao等［3］針對(duì)客戶同時(shí)有配送和回收需求，研究了同時(shí)送取貨的選址路徑問(wèn)題（Location-Routing Problem with Simultaneous Pickup and Delivery， LRPSPD）。以往關(guān)于選址路徑的文獻(xiàn)一個(gè)共同的假設(shè)是為一輛車(chē)分配一條路線，然而獲取車(chē)輛的成本通常比路徑成本更大，因此Wang等［4］提出了多目標(biāo)的選址路徑問(wèn)題（Multi-Objective Location-Routing Problem， MOLRP）。在實(shí)際運(yùn)輸中，車(chē)輛都是有容量限制的，Oudouar等［5］研究了帶車(chē)容量限制的選址路徑問(wèn)題（Capacitated Location-Routing Problem， CLRP）。Farham等［6］針對(duì)冷鏈生鮮、災(zāi)后救援、應(yīng)急醫(yī)療系統(tǒng)對(duì)物資的時(shí)效性要求較高，研究了帶時(shí)間窗約束的選址路徑問(wèn)題（Location-Routing Problem with Time Window，LRPTW）。目前，有關(guān)滿足多種條件的LRP延伸問(wèn)題相關(guān)文獻(xiàn)較少：羅耀波等［7］研究了基于模糊時(shí)間窗的同時(shí)送取貨LRP規(guī)劃和帶模糊時(shí)間窗的有容量約束的LRP；張震［8］研究了多商品同時(shí)送取貨選址路徑問(wèn)題。關(guān)于選址路徑及其擴(kuò)展問(wèn)題還有待進(jìn)一步研究。

LRP屬于NP-Hard問(wèn)題，精確算法可以求得最優(yōu)解，往往運(yùn)行時(shí)間長(zhǎng)，F(xiàn)arham等［6］使用分支切割方法求解了不同大小的客戶群體和潛在倉(cāng)庫(kù)的LRPSPD?，F(xiàn)研究中求解LRP大多采用啟發(fā)式方法逼近全局最優(yōu)解，在求解質(zhì)量和時(shí)間上均能達(dá)到滿意的效果。羅耀波等［7］設(shè)計(jì)改進(jìn)的自適應(yīng)遺傳算法用于求解多倉(cāng)庫(kù)選址路徑問(wèn)題（Multi-Depot Location Routing Problem， MDLRP）。張震［8］設(shè)計(jì)高效變鄰域搜索算法，對(duì)小規(guī)模算例求得最優(yōu)或近似最優(yōu)解，大規(guī)模算例求得滿意解，在求解質(zhì)量和時(shí)間上也證實(shí)比用CPLEX優(yōu)化軟件求解效果好。Setak等［9］將禁忌搜索和變鄰域搜索算法分別同時(shí)或先后進(jìn)行車(chē)輛路徑分配并比較兩種情況下的性能，結(jié)果表明在路徑容量受限的情況下同時(shí)進(jìn)行比先后順序具有優(yōu)勢(shì)，但在時(shí)間維度上沒(méi)有優(yōu)勢(shì)，同時(shí)進(jìn)行在生成非支配解方面也比先后順序更有效。Fan等［10］采用學(xué)習(xí)過(guò)程和路徑重連兩階段啟發(fā)式方法求解CLRP，并在合理的時(shí)間內(nèi)獲得了滿意的解。還有其他啟發(fā)式算法對(duì)求解LRP有待發(fā)掘。

根據(jù)現(xiàn)有文獻(xiàn)可知，已經(jīng)有大量文獻(xiàn)研究LRP的擴(kuò)展問(wèn)題，模型方面主要集中在單一選址路徑擴(kuò)展研究上，考慮同時(shí)送取貨的選址路徑問(wèn)題（LRPSPD）沒(méi)有考慮到客戶對(duì)時(shí)間的要求，考慮客戶時(shí)間窗的選址路徑問(wèn)題（LRPTW）又缺乏對(duì)取貨的需求。如今配送日益完善便捷，退換貨也更加有保障，所以現(xiàn)實(shí)規(guī)劃中需要全面考慮各種因素。本文考慮客戶對(duì)商品有退換貨、時(shí)效強(qiáng)的需求，即對(duì)帶時(shí)間窗的同時(shí)送取貨選址路徑問(wèn)題（Location-Routing Problem with Simultaneous Pickup and Delivery & Time Window， LRPSPDTW）加以研究。另外，既考慮同時(shí)送取貨又考慮時(shí)間窗的LRP，大多文獻(xiàn)是用成熟的遺傳算法來(lái)求解，用煙花算法求解的文獻(xiàn)相對(duì)欠缺，本文采用改進(jìn)煙花算法（Improved FireWorks Algorithm， IFWA）求解所提出的問(wèn)題，并通過(guò)實(shí)驗(yàn)證明在有效的時(shí)間內(nèi)可以提供較優(yōu)的解。

1 本文模型

1.1　行車(chē)策略選擇

一般LRP顧客只有送貨需求，由于退換貨便捷，考慮顧客同時(shí)有送貨和取貨兩種需求更符合生活實(shí)際，根據(jù)送取貨是否具有順序的要求可以將其分為3種行車(chē)策略：先送貨后取貨、混合送取貨和同時(shí)送取貨。先送貨后取貨限制取貨需求只能在所有顧客送貨需求滿足后才能開(kāi)始；混合送取貨則沒(méi)有先滿足送貨需求再取貨的限制，車(chē)輛可以任意順序選擇進(jìn)行送貨還是取貨，但每次只進(jìn)行單純的送貨或取貨；而同時(shí)送取貨可以滿足每個(gè)客戶點(diǎn)只需要被車(chē)輛訪問(wèn)一次，車(chē)輛在訪問(wèn)客戶點(diǎn)時(shí)一次性滿足客戶送貨和取貨兩種需求，有利于節(jié)省時(shí)間和運(yùn)輸成本。本文以同時(shí)送取貨作為行車(chē)策略，可以很好地達(dá)到降本增效的目的。

1.2　問(wèn)題描述與模型假設(shè)

物流作為企業(yè)第三利潤(rùn)源，在企業(yè)競(jìng)爭(zhēng)中有著舉足輕重的地位，提高配送效率和節(jié)約配送成本至關(guān)重要，配送回收中心的選址是決定配送好壞的關(guān)鍵因素?；趯?shí)際，本文研究的帶時(shí)間窗同時(shí)送取貨選址路徑問(wèn)題，其研究對(duì)象是由配送中心到顧客的供應(yīng)鏈的一級(jí)分銷(xiāo)網(wǎng)絡(luò)，有多個(gè)位置已知的客戶和候選倉(cāng)庫(kù)，要在倉(cāng)庫(kù)容量和車(chē)載量承受范圍內(nèi)為客戶提供配送回收服務(wù)，并規(guī)劃從倉(cāng)庫(kù)到客戶點(diǎn)的車(chē)輛行駛路線，在客戶可接受時(shí)間范圍內(nèi)滿足客戶需求使總成本最小?？蓪?duì)模型做如下假設(shè)：

1）各候選倉(cāng)庫(kù)點(diǎn)地理位置已知，客戶需求量和退貨量不超過(guò)倉(cāng)庫(kù)容量和車(chē)載量；

2）候選倉(cāng)庫(kù)建設(shè)成本、運(yùn)營(yíng)成本、倉(cāng)庫(kù)容量已知；

3）每輛車(chē)只服務(wù)一條回路，客戶配送回收需求一次性滿足；

4）車(chē)輛中心出發(fā)，滿足客戶時(shí)間要求，最后返回到配送中心。

1.3　符號(hào)說(shuō)明

集合

常量

決策變量

1.4　模型建立

式（1）表示物流總成本最小，其中包括配送回收中心建設(shè)成本、運(yùn)輸成本、車(chē)輛啟用成本，早到以及遲到的懲罰成本；式（2）［8］表示每個(gè)需求客戶點(diǎn)有且只能被訪問(wèn)一次；式（3）［8］表示路流平衡，即進(jìn)入該節(jié)點(diǎn)的流等于從該節(jié)點(diǎn)流出的流；式（4）表示一輛車(chē)只能在一條路徑中行駛一次：式（5）表示每個(gè)需求客戶點(diǎn)都指定由一個(gè)倉(cāng)庫(kù)設(shè)施為其提供配送服務(wù)；式（6）表示消除子回路；式（7）（8）分別表示送貨和取貨量不超過(guò)倉(cāng)庫(kù)的容量限制；式（9）表示裝卸平衡，車(chē)輛訪問(wèn)客戶點(diǎn)時(shí)所裝載貨物的量減去車(chē)輛訪問(wèn)客戶點(diǎn)時(shí)所裝載貨物的量等于車(chē)輛在客戶點(diǎn)時(shí)的送貨量加上在客戶點(diǎn)時(shí)的取貨量；式（10）表示車(chē)輛的裝載量不能超過(guò)車(chē)輛的容量限制；式（11）（12）是時(shí)間窗約束，式（11）表示配送車(chē)輛到達(dá)需求客戶點(diǎn)，如果早于需求客戶點(diǎn)的接受配送的開(kāi)始時(shí)間，則存在一個(gè)等待時(shí)間；如果在需求客戶點(diǎn)最早接受配送的時(shí)間之后，則等待時(shí)間為0；式（12）表示配送車(chē)輛到達(dá)需求客戶點(diǎn)的時(shí)間等于車(chē)輛到達(dá)上一個(gè)節(jié)點(diǎn)的時(shí)間加上車(chē)輛在點(diǎn)的服務(wù)時(shí)間加上從到的行駛時(shí)間加上在點(diǎn)的取貨和送貨時(shí)間；式（13）～（15）表示0-1決策變量。

2 煙花算法

煙花算法是由Tan［11］提出的一種新型群智能優(yōu)化算法。在該算法中，每個(gè)煙花都是解空間中的一個(gè)可行解，根據(jù)目標(biāo)函數(shù)計(jì)算煙花的適應(yīng)度值來(lái)確定煙花質(zhì)量的好壞，適應(yīng)度值大的煙花爆炸半徑小，產(chǎn)生火花多，具有強(qiáng)大的局部搜索性能；適應(yīng)度值小的煙花爆炸半徑大、火花少，具有全局搜索能力。煙花算法由4個(gè)部分組成：爆炸算子、變異算子、映射規(guī)則和選擇策略。

2.1　編碼方式

圖1　解的編碼表示

從前10個(gè)編碼可以看出開(kāi)放了倉(cāng)庫(kù)1、2和4。

倉(cāng)庫(kù)1：服務(wù)的客戶節(jié)點(diǎn)有6、7、10，車(chē)輛服務(wù)客戶點(diǎn)的次序?yàn)?0→7→6；

倉(cāng)庫(kù)2：服務(wù)的客戶節(jié)點(diǎn)有3、4、5、8，車(chē)輛服務(wù)客戶點(diǎn)的次序?yàn)?→8→4→5；

倉(cāng)庫(kù)4：服務(wù)的客戶節(jié)點(diǎn)有1、2、9，車(chē)輛服務(wù)客戶點(diǎn)的次序?yàn)?→2→1。

2.2　初始種群的生成

2.3　爆炸操作

2.3.1火花數(shù)和爆炸幅度

見(jiàn)到老鉗工，她心里針扎般的痛。過(guò)去，這是一家有名的國(guó)有企業(yè)，是濱湖人的驕傲?，F(xiàn)在一半職工拿六百塊錢(qián)生活費(fèi)在家待業(yè)。

2.3.2產(chǎn)生火花數(shù)

圖2　的火花產(chǎn)生過(guò)程

2.4　變異操作

在群智能啟發(fā)式算法中，種群多樣性至關(guān)重要，變異火花的引入可以增強(qiáng)種群多樣性，增強(qiáng)局部搜索能力，避免陷入局部最優(yōu)。在本文中，為解決離散問(wèn)題，變異過(guò)程使用4種搜尋機(jī)制：插入移動(dòng)、反轉(zhuǎn)移動(dòng)、單點(diǎn)變異和多點(diǎn)變異。前兩種移動(dòng)分別對(duì)倉(cāng)庫(kù)和路徑起作用，后兩種移動(dòng)只對(duì)倉(cāng)庫(kù)起作用。選擇每種移動(dòng)類(lèi)型的概率相等。

圖3　插入移動(dòng)

圖4　逆轉(zhuǎn)移動(dòng)

圖5　單點(diǎn)變異

圖6　多點(diǎn)變異

2.5　映射規(guī)則

爆炸操作和變異操作生成的火花可能是不可行的。在這個(gè)情況下，應(yīng)將其映射回可行的空間。任何產(chǎn)生不可行的火花應(yīng)再次編碼以確保其可行性。產(chǎn)生不可行火花的原因主要是以下兩種，通過(guò)消除這兩種情況，對(duì)不可行煙花進(jìn)行修正。

2.6　選擇策略

（21）

2.7　煙花算法求解模型約束處理

本文模型約束主要分為客戶、車(chē)、倉(cāng)庫(kù)三者間關(guān)系約束，流量約束、容量約束、載重約束、時(shí)間約束和決策變量約束。

式（2）是客戶與車(chē)和倉(cāng)庫(kù)三者間的關(guān)系約束，式（3）是流量約束；式（4）是車(chē)輛和倉(cāng)庫(kù)間的關(guān)系約束；式（5）是客戶與車(chē)輛之間的關(guān)系約束；式（6）是消除回路約束；式（7）（8）是倉(cāng)庫(kù)容量約束；式（9）是載重約束；式（10）是車(chē)容量約束；式（11）（12）是時(shí)間約束；式（13）～（15）是決策變量約束。這些約束一起作用會(huì)促使一個(gè)解的生成，生成解會(huì)明確包含客戶和倉(cāng)庫(kù)的歸屬關(guān)系，同一倉(cāng)庫(kù)下客戶點(diǎn)路徑的分配以及車(chē)輛的派遣。本文的煙花算法求解過(guò)程中，式（2）確定哪些客戶被分配給哪些倉(cāng)庫(kù)，起初客戶被隨機(jī)分配給倉(cāng)庫(kù)，通過(guò)式（7）（8）約束判斷是否超過(guò)倉(cāng)庫(kù)容量，決定是否在剩下的候選倉(cāng)庫(kù)中開(kāi)放新的倉(cāng)庫(kù)；對(duì)于開(kāi)放了的倉(cāng)庫(kù)，式（3）（6）（9）（11）（12）確定在同一開(kāi)放倉(cāng)庫(kù)中每條路徑上客戶點(diǎn)的分配，通過(guò)判別其是否超過(guò)車(chē)容量和違反客戶時(shí)間窗決定是否開(kāi)辟新的路徑；式（4）（5）（10）確定車(chē)輛的派遣；式（13）～（15）決定開(kāi)放哪些倉(cāng)庫(kù)，每個(gè)倉(cāng)庫(kù)派遣幾輛車(chē)，每輛車(chē)為哪些客戶提供服務(wù)。通過(guò)此種方式生成初始解，進(jìn)而生成初始種群，往往初始解不一定是最優(yōu)解，結(jié)合本文設(shè)計(jì)的煙花算法對(duì)倉(cāng)庫(kù)和路徑進(jìn)行交叉、變異等鄰域操作離散化迭代出最優(yōu)解。

2.8　算法步驟

改進(jìn)煙花算法（IFWA）求解帶時(shí)間窗的同時(shí)送取貨選址路徑問(wèn)題（IRPSPDTW）步驟如下：

步驟3 開(kāi)始迭代，基于設(shè)定的爆炸火花個(gè)數(shù)和半徑的參數(shù)值，根據(jù)適應(yīng)度值計(jì)算每個(gè)煙花的爆炸火花個(gè)數(shù)和半徑。

步驟4 對(duì)每個(gè)煙花進(jìn)行鄰域操作產(chǎn)生爆炸火花和變異火花，對(duì)產(chǎn)生的爆炸火花和變異火花進(jìn)行映射，將不滿足條件的火花映射回可行空間，更新個(gè)體。

步驟7 滿足算法終止條件，停止算法，輸出最優(yōu)解。

3 算例分析

為了驗(yàn)證模型的可行性和有效性，評(píng)估IFWA求解LRPSPDTW的性能，使用Matlab R2018b實(shí)現(xiàn)該算法，并在Windows 7系統(tǒng)下，在一臺(tái)配備2.7 GHz主頻處理器和4 GB內(nèi)存的PC上進(jìn)行了大量的數(shù)值實(shí)驗(yàn)。

3.1　算例測(cè)試

如表1所示，IFWA的平均誤差值為0.65%，小于B&C的0.98%。IFWA可以求得所有小規(guī)模算例（客戶<50）的最佳解決方案，只有在求解50-5-2b算例時(shí)IFWA的Gap值超過(guò)2%，其余算例的Gap值均小于2%。對(duì)求解小規(guī)模算例，B&C和IFWA都能在較短時(shí)間內(nèi)求得最優(yōu)解；B&C除了在求解50-5-2b算例時(shí)運(yùn)行時(shí)間小于20 min，其他大規(guī)模算例（客戶>50）都無(wú)法在4 h內(nèi)求得最優(yōu)解；而對(duì)于求解小于或等于100客戶的算例，IFWA都可以在小于100 s的時(shí)間內(nèi)求得最優(yōu)解。IFWA求解44個(gè)算例的平均運(yùn)行時(shí)間為271.51 s，可以看出，IFWA可以在較短的時(shí)間內(nèi)找到問(wèn)題的最優(yōu)解，尋優(yōu)能力更強(qiáng)、效率更高，由此可以驗(yàn)證IFWA的有效性。

表1　IFWA與B&C求解LRPSPD算例結(jié)果對(duì)比

3.2　參數(shù)靈敏度分析

較少的突變火花會(huì)增加獲得最優(yōu)解的難度，因?yàn)樗荒鼙３址N群的多樣性，或者很難跳出局部最優(yōu)解；然而，較多的突變火花則會(huì)產(chǎn)生更多相同的解。表4顯示了使用不同數(shù)量的突變火花的兩個(gè)測(cè)試實(shí)例20次運(yùn)行的平均結(jié)果。

表2　煙花數(shù)對(duì)解的影響

表3　參數(shù)M對(duì)解的影響

表4　參數(shù)S對(duì)解的影響

3.2.6參數(shù)組合

表5　參數(shù)對(duì)解的影響

表6　參數(shù)G對(duì)解的影響

圖7　參數(shù)靈敏度分析

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)煙花算法不能解決離散問(wèn)題，本文在煙花爆炸過(guò)程中引入重復(fù)交換移動(dòng)，在變異過(guò)程中設(shè)計(jì)4種搜尋機(jī)制，設(shè)計(jì)了IFWA，既開(kāi)發(fā)了全局搜索能力，提高解的質(zhì)量，也保證了火花的多樣性。通過(guò)和B&C在44個(gè)基準(zhǔn)LRPSPD算例上對(duì)比分析，結(jié)果表明，本文設(shè)計(jì)的IFWA在求解質(zhì)量和效率上都能達(dá)到令人滿意的效果。在后續(xù)工作中，會(huì)探討改進(jìn)煙花算法對(duì)包含客戶滿意度的多目標(biāo)模型的求解以及考慮多種商品的模型的求解。

（

）

[1] BENOTMANE Z， BELALEM G， NEKI A. Green optimisation for LRP problem using a genetic algorithm and a dynamic island model［J］. International Journal of Advanced Operations Management， 2019， 11（1/2）：46-68.

[2] FAZAYELI S， EYDI A， NAKHAI KAMALABADI I. Location-routing problem in multimodal transportation network with time windows and fuzzy demands： presenting a two-part genetic algorithm［J］. Computers and Industrial Engineering， 2018， 119：233-246.

[3] ZHAO Y W， LENG L L， ZHANG C M. A novel framework of hyper-heuristic approach and its application in location-routing problem with simultaneous pickup and delivery［J］. Operational Research， 2021， 21（2）：1299-1332.

[4] WANG X F， YANG F， LU D W. Multi-objective location-routing problem with simultaneous pickup and delivery for urban distribution［J］. Journal of Intelligent and Fuzzy Systems， 2018， 35（4）：3987-4000.

[5] OUDOUAR F， LAZAAR M， EL MILOUD Z. A novel approach based on heuristics and a neural network to solve a capacitated location routing problem［J］. Simulation Modelling Practice and Theory， 2020， 100： No.102064.

[6] FARHAM M S， SüRAL H， IYIGUN C. A column generation approach for the location-routing problem with time windows［J］. Computers and Operations Research， 2018， 90：249-263.

[7] 羅耀波，孫延明，廖鵬. 帶退貨和軟時(shí)間窗的多倉(cāng)庫(kù)選址-路徑問(wèn)題研究［J］. 運(yùn)籌與管理， 2014， 23（5）：78-85.（LUO Y B， SUN Y M， LIAO P. Research on multi-depot location routing problem with backhauls and soft time windows［J］. Operations Research and Management， 2014， 23（5）： 78-85.）

[8] 張震. 多商品多來(lái)源閉環(huán)選址-庫(kù)存-路徑問(wèn)題模型與算法研究［D］.武漢：華中師范大學(xué)， 2018：34-37.（ZHANG Z. Research on model and algorithm for the multi-commodity and multi-source closed-loop location-inventory-routing problem［D］. Wuhan： Central China Normal University， 2018： 34-37.）

[9] SETAK M， SADEGHI-DASTAKI M， KARIMI H. The multi-route location-routing problem and zone price decision-making using a tabu and variable neighborhood search algorithm［J］. Journal of Industrial and Production Engineering， 2018， 35（5）：277-297.

[10] FAN H M， WU J X， LI X， et al. Presenting a multi-start hybrid heuristic for solving the problem of Two-Echelon Location-Routing Problem with Simultaneous Pickup and Delivery （2E-LRPSPD）［J］. Journal of Advanced Transportation， 2020， 2020： No.9743841.

[11] TAN Y. Fireworks Algorithm： A Novel Swarm Intelligence Optimization Method［M］. Berlin： Springer， 2015：31-42.

[12] PRINS C， PRODHON C， CALVO R W. Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking［J］. 4OR — A Quarterly Journal of Operations Research， 2006， 4（3）：221-238.

[13] SALHI S， NAGY G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling［J］. Journal of the Operational Research Society， 1999， 50（10）：1034-1042.

[14] KARAOGLAN I， ALTIPARMAK F， KARA I， et al. A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery［J］. European Journal of Operational Research， 2011， 211（2）：318-332.

[15] RAHMANI Y， CHERIF-KHETTAF W R， OULAMARA A. The two-echelon multi-products location-routing problem with pickup and delivery： formulation and heuristic approaches［J］. International Journal of Production Research， 2016， 54（4）：999-1019.

[16] TAIDI Z， BENAMEUR L， CHENTOUFI J A. A fireworks algorithm for solving travelling salesman problem［J］. International Journal of Computational Systems Engineering， 2017， 3（3）：157-162.

[17] FERREIRA K M， DE QUEIROZ T A. Two effective simulated annealing algorithms for the location-routing problem［J］. Applied Soft Computing， 2018， 70：389-422.

[18] FERDI I， LAYEB A. A GRASP algorithm based new heuristic for the capacitated location routing problem［J］. Journal of Experimental and Theoretical Artificial Intelligence， 2018， 30（3）：369-387.

[19] 黃凱明，盧才武，連民杰. 三層級(jí)設(shè)施選址-路徑規(guī)劃問(wèn)題建模及算法研究［J］. 系統(tǒng)工程理論與實(shí)踐， 2018， 38（3）：743-754.（HUANG K M， LU C W， LIAN M J. Research on modeling and algorithm for three-echelon location-routing problem［J］. Systems Engineering — Theory and Practice， 2018， 38（3）： 743-754.）

[20] DARVISH M， ARCHETTI C， COELHO L C， et al. Flexible two-echelon location routing problem［J］. European Journal of Operational Research， 2019， 277（3）：1124-1136.

[21] 陳庭貴，琚春華. 多干擾的資源約束項(xiàng)目調(diào)度問(wèn)題［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2012， 18（11）：2409-2418.（CHEN T G， JU C H. Resource-constrained project scheduling problem with multi-factor disruptions［J］. Computer Integrated Manufacturing Systems， 2012， 18（11）： 2409-2418.）

[22] 陳庭貴，楊俊蓉. 網(wǎng)絡(luò)群體極化現(xiàn)象的形成機(jī)理及仿真實(shí)驗(yàn)研究［J］. 重慶科技學(xué)院學(xué)報(bào)（自然科學(xué)版）， 2019， 21（1）：108-113.（CHEN T G， YANG J R. Research on formation mechanism and simulation experiment of network group polarization［J］. Journal of Chongqing University of Science and Technology （Natural Science Edition）， 2019， 21（1）： 108-113.）

LIU Yaping， born in 1997， M. S. candidate. Her research interests include intelligent optimization.

ZHANG Huizhen， born in 1979， Ph. D.， associate professor. Her research interests include operations research， intelligent optimization.

ZHANG Li，born in 1995， M. S. candidate. Her research interests include intelligent optimization.

LIU Youyou， born in 1999. Her research interests include information management， intelligent optimization.

Fireworks algorithm for location-routing problem of simultaneous pickup and delivery with time window

LIU Yaping， ZHANG Huizhen*， ZHANG Li， LIU Youyou

（，，200093，）

With the rapid development of e-commerce and the popularity of the Internet， it is more convenient to exchange and return goods. Therefore， the customers’ demands for goods show the characteristics of timeliness， variety， small batch， exchanging and returning. Aiming at Location-Routing Problem with Simultaneous Pickup and Delivery （LRPSPD） with capacity and considering the characteristics of customers’ diversified demands， a mathematical model of LRPSPD & Time Window （LRPSPDTW） was established. Improved FireWorks Algorithm （IFWA） was used to solve the model， and the corresponding neighborhood operations were carried out for the fireworks explosion and mutation. The performance of the fireworks algorithm was evaluated with some benchmark LRPSPD examples. The correctness and effectiveness of the proposed model and algorithm were verified by a large number of numerical experiments. Experimental results show that compared with Branch and Cut algorithm （B&C）， the average error between the result of IFWA and the standard solution is reduced by 0.33 percentage points. The proposed algorithm shortens the time to find the optimal solution， and provides a new way of thinking for solving location-routing problems.

time window; simultaneous pickup and delivery; location-routing; FireWorks Algorithm （FWA）; neighborhood operation

TP391.9

A

1001-9081（2022）07-2292-09

10.11772/j.issn.1001-9081.2021040697

2021?04?30；

2021?07?16；

2021?07?20。

劉亞平（1997—），女，江西九江人，碩士研究生，主要研究方向：智能優(yōu)化； 張惠珍（1979—），女，山西忻州人，副教授，博士，主要研究方向：運(yùn)籌學(xué)、智能優(yōu)化； 張莉（1995—），女，湖北荊州人，碩士研究生，主要研究方向：智能優(yōu)化； 劉優(yōu)優(yōu)（1999—），女，湖南岳陽(yáng)人，主要研究方向：信息管理、智能優(yōu)化。