虎翼飛，張惠珍，陳曦

改進(jìn)野馬算法求解低碳開(kāi)放式送取貨選址路徑問(wèn)題

虎翼飛，張惠珍*，陳曦

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

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

選址路徑問(wèn)題；開(kāi)放式問(wèn)題；同時(shí)送取貨；改進(jìn)野馬算法；元啟發(fā)式算法

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

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

隨著多項(xiàng)節(jié)能減排政策的實(shí)施和中國(guó)碳排放權(quán)交易市場(chǎng)的建立，物流活動(dòng)中的碳排放成為一個(gè)亟待解決的關(guān)鍵問(wèn)題。為此，國(guó)內(nèi)外學(xué)者們通過(guò)在LRP中加入低碳要素，通過(guò)構(gòu)建低碳模型來(lái)減少碳排放量。Barth等[8]考慮了車(chē)輛的速度和裝載量對(duì)車(chē)輛油耗的關(guān)系，建立了貨車(chē)燃油消耗模型。Zhang等[9]考慮了行駛距離、汽車(chē)行駛速度、車(chē)輛裝載量等，假設(shè)燃油消耗隨著車(chē)輛的載質(zhì)量呈等比例增加，提出了燃油消耗模型。由于在LRP中很難具體描述車(chē)輛的速度和加速度，故Xiao等[10]假設(shè)車(chē)輛勻速行駛，只考慮載質(zhì)量和行駛距離對(duì)車(chē)輛燃油排放的影響。文中在OLRPSPD模型的基礎(chǔ)上加入油耗計(jì)算公式，建立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ái)自野馬的放牧、交配和群體領(lǐng)導(dǎo)行為。通過(guò)模擬野馬放牧過(guò)程中馬駒在領(lǐng)頭馬周?chē)问幒筒煌R駒群體間交配的特點(diǎn)，將領(lǐng)頭馬和馬駒群體位置的變化過(guò)程作為算法的優(yōu)化過(guò)程。WHO具有參數(shù)少、尋優(yōu)能力強(qiáng)、時(shí)間復(fù)雜度低等優(yōu)點(diǎn)。該算法仍然存在種群初始化階段種群多樣性差、全局搜索能力弱、后期難以脫離局部最優(yōu)等問(wèn)題。針對(duì)基本W(wǎng)HO的不足，文中提出一種混合多策略改進(jìn)野馬優(yōu)化算法（Improved Wild Horse Optimizer，IWHO），并將其運(yùn)用于LCLRPSPD問(wèn)題。

1 低碳開(kāi)放式送取貨選址路徑問(wèn)題

1.1 碳排放成本

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

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

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

1.3 模型建立

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

s.t.

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

2 野馬算法

2.1 基本野馬算法

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

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

2.2 編碼及解碼方式

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

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

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

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

2.3 改進(jìn)野馬算法

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

圖1 完整染色體實(shí)例

圖2 備選車(chē)輛基因選擇設(shè)施點(diǎn)流程

圖3 需求點(diǎn)基因解碼邏輯

2.3.1 初始種群的生成

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

2.3.2 非線性進(jìn)化概率因子

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

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

2.3.3 模擬二進(jìn)制交叉算子

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

2.3.4 多項(xiàng)式變異算子

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

2.3.5 精英保留策略

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

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

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

2.4 改進(jìn)野馬算法流程描述

改進(jìn)野馬算法（IWHO）求解低碳開(kāi)放式送取貨選址路徑問(wèn)題（LOLRPSPD）步驟如下。

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

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

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

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

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

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

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

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

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

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

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

3 算例分析

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

Tab.1 Example data

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

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

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

Tab.2 Influence of population size on the solution

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

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

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

Tab.4 Influence of iteration times on the solution

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

3.2 算法性能分析

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

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

與其他3個(gè)經(jīng)典算法相比，遺傳算法GA和粒子群算法PSO都較適合求解LOLRPSPD問(wèn)題。這可能是因?yàn)樗惴ū旧淼娜炙阉髂芰^強(qiáng)，且收斂速度較慢。模擬退火算法SA與原始野馬算法WHO一樣，雖然局部搜索能力較強(qiáng)，但全局搜索能力較弱、收斂速度較快，不太適合求解LRP類問(wèn)題。針對(duì)20個(gè)需求點(diǎn)的中型算例，改進(jìn)野馬算法IWHO對(duì)比PSO和GA在時(shí)間上具有優(yōu)勢(shì)。針對(duì)50個(gè)需求點(diǎn)的大型算例，IWHO可以一次求得已知最優(yōu)解，但求解時(shí)間弱于GA。針對(duì)100個(gè)需求點(diǎn)的大型算例，IWHO會(huì)過(guò)早陷入局部最優(yōu)，難以求出超過(guò)GA的結(jié)果，但勝過(guò)PSO。

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

3.3 IWHO有效性評(píng)估

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

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

表5 5種算法求解LOLRPSPD算例對(duì)比

Tab.5 Comparison of five algorithms for solving LOLRPSPD examples

表6 標(biāo)準(zhǔn)算例的求解結(jié)果

Tab.6 Solution results of standard examples

4 結(jié)語(yǔ)

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

為了進(jìn)一步加強(qiáng)該問(wèn)題的現(xiàn)實(shí)意義，人文關(guān)懷是不可或缺的，因此后續(xù)研究將構(gòu)建多目標(biāo)模型，考慮顧客滿意度及配送員工作量，并設(shè)計(jì)其相應(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] 劉亞平, 張惠珍, 張莉, 等. 帶時(shí)間窗同時(shí)送取貨選址路徑問(wèn)題及其煙花算法求解[J]. 計(jì)算機(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ìn)蘑菇算法求解開(kāi)放式同時(shí)送取貨選址–路徑問(wèn)題[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] 張春苗, 趙燕偉, 張景玲, 等. 低碳定位——車(chē)輛路徑問(wèn)題[J]. 計(jì)算機(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ā)算法的低碳選址–路徑問(wèn)題[J]. 計(jì)算機(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

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