帶時間窗同時送取貨選址路徑問題及其煙花算法求解

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

帶時間窗同時送取貨選址路徑問題及其煙花算法求解

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

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

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

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

0 引言

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

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

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

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

1 本文模型

1.1　行車策略選擇

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

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

物流作為企業(yè)第三利潤源，在企業(yè)競爭中有著舉足輕重的地位，提高配送效率和節(jié)約配送成本至關(guān)重要，配送回收中心的選址是決定配送好壞的關(guān)鍵因素。基于實際，本文研究的帶時間窗同時送取貨選址路徑問題，其研究對象是由配送中心到顧客的供應(yīng)鏈的一級分銷網(wǎng)絡(luò)，有多個位置已知的客戶和候選倉庫，要在倉庫容量和車載量承受范圍內(nèi)為客戶提供配送回收服務(wù)，并規(guī)劃從倉庫到客戶點的車輛行駛路線，在客戶可接受時間范圍內(nèi)滿足客戶需求使總成本最小?？蓪δＰ妥鋈缦录僭O(shè)：

1）各候選倉庫點地理位置已知，客戶需求量和退貨量不超過倉庫容量和車載量；

2）候選倉庫建設(shè)成本、運營成本、倉庫容量已知；

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

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

1.3　符號說明

集合

常量

決策變量

1.4　模型建立

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

2 煙花算法

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

2.1　編碼方式

圖1　解的編碼表示

從前10個編碼可以看出開放了倉庫1、2和4。

倉庫1：服務(wù)的客戶節(jié)點有6、7、10，車輛服務(wù)客戶點的次序為10→7→6；

倉庫2：服務(wù)的客戶節(jié)點有3、4、5、8，車輛服務(wù)客戶點的次序為3→8→4→5；

倉庫4：服務(wù)的客戶節(jié)點有1、2、9，車輛服務(wù)客戶點的次序為9→2→1。

2.2　初始種群的生成

2.3　爆炸操作

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

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

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

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

2.4　變異操作

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

圖3　插入移動

圖4　逆轉(zhuǎn)移動

圖5　單點變異

圖6　多點變異

2.5　映射規(guī)則

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

2.6　選擇策略

（21）

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

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

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

2.8　算法步驟

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

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

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

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

3 算例分析

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

3.1　算例測試

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

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

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

較少的突變火花會增加獲得最優(yōu)解的難度，因為它不能保持種群的多樣性，或者很難跳出局部最優(yōu)解；然而，較多的突變火花則會產(chǎn)生更多相同的解。表4顯示了使用不同數(shù)量的突變火花的兩個測試實例20次運行的平均結(jié)果。

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

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

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

3.2.6參數(shù)組合

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

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

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

4 結(jié)語

針對傳統(tǒng)煙花算法不能解決離散問題，本文在煙花爆炸過程中引入重復(fù)交換移動，在變異過程中設(shè)計4種搜尋機(jī)制，設(shè)計了IFWA，既開發(fā)了全局搜索能力，提高解的質(zhì)量，也保證了火花的多樣性。通過和B&C在44個基準(zhǔn)LRPSPD算例上對比分析，結(jié)果表明，本文設(shè)計的IFWA在求解質(zhì)量和效率上都能達(dá)到令人滿意的效果。在后續(xù)工作中，會探討改進(jìn)煙花算法對包含客戶滿意度的多目標(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] 羅耀波，孫延明，廖鵬. 帶退貨和軟時間窗的多倉庫選址-路徑問題研究［J］. 運籌與管理， 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] 張震. 多商品多來源閉環(huá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] 黃凱明，盧才武，連民杰. 三層級設(shè)施選址-路徑規(guī)劃問題建模及算法研究［J］. 系統(tǒng)工程理論與實踐， 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] 陳庭貴，琚春華. 多干擾的資源約束項目調(diào)度問題［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ī)理及仿真實驗研究［J］. 重慶科技學(xué)院學(xué)報（自然科學(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—），女，山西忻州人，副教授，博士，主要研究方向：運籌學(xué)、智能優(yōu)化； 張莉（1995—），女，湖北荊州人，碩士研究生，主要研究方向：智能優(yōu)化； 劉優(yōu)優(yōu)（1999—），女，湖南岳陽人，主要研究方向：信息管理、智能優(yōu)化。