基于局部搜索的逆向物流車輛最短路徑優(yōu)化

趙 嬈，陳志華

(1.太原學(xué)院，山西 太原030032；2.廣東技術(shù)師范大學(xué)網(wǎng)絡(luò)信息中心，廣東 廣州 510665)

1 引言

資源環(huán)境惡劣情況日益嚴(yán)重，可持續(xù)發(fā)展與回收再利用經(jīng)濟(jì)觀念備受關(guān)注，逆向物流的核心思想為回收再利用廢舊物品，緩解環(huán)境惡化情況[1-3]，為此其逐漸成為科研領(lǐng)域與社會各界的研究方向[4]。逆向物流屬于一個(gè)閉環(huán)供應(yīng)鏈，但該物流具備成本高與操作難度高等問題，而車輛路徑優(yōu)化屬于運(yùn)輸規(guī)范化的重要步驟。孟小玲等人以降低運(yùn)輸成本為目的，塑造車輛路徑優(yōu)化的概率模型與信息素更新模型，利用改進(jìn)蟻群算法求解該模型，提升模型求解過程中的尋優(yōu)效果與穩(wěn)定性，但該模型的求解算法在求解大規(guī)模問題時(shí)，存在局限性的缺點(diǎn)，同時(shí)信息素更新頻率較高，且局部搜索能力不足，嚴(yán)重降低模型求解的收斂速度[5]；張慶華等人塑造帶軟時(shí)間窗的路徑優(yōu)化模型，利用混合變鄰域的蟻群算求解該模型，提升求解算法的搜索能力，但該模型中求解算法信息素的更新方式為靜態(tài)的，未考慮迭代次數(shù)增長對求解過程的影響，降低收斂速度[6]；李雙艷等人以降低CO2排放量為目的，塑造可拆分的路徑優(yōu)化模型，利用禁忌搜索算法求解該模型，解決路徑優(yōu)化問題，但該模型的求解算法過分依賴初始解，局部搜索能力較差，降低最優(yōu)解的質(zhì)量[7]。局部搜索算法具備跳出局部最優(yōu)解，搜索最佳值的特點(diǎn)，屬于可以避開局部極值點(diǎn)的優(yōu)化算法，為此研究基于局部搜索的逆向物流車輛最短路徑優(yōu)化，優(yōu)化車輛最短路徑，降低運(yùn)輸成本。

2 基于局部搜索的逆向物流車輛最短路徑優(yōu)化

2.1 逆向物流車輛最短路徑優(yōu)化模型

逆向物流車輛最短路徑優(yōu)化中包含一個(gè)回收中心，n個(gè)回收點(diǎn)，m輛車，在符合回收需求時(shí)，采取最恰當(dāng)?shù)姆绞綄?shí)現(xiàn)協(xié)調(diào)車輛使用情況，優(yōu)化車輛最短總運(yùn)行路徑。

2.1.1 模型假設(shè)

1)模型內(nèi)僅存在一個(gè)回收中心，且坐標(biāo)已知；

2)模型內(nèi)存在多于1個(gè)的回收點(diǎn)，且坐標(biāo)已知；

3)回收點(diǎn)回收量固定，要求低于車輛正常容量；

4)路況與車輛運(yùn)行距離無關(guān)聯(lián)[8]；

5)回收物品種類一致；

6)同一輛車僅可為一個(gè)回收點(diǎn)服務(wù)一次；

7)回收中心車輛完全一致，不會出現(xiàn)車輛缺少情況，單次回收操作運(yùn)行距離低于車輛最遠(yuǎn)運(yùn)行距離；

8)回收中心容量無上限。

2.1.2 模型構(gòu)建

根據(jù)模型假設(shè)構(gòu)建逆向物流車輛最短路徑優(yōu)化模型，最短路徑優(yōu)化模型也是目標(biāo)函數(shù)公式如下

(1)

其中，minZ代表最短路徑；i、j代表回收點(diǎn)編號；k代表車輛編號；Z代表遍歷全部回收點(diǎn)車輛運(yùn)行的總里程；i=0、j=0代表回收中心；dij代表i與j間的距離，且dij=dji；aijk代表變量，取值為0或1，以i為起始點(diǎn)，k駛向j時(shí)，aijk=1；反之，aijk=0。

模型內(nèi)車輛容量約束條件如下

(2)

其中，qi代表i的回收量；bik代表變量，取值0或1，在k服務(wù)i的情況下，bik=1；反之，bik=0；G代表單輛車的最大容量；n代表車輛總數(shù)；通過式(2)可確保單個(gè)回收點(diǎn)的qi低于車輛正常容量。

車輛服務(wù)回收點(diǎn)的次數(shù)約束條件如下

(3)

通過式(3)確保一輛車僅為一個(gè)回收點(diǎn)服務(wù)一次。

車輛服務(wù)回收點(diǎn)的時(shí)間約束條件如下

(4)

通過式(4)確保單個(gè)車輛服務(wù)單個(gè)回收點(diǎn)后即刻離開。

變量取值公式如下：

(5)

2.2 模型求解

2.2.1 算法思路

利用局部搜索結(jié)合果蠅算法求解2.1小節(jié)的模型，具體步驟如下：

步驟1：建立原始解，初始化路徑軌跡強(qiáng)度；

步驟2：為果蠅塑造路線，果蠅數(shù)量為z個(gè)；

步驟3：遍歷本地信息，獲取優(yōu)化單個(gè)果蠅生成的解決方案；

步驟4：通過局部搜索更新最優(yōu)解即最優(yōu)方案；

步驟5：通過最優(yōu)方案更新全部弧即路徑的軌跡強(qiáng)度；

步驟6：反復(fù)操作步驟2至步驟6，以獲取最優(yōu)解為止；

步驟7：結(jié)束操作，報(bào)告最優(yōu)解。

2.2.2 初始化果蠅群與路徑軌跡的正交離散法

果蠅以首個(gè)回收點(diǎn)為起始點(diǎn)，依次遍歷各個(gè)回收點(diǎn)的正交離散點(diǎn)，以達(dá)到車輛最大容輛返回回收中心為止，完成一次循環(huán)，構(gòu)建一個(gè)完成的回收點(diǎn)至回收中心的組合。正交離散法的具體步驟如下：

步驟1：利用正交離散法降低搜索原始解群的組合數(shù)量，提升果蠅群體的計(jì)算速度；

步驟2：在確定的正交離散點(diǎn)內(nèi)，選擇具有較強(qiáng)代表性的初始組合點(diǎn)，分析確定對回收路徑影響最大的回收點(diǎn)。

正交離散化完成后開始初始化路徑，初始化路徑的流程如圖1所示。

圖1 初始化路徑的流程圖

初始化路徑的具體步驟如下：

步驟1：按照回收點(diǎn)至回收中心的配對組合，獲取等待回收的回收點(diǎn)序列；

步驟2：若車輛容量符合回收點(diǎn)回收量的需求[9]，則該回收點(diǎn)加入車輛路徑內(nèi)，令路徑軌跡是[0，1]間的任意數(shù)，反之，在回收下一個(gè)回收點(diǎn)前，車輛返回回收中心；

步驟3：重復(fù)以上步驟，獲取逆向物流車輛最短路徑內(nèi)全部弧的軌跡強(qiáng)度。

2.2.3 路徑創(chuàng)建

每個(gè)果蠅均會產(chǎn)生一個(gè)完成的路線即逆向物流車輛最短路徑優(yōu)化的解決方案，m個(gè)果蠅會產(chǎn)生m個(gè)解決方案。按照弧的軌跡強(qiáng)度τij與味道強(qiáng)度μij，令單個(gè)果蠅由一個(gè)回收點(diǎn)移至另一個(gè)回收點(diǎn)。將果蠅需尋找下一個(gè)回收點(diǎn)和目前地點(diǎn)間的距離的倒數(shù)當(dāng)成μij，距離與μij成反比，果蠅易于選取距離短的回收點(diǎn)，實(shí)現(xiàn)路徑長度最短化[10]?；ij的吸引力包含τij與μij，τij代表迭代時(shí)路徑Zij被重復(fù)使用的程度；μij代表Zij長度的倒數(shù)，即果蠅從i移至j的傾向程度。吸引力值的表達(dá)公式如下

εij=(τij)α(μij)β

(6)

其中，α、β代表τij、μij的影響權(quán)重。在果蠅服務(wù)i后，j屬于下一個(gè)回收點(diǎn)的概率如下

(7)

其中，全部可行回收點(diǎn)的列表是Mi，代表未被當(dāng)前車輛服務(wù)過，同時(shí)低于車輛最大容量以及最大運(yùn)行距離[11，12]，可以被服務(wù)的回收點(diǎn)；式(7)代表pij與Zij的吸引力成正比。

設(shè)計(jì)閾值控制機(jī)制提升算法的收斂速度[13]，單個(gè)果蠅按照式(10)選取下一個(gè)回收點(diǎn)j前，產(chǎn)生一個(gè)隨機(jī)變量s，s∈[0，1]。若s>s0，按照式(7)選取下一個(gè)回收點(diǎn)；反之，在Mi內(nèi)選取存在最大吸引力的弧的回收點(diǎn)；s0代表已知的常數(shù)閾值，說明下一個(gè)回收點(diǎn)的選取是否按照式(7)獲取。

單個(gè)果蠅依據(jù)上述方法持續(xù)添加回收點(diǎn)，以Mi為空為止；果蠅返回回收中心，繼續(xù)另一條回收路徑。若回收路徑內(nèi)的首個(gè)回收點(diǎn)按照式(7)獲取的，那么路徑中的首個(gè)回收點(diǎn)為回收中心的鄰節(jié)點(diǎn)，減少回收點(diǎn)尋找的多樣性[14]。

2.2.4 基于模擬退火算法的局部搜索策略

利用基于模擬退化算法的局部搜索策略提高解決方案的質(zhì)量，模擬退火算法按照Metropolis準(zhǔn)則衡量是否接受搜索時(shí)獲取被原始解決方案Z0支配的新解決方案Z1，接受新解決方案的概率如下

(8)

其中，f(Z0)、f(Z1)代表Z0、Z1的目標(biāo)函數(shù)值；g代表Boltzmann常數(shù)；T代表進(jìn)化代相應(yīng)熱度；從式(8)得知，p′和T相關(guān)，p′和T成正比，T的迭代公式如下

(9)

其中，T0代表初始溫度；t代表迭代次數(shù)。

局部搜索策略的局部步驟如下：

步驟1：設(shè)置參數(shù)T0，t的上限h，鄰域搜索次數(shù)r，r的上限R；

步驟4：如果r

步驟5：更新T，如果t>h，則結(jié)束算法，反之，轉(zhuǎn)至步驟3。

2.2.5 更新軌跡強(qiáng)度

2.2.4小節(jié)的作用為增強(qiáng)果蠅算法解決方案的質(zhì)量。利用最優(yōu)的Z′ij更新全部弧的τij，通過τij隨時(shí)間降低的方式仿真實(shí)際情況。τij的更新步驟如下：

步驟1：減輕全部弧中的τij，仿真其衰減過程[15]；

步驟2：僅提升最優(yōu)路徑中弧的τij，提高果蠅選取最短路徑的概率。

假設(shè)軌跡維持系數(shù)是ρ，0≤ρ<1，因此，1-ρ代表τij隨迭代增長而降低的比率，弧的τij更新公式如下：

(10)

3 仿真研究

以某逆向物流站為實(shí)驗(yàn)對象，將該回收站的逆向物流回收實(shí)例代入本文模型展開仿真，利用C語言編程，在Intel(R)Core(TM)2Duo 2.53GHz，4GB內(nèi)存運(yùn)行環(huán)境中仿真分析本文模型的有效性。該物流站的回收中心內(nèi)車輛類型一致，車輛正常容量是12t，仿真中共包含1個(gè)回收中心與18個(gè)回收點(diǎn)，具體數(shù)據(jù)如表1所示。

表1 回收中心與回收點(diǎn)的基礎(chǔ)數(shù)據(jù)

為驗(yàn)證本文模型中引入局部搜索策略的有效性，分析引入局部搜索策略前后對本文模型求解結(jié)果的影響，為確保實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，共展開5次實(shí)驗(yàn)，影響結(jié)果如圖2所示。

圖2 影響結(jié)果

根據(jù)圖2可知，兩種前提下的五次實(shí)驗(yàn)結(jié)果變化幅度均較小，說明本文模型的穩(wěn)定性較優(yōu)；在本文模型的求解算法中引入局部搜索策略后的最短路徑總長度顯著低于未引入局部搜索策略，未引入局部搜索策略的最短路徑總長度始終高于480km左右，引入局部搜索策略后的最短路徑總長度始終低于476km左右；未引入局部搜索策略的最優(yōu)解質(zhì)量提升比率始終低于12%左右，引入局部搜索策略的最優(yōu)解質(zhì)量提升比率始終高于12%左右；綜合分析可知，引入局部搜索策略的最短路徑總長度的高值值低于未引入局部搜索策略最短路徑總長度的最低值，其最優(yōu)解質(zhì)量提升比率的最低值高于未引入局部搜索策最優(yōu)解質(zhì)量提升比率的最高值。仿真結(jié)果證明：在本文模型的求解算法內(nèi)引入局部搜索策略可有效提升最優(yōu)解的質(zhì)量，優(yōu)化最短路徑。

根據(jù)表1的基礎(chǔ)數(shù)據(jù)，利用本文模型優(yōu)化逆向物流車輛的最短路徑，并與原始路徑作對比，測試本文方法的有效性，原始逆向物流車輛最短路徑如圖3所示，本文模型優(yōu)化后的逆向物流車輛最短路徑如圖4所示。

圖3 原始逆向物流車輛最短路徑

圖4 本文模型優(yōu)化的逆向物流車輛最短路徑

根據(jù)圖3與圖4可知，原始路徑中車輛1的回收路徑為0-1-2-3-4-5-0，車輛2的路徑為0-8-9-6-7-0，車輛3的路徑為0-10-14-12-13-15-11-0，車輛5的路徑為0-18-17-16-0；本文模型優(yōu)化后車輛1的回收路徑與原始路徑一致，車輛2的路徑為0-8-7-6-9-0，車輛3的路徑為0-10-12-13-15-11-14-0，車輛4的路徑為0-17-18-16-0；經(jīng)過本文模型優(yōu)化后的車輛路徑明顯短于原始路徑，說明本文模型可有效優(yōu)化逆向物流車輛的最短路徑，獲取最優(yōu)的最短路徑，為物流站節(jié)約成本。

現(xiàn)實(shí)生活中，因?yàn)楦鞣N條件的約束，所以回收點(diǎn)與回收中心建立的回收網(wǎng)絡(luò)可能為隨機(jī)網(wǎng)路或小世界網(wǎng)絡(luò)；將每個(gè)回收點(diǎn)看成一個(gè)節(jié)點(diǎn)，隨機(jī)網(wǎng)絡(luò)為已知N個(gè)節(jié)點(diǎn)，按照固定的隨機(jī)概率p連接全部可能出現(xiàn)的N(N-1)/2；小世界網(wǎng)絡(luò)為以規(guī)則網(wǎng)絡(luò)為起始點(diǎn)，令存在N個(gè)節(jié)點(diǎn)的近鄰耦合網(wǎng)絡(luò)形成一個(gè)圓圈，其中各節(jié)點(diǎn)均和其左右鄰近的K/2各節(jié)點(diǎn)連接，K非奇數(shù)；測試本文模型在兩種網(wǎng)絡(luò)情況下的收斂情況，測試結(jié)果如圖5所示。

圖5 不同網(wǎng)絡(luò)情況下的收斂情況

根據(jù)圖5可知，在不同網(wǎng)絡(luò)時(shí)，本文模型最短路徑與平均路徑的收斂速度均較快，差距較小；兩種網(wǎng)絡(luò)時(shí)最短路徑均在迭代次數(shù)約為100次時(shí)已完成收斂，最優(yōu)解的質(zhì)量均趨于穩(wěn)定，均收斂至468km以下；前期兩種網(wǎng)絡(luò)時(shí)的平均路徑長度的收斂情況存在小幅度的波動(dòng)，當(dāng)?shù)螖?shù)超過125次時(shí)，最優(yōu)解不再發(fā)生變化，趨于穩(wěn)定完成收斂，均收斂至476km以下。

該逆向物流站應(yīng)用本文模型優(yōu)化最優(yōu)車輛路徑半年(2019年1月至6月)后，測試應(yīng)用本文模型前后的逆向物流運(yùn)輸成本與CO2排放量，測試結(jié)果如圖6所示。

圖6 測試結(jié)果

根據(jù)圖6可知，在2019年1月至6月份期間，應(yīng)用本文模型后的逆向物流運(yùn)輸成本顯著低于應(yīng)用本文模型前，應(yīng)用本文模型前后CO2排放量均與逆向物流運(yùn)輸成本的變化趨勢一致，應(yīng)用本文模型后的CO2排放量也顯著低于應(yīng)用本文模型前。仿真結(jié)果表明，應(yīng)用本文模型后可有效降低逆向物流站的運(yùn)輸成本與CO2排放量，對于環(huán)境保護(hù)具有一定的貢獻(xiàn)。

4 結(jié)論

逆向物流車輛最短路徑優(yōu)化可有效縮短車輛運(yùn)行里程，減少運(yùn)輸成本，降低CO2排放量，為環(huán)境保護(hù)作出貢獻(xiàn)，促進(jìn)逆向物流行業(yè)的綠色健康發(fā)展。為此研究基于局部搜索的逆向物流車輛最短路徑優(yōu)化，融合局部搜索和果蠅算法的優(yōu)點(diǎn)，獲取最短路徑優(yōu)化問題的最優(yōu)解，加快求解過程的收斂速度，提高最優(yōu)解的質(zhì)量，獲取最優(yōu)方案，優(yōu)化最短路徑，降低運(yùn)輸成本。