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

劉亞平，張惠珍，張莉，劉優優

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

劉亞平，張惠珍*，張莉，劉優優

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

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

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

0 引言

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

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

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

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

1 本文模型

1.1　行車策略選擇

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

1.2　問題描述與模型假設

物流作為企業第三利潤源，在企業競爭中有著舉足輕重的地位，提高配送效率和節約配送成本至關重要，配送回收中心的選址是決定配送好壞的關鍵因素。基于實際，本文研究的帶時間窗同時送取貨選址路徑問題，其研究對象是由配送中心到顧客的供應鏈的一級分銷網絡，有多個位置已知的客戶和候選倉庫，要在倉庫容量和車載量承受范圍內為客戶提供配送回收服務，并規劃從倉庫到客戶點的車輛行駛路線，在客戶可接受時間范圍內滿足客戶需求使總成本最小。可對模型做如下假設：

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

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

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

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

1.3　符號說明

集合

常量

決策變量

1.4　模型建立

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

2 煙花算法

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

2.1　編碼方式

圖1　解的編碼表示

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

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

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

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

2.2　初始種群的生成

2.3　爆炸操作

2.3.1火花數和爆炸幅度

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

2.3.2產生火花數

圖2　的火花產生過程

2.4　變異操作

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

圖3　插入移動

圖4　逆轉移動

圖5　單點變異

圖6　多點變異

2.5　映射規則

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

2.6　選擇策略

（21）

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

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

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

2.8　算法步驟

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

步驟3 開始迭代，基于設定的爆炸火花個數和半徑的參數值，根據適應度值計算每個煙花的爆炸火花個數和半徑。

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

步驟7 滿足算法終止條件，停止算法，輸出最優解。

3 算例分析

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

3.1　算例測試

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

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

3.2　參數靈敏度分析

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

表2　煙花數對解的影響

表3　參數M對解的影響

表4　參數S對解的影響

3.2.6參數組合

表5　參數對解的影響

表6　參數G對解的影響

圖7　參數靈敏度分析

4 結語

針對傳統煙花算法不能解決離散問題，本文在煙花爆炸過程中引入重復交換移動，在變異過程中設計4種搜尋機制，設計了IFWA，既開發了全局搜索能力，提高解的質量，也保證了火花的多樣性。通過和B&C在44個基準LRPSPD算例上對比分析，結果表明，本文設計的IFWA在求解質量和效率上都能達到令人滿意的效果。在后續工作中，會探討改進煙花算法對包含客戶滿意度的多目標模型的求解以及考慮多種商品的模型的求解。

（

）

[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] 張震. 多商品多來源閉環選址-庫存-路徑問題模型與算法研究［D］.武漢：華中師范大學， 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］. 系統工程理論與實踐， 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] 陳庭貴，琚春華. 多干擾的資源約束項目調度問題［J］. 計算機集成制造系統， 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] 陳庭貴，楊俊蓉. 網絡群體極化現象的形成機理及仿真實驗研究［J］. 重慶科技學院學報（自然科學版）， 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—），女，江西九江人，碩士研究生，主要研究方向：智能優化； 張惠珍（1979—），女，山西忻州人，副教授，博士，主要研究方向：運籌學、智能優化； 張莉（1995—），女，湖北荊州人，碩士研究生，主要研究方向：智能優化； 劉優優（1999—），女，湖南岳陽人，主要研究方向：信息管理、智能優化。