程元棟，楊齊威

基于混合自適應(yīng)遺傳算法的路徑規(guī)劃研究

程元棟，楊齊威

（安徽理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，安徽 淮南 232000）

為解決供應(yīng)商管理庫存（VMI）模式下帶時(shí)間窗的車輛路徑規(guī)劃（VRPTW）問題，綜合考慮多種條件建立了具有多目標(biāo)約束的數(shù)學(xué)模型，并創(chuàng)新性提出混合式自適應(yīng)遺傳算法，該算法在自適應(yīng)遺傳算法（AGA）的基礎(chǔ)上加入了節(jié)約算法構(gòu)造種群的初始解，引入了隨機(jī)遍歷抽樣法進(jìn)行選擇操作，改進(jìn)了算法的交叉方式，最后運(yùn)用大規(guī)模鄰域搜索法（LNS）對(duì)變異后的種群進(jìn)行破壞和修復(fù)操作。通過MATLAB軟件進(jìn)行仿真實(shí)驗(yàn)，與傳統(tǒng)自適應(yīng)遺傳算法進(jìn)行對(duì)比，運(yùn)輸成本顯著性降低了50%，據(jù)此得出該混合式自適應(yīng)遺傳算法在解決VRPTW問題時(shí)具有更強(qiáng)更科學(xué)的全局搜索和快速收斂的能力，以期更高效合理地優(yōu)化供應(yīng)商車輛配送路徑規(guī)劃。

供應(yīng)商管理庫存；節(jié)約算法；自適應(yīng)遺傳算法

VMI模式是供應(yīng)鏈管理大環(huán)境下上下游企業(yè)緊密合作產(chǎn)生的一種運(yùn)作方式，主要是供應(yīng)商通過對(duì)下游企業(yè)銷售資料的分析進(jìn)行原材料配送，抑制“牛鞭效應(yīng)”，達(dá)到“零庫存”效果。而在供應(yīng)鏈管理庫存模式下帶時(shí)間窗約束的路徑規(guī)劃一直是一個(gè)熱門問題，因?yàn)楦咝Ш侠淼木€路規(guī)劃能提高配送效率及合作的緊密性，降低成本，對(duì)企業(yè)來說具有重大意義。

近年來對(duì)VMI模式和VRPTW問題有很多學(xué)者進(jìn)行了大量的深入研究，在針對(duì)VMI模式的研究中，康凱等[1]通過建立Stackelberg博弈模型分析了庫存補(bǔ)貼及零售商預(yù)付款策略的適用范圍和對(duì)供應(yīng)鏈績效的影響，對(duì)提高資金受限的供應(yīng)鏈整體績效有很大的意義；劉云志等[2]利用不公平厭惡模型分析了模糊需求下考慮供應(yīng)商存在偏好的二級(jí)VMI供應(yīng)鏈協(xié)調(diào)問題；羅嶺[3]通過建立帶有庫存成本變化的EOQ模型研究了受庫存成本變化的VMI系統(tǒng)的最優(yōu)協(xié)議問題等，解決了庫存成本變化下如何實(shí)現(xiàn)VMI供應(yīng)鏈協(xié)調(diào)的問題。而在解決VRPTW問題方面大多數(shù)學(xué)者采用了一些啟發(fā)式算法從優(yōu)化的角度進(jìn)行研究，其中李珍萍等[4]利用Gurobi求解器對(duì)算例進(jìn)行求解，表明了VMI模式下配送線路有效規(guī)劃能夠降低庫存和配送成本，并利用貪婪算法與Gurobi求解器對(duì)比，證明了貪婪算法能夠在最短的時(shí)間內(nèi)得到較優(yōu)的配送路線規(guī)劃方案；LI等[5]提出了一種由貪婪算法改進(jìn)的禁忌搜索算法（improved tabu search, I-TS）來解決具有軟時(shí)間窗和隨機(jī)出行服務(wù)時(shí)間的車輛路徑問題，并用實(shí)例驗(yàn)證了其優(yōu)越性；FAZI等[6]將貪婪算法與局部搜索法相結(jié)合構(gòu)建了一種混合局部搜索元啟發(fā)式算法用來解決海上集裝箱駁船運(yùn)輸問題；劉輝[7]、朱永強(qiáng)[8]和SONG[9]等在蟻群算法的基礎(chǔ)上進(jìn)行了改進(jìn)，使改進(jìn)后的蟻群算法在路徑規(guī)劃尋優(yōu)能力上有了較大的提升；胡卉等[10]提出了一種帶有回火與緩冷操作的改進(jìn)模擬退火算法對(duì)受推動(dòng)式生產(chǎn)調(diào)度影響的物資配送規(guī)劃模型進(jìn)行求解，對(duì)比傳統(tǒng)的模擬退火算法結(jié)果更穩(wěn)定且更好；裴時(shí)域[11]、CRUZ-CHáVEZ[12]等也將改進(jìn)后的模擬退火算法分別運(yùn)用到物流配送中心選址和調(diào)度問題中，提供了新的解決方案；綜上所述，雖然針對(duì)VMI模式和VRPTW問題學(xué)者們已經(jīng)進(jìn)行了大量研究，但針對(duì)VMI模式下車輛配送路徑規(guī)劃方向的研究少之又少；為此本文預(yù)建立一種具有碳排放成本、時(shí)間窗和容量約束等多目標(biāo)約束的線性規(guī)劃模型，并提出了一種混合式自適應(yīng)遺傳算法，該算法相比傳統(tǒng)啟發(fā)式算法優(yōu)化了初始解隨機(jī)性大、算法全局搜索能力差、容易陷入局部最優(yōu)解的困局等問題，經(jīng)驗(yàn)證具有很好的使用效果。

1 模型建立

1.1 問題描述

基本假設(shè)：

VRPTW問題是一個(gè)NP-Hard問題，為簡化問題，作出以下假設(shè)：

（1）車輛從供應(yīng)商出發(fā)，完成任務(wù)后空載返回供應(yīng)商；

（2）單個(gè)顧客的需求量由單車輛配送且一次性滿足需求；

（3）車輛的運(yùn)輸成本與車輛行駛距離系線性相關(guān)；

（4）單條線路的最大需求量不大于單輛車的最大載重量；

（5）車輛在配送過程中勻速行駛，不受其他條件影響；

（6）車輛返回供應(yīng)商的時(shí)間不能超過供應(yīng)商要求完成服務(wù)的終點(diǎn)時(shí)刻。

1.2 參數(shù)定義

相關(guān)參數(shù)定義：

決策變量：

1.3 模型構(gòu)建

2 算法設(shè)計(jì)

2.1 相關(guān)算法概述

2.1.1 自適應(yīng)遺傳算法

遺傳算法（genetic algorithm, GA）是John Holland受物種進(jìn)化原理啟發(fā)產(chǎn)生的一種優(yōu)化方法，原理是在種群進(jìn)化中，只有適應(yīng)能力強(qiáng)的個(gè)體才會(huì)遺傳下去。AGA是基于傳統(tǒng)遺傳算法固定的遺傳算子在種群進(jìn)化期初能有效篩選較差個(gè)體，但隨著種群進(jìn)化，后期同樣會(huì)對(duì)較好的解產(chǎn)生破壞，從而導(dǎo)致算法收斂速度慢，易“早熟”的現(xiàn)象提出的一種改進(jìn)算法，AGA能夠在種群迭代中自適應(yīng)的調(diào)節(jié)交叉和變異概率，極大提高了算法收斂的速度。

2.1.2 節(jié)約算法

節(jié)約算法是Clarke和Wright提出的一種以最短運(yùn)輸里程為目標(biāo)的路徑規(guī)劃方法，又稱C-W算法，原理是在滿足用戶到貨時(shí)間要求和車輛載重要求前提下，通過路徑的合并使配送總路徑距離減小的幅度最大，是一種解決車輛合理調(diào)配的啟發(fā)式算法。

2.1.3 大規(guī)模鄰域搜索法

LNS算法是局部搜索法的一種，主要是運(yùn)用Destroy和Repair的思想，利用Removed和Re-inserting方式隨機(jī)選擇幾個(gè)配送點(diǎn)對(duì)線路進(jìn)行破壞，將選擇的配送點(diǎn)從線路里面拿掉，剩下的配送點(diǎn)依次排序保存，然后再用修復(fù)的方法將選擇出的配送點(diǎn)隨機(jī)插入被破壞的線路中，從中選出最好的解。破壞方法通常包含隨機(jī)性的元素，以便在每次調(diào)用破壞方法時(shí)破壞線路的不同部分。

2.2 混合自適應(yīng)遺傳算法

為解決VMI模式下VRPTW問題，本文創(chuàng)造性提出了一種混合自適應(yīng)遺傳算法（CW-AGA-LNS），具體流程如圖1所示。該算法首先引入了節(jié)約算法來構(gòu)造符合時(shí)間窗和載重容量約束的遺傳算法初始解，降低了遺傳算法隨機(jī)生成初始解的隨機(jī)性，使算法能夠快速收斂；然后引入具有自適應(yīng)的交叉變異概率的AGA，提高進(jìn)化前期的搜索能力和后期的收斂速度；最后引入了LNS算法，對(duì)交叉變異后的結(jié)果進(jìn)行破壞和修復(fù)操作后進(jìn)行局部搜索，進(jìn)一步提高算法的全局尋優(yōu)能力。

圖1 CW-AGA-LNS算法流程圖

2.2.1 編碼

2.2.2 構(gòu)造種群初始解

采用C-W算法構(gòu)造種群初始解：

步驟1 將所有顧客與供應(yīng)商相連，只含有一個(gè)配送起點(diǎn)，計(jì)算總費(fèi)用；

步驟2 將路徑融合后的距離節(jié)約值降序排列，節(jié)約值越大，說明并線后路程節(jié)約越多；

步驟3 如果線路周圍還有其他客戶，在滿足時(shí)間窗和載重約束下按照里程節(jié)約大小插入巡回路線，直到不能融合為止；

步驟4 以同樣的方法融合第二條線路；

步驟5 判斷是否還存在只有一個(gè)顧客的線路，如果有，重復(fù)上述步驟，否則輸出每條線路的顧客序列號(hào)。

2.2.3 計(jì)算種群適應(yīng)度

2.2.4 選擇操作

圖2 隨機(jī)遍歷抽樣選擇法示意圖

2.2.5 自適應(yīng)交叉和變異操作

在GA中交叉概率P和變異概率P是衡量算法性能的關(guān)鍵性指標(biāo)，P值越大，新染色體產(chǎn)生速度就越快，但過大時(shí)會(huì)破壞整個(gè)遺傳模式，P過小會(huì)使整個(gè)搜索過程進(jìn)程緩慢；而P值越大，對(duì)優(yōu)質(zhì)解的破環(huán)概率越大，P過小時(shí)產(chǎn)生新的染色體結(jié)構(gòu)概率較小。本文采用的是任子武等[13]改進(jìn)后的自適應(yīng)交叉變異概率，如式(16)和式(17)所示。

（1）交叉操作。采用改進(jìn)的OX交叉方式，具體操作如圖3所示。原理是在待交叉兩條染色體上隨機(jī)產(chǎn)生兩個(gè)交叉位點(diǎn)，將交叉位點(diǎn)的個(gè)體提出來放在另一個(gè)染色體的前面和后面，然后刪除交叉片段外的重復(fù)片段。改進(jìn)后的交叉方式在面對(duì)兩個(gè)同樣的待交叉染色體也能產(chǎn)生新的子代個(gè)體，對(duì)保持種群的多樣性有一定作用。

圖3 改進(jìn)OX交叉流程圖

圖4 變異操作流程圖

2.2.6 局部搜索操作

（1）Removed操作。隨機(jī)選取個(gè)顧客，將其從所有顧客中逐一摘選出來，具體過程為：

步驟1 隨機(jī)選擇一個(gè)顧客，將其從原顧客集中移除出來，保存到被移除顧客集合之中；

步驟2 計(jì)算該被移除顧客與剩余其他顧客的相關(guān)性值；

步驟3 將剩余顧客按照與被移除顧客的相關(guān)性值大小從高到低排列，再從中隨機(jī)選取下一個(gè)顧客移除出來，重復(fù)上述操作，選出個(gè)顧客為止；

步驟4 保存被移除顧客合集和剩余顧客的排序。

（2）Re-inserting操作。將被移出的所有顧客重新插入到各個(gè)線路中去，采用最遠(yuǎn)插入啟發(fā)式，即將最小插入距離增量最大的元素找出來；首先找出滿足時(shí)間窗和載重約束的所有插入點(diǎn)，再計(jì)算所有插入點(diǎn)的距離增量；然后找出各顧客距離增量最小的最佳插入點(diǎn)，并記錄距離增量；最后將對(duì)應(yīng)距離增量最大的顧客插入到所在位置。該循環(huán)需要進(jìn)行次，直到所有被移出的顧客全部插入各條線路中。

2.2.7 終止操作

當(dāng)種群迭代次數(shù)達(dá)到最大值時(shí)，結(jié)束循環(huán)操作，輸出最終解。

3 算法仿真

為有效驗(yàn)證CW-AGA-LNS算法在求解VRPTW問題的可行性和有效性，本文運(yùn)用MATLAB R2018a軟件并采用綜合算例對(duì)比分析和具體算例對(duì)比分析的方式進(jìn)行算例驗(yàn)證。

3.1 測試算例介紹

本文采用Solomon在研究VRPTW問題提出的Solomon案例集進(jìn)行驗(yàn)證。該案例集每個(gè)案例包括客戶的坐標(biāo)集、接受服務(wù)的時(shí)間窗、客戶點(diǎn)需求量、車輛最大載重和最大使用車輛數(shù)等，同時(shí)分為R、C、RC三種類型，每種類型又分為兩種系列，具體特點(diǎn)為R型算例客戶坐標(biāo)點(diǎn)由均勻分布產(chǎn)生，C型算例客戶坐標(biāo)集由結(jié)構(gòu)性分布產(chǎn)生，RC型算例是二者的混合分布形式。其中具體系列特征如表1所示。

表1 Solomon案例集典型算例特征

3.2 綜合算例對(duì)比分析

根據(jù)多次驗(yàn)證結(jié)果，算法具體參數(shù)為種群規(guī)模為150，最大迭代次數(shù)為600代，自適應(yīng)交叉和變異概率借鑒文獻(xiàn)[13]多次試驗(yàn)結(jié)果設(shè)定為P10.9,P20.6, P10.1,P=0.01。

選取Solomon算例集中幾個(gè)典型類型的數(shù)據(jù)分別用AGA和CW-AGA-LNS算法進(jìn)行分別多次驗(yàn)證進(jìn)行橫向?qū)Ρ?，具體結(jié)果如表2所示，可以看出無論面對(duì)何種類型的客戶，CW-AGA-LNS所得出的結(jié)果都明顯優(yōu)于AGA，從各個(gè)算例達(dá)到迭代最優(yōu)解的迭代代數(shù)可以看出后者收斂速度較慢，容易陷入“早熟”。

表2 算法橫向?qū)Ρ冉Y(jié)果

3.3 具體算例對(duì)比分析

為了具體體現(xiàn)CW-AGA-LNS算法的性能，減少誤差，分別利用AGA和CW-AGA-LNS算法對(duì)C105案例進(jìn)行多次求解求平均值，將兩種算法進(jìn)行縱向?qū)Ρ确治?。根?jù)C類型算例的多次驗(yàn)證結(jié)果，C類型算例無論是CW-AGA-LNS或AGA都能在迭代200代以內(nèi)得到最優(yōu)結(jié)果，所以此時(shí)算法的具體參數(shù)可以設(shè)置為種群規(guī)模為150，最大迭代次數(shù)為200代，P10.9,P20.6, P10.1,P=0.01。

將兩種算法生成的種群初始解進(jìn)行對(duì)比，如表3所示。結(jié)果表明，C-W算法產(chǎn)生的種群初始解與隨機(jī)遍歷生成的初始解相比總行駛里程和成本更低，且不存在違反約束的現(xiàn)象，降低了遺傳算法隨機(jī)生成初始解的隨機(jī)性，使算法能夠快速收斂。

表3 AGA和CW-AGA-LNS算法初始解對(duì)比

圖5和圖6是AGA和CW-AGA-LNS算法最終的里程迭代圖，二者對(duì)比可以明顯看出后者算法初始解適應(yīng)度值較小，收斂速度明顯更快，在進(jìn)行第10次迭代時(shí)就達(dá)到了最優(yōu)解，而前者的初始解適應(yīng)度值比較高，在第47次迭代才達(dá)到最優(yōu)解。而且從迭代圖的曲線拐點(diǎn)多少也可以看出前者拐點(diǎn)更多，表明其尋優(yōu)過程中陷入局部最優(yōu)解的次數(shù)更多。

圖5 AGA里程迭代圖

圖6 CW-AGA-LNS里程迭代圖

兩種算法最終結(jié)果對(duì)比如表4所示，可以看出CW-AGA-LNS比AGA最終結(jié)果所使用車輛的數(shù)目、行駛里程和總成本都要少且差別顯著，前者效果更優(yōu)。

表4 AGA和CW-AGA-LNS算法最終結(jié)果對(duì)比

3.4 結(jié)果對(duì)比

通過綜合算例和具體算例的對(duì)比分析可以得出無論顧客分布屬于何種類型，本文提出的CW-AGA-LNS都能很好地解決問題，并且相比傳統(tǒng)的AGA結(jié)果更優(yōu)秀，收斂速度快，陷入局部最優(yōu)的次數(shù)更少；Solomon案例集幾乎涵蓋了所有的客戶分布和需求類型，從各類型算例驗(yàn)證結(jié)果也可以表明CW-AGA-LNS比AGA收斂速度快，陷入局部最優(yōu)的次數(shù)更少的結(jié)論并非偶然。這是因?yàn)镃W-AGA-LNS在初始解生成時(shí)能夠極大地降低初始解的隨機(jī)性，并且經(jīng)過改進(jìn)交叉方式和局部搜索的操作能夠加快算法收斂速度，增加算法的全局搜索能力。由此可見本文提出的CW-AGA-LNS在解決此類問題上更具實(shí)用性。

4 結(jié)論

本文主要是針對(duì)VMI模式下供應(yīng)商配貨路徑規(guī)劃所遇到的VRPTW問題進(jìn)行研究，建立了滿足多種約束條件的數(shù)學(xué)模型，并基于自適應(yīng)遺傳算法提出了一種混合式自適應(yīng)遺傳算法對(duì)模型進(jìn)行求解，通過MATLAB軟件將該算法與傳統(tǒng)自適應(yīng)遺傳算法進(jìn)行對(duì)比驗(yàn)證，得出該算法在解決此類VRPTW問題中效果更好，具有生成種群初始解的隨機(jī)性低，算法跳出局部最優(yōu)能力強(qiáng)，全局搜索能力強(qiáng)，收斂速度快等優(yōu)點(diǎn)且結(jié)果相比AGA效果更優(yōu)。但該研究也有一些不足之處，首先在實(shí)際情況中，供應(yīng)商在配貨路徑規(guī)劃上還會(huì)受到很多其他因素的影響，比如實(shí)時(shí)路況及車輛滿載情況對(duì)車輛速度和燃油的影響、實(shí)際線路距離可能比歐氏距離要短等，本文所建立的數(shù)學(xué)模型有待改善；其次，從仿真過程中可以發(fā)現(xiàn)加入了局部搜索操作雖然會(huì)增加算法的搜索能力，但也會(huì)導(dǎo)致算法運(yùn)行時(shí)間較長。這些都需要我們進(jìn)一步的研究。

[1] 康凱，高思穎，穆秀清. 基于VMI供應(yīng)商資金受限的供應(yīng)鏈協(xié)調(diào)策略[J]. 計(jì)算機(jī)工程與應(yīng)用，2020, 56(14): 264-271.

[2] 劉云志，樊治平. 模糊需求下考慮供應(yīng)商公平偏好的VMI供應(yīng)鏈協(xié)調(diào)[J]. 系統(tǒng)工程理論與實(shí)踐，2016, 36(07): 1661-1675.

[3] 羅嶺. 庫存成本變化的VMI供應(yīng)鏈協(xié)調(diào)[J]. 中國管理科學(xué)，2022, 30(10): 187-197.

[4] 李珍萍，焦鵬博. 基于供應(yīng)商管理庫存模式的配送路徑優(yōu)化問題[J]. 科學(xué)技術(shù)與工程，2021, 21(26): 11362-11367.

[5] LI G M, LI J H. An improved tabu search algorithm for the stochastic vehicle routing problem with soft time windows[J]. IEEE Access, 2020, (8): 158115-158124.

[6] FAZI S, FRANSOO J C, VAN WOENSEL T, et al. A variant of the split vehicle routing problem with simultaneous deliveries and pickups for inland container shipping in dry-port based systems[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 142: 102057.

[7] 劉輝，肖克，王京擘. 基于改進(jìn)蟻群算法的無人礦車路徑規(guī)劃研究[J]. 制造業(yè)自動(dòng)化，2021, 43(04): 108-112.

[8] 朱永強(qiáng)，孫宗濤. 改進(jìn)蟻群算法在物流機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 科學(xué)技術(shù)與工程，2020, 20(30): 12467-12471.

[9] SONG B Y, MIAO H M, XU L. Path planning for coal mine robot via improved ant colony optimization algorithm[J]. Systems Science & Control Engineering, 2021, 9(1): 283-289.

[10] 胡卉，劉富鑫，王愚勤，等. 基于改進(jìn)模擬退火算法的推動(dòng)式生產(chǎn)-配送協(xié)調(diào)優(yōu)化[J]. 運(yùn)籌與管理，2022, 31(02): 15-22.

[11] 裴時(shí)域，李元香. 改進(jìn)的模擬退火算法在物流配送中心選址中的應(yīng)用[J]. 統(tǒng)計(jì)與決策，2021, 37(09): 172-176.

[12] CRUZ-CHáVEZ M A, PERALTA-ABARCA J C, CRUZ-ROSALES M H. Cooperative threads with effective-address in simulated annealing algorithm to job shop scheduling problems[J]. Applied Sciences, 2019, 9(16): 3360.

[13] 任子武，傘冶. 自適應(yīng)遺傳算法的改進(jìn)及在系統(tǒng)辨識(shí)中應(yīng)用研究[J]. 系統(tǒng)仿真學(xué)報(bào)，2006(01): 41-43, 66.

Research on path planning based on hybrid adaptive genetic algorithm

CHENG Yuan-dong，YANG Qi-wei

(School of Economics and Management, Anhui University of Science and Technology, Anhui Huainan 232000, China)

To solve the vehicle routing problem with time window in vendor managed inventory mode, a mathematical model with multi-objective constraints is established considering various conditions, and a hybrid adaptive genetic algorithm is innovatively proposed. The hybrid adaptive genetic algorithm is based on the adaptive genetic algorithm, which adds the saving algorithm to construct the initial solution of the population, introduces the random traversal sampling method for selection operation, improves the crossover method of the algorithm, and finally uses the large neighborhood search to search for the variance. Finally, the large-scale neighborhood search is applied to destroy and repair the mutated population. The simulation experiments were conducted by MATLAB software, and the transportation cost was significantly reduced by 50% when compared with the traditional adaptive genetic algorithm. Accordingly, it was concluded that the hybrid adaptive genetic algorithm has stronger and more scientific global search and fast convergence capability in solving the VRPTW problem, in order to optimize the supplier vehicle distribution path planning more efficiently and reasonably.

vendor managed inventory；saving algorithm；adaptive genetic algorithm

2022-08-16

國家自然科學(xué)基金項(xiàng)目（71473001）；研究生創(chuàng)新基金項(xiàng)目（2022CX2159）

程元棟（1979-），男，山東泰安人，副教授，博士，主要從事物流系統(tǒng)工程研究，Andoncheng@foxmail.com。

楊齊威（1996-），男，河南周口人，碩士，主要從事配送路徑優(yōu)化研究，23606116@qq.com。

TP301.6

A

1007-984X(2023)01-0087-08