卞俊麗 張惠珍 劉冬 楊健豪

文章編號：1002-3100（2024）03-0006-06

摘? 要：針對同時送取貨的選址路徑問題（Location-routing Problem with Simultaneous Pickup and Delivery，LRPSPD），設(shè)計一種改進煙花算法（Improved Firework Algorithm，IFWA）求解。首先，考慮倉庫建設(shè)、車輛啟用、車輛路徑等成本因素，建立最小成本的LRPSPD模型，該模型強調(diào)需求點的送貨需求和取貨需求只能由一輛車同時進行服務(wù)。其次，設(shè)計一種改進煙花算法，該算法結(jié)合貪心聚類算法生成初始解，由煙花爆炸算子操作生成鄰域解，利用變異操作協(xié)助產(chǎn)生新種群。最后，通過使用混合免疫算法、模擬退火算法求解相同算例，對結(jié)果進行分析比較，驗證模型的可行性和改進算法的有效性。

關(guān)鍵詞：選址路徑；同時送取貨；改進煙花算法；貪心聚類；變異操作

中圖分類號：F253? ? 文獻標(biāo)志碼：A? ? DOI：10.13714/j.cnki.1002-3100.2024.03.002

Abstract： This paper studied the location-routing problem with simultaneous pickup and delivery（LRPSPD）and designed an improved fireworks algorithm（IFWA）to solve the problem. Firstly， a LRPSPD model of minimizing warehouse construction cost， vehicle using cost and vehicle routing cost was build. The model emphasized customers' delivery and pickup needs should be served by one same vehicle. Secondly， an improved firework algorithm（IFWA）was designed to solve the model. The IFWA generated initial solutions via combining greedy clustering algorithm， produced neighborhood solutions by firework explosion operator operations， and created new populations through mutation operations. Finally， a mixed immune algorithm and simulated annealing algorithm were used to solve the same cases respectively， and the results are verified the feasibility of the model and effectiveness of the IFWA.

Key words： location-routing problem; simultaneous pickup and delivery; firework algorithm; greedy clustering; mutation operation

0? 引? 言

選址決策與路徑?jīng)Q策是物流供應(yīng)鏈中兩個相互依賴的關(guān)鍵問題，對公司的運營有著重要的影響。選址-路徑問題（Location-routing problem， LRP）一直是當(dāng)前物流供應(yīng)鏈以及運籌學(xué)優(yōu)化的研究熱點。眾多學(xué)者將LRP問題與實際情況結(jié)合起來，提出拓展的LRP問題，比如有容量選址路徑問題（Capacitated LRP， CLRP）^[1]、低碳選址路徑問題（Low-Carbon LRP， LCLRP）^[2]、同時送取貨選址路徑問題（LRP with Simultaneous Pickup and Delivery， LRPSPD）^[3]等。

在現(xiàn)代物流中，對于存在多級加工廠和供應(yīng)鏈的企業(yè)來說，同時送取貨的物流配送模式更加貼合實際情況，因此，LRPSPD也逐漸成為國內(nèi)外眾多學(xué)者研究的熱點課題。Khodashenas等^[4]提出了需求和成本參數(shù)不確定的兩階段LRPSPD問題，并使用NSGA-II和MOLAO算法對其進行求解。Dehghan等^[5]研究了在中斷風(fēng)險狀態(tài)下的同時送取貨問題，并設(shè)計三種元啟發(fā)式算法進行求解，并研究其算法性能。Yilmaz等^[6]研究了可變鄰域搜索算法求解電動車同時送取貨問題。張穎鈺等^[7]研究了帶時間窗的多中心半開放式VRPSDP問題研究，并設(shè)計混沌變異頭腦風(fēng)暴算法來求解。李珺等^[8]提出基于模擬退火與自適應(yīng)大規(guī)模鄰域搜索相結(jié)合的混合優(yōu)化算法研究同時送取貨車輛路徑問題。陳其賽和倪靜^[9]提出了同時送取貨電動車選址路徑問題并用混合模擬退火-蟻群優(yōu)化算法求解該問題。

針對LRPSPD問題，大部分學(xué)者都是將需求點的送貨需求和取貨需求分開計算，并派出相應(yīng)的送貨和派送車輛來滿足需求點的不同需求，存在如下問題：（1）資源浪費，如車輛送貨回程時空車，取車時空車，造成空車裝載資源閑置等；（2）路徑不合理，如需要兩輛車分別服務(wù)需求點的取貨需求和送貨需求，且兩輛車的行駛路徑重復(fù)。以上問題極大地增加了物流成本。本文通過改進傳統(tǒng)的LRPSPD模型，將送貨和取貨需求同時考慮進車輛負(fù)載中，并根據(jù)車輛負(fù)載的動態(tài)變化選擇合適的需求點進行分配，防止因車輛容量問題導(dǎo)致需求點服務(wù)損失。此外，提出一種求解LRPSPD問題的煙花算法，采用爆炸算子對煙花進行操作，生成一定數(shù)量的火花，利用變異操作隨機對火花進行操作，在增加種群多樣性的同時探索更好的解決方案。本文對算法的參數(shù)設(shè)置上采取Taguchi試驗設(shè)計方法確定參數(shù)組合，并通過AM分離法改進Pordhon標(biāo)準(zhǔn)數(shù)據(jù)庫獲取算例。最后將本文算法，模擬退火算法和混合免疫算法對算例分別求解，驗證所提算法的有效性。

1? 同時送取貨選址路徑問題（LRPSPD）

1.1? LRPSPD問題描述與模型假設(shè)

本文研究的LRPSPD模型可以描述如下：在物流網(wǎng)絡(luò)中存在多個倉庫候選點和需求點，且需求點同時具有送取貨需求，車輛從其所屬倉庫出發(fā)，為其分配的需求點一次性提供先送貨，再取貨的服務(wù)。該模型需要確定倉位的選址，車輛數(shù)量和車輛對其分配需求點的服務(wù)路線。

本文基于如下假設(shè)構(gòu)建模型：（1）每個需求點只能接受一個倉庫和一輛車服務(wù)，且其服務(wù)容量須滿足需求點的需求量；（2）任意兩個倉庫之間相互獨立，沒有車輛來往；（3）所有車輛提供服務(wù)后須返回其出發(fā)倉庫；（4）所有車輛為同一類型。

1.2? 模型構(gòu)建

以往文獻大多是分別計算取貨和送貨需求，并派出相應(yīng)的取貨和送貨車輛來滿足需求量的不同，這樣操作不僅復(fù)雜，而且還易造成資源浪費和行駛路徑重復(fù)，極大地增加了物流成本。因此，本文統(tǒng)一計算需求量的送貨與取貨，并將其與車輛的實時負(fù)載能力聯(lián)系起來，共同構(gòu)成車輛的負(fù)載約束。這樣，該路線的車輛同時進行提貨和送貨業(yè)務(wù)，滿足每個需求點的兩種需求，并根據(jù)車輛的負(fù)載分配合適的需求點，確保滿足每一個需求點的需求，從而避免了車輛的空載發(fā)生和運輸路線的復(fù)制。

1.2.1? 模型參數(shù)說明

模型中所使用的參數(shù)變量定義如下：

1.2.2? 模型建立

目標(biāo)函數(shù)（1）表示總成本最小化，其中第一部分是倉庫的選址成本，第二部分是車輛的啟動成本，第三部分是運輸路徑成本；約束條件（2）和（3）表示被選中的倉庫服務(wù)容量不得小于需求點的送取貨需求量；約束條件（4）和（5）表示車輛的服務(wù)容量不得小于需求點的送取貨需求；約束條件（6）和（7）表示節(jié)點的負(fù)載能力；約束條件（8）和（9）表示每個需求點只有一輛車和一個倉庫可以為其提供服務(wù)；約束條件（10）表示每輛車最多只能被使用一次；約束條件（11）表示任意兩個倉庫之間相互獨立，沒有車輛來往；約束條件（12）表示節(jié)點的流量平衡；約束條件（13）表示消除子回路；約束條件（14）表示只有當(dāng)需求點被分配到倉庫時，才能接受服務(wù)；約束條件（15）～（18）表示變量之間的關(guān)系；約束條件（19）表示決策變量的取值范圍。

2? 求解LRPSPD的改進煙花算法

煙花算法是由Tan等^[10]在2010年提出的一種優(yōu)化算法。該算法將一定范圍的爆炸區(qū)域視作搜索空間，每個煙花都代表一個可行解，根據(jù)煙花的適應(yīng)度值進行迭代。適應(yīng)度高的煙花質(zhì)量好，爆炸半徑小，生成的火花數(shù)量多，局部搜索能力強；適應(yīng)度低的煙花質(zhì)量相對差一些，其爆炸半徑大，具有更好的全局搜索能力^[11]。煙花算法計算原理簡便，且全局尋優(yōu)能力較強^[12]。因此，本文設(shè)計一種改進的煙花算法來求解LRPSPD問題。

針對LRPSPD模型的具體特點，本文將煙花算法與貪心聚類算法和鄰域搜索相結(jié)合，設(shè)計了一種改進的的煙花算法。首先，在初始解的生成部分參考貪心聚類思想，提高初始解的質(zhì)量。其次，使用煙花算法生成火花，使用變異操作變異部分煙花。最后，使用選擇策略來選擇較好的個體迭代為新的煙花。

本文設(shè)計的煙花算法主要由四個部分組成：（1）初始化：采用貪婪策略對需求點進行聚類和劃分，然后根據(jù)每個集群的中心分配倉庫和車輛，并形成派送路徑；（2）爆炸算子：根據(jù)爆炸強度和爆炸幅度將煙花引爆，產(chǎn)生火花。本文利用變異操作生成新的火花個體，擴大可行解的范圍。所采用的變異操作主要包括：交換、插入、逆轉(zhuǎn)和單點變異；（3）選擇策略：選擇優(yōu)秀的火花個體作為新的煙花進行迭代，不斷優(yōu)化煙花種群；（4）接受機制：以一定的概率接受一個好的解，從而跳出局部最優(yōu)。

算法中涉及到的解的編碼、初始解的生成和變異操作介紹如下：

2.1? 解的編碼

同時送取貨選址路徑問題可以形成長度為2n的解，解的構(gòu)成主要分成兩部分。1，…，n部分代表需求點和倉庫點的分配關(guān)系，n+1，…，2n部分代表需求點的被服務(wù)次序，假設(shè)有4個候選倉庫點，10個需求點，則解的長度為20，圖1給出了一個可行解。

由圖1中1，…，n部分可知，4個倉庫中4號倉庫未開放，10個需求點被分配到剩下3個倉庫中，需求點與倉庫的所屬關(guān)系如下（需求點編號→倉庫編號）：1，3，8，10→3；4，7，9→2；2，5，6→1；由n+1，…，2n部分可知每個倉庫服務(wù)需求點的順序，例如3號倉庫服務(wù)的需求點為1，3，8，10。1號需求點的被服務(wù)次序為第10個，3號需求點為第6個，8號需求點為第1個10號需求點為第9個，因此，3號倉庫所服務(wù)的需求點的次序為8→3→10→1。

2.2? 初始解的生成

對于初始解的生成，本文受貪心聚類的啟發(fā)，采用需求點分塊、倉庫指派和掃描路徑三段式生成策略，具體如下：

（1）根據(jù)車輛的容量、需求點的送取貨需求和需求點間的距離，將需求點分塊。第一步，隨機選擇需求點ka。第二步，在車輛容量的約束下選擇距離最近的需求點kb，并從需求點索引中刪除需求點ka和kb。第三步，從剩下需求點中選擇離kb最近的需求點kc，并判斷車輛的容量約束是否被超出。如果不被超出，則將kc加入當(dāng)前區(qū)塊，否則，該需求點不被該車輛考慮。直到所有需求點都被分塊，記錄需求點的分塊計數(shù)。

（2）每個細(xì)分的需求點群體被拉入一個超等需求點。具體操作方法是用公式（20）計算每個需求點分塊的重心，用該重心作為超等需求點的坐標(biāo)，然后用公式（21）計算每個倉庫到每個超等需求點的距離之和，在滿足倉庫容量的前提下分配超等需求點，確定需求點和倉庫的所有權(quán)。

（3）對每個倉庫所服務(wù)的需求點通過掃描法形成派送路線。掃描法是指用極坐標(biāo)表示倉庫及其指定需求點的位置，然后以任意一點為起點，設(shè)置其角度為零度，以車輛容量為限，順時針方向掃描需求點，形成一個序列的需求點，直到掃描完所有需求點，并生成倉庫的配送路線方案。

2.3? 變異操作

設(shè)計的變異操作主要包括交換、插入、反轉(zhuǎn)和單點變異。通過變異操作生成爆炸火花和變異火花，可以在增加種群多樣性的同時探索更好的解決方案。

2.3.1? 交? 換

隨機選擇一個解的1，…，n部分，從中隨機選擇兩個位置，交換其序列號。例如：圖2中2號和10號是選中的位置，通過交換他們所屬的倉庫，可以生成一個新的解決方案。

2.3.2? 插? 入

隨機選擇一個解的1，…，n部分，隨機選擇兩個位置，將第二個位置的序號插入到第一個位置上，依次更替序號。例如：圖3中選擇10號需求點，插入到2號需求點的位置，插入點為2號需求點。10號需求點的所屬倉庫從3號變成了2號，2～9號需求點的所屬倉庫也相應(yīng)變化。

2.3.3? 逆? 轉(zhuǎn)

隨機選擇一個解的1，…，n部分，從中隨機選擇兩個位置，將這兩個位置的序號倒序插入。例如：圖4中選擇2號和10號這兩個需求點，將它們和它們之間的需求點倒序插入。

2.3.4? 單點變異

隨機選擇一個解的1，…，n部分，從中隨機選擇一個位置，隨機生成新的倉庫為其提供服務(wù)。例如：圖5中紅色標(biāo)注的是2號需求點，變異之后，2號需求點便由2號倉庫對其進行服務(wù)。

2.4? 算法步驟

改進的煙花算法解決同時送取貨問題的步驟如下：

Step1：確定算法的各種控制參數(shù)，包括初始種群數(shù)Nq、迭代次數(shù)D、爆炸火花數(shù)Mp和煙花爆炸半徑參數(shù)R等；

Step2：結(jié)合貪心聚類策略生成初始種群Nq，計算每個煙花的適應(yīng)度值，記錄當(dāng)前最優(yōu)解；

Step3：開始迭代，根據(jù)相關(guān)控制參數(shù)，利用適應(yīng)度值計算煙花的爆炸火花數(shù)和爆炸半徑；

Step4：對煙花種群進行變異操作（交換，插入，逆轉(zhuǎn)，單點變異），生成爆炸火花，將生成的爆炸火花中不滿足條件的火花映射回可行空間，更新個體；

Step5：對于由爆炸火花和當(dāng)前煙花組成的新候選種群，根據(jù)選擇策略選擇新的種群；

Step6：判斷當(dāng)前迭代次數(shù)是否滿足最大迭代次數(shù)，如果滿足，執(zhí)行Step7，否則，返回Step3；

Step7：滿足終止條件，停止算法并輸出結(jié)果。

3? 算例對比與結(jié)果分析

為了驗證改進煙花算法求解LRPSPD模型的有效性，仿照文獻^[13]中的測試數(shù)據(jù)，生成8-2（8個需求點，2個候選倉庫）和15-5（15個需求點，5個候選倉庫）兩組數(shù)據(jù)，并采用AM分離法^[14]生成需求點送取貨需求，相關(guān)數(shù)據(jù)見表1。

3.1? 算例參數(shù)設(shè)置

設(shè)置IFWA的相關(guān)參數(shù)，利用IFWA針對CLRP的Prodhon算例求解，設(shè)定種群數(shù)目M為50。其他影響著算法性能的重要參數(shù)有煙花數(shù)Nq、爆炸火花數(shù)Mp、最大半徑參數(shù)R、突變火花數(shù)Mq和迭代次數(shù)D等。利用Taguchi試驗的設(shè)計方法（Design of Experiment，DOE）^[15]對此類參數(shù)進行靈敏度分析。構(gòu)建正交試驗表L16對50-5-1算例求解，給出每個參數(shù)的4個合理水平值。將每個參數(shù)獨立運行20次，參數(shù)的水平、正交表和AVG統(tǒng)計以及參數(shù)響應(yīng)值數(shù)據(jù)如表2至表4所示。

由表4可以看出，爆炸火花數(shù)Mp的范圍最大，說明爆炸算子在解集中的運算對算法性能的影響最大。迭代次數(shù)D對1.5n（n為需求點數(shù)）次后算法的收斂性影響不大。此時種群趨于最優(yōu)解，群體中個體值接近一致，算法呈現(xiàn)收斂狀態(tài)。當(dāng)參數(shù)Mq為2n時，更有利于算法的收斂。綜合考慮，推薦的參數(shù)值為Nq=2n，Mp=2n，R=0.5n，Mq=2n，D=1.5n。

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

實驗所用硬件環(huán)境為Intel（R）Core（TM）i5-8250U CPU@1.60GHz，8GB內(nèi)存，64位Windows10操作系統(tǒng)，使用MatlabR2020a進行編程。實驗得到兩組算例的求解結(jié)果如表5所示。

由表5可知，改進的煙花算法可以在較短的時間內(nèi)獲得相對于精確算法的較好解?？傮w而言，CPLEX的結(jié)果不僅驗證了模型的準(zhǔn)確性，而且證實了算法的有效性。為了更好地驗證算法的求解效率，文章對CLRP標(biāo)準(zhǔn)算例庫中的Prodhon算例進行改進以適應(yīng)模型的求解，并采用本文算法（IFWA）、混合免疫算法^[16]和模擬退火算法^[17]等3種算法求解。每個例子求解20次，記錄最優(yōu)解和運行時間，求解結(jié)果如表6所示。

由表6可知，改進煙花算法和混合免疫算法結(jié)果對比，雖然混合免疫算法在運行時間上稍優(yōu)，但是總成本均劣于利用改進煙花算法求解的結(jié)果。改進煙花算法和模擬退火算法結(jié)果對比，在運行時間方面，改進煙花算法全面占優(yōu)；在總成本方面，除了Gaskell67-29x5外，其余7個算例利用改進煙花算法求解結(jié)果均明顯優(yōu)于模擬退火算法。

4? 結(jié)? 論

本文研究同時送取貨選址路徑問題，一方面，在需求點有同時取貨和送貨需求的情況下，根據(jù)需求點分布，合理選擇倉庫設(shè)施；另一方面，根據(jù)車輛容量和最大行駛距離調(diào)度車輛，有效規(guī)劃行駛路線，減少資源浪費，降低配送成本。文章將煙花算法與貪心聚類和鄰域搜索相結(jié)合，設(shè)計了一種求解LRPSPD的改進煙花算法，并與模擬退火算法和混合免疫優(yōu)化算法對比，結(jié)果表明該算法在運行時間和解的質(zhì)量上均有明顯提升。文章所構(gòu)建模型和設(shè)計算法可為相關(guān)決策者對物流網(wǎng)絡(luò)的優(yōu)化提供有效參考。

參考文獻：

[1]? AKPUNAR ？魻 S， AKPINAR S. A hybrid adaptive large neighbourhood search algorithm for the capacitated location routing problem[J]. Expert Systems with Applications， 2021，168：114304.

[2] 張坤，張惠珍，馬良，等. 分布估計灰狼算法求解低碳選址路徑問題[J/OL]. 系統(tǒng)管理學(xué)報：1-16[2023-03-22]. https：//kns-cnki-net.webvpn.usst.edu.cn/kcms/detail/31.1977.n.20221021.1055.002.html.

[3]? WANG X. Research on hybrid immune algorithm for solving the location-routing problem with simultaneous pickup and delivery[J]. Journal of Cases on Information Technology （JCIT）， 2022，24（5）：1-17.

[4]? KHODASHENAS M， KAZEMIPOOR H， NAJAFI S E， et al. A two-stage uncertain model to arrange and locate vehicle routing with simultaneous pickup and delivery[J]. International Journal of Research in Industrial Engineering， 2022，11（3）：273-305.

[5]? DEHGHAN M， HEJAZI S R， KARIMI-MAMAGHAN M， et al. Capacitated location routing problem with simultaneous pickup and delivery under the risk of disruption[J]. RAIRO-Operations Research， 2021，55（3）：1371-1399.

[6]? YILMAZ Y， KALAYCI C B. Variable neighborhood search algorithms to solve the electric vehicle routing problem with simultaneous pickup and delivery[J]. Mathematics， 2022，10（17）：3108.

[7] 張穎鈺，吳立云，賈勝鈦. 帶時間窗的多中心半開放式VRPSDP問題研究[J/OL]. 系統(tǒng)仿真學(xué)報：1-12[2023-03-27]. https：//doi.org/10.16182/j.issn1004731x.joss.22-0727.

[8] 李珺，段鈺蓉，郝麗艷，等. 混合優(yōu)化算法求解同時送取貨車輛路徑問題[J]. 計算機科學(xué)與探索，2022，16（7）：1623-1632.

[9] 陳其賽，倪靜. 基于同時送取貨電動車選址路徑問題優(yōu)化研究[J]. 上海理工大學(xué)學(xué)報，2021，43（5）：515-522.

[10]? TAN Y， ZHU Y. Fireworks algorithm for optimization[C] // International Conference in Swarm Intelligence， 2010：355-364.

[11] 馬創(chuàng)濤，邵景峰. 煙花算法改進BP神經(jīng)網(wǎng)絡(luò)預(yù)測模型及其應(yīng)用[J]. 控制工程，2020，27（8）：1324-1331.

[12] 聶浩程. 生鮮農(nóng)產(chǎn)品冷鏈物流配送網(wǎng)絡(luò)優(yōu)化研究[D]. 杭州：浙江理工大學(xué)，2022.

[13]? YU V F， LIN S Y. Solving the location-routing problem with simultaneous pickup and delivery by simulated annealing[J]. International Journal of Production Research， 2016，54（2）：526-549.

[14] 劉冬，張惠珍，劉亞平，等. 改進蘑菇算法與開放式送取貨選址路徑問題[J/OL]. 控制工程：1-12[2023-03-27]. https：//doi.org/10.14107/j.cnki.kzgc.20210630.

[15]? ZHANG B， PAN Q， GAO L， et al. An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming[J]. Applied Soft Computing， 2017，52：14-27.

[16]? QIAO J， LI F， YANG S， et al. An adaptive hybrid evolutionary immune multi-objective algorithm based on uniform distribution selection[J]. Information Sciences， 2020，512：446-470.

[17]? VINCENT F Y， LIN S Y. A simulated annealing heuristic for the open location-routing problem[J]. Computers & Operations Research， 2015，62：184-196.

收稿日期：2023-03-28

基金項目：國家自然科學(xué)基金項目（72101149）；教育部人文社會科學(xué)基金項目（21YJC630087）

作者簡介：卞俊麗（1989—），女，江蘇鹽城人，上海理工大學(xué)管理學(xué)院碩士研究生，研究方向：智能優(yōu)化；張惠珍（1979—），女，山西忻州人，上海理工大學(xué)管理學(xué)院，副教授，碩士生導(dǎo)師，研究方向：運籌學(xué)、智能優(yōu)化；劉? 冬（1996—），男，河北保定人，上海理工大學(xué)管理學(xué)院碩士研究生，研究方向：智能優(yōu)化。

引文格式：卞俊麗，張惠珍，劉冬，等. 改進煙花算法求解同時送取貨選址路徑問題[J]. 物流科技，2024，47（3）：6-11.