改進野馬算法求解低碳開放式送取貨選址路徑問題

虎翼飛，張惠珍，陳曦

改進野馬算法求解低碳開放式送取貨選址路徑問題

虎翼飛，張惠珍*，陳曦

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

針對當(dāng)前物流背景下普遍出現(xiàn)的送貨公司外包、退換貨頻繁等問題，結(jié)合現(xiàn)有的碳排放政策，提出低碳背景下開放式同時送取貨選址?路徑模型（Low-Carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem，LOLRPSPD），并通過改進野馬算法進行求解。首先設(shè)計一種新的解碼方式，使得原離散問題可以采用連續(xù)算法求解。之后，運用哈爾頓序列生成初始解，改進非線性進化概率因子，使用模擬二進制交叉，增加變異操作，以及精英保留、設(shè)置連續(xù)失敗重新初始化等步驟，改進野馬算法。最后，通過6組不同大小的算例將改進野馬算法與原始野馬算法、模擬退火算法、粒子群算法、遺傳算法進行對比。針對中大型算例，改進野馬算法遠超原始野馬算法。針對小型算例，在確保準確率的同時，改進野馬算法對比各經(jīng)典算法也在速度上具有優(yōu)勢。提出的LOLRPSD模型具備合理性，改進的野馬算法針對選址路徑問題具有較好的搜索能力。

選址路徑問題；開放式問題；同時送取貨；改進野馬算法；元啟發(fā)式算法

選址路徑問題（Location-routing Problem, LRP）是一類經(jīng)典的組合優(yōu)化問題，需要同時將設(shè)施點的選址及車輛路線的選擇納入決策。中國作為人口大國，物流行業(yè)規(guī)模龐大，且發(fā)展迅速。相對而言，我國在物流研究方面仍較落后，大多企業(yè)只能依靠經(jīng)驗來制定物流標準，使得物流服務(wù)缺乏創(chuàng)新。隨著互聯(lián)網(wǎng)的普及，更多中老年群體開始使用手機購物，使得快遞名目更繁雜，且退換貨的比例加大。將開放式與同時送取貨組合對增強企業(yè)競爭優(yōu)勢、減少社會不必要浪費具有顯著意義。

Cooper[1]首次將設(shè)施選址問題與車輛路徑問題結(jié)合起來，提出了LRP。將標準LRP與實際情況結(jié)合后，可以形成多種擴展LRP，如有容量限制的LRP（Capacitated LRP, CLRP）、帶車容量限制的選址路徑問題（Capacitated Location-Routing Problem，CLRP）、開放式選址路徑問題（Open Location-routing Problem，OLRP）、同時送取貨選址路徑問題（Location-Routing Problem with Simultaneous Pickup and Delivery，LRPSPD）等。已有大量學(xué)者對LRP及其擴展問題進行了研究。Karaoglan等[2-4]根據(jù)實際運輸網(wǎng)絡(luò)中同時送取貨的需要，提出了同時送取貨選址路徑問題（Location Routing Problem with Simultaneous Pickup and Delivery，LRPSPD），并分別使用混合遺傳算法、分支定界法、啟發(fā)式算法進行求解。Wang[5]提出了具有多種服務(wù)模式和模糊時間窗的 LRPSPD ，使用禁忌搜索算法進行求解驗證，作為單起點式算法，其求解速度相對較慢，未發(fā)揮啟發(fā)式算法的優(yōu)勢。劉亞平等[6]在同時送取貨的基礎(chǔ)上，考慮了客戶時間窗，建立了LRPSPDTW模型，并用改進的煙花算法求解。通過與B&C（Branch and Cut algorithm）獲得的最優(yōu)解進行比較，取得了不錯的成果，但在大規(guī)模算例中缺少與其他啟發(fā)式算法的對比實驗。劉東等[7]在同時送取貨的基礎(chǔ)上，考慮了開放式，即車輛配送后不返回倉庫，提出了OLRPSPD（Open Location-routing Problem with Simultaneous Pickup and Delivery Problem）模型，進一步增大了現(xiàn)實意義。還改進了蘑菇算法，相較于模擬退火算法、蟻群算法、混合免疫算法等經(jīng)典啟發(fā)式算法，此改進方法在中型算例中具有明顯的優(yōu)勢。

隨著多項節(jié)能減排政策的實施和中國碳排放權(quán)交易市場的建立，物流活動中的碳排放成為一個亟待解決的關(guān)鍵問題。為此，國內(nèi)外學(xué)者們通過在LRP中加入低碳要素，通過構(gòu)建低碳模型來減少碳排放量。Barth等[8]考慮了車輛的速度和裝載量對車輛油耗的關(guān)系，建立了貨車燃油消耗模型。Zhang等[9]考慮了行駛距離、汽車行駛速度、車輛裝載量等，假設(shè)燃油消耗隨著車輛的載質(zhì)量呈等比例增加，提出了燃油消耗模型。由于在LRP中很難具體描述車輛的速度和加速度，故Xiao等[10]假設(shè)車輛勻速行駛，只考慮載質(zhì)量和行駛距離對車輛燃油排放的影響。文中在OLRPSPD模型的基礎(chǔ)上加入油耗計算公式，建立LOLRPSPD（Low-Carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem）模型。

野馬優(yōu)化算法（Wild Horse Optimizer，WHO）是Naruei等[11]在2021年提出的一種智能優(yōu)化算法，該算法的靈感來自野馬的放牧、交配和群體領(lǐng)導(dǎo)行為。通過模擬野馬放牧過程中馬駒在領(lǐng)頭馬周圍游蕩和不同馬駒群體間交配的特點，將領(lǐng)頭馬和馬駒群體位置的變化過程作為算法的優(yōu)化過程。WHO具有參數(shù)少、尋優(yōu)能力強、時間復(fù)雜度低等優(yōu)點。該算法仍然存在種群初始化階段種群多樣性差、全局搜索能力弱、后期難以脫離局部最優(yōu)等問題。針對基本W(wǎng)HO的不足，文中提出一種混合多策略改進野馬優(yōu)化算法（Improved Wild Horse Optimizer，IWHO），并將其運用于LCLRPSPD問題。

1 低碳開放式送取貨選址路徑問題

1.1 碳排放成本

基于模型的復(fù)雜性，以及在實際情況中難以預(yù)測車輛的情況，這里依照Xiao等[10]的方法將車輛的行駛速度設(shè)為勻速，僅考慮車輛的負載和行駛路程?？紤]到車輛在行駛過程中的油耗與負載近似呈線性關(guān)系[12-13]，將其表示為式（1）。

式中：為單位碳排放價格；μ為燃油轉(zhuǎn)換碳排放系數(shù)；d為兩點之間的距離。

1.2 符號說明

1.3 模型建立

總成本最小值的計算見式（3），包括設(shè)施點開放成本、運輸成本、車輛啟用成本和碳排放成本。碳排放的計算見式（4）。式（5）表示每個需求點被訪問有且僅有1次。式（6）表示進入節(jié)點的流等于流出節(jié)點的流。式（7）表示每輛車只能行駛1次。式（8）表示每個需求點都有唯一指定的設(shè)施點為其服務(wù)。式（9）表示消除子回路。式（10）和（11）分別表示送取貨不超過設(shè)施點容量限制。式（12）表示車輛裝卸平衡約束。式（13）表示車輛不能超載。式（14）表示車輛運送完成后不返回設(shè)施點。式（15）～（17）為決策變量取值范圍。

s.t.

上述模型中，各點位置集合、建設(shè)費用、容量及啟用成本已知，車輛啟用成本及最大負荷已知，運輸成本已知。送取貨需求量和碳排放相關(guān)系數(shù)由后文擬定。車輛實時載重可由送取貨需求計算得到。為計算過程中的罰成本，用以篩除不符合約束的路線。

2 野馬算法

2.1 基本野馬算法

之后，種馬帶領(lǐng)種群前往合適的水洼，但若該水洼已被另一個種群占領(lǐng)，則后來的種馬只能找尋其他水洼。具體計算見式（21）。

再后，當(dāng)種馬適應(yīng)度被其他成員超越時，則執(zhí)行種馬交換，見式（22）。

2.2 編碼及解碼方式

采用實數(shù)編碼方式，每個基因的取值為0～1內(nèi)的實數(shù)。重要的是解碼方式，在計算適應(yīng)度前解碼。解碼方式如圖1所示，給定具有可選設(shè)施點5個、需求點20個、備選車輛7輛的LRP，其染色體維度為5+7+20=32。

2）之后的7個基因代表備選車輛，分別乘以可建設(shè)設(shè)施點的數(shù)目2（從步驟1得出），并向上取整，得到備選車輛所服務(wù)設(shè)施點的編號。需要說明的是，這里求出的編號2代表建設(shè)的第2個設(shè)施點，即5，編號1表示4，如圖2所示。

3）剩余的20個基因代表需求點，用于計算需求點所選擇的車輛及運輸順序。同理，將其乘以備選車輛數(shù)量7，并向上取整，得到每個需求點所選車輛編號。若此步驟未出現(xiàn)某輛候選車輛編號，則此車輛停止使用。之后分別按基因排序，可得車輛服務(wù)需求點的順序。以第2輛車為例，共有編號5、9、10、11需要2號車服務(wù)，如圖3所示。

通過此種編碼方式，倉庫開放與否、客戶點服務(wù)順序及歸屬清晰可見。另外，此編碼考慮了實際情況中車輛運輸能力的差異性，更加符合數(shù)學(xué)模型和實際情況。

2.3 改進野馬算法

這里詳細介紹改進野馬算法（IWHO）的改進策略。為了增強基本算法的全局搜索能力、提升初始化種群多樣性，改善后期難以逃脫局部最優(yōu)等問題，進行了多次實驗。這里改進了6種方法，包括引入哈爾頓序列生成初始種群、非線性進化參數(shù)、模擬二進制交叉、多項式變異、精英保留策略、多次失敗后個體重新初始化。

圖1 完整染色體實例

圖2 備選車輛基因選擇設(shè)施點流程

圖3 需求點基因解碼邏輯

2.3.1 初始種群的生成

算法的種群初始化階段會極大地影響算法的后期處理?；镜腤HO是先根據(jù)種群數(shù)量選擇等量種馬，再在其他所有馬駒里隨機選擇個體跟隨指定的種馬行動。這樣會導(dǎo)致前期種群的混亂。例如，存在一個較好的馬駒個體，在周圍有優(yōu)秀種馬的情況下，因過分隨機而被分配給遙遠的種馬，使得該馬駒在迭代初期并未向有利個體靠近。在多次重復(fù)實驗過程中發(fā)現(xiàn)，針對LRP，基本W(wǎng)HO算法這種對于前期種群過于“混亂”的處理方式，對整體迭代有著不良影響。Halton序列是一種更接近于均勻分配的偽隨機。經(jīng)大量反復(fù)實驗后可以得出結(jié)論，針對LRP引入Halton序列，可以降低算法開局迭代中的種群混亂程度，加快全局搜索。

2.3.2 非線性進化概率因子

在原始算法中，放牧行為的進化概率參數(shù)（DR）按迭代次數(shù)線性遞減，見式（23）。

式中：iter為當(dāng)前迭代次數(shù)；iterations為總迭代次數(shù)。

2.3.3 模擬二進制交叉算子

為自定義參數(shù)，越大，則產(chǎn)生的后代逼近父代個體的概率越大。SBX算子在使用實數(shù)編碼的進化算法中，針對局部搜索的表現(xiàn)優(yōu)越，且處理高維目標優(yōu)化問題時對于個體空間稀疏性的效果良好，十分適用于LRP。

2.3.4 多項式變異算子

在原算法交叉環(huán)節(jié)后加入變異操作，即使用多項式變異（Polynomial Mutation Operator，PMO）算子對當(dāng)前解施加擾動，并以一定概率接受劣化解，且接受劣化解的概率隨時間的推移而降低。一方面，可以在算法前期維持解的多樣性，以加強全局搜索能力。另一方面，可以使算法后期變異產(chǎn)生的新解逐漸逼近當(dāng)前解，提升局部隨機搜索能力。多項式變異算子形式見式（27）～（28）。

2.3.5 精英保留策略

為了避免交叉及變異步驟丟失父代種群中的精英個體，采取精英保留策略存儲運算過程中的精英個體。精英個體是種群進化中搜索到的具有最優(yōu)適應(yīng)度的個體，它包含目前最好的基因數(shù)據(jù)。精英保留策略的核心思想是把種群進化過程中出現(xiàn)的精英個體復(fù)制到下一代中。在變異后進行精英保留操作，通過合并交叉和變異的種群，并與原種群對比，選擇最優(yōu)的保留下來，有效地提高了算法的收斂能力。

2.3.6 連續(xù)失敗重新初始化

原始野馬算法極易陷入局部最優(yōu)，為了改善這種情況，在算法中設(shè)定最大失敗統(tǒng)計數(shù)fail（設(shè)定為迭代次數(shù)的1/10）。當(dāng)算法連續(xù)運行fail都未找到更好的解時，說明局部收斂。此時對個體重新初始化，計算個體適應(yīng)度，并進行迭代。經(jīng)大量實驗證明，該方法對防止算法過快陷入局部最優(yōu)有效。

2.4 改進野馬算法流程描述

改進野馬算法（IWHO）求解低碳開放式送取貨選址路徑問題（LOLRPSPD）步驟如下。

1）初始化算法參數(shù)。包括種群規(guī)模、種馬比例S、最大迭代次數(shù)、交配概率C等。

2）解碼。計算種群個體適應(yīng)度，通過哈爾頓序列初始化種群，并選取種馬。

3）根據(jù)式（24）計算DR，根據(jù)式（18）～（19）進行放牧行為。

4）先根據(jù)式（20）進行交配行為，再根據(jù)式（25）～（26）進行二進制交叉，根據(jù)式（27）～（28）進行多項式變異，然后解碼，并按精英保留策略將優(yōu)秀個體保留。

5）根據(jù)式（21），種馬選擇新的水洼（目標區(qū)域）。

6）解碼。更新種群適應(yīng)度，若種群中存在適應(yīng)度優(yōu)于種馬個體，則根據(jù)式（22）更換種馬。

7）若連續(xù)失敗，則重新初始化種群，轉(zhuǎn)到步驟2）。

8）判斷是否達到最大迭代次數(shù)，若是，終止循環(huán)，否則轉(zhuǎn)到步驟3）。

9）滿足算法終止條件，輸出最優(yōu)解。

2.5 時間復(fù)雜性分析

文中對野馬算法的變動有6點。首先，在初始種群階段引入Halton序列，替代原有隨機序列，然后保持時間復(fù)雜度不變，仍為1()。在放牧階段改進了進化概率參數(shù)DR，雖然增加了運算量，但未產(chǎn)生額外的循環(huán)，故時間復(fù)雜度仍為2()。交配階段改變較大，改進了交叉方式，使用多項式交叉，又增加了多項式變異和精英保留策略。對于交叉與變異，依舊只增加運算量，未產(chǎn)生額外的循環(huán)。在精英保留步驟中，多使用了1個循環(huán)，影響較大，故改進后的交配階段時間復(fù)雜度為3(2)。領(lǐng)導(dǎo)者階段不變，時間復(fù)雜度仍為4()。最后新增連續(xù)失敗重新初始化階段，時間復(fù)雜度應(yīng)為5()。故改進野馬算法的時間復(fù)雜度(2)=1()+2()3(2)4()+5()。

3 算例分析

表1 算例數(shù)據(jù)

Tab.1 Example data

3.1 算法參數(shù)設(shè)置

為了得到優(yōu)秀的參數(shù)組合，分別對算例1和算例3進行了分析。通過比較每個算例最優(yōu)目標函數(shù)值和平均運行時間，對種群規(guī)模、種馬數(shù)量和迭代次數(shù)進行了靈敏度分析。在研究其中1個參數(shù)的性能時，保持其他參數(shù)不變。表2～4分別為3種參數(shù)在6組不同取值情況下對2組不同算例的平均運行結(jié)果，黑體表示最優(yōu)結(jié)果。對應(yīng)的變化曲線如圖4所示。不難看出，種群規(guī)模的改變對運行時間的影響不大，但當(dāng)過大或過小時，IWHO很容易陷入局部最優(yōu)，從而產(chǎn)生較差的平均目標值。種馬數(shù)量的改變對運行時間的影響很大，運行時間隨著種馬數(shù)量的提升顯著延長。在種馬數(shù)量為36時，運行時間甚至超過種馬數(shù)量為12時的8倍。對總成本的影響可以從折線圖看出，算例1和算例3均在種馬數(shù)量為12時存在明顯的低谷，在結(jié)合了適當(dāng)運行時間的情況下，這里選擇種馬數(shù)量12作為實驗標準。迭代次數(shù)對解的影響最明顯，在基本不影響運行時間的前提下，2組算例均在迭代次數(shù)為40時取到最優(yōu)成本。綜上所述，選取種群規(guī)模=60、種馬數(shù)量=12、迭代次數(shù)40作為實驗標準。

表2 種群規(guī)模對解的影響

Tab.2 Influence of population size on the solution

表3 種馬數(shù)量對解的影響

Tab.3 Influence of the number of stallions on the solution

表4 迭代次數(shù)對解的影響

Tab.4 Influence of iteration times on the solution

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

3.2 算法性能分析

為了檢驗IWHO算法的性能，針對以上6個算例進行求解，并與原始野馬算法（WHO）、粒子群優(yōu)化算法（Particle Swarm Optimization, PSO）、模擬退火算法（Simulated Annealing, SA）、遺傳算法（Genetic Algorithm，GA）進行了對比。實驗對每個算例求解20次，記錄最優(yōu)解及所用時間，求解結(jié)果如表5所示。

實驗結(jié)果表明，針對中型（編號1～2）、大型（編號3～6）算例，文中所提改進野馬算法相較于原始野馬算法具有顯著優(yōu)勢。從運行結(jié)果來看，由于LOLRPSPD問題的復(fù)雜性，原始野馬算法在實驗過程中極易過早陷入局部收斂，難以獲得最優(yōu)結(jié)果。IWHO在2組中型算例中都取得了已知最優(yōu)解，說明改進后非線性進化概率因子及連續(xù)失敗多次重新初始化步驟均取得了十分理想的結(jié)果。從運行穩(wěn)定性來看，IWHO針對中型算例每次都能求得已知最優(yōu)解，且迭代次數(shù)不多。原始野馬算法不論在中型算例還是大型算例上的結(jié)果都難令人滿意，在中型算例上，即使迭代20次都無法求得已知最優(yōu)解，且結(jié)果平均偏差在15%以上。對比分析后不難得出，改進后運用Halton序列種群初始化配合多次失敗重新初始化產(chǎn)生了良好效果。從運算速度來看，雖然IWHO每次迭代的時間約為原始WHO的3倍，但得出合適解的總時間更短。由于WHO在處理LOLRPSPD問題上總是過早收斂，很難統(tǒng)計有效時間，因此對于2組中型算例，這里在規(guī)定運行時間的前提下設(shè)置了合適的迭代次數(shù)。實驗結(jié)果基本證明文中所提的二進制交叉算子SBX、多項式變異算子（PMO）及精英保留策略較大程度地改善了原始WHO的全局搜索能力，使得IWHO可以適應(yīng)LRP。

與其他3個經(jīng)典算法相比，遺傳算法GA和粒子群算法PSO都較適合求解LOLRPSPD問題。這可能是因為算法本身的全局搜索能力較強，且收斂速度較慢。模擬退火算法SA與原始野馬算法WHO一樣，雖然局部搜索能力較強，但全局搜索能力較弱、收斂速度較快，不太適合求解LRP類問題。針對20個需求點的中型算例，改進野馬算法IWHO對比PSO和GA在時間上具有優(yōu)勢。針對50個需求點的大型算例，IWHO可以一次求得已知最優(yōu)解，但求解時間弱于GA。針對100個需求點的大型算例，IWHO會過早陷入局部最優(yōu)，難以求出超過GA的結(jié)果，但勝過PSO。

從實驗結(jié)果推斷，求解LOLRPSPD問題更需要算法的廣度，即全局搜索能力。雖然原始野馬算法WHO擁有不錯的局部搜索能力，但初始化種群不穩(wěn)定、全局搜索能力弱、收斂快，不適合求解LOLRPSPD問題。文中提出的改進野馬算法IWHO在保留原算法優(yōu)勢的同時，彌補了其劣勢，處理小型LRP問題具有一定優(yōu)勢。

3.3 IWHO有效性評估

為了進一步驗證IWHO在求解LRP上的有效性，這里用IWHO求解了6組標準CLRP數(shù)據(jù)庫中的算例，將其求解結(jié)果與GRASP[15]、MAPW[16]和2phase-HGTS[17]的求解結(jié)果進行對比分析。其中，Best是算例已知最優(yōu)解。GRASP、MAPW和2phase-HGTS由C++編寫，運行環(huán)境參見文獻[15-17]。IWHO由Matlab編寫。

由表6可知，IWHO可以取得前5個中型算例的最優(yōu)解，證明文中提出的改進野馬算法IWHO在處理LRP上可信。

表5 5種算法求解LOLRPSPD算例對比

Tab.5 Comparison of five algorithms for solving LOLRPSPD examples

表6 標準算例的求解結(jié)果

Tab.6 Solution results of standard examples

4 結(jié)語

在開放式送取貨選址?路徑問題模型上加入碳排放成本，以適應(yīng)目前的低碳背景，并使用改進的野馬算法進行求解。通過引入哈爾頓序列生成初始種群、非線性進化參數(shù)、模擬二進制交叉、多項式變異、精英保留策略和多次失敗后個體重新初始化等，有效改善了原始算法針對LRP存在的初始種群分布不均、全局搜索能力弱和容易陷入局部最優(yōu)等問題。算例分析結(jié)果表明，文中所提的改進IWHO算法對于LCLRPSPD問題具有良好的優(yōu)化性能。

為了進一步加強該問題的現(xiàn)實意義，人文關(guān)懷是不可或缺的，因此后續(xù)研究將構(gòu)建多目標模型，考慮顧客滿意度及配送員工作量，并設(shè)計其相應(yīng)的IWHO求解算法。

[1] COOPER L. The Transportation-Location Problem[J]. Operations Research, 1972, 20(1): 94-108.

[2] KARAOGLAN I, ALTIPARMAK F, KARA I, et al. Formulations for Location-Routing Problem with Simultaneous Pickup and Delivery[E/OL]. 2009. http://w3.gazi. edu.tr/～fulyaal/Papers/LRPSPD_MIP Formulations.

[3] 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.

[4] KARAOGLAN I, ALTIPARMAK F, KARA I, et al. The Location-Routing Problem with Simultaneous Pickup and Delivery: Formulations and a Heuristic Approach[J]. Omega, 2012, 40(4): 465-477.

[5] WANG X F. An Location-Routing Problem with Simultaneous Pickup and Delivery in Urban-Rural Dual- Directions Logistics Network[J]. Advanced Materials Research, 2013, 756/757/758/759: 3423-3429.

[6] 劉亞平, 張惠珍, 張莉, 等. 帶時間窗同時送取貨選址路徑問題及其煙花算法求解[J]. 計算機應(yīng)用, 2022, 42(7): 2292-2300.

LIU Y P, ZHANG H Z, ZHANG L, et al. Fireworks Algorithm for Location-Routing Problem of Simultaneous Pickup and Delivery with Time Window[J]. Journal of Computer Applications, 2022, 42(7): 2292-2300.

[7] 劉冬, 張惠珍, 劉亞平, 等. 改進蘑菇算法求解開放式同時送取貨選址–路徑問題[J]. 控制工程, 2023, 30(10): 1801-1811.

LIU D, ZHANG H Z, LIU Y P, et al. An Improved Mushroom Algorithm for Solving the Open Location- Routing Problem with Simultaneous Pickup and Delivery[J]. Control Engineering of China, 2023, 30(10): 1801-1811.

[8] BARTH M, YOUNGLOVE T, SCORA G. Development of a Heavy-Duty Diesel Modal Emissions and Fuel Consumption Model，UCB-ITS-PRR-2005-1[R]. California PATH Research Report, 2005.

[9] ZHANG J H, ZHAO Y X, XUE W L, et al. Vehicle Routing Problem with Fuel Consumption and Carbon Emission[J]. International Journal of Production Economics, 2015, 170: 234-242.

[10] XIAO Y Y, ZHAO Q H, KAKU I, et al. Development of a Fuel Consumption Optimization Model for the Capacitated Vehicle Routing Problem[J]. Computers & Operations Research, 2012, 39(7): 1419-1431.

[11] NARUEI I, KEYNIA F. Wild Horse Optimizer: A New Meta-Heuristic Algorithm for Solving Engineering Optimization Problems[J]. Engineering with Computers, 2022, 38(4): 3025-3056.

[12] 張春苗, 趙燕偉, 張景玲, 等. 低碳定位——車輛路徑問題[J]. 計算機集成制造系統(tǒng), 2017, 23(12): 2768-2777.

ZHANG C M, ZHAO Y W, ZHANG J L, et al. Location and Routing Problem with Minimizing Carbon[J]. Computer Integrated Manufacturing Systems, 2017, 23(12): 2768-2777.

[13] 王舜, 趙燕偉, 冷龍龍, 等. 基于蟻群選擇超啟發(fā)算法的低碳選址–路徑問題[J]. 計算機集成制造系統(tǒng), 2020, 26(6): 1702-1716.

WANG S, ZHAO Y W, LENG L L, et al. Low Carbon Location-Routing Problem Based on Evolutionary Hyper-Heuristic Algorithm of Ant Colony Selection Mechanism[J]. Computer Integrated Manufacturing Systems, 2020, 26(6): 1702-1716.

[14] LI Y C, YUAN Q Y, HAN M X, et al. Hybrid Multi-Strategy Improved Wild Horse Optimizer[J]. Advanced Intelligent Systems, 2022, 4(10): 2200097.

[15] 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, 2006, 4(3): 221-238.

[16] PRINS C, PRODHON C, CALVO R W. A Memetic Algorithm with Population Management (MA|PM) for the Capacitated Location-Routing Problem[M]// Evolutionary Computation in Combinatorial Optimization. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006: 183-194.

[17] ESCOBAR J W, LINFATI R, TOTH P. A Two-Phase Hybrid Heuristic Algorithm for the Capacitated Location-Routing Problem[J]. Computers & Operations Research, 2013, 40(1): 70-79.

Improved Wild Horse Optimizer for Solving Low-carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem

HU Yifei, ZHANG Huizhen*,CHEN Xi

(School of Management, University of Shanghai for Science & Technology, Shanghai 200093, China)

The work aims to propose an Open Location-Routing Problem with Simultaneous Pickup and Delivery (LOLRPSPD) model under the low-carbon background to solve the common problems of outsourcing, frequent return and exchange of goods in delivery companies and solve the problem through the Wild Horse Optimizer. Firstly, a new decoding mode was designed so that the discrete problems could be solved by continuous algorithms. Then, the initial solutions were generated through the Halton sequence to improve the nonlinear evolution probability factor TDR; The simulated binary crossover was used. Polynomial mutation operators were added. Elite preservation, and setting of consecutive failed reinitialization steps were completed. Finally, the effectiveness of the improved algorithm was verified through the comparison results between Improved Wild Horse Optimizer (IWHO), Wild Horse Optimizer (WHO), Simulated Annealing (SA), Particle Swarm Optimization (PSO), and genetic algorithm (GA). The experimental results showed that IWHO in this paper had better optimization ability than normal WHO in terms of large and medium-sized examples, and had a good advantage in the processing of small examples whiling ensuring accuracy. The proposed LOLRPSD model is reasonable, and the Improved Wild Horse Optimizer has better searching ability for LRP problems.

location-routing problem; open location-routing problem; simultaneous pickup and delivery; improved wild horse optimizer; heuristic algorithm

TP302；TB48

A

1001-3563(2024)01-0229-10

10.19554/j.cnki.1001-3563.2024.01.027

2023-05-17

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