摘 要：針對(duì)帶可容忍時(shí)間窗的車輛路徑規(guī)劃問題建立最小化配送總成本的規(guī)劃模型，結(jié)合遺傳算法構(gòu)造改進(jìn)自適應(yīng)大鄰域搜索算法對(duì)該問題求解。利用遺傳算法構(gòu)建高質(zhì)量解開始自適應(yīng)大鄰域搜索尋優(yōu)，減小算法計(jì)算時(shí)間成本；加入3種破壞算子和3種修復(fù)算子，以增加種群多樣性；嵌入模擬退火接受準(zhǔn)則以一定概率接受較差解，自適應(yīng)更新破壞和修復(fù)算子權(quán)重，避免算法陷入局部最優(yōu)。選取Solomon標(biāo)準(zhǔn)測(cè)試集進(jìn)行3組實(shí)驗(yàn)，與已知最優(yōu)解比較距離成本驗(yàn)證算法可行性；在單邊容忍度時(shí)間窗模型下，與基礎(chǔ)ALNS算法對(duì)比驗(yàn)證算法改進(jìn)效果；在雙邊可容忍時(shí)間窗模型下，與相關(guān)文獻(xiàn)的最優(yōu)結(jié)果對(duì)比。實(shí)驗(yàn)結(jié)果表明，提出的GA-ALNS算法改進(jìn)效果較為顯著，求得的最優(yōu)解同其他算法相比優(yōu)化率較好，計(jì)算得到的最優(yōu)方案能實(shí)現(xiàn)更低的車輛配送總成本，具有一定的可行性和有效性。

關(guān) 鍵 詞：氧化鈷; 納米結(jié)構(gòu); 電容器; 電催化可容忍時(shí)間窗； 車輛路徑規(guī)劃問題； 自適應(yīng)大鄰域搜索算法； 遺傳算法； 模擬退火接受準(zhǔn)則

中圖分類號(hào)：TP18；U116.2 文獻(xiàn)標(biāo)志碼：A

doi：10.3969/j.issn.1673-5862.2024.03.014

GA-ALNS algorithm for solving VRP with tolerable time window

CUI Song^1，2， LYU Yan^1，2， CHEN Lanfeng^1，2BAI Xueyuan， ZHANG Lei， LI Lin

（1. College of Physical Science and Technology， Shenyang Normal University， Shenyang 110034， China）（College of Science， Shenyang Aerospace University， Shenyang 110136， China ）

Abstract：To solve the vehicle routing problem with tolerable time window， establish a planning model minimizing the total cost， an improved adaptive large neighborhood search algorithm （GA-ALNS） is constructed with genetic algorithm to solve the problem. Use genetic algorithm to build high-quality solutions to start adaptive large neighborhood search optimization， reduce the time cost of calculation algorithm; add three destroy operators and three repair operators to increase the population diversity; embed the simulated annealing acceptance criterion to accept poor solutions with a certain probability， adaptive update destroy and repair operator weight， to avoid the algorithm falling into local optimum. The Solomon standard test set is selected for three experiments，and the distance cost is compared with the best known solution to verify the feasibility of the algorithm; compare with the basic ALNS algorithm and contrast with the optimal results of the relevant literature under the bilateral tolerance time window model. The experimental results show that the improvement effect of GA-ALNS is significant， and the optimal solution is better than other algorithms. The calculated optimal solution can achieve lower than the total cost of vehicle distribution， which has certain feasibility and effectiveness.

Key words：tolerable time window; vehicle routing problem; adaptive large neighborhood search algorithm; genetic algorithm; simulated annealing acceptance criterion

物流配送車輛的路徑規(guī)劃是電子商務(wù)的關(guān)鍵環(huán)節(jié)，為降低配送成本并增加商業(yè)盈利，需要進(jìn)行適當(dāng)?shù)穆窂揭?guī)劃。該問題是帶時(shí)間窗的車輛路徑規(guī)劃問題（vehicle routing problem with time window，VRPTW）的實(shí)際應(yīng)用，因現(xiàn)實(shí)中交通、天氣等不確定因素，軟時(shí)間窗相對(duì)于傳統(tǒng)硬時(shí)間窗更貼近實(shí)際配送情況。Solomon^［1］最先提出VRPTW，旨在滿足客戶需求的同時(shí)對(duì)配送路徑進(jìn)行優(yōu)化，以實(shí)現(xiàn)成本最小化。軟時(shí)間窗允許車輛可以不在客戶原本規(guī)定的時(shí)間窗內(nèi)到達(dá)，但遲到或早到時(shí)會(huì)受到相應(yīng)懲罰。

問題規(guī)模小、結(jié)構(gòu)簡(jiǎn)單的VRPTW可用精確算法求解。He等^［2］將客戶的不便成本設(shè)計(jì)成客戶服務(wù)開始時(shí)間的凸函數(shù)節(jié)點(diǎn)成本，用分支定界法求解。VRPTW是NP-Hard問題，計(jì)算量隨數(shù)據(jù)規(guī)模增大呈指數(shù)增長(zhǎng)，現(xiàn)多用啟發(fā)式與元啟發(fā)式算法求解。Saksuriya和Likasiri^［3］將粒子群算法與局部搜索、破壞和修復(fù)算子進(jìn)行結(jié)合，解決了帶客戶和服務(wù)商約束間的通用兼容匹配性的VRPTW。Shen等^［4］將蟻群算法和頭腦風(fēng)暴優(yōu)化算法結(jié)合，引入路徑間和路徑內(nèi)交換，求解了最小化總距離的路徑規(guī)劃問題。

為求解VRPTW，Yassen等^［5］在和聲搜索算法中加入模擬退火算法（simulated annealing，SA），克服了和聲搜索收斂緩慢的問題。Marinakis等^［6］提出多適應(yīng)粒子群算法，利用自適應(yīng)貪婪算法產(chǎn)生初始解，自適應(yīng)鄰域拓?fù)浣鉀Q了粒子移動(dòng)過程中的適應(yīng)性。韓亞娟等^［7］考慮客戶對(duì)服務(wù)時(shí)間的偏離有一定容忍度，制定折線軟時(shí)間窗模型，這個(gè)模型在客戶規(guī)定時(shí)間內(nèi)無懲罰成本，在可容忍限度內(nèi)有較少懲罰成本，在限度外，需付出較多的懲罰成本。劉爍佳和李學(xué)強(qiáng)^［8］根據(jù)時(shí)間窗參數(shù)調(diào)整客戶優(yōu)先級(jí)，利用改進(jìn)的節(jié)約算法和改進(jìn)的插入法分別對(duì)VRPTW求解，結(jié)果表明改進(jìn)的插入法能得到更好解。

Ropke和Pisinger^［9］提出自適應(yīng)大鄰域搜索（adaptive large neighborhood search，ALNS）算法，搜索過程中采用多種破壞和修復(fù)算子，每輪迭代只選擇一種，算子被選擇的概率與其歷史表現(xiàn)相關(guān)，且隨迭代更新。Krebs等^［10］研究帶三維加載約束的VRPTW，用混合自適應(yīng)大鄰域搜索算法結(jié)合內(nèi)部最深左下角填充解決集裝箱裝載問題，提出3種填充算法新變體，結(jié)果表明自由空間的填充算法更佳。Gu等^［11］利用ALNS算法解決商品受限的分批配送問題，加入了3種局部搜索算子。Li等^［12］研究同時(shí)取送貨的VRPTW，提出混合整數(shù)線性規(guī)劃模型，用ALNS算法解決大規(guī)模問題實(shí)例。Liang等^［13］研究有時(shí)間窗口和裝載調(diào)度的車輛路線問題，在ALNS算法中嵌入高效的可行性檢查機(jī)制，確定碼頭的裝載計(jì)劃和車輛訪問順序，以最小化總行駛距離。Chen等^［14］將自動(dòng)駕駛機(jī)器人配送加入送貨路線中，利用ALNS算法研究VRPTWDR，為自動(dòng)駕駛機(jī)器人替代最后一公里配送提供了解決方案。

基于上述研究，本文構(gòu)造了改進(jìn)的自適大鄰域搜索（GA-ALNS）算法求解帶可容忍時(shí)間窗的路徑規(guī)劃問題，利用遺傳算法（genetic algorithm，GA）構(gòu)建質(zhì)量較高的初始解，以減少算法計(jì)算時(shí)間成本；利用GA構(gòu)建的初始解開始ALNS算法的尋優(yōu)，加入3種破壞算子和3種修復(fù)算子增加種群多樣性，為種群生成新解；嵌入SA接受準(zhǔn)則更新算子權(quán)重，以一定概率接受較差解，避免算法陷入局部最優(yōu)。

1 問題描述及模型

1.1 問題描述

本文研究VRPTW，車輛從倉(cāng)庫(kù)出發(fā)，并在規(guī)定時(shí)間內(nèi)返回，對(duì)每個(gè)客戶進(jìn)行不重復(fù)服務(wù)，規(guī)劃車輛的路徑讓車輛在滿足所有客戶需求的同時(shí)，盡可能降低總成本。帶可容忍度的VRPTW定義在圖G（N，E）上，節(jié)點(diǎn)集為N={0，1，2，…，n}，節(jié)點(diǎn)0表示倉(cāng)庫(kù)，節(jié)點(diǎn){1，2，…，n}表示需服務(wù)的客戶點(diǎn)，節(jié)點(diǎn)i∈N/{0}的需求為q_i，從節(jié)點(diǎn)i到j(luò)的運(yùn)輸成本為C_ij，K為倉(cāng)庫(kù)中心所擁有的車輛集合，Q為車輛最大載重。t_i表示到達(dá)客戶i的時(shí)間，w_i表示在客戶i的等待時(shí)間，t_ij表示客戶i到客戶j的時(shí)間，e_i表示客戶i可以服務(wù)的最早時(shí)間，l_i表示客戶i可以服務(wù)的最晚時(shí)間，s_i表示在客戶i服務(wù)的時(shí)間，β是單位車輛固定使用成本，γ是車輛單位距離的運(yùn)輸成本。

1.2 帶可容忍的時(shí)間窗及懲罰函數(shù)設(shè)置

對(duì)于最佳服務(wù)時(shí)間窗的偏離，客戶有可容忍和不可容忍的區(qū)分。在傳統(tǒng)軟時(shí)間窗的基礎(chǔ)上考慮客戶容忍水平為α，提出帶可容忍的時(shí)間窗?？蛻羝诖龝r(shí)間窗（e_i，l_i）加入容忍水平α后時(shí)間窗為（_i，_i），其中_i=e_i－α_is_i，_i=l_i+α_is_i，i=1，2，…，N。與傳統(tǒng)軟時(shí)間窗不同，該時(shí)間窗可以在滿足客戶需求的同時(shí)更好地合理配置優(yōu)化資源。帶可容忍時(shí)間窗下的懲罰函數(shù)成本為

其中，p₁，p₂，p₃，p₄為懲罰函數(shù)系數(shù)，應(yīng)該滿足p₁gt;p₂，p₃gt;p₂，p₃lt;p₄，p₁lt;p₄。

1.3 數(shù)學(xué)模型建立

VRPTW的數(shù)學(xué)模型可描述如下：

MinZ=γ∑k∈K∑i∈N∑j∈NC_ijx^k_ij+β∑k∈K∑j∈Nx_0jk+∑k∈K∑i∈NP（T^k_i）（2）

約束：

∑k∈K∑i∈Nx^k_ij=1j∈{1，2，…，n}，i≠j（3）

∑k∈K∑j∈Nx^k_ij=1i∈{1，2，…，n}，i≠j（4）

∑i∈N∑j∈Nx^k_ijq_i≤Qk∈K（5）

∑j∈Nx^k_ij=∑j∈Nx^k_jii=0，k∈K（6）

t₀=w₀=s₀=0（7）

∑Kk=1∑ni=0，i≠jx^k_ij（t_i+t_ij+s_i+w_i）=t_j j∈（1，2，…，n）（8）

e_i≤（t_i+w_i）≤l_i i∈（1，2，…，n）（9）

x^k_ij=1車輛k從節(jié)點(diǎn)i到節(jié)點(diǎn)j（i≠j）

0其他（10）

目標(biāo)函數(shù)式（2）為服務(wù)完所有客戶點(diǎn)后包括車輛固定使用成本、車輛行駛總成本和懲罰成本在內(nèi)的最小車輛總運(yùn)輸成本，式（3）和式（4）保證每個(gè)節(jié)點(diǎn)僅被訪問一次，式（5）保證運(yùn)輸過程中車輛載重不得超過最大載重，式（6）保證車輛從倉(cāng)庫(kù)中心出發(fā)并回到倉(cāng)庫(kù)中心，式（7）～（9）是時(shí)間窗約束。

2 問題求解

本文構(gòu)建GA-ALNS算法，先用GA高效構(gòu)建初始解，把GA搜尋的最優(yōu)解作為ALNS算法初始解；繼而用3種破壞算子移除客戶點(diǎn)，用3種修復(fù)算子將移除客戶重新插回路徑，生成新解，破壞和修復(fù)算子可以擴(kuò)大搜索解的空間，改進(jìn)當(dāng)前解，增大尋找到最優(yōu)解的可能性；最后，根據(jù)SA接受準(zhǔn)則判斷是否接受新解，按一定概率接受差解，避免陷入局部最優(yōu)。在迭代過程中，自適應(yīng)更新算子得分權(quán)重，利用輪盤賭選擇算子選擇本輪迭代所使用的算子，更多使用歷史表現(xiàn)優(yōu)良算子，找到更優(yōu)的解決方案。

2.1 遺傳算法構(gòu)造初始解

基礎(chǔ)ALNS算法的初始解是隨機(jī)生成的，為減少迭代次數(shù)，避免算法時(shí)間成本過大，本文使用GA進(jìn)行初始解構(gòu)建，增大找到更好解的概率，降低算法耗時(shí)成本。利用GA生成初始解的步驟如下：

1）車輛從倉(cāng)庫(kù)出發(fā)隨機(jī)選擇客戶服務(wù)，并將該客戶點(diǎn)從待服務(wù)列表USL中刪除，以免重復(fù)服務(wù); 2）將選中客戶加入該路徑; 3）判斷服務(wù)該客戶后的車輛是否超載，若未超載則重復(fù)1）和2），否則車輛返回倉(cāng)庫(kù)，并派出下一輛車?yán)^續(xù)服務(wù); 4）重復(fù)操作，直至數(shù)據(jù)集內(nèi)所有客戶點(diǎn)都被服務(wù)完。

上述步驟每進(jìn)行一次得到一個(gè)可行解，多次重復(fù)后得到初始種群，計(jì)算種群中每個(gè)解的目標(biāo)函數(shù)值，利用錦標(biāo)賽選擇算子選擇優(yōu)良個(gè)體進(jìn)行交叉變異操作。在錦標(biāo)賽選擇中，從種群中隨機(jī)有放回地抽取任意TOS個(gè)個(gè)體，選最優(yōu)個(gè)體進(jìn)入下一代，當(dāng)該個(gè)體的適應(yīng)度優(yōu)于其他TOS-1個(gè)“競(jìng)爭(zhēng)者”時(shí)才能贏得錦標(biāo)賽。在該過程中最差的個(gè)體永遠(yuǎn)不會(huì)幸存，而最優(yōu)個(gè)體總是能獲勝。

對(duì)優(yōu)良個(gè)體進(jìn)行部分匹配交叉（partially mapped crossover，PMX）操作，可挖掘種群多樣性，克服啟發(fā)式算法易陷入局部最優(yōu)解的問題。根據(jù)給定交叉率（probability of crossover，PC）在優(yōu)良個(gè)體中選取父代染色體進(jìn)行PMX操作，交叉后得到2個(gè)子代，計(jì)算2個(gè)子代對(duì)應(yīng)的目標(biāo)函數(shù)值，若出現(xiàn)目標(biāo)函數(shù)更小的解則更新父代，否則不更新。二元變異可以維持種群多樣性，一定程度上克服算法易陷入局部最優(yōu)的缺陷。根據(jù)給定變異率（probability of mutation，MU）在區(qū)間（0，1）內(nèi)產(chǎn)生隨機(jī)數(shù)，當(dāng)該隨機(jī)數(shù)小于MU時(shí)，利用變異算子產(chǎn)生新可行解加入新種群。當(dāng)達(dá)到迭代次數(shù)后，選擇遺傳算法找到的最優(yōu)解作為ALNS的初始解進(jìn)行后續(xù)操作。

2.2 破壞算子

本文應(yīng)用3種破壞算子將客戶從當(dāng)前解中移除，移除客戶后將客戶存放在破壞算子列表（destroy list，DL）中，等待后續(xù)修復(fù)算子對(duì)其進(jìn)行操作。下面介紹這3種破壞算子。

1）random destroy

random destroy從當(dāng)前解中隨機(jī)選擇并移除f個(gè)客戶點(diǎn)。該破壞算子的優(yōu)點(diǎn)是計(jì)算速度快，并通過引入隨機(jī)性幫助算法跳出局部最優(yōu)。隨機(jī)移除的操作可以增加ALNS算法的隨機(jī)性，增加種群多樣性，避免算法陷入局部最優(yōu)解。

2）worst destroy

worst destroy的核心思想是將當(dāng)前解中位置不合適的客戶移除，通過計(jì)算客戶點(diǎn)從當(dāng)前解移除后的節(jié)約成本判斷客戶點(diǎn)的合適程度，節(jié)約成本越高代表該客戶在當(dāng)前解的位置越不合適。TC^a_i和TC^b_i分別代表該客戶被移除前后的當(dāng)前解成本，ΔTZ越大，說明將該客戶移除后節(jié)省的成本越高。

ΔTZ=TZ^b_i－TZ^a_i（11）

計(jì)算所有客戶的ΔTZ，并從高到低進(jìn)行排序，按該順序移除客戶。為了增加算子的隨機(jī)性，移除個(gè)數(shù)在（wor_d_min，wor_d_max）中均勻抽取。該算子可以將部分使成本增多的客戶移除，從而達(dá)到減少總成本的目的。

3）related destroy

related destroy根據(jù)客戶間的相關(guān)度η_ij將客戶成對(duì)進(jìn)行移除，相關(guān)度計(jì)算公式如下：

η_ij=d_ij+（l_i－l_j）+（e_i－e_j）2（12）

先隨機(jī)選擇一個(gè)客戶i進(jìn)行移除，接下來計(jì)算其他客戶與i的相似度并按降序排列，從相似度高的客戶開始移除操作，直至移除足量客戶。

2.3 修復(fù)算子

下面介紹的3種修復(fù)算子將DL中客戶重新插入到解中。

1）greedy repair

greedy repair將被移除客戶插入到最好路徑的最佳位置，計(jì)算客戶i插入路徑rou_r的位置loc_q的插入成本，Δ_i=ΔI（i，r，q）=d_i，q+d_q，i+1－d_i，i+1，將客戶i插入最佳位置bestloc_q。若所有剩余要插入的客戶沒有了可行的插入位置，則生成一條新的路徑，直至所有被移除客戶都重新插回路徑中，最終得到新解。

2）regret repair

regret repair按照客戶插入成本后悔值大小來決定客戶點(diǎn)的插入位置，直至將DL中的客戶點(diǎn)都重新插入新解中。后悔值是客戶點(diǎn)在最佳插入位置和次佳插入位置之間的成本差異，二者差異越大，后悔值越大，代表如果不在當(dāng)前位置進(jìn)行插入，則未來進(jìn)行插入操作花費(fèi)的成本會(huì)更高，從而感到后悔。后悔值reg_i的計(jì)算公式如下：

reg_i=IZ^2nd_i-IZ^1st_i（13）

計(jì)算客戶點(diǎn)在每個(gè)可插入位置的后悔值，選擇后悔值最高的位置進(jìn)行插入，循環(huán)迭代直至所有客戶都被插入，得到新解。

3）random repair

random repair隨機(jī)將客戶從DL中插回解的某條路徑內(nèi)，直至DL中的所有客戶點(diǎn)都重新插入到路徑中，以產(chǎn)生新解。

2.4 接受準(zhǔn)則和算子權(quán)重更新

若在尋優(yōu)過程中只接受優(yōu)解，則算法容易陷入局部最優(yōu)。為避免該情況發(fā)生，利用模擬退火算法，允許一定差解被接受，退火過程中按照Metropolis準(zhǔn)則以一定概率接受較差解，接受概率隨著溫度下降而減少。本文制定SA接受準(zhǔn)則：若產(chǎn)生新解的總成本小于最優(yōu)解，則接受該解，并將最優(yōu)解和當(dāng)前解都更新；若新解的總成本大于最優(yōu)解但小于當(dāng)前解的總成本，則接受該解，并將當(dāng)前解更新；若新解的總成本大于當(dāng)前解總成本，則以一定概率接受新解，概率計(jì)算如下：

RE_p=e^（Z_cur－Z_new）/TEM（14）

其中：Z_cur和Z_new分別為當(dāng)前解和新解的總成本；e為自然常數(shù)；TEM為當(dāng)前溫度，溫度以冷卻速率ΔTEM下降，初始溫度為TEM₀，終止溫度為TEM_e。

考慮各破壞算子和修復(fù)算子探索解的能力不同，結(jié)合SA接受準(zhǔn)則更新算子得分權(quán)重，并利用輪盤賭算法選擇破壞算子和修復(fù)算子。初始時(shí)，所有算子的得分權(quán)重相同，在迭代過程中按表1更新算子得分，以便增大能發(fā)現(xiàn)優(yōu)解和新解的算子的得分權(quán)重。算子探索解的能力影響算子的分值，并直接決定了算子權(quán)重，通過算子權(quán)重決定迭代過程中該算子被選中的概率。在迭代過程中，GA-ALNS算法可以根據(jù)算子的性能自適應(yīng)地調(diào)整算子權(quán)重，強(qiáng)化搜索。

3 實(shí)驗(yàn)結(jié)果及分析

本文對(duì)Solomon標(biāo)準(zhǔn)算例進(jìn)行了3組實(shí)驗(yàn)：第1組利用18組實(shí)例，計(jì)算硬時(shí)間窗下的車輛行駛距離，同Solomon標(biāo)準(zhǔn)算例集公布的最優(yōu)解進(jìn)行比較，測(cè)試本文提出的GA-ALNS算法的求解效果，驗(yàn)證該算法的可行性；第2組使用基礎(chǔ)的ALNS算法和GA-ALNS算法在單邊可容忍時(shí)間窗模型下對(duì)18組實(shí)例進(jìn)行求解并對(duì)比2種算法的結(jié)果，分析GA-ALNS算法的提升效果；第3組利用GA-ALNS算法在雙邊可容忍時(shí)間窗模型下首先對(duì)9組數(shù)據(jù)求解并同何美玲等^［15］的IACO算法的結(jié)果比較，再比較IACO算法、韓亞娟等^［7］的算法和GA-ALNS算法在計(jì)算客戶數(shù)量為25對(duì)的R101實(shí)例時(shí)的計(jì)算結(jié)果。

實(shí)驗(yàn)抽取三大類兩小類共6種不同類型集群中的不同數(shù)量客戶的實(shí)例，其中R1和R2型客戶隨機(jī)分布，C1和C2客戶集群分布，RC1和RC2是以上2種的混合。算例集R1，C1和RC1的車輛載重、調(diào)度范圍較小，時(shí)間窗較緊湊；算例集R2，C2和RC2的車輛載重、調(diào)度范圍較大，時(shí)間窗較寬。

本文參數(shù)設(shè)置：GA最大迭代次數(shù)為200，ALNS算法迭代10輪，每輪20次，容忍度水平α=0.5，SA接受準(zhǔn)則中TEM₀=100，TEM_e=0.017，ΔTEM=0.75，目標(biāo)函數(shù)中所用參數(shù)同文獻(xiàn)［14］，車輛單位距離運(yùn)輸成本γ=8，單位車輛固定使用成本β=60，懲罰函數(shù)中懲罰系數(shù)p₁=1，p₂=0.5，p₃=1.5，p₄=2，算子參數(shù)ran_min=0.1，ran_max=0.4，wor_min=0.2×C，wor_max=0.4×NC。

3.1 硬時(shí)間窗下的距離比較

本實(shí)驗(yàn)時(shí)間窗設(shè)置為硬時(shí)間窗，不允許提前或推遲服務(wù)。使用GA-ALNS算法對(duì)每個(gè)實(shí)例計(jì)算在硬時(shí)間窗下解決方案的總行駛距離，取10次計(jì)算中的最優(yōu)結(jié)果同公布的最優(yōu)解進(jìn)行比較，其中NV代表車輛數(shù)目，NC代表客戶數(shù)量，Distance表示解決方案的總行駛距離，得到結(jié)果見表2。從表 2中可以看出：對(duì)于客戶數(shù)量為25的算例，本文算法計(jì)算出的最優(yōu)解與已知最優(yōu)解一致；對(duì)于客戶數(shù)量為50的算例，除R201和RC101外本文算法都達(dá)到已知最優(yōu)解；對(duì)于客戶數(shù)量為100的算例，本文算法求得的解與已知最優(yōu)解相比總距離稍長(zhǎng)，但結(jié)果相差較小，誤差范圍在5%以內(nèi)，所需車輛數(shù)相同，說明利用本文GA-ALNS算法求解帶可容忍時(shí)間窗車輛路徑規(guī)劃問題的可行性。

3.2 單邊可容忍時(shí)間窗模型下的實(shí)驗(yàn)結(jié)果

將時(shí)間窗設(shè)為單邊可容忍時(shí)間窗，即只允許提前服務(wù)客戶，且有相應(yīng)懲罰成本，計(jì)算包含車輛固定使用成本、車輛行駛成本和懲罰成本的總成本。用基礎(chǔ)ALNS算法和GA-ALNS算法分別對(duì)18組數(shù)據(jù)運(yùn)行10次，選成本最小的結(jié)果（表3），其中優(yōu)化程度（develop，DEV）表示2種算法結(jié)果相比成本的優(yōu)化率。

由表3可以看出，優(yōu)化效果最好的R101-100實(shí)例優(yōu)化率達(dá)到30.2%，效果最差的C201-25實(shí)例優(yōu)化率也達(dá)到0.7%，說明不論客戶數(shù)量多少，GA-ALNS算法的結(jié)果都優(yōu)于ALNS算法，改進(jìn)效果顯著。

3.3 雙邊可容忍時(shí)間窗模型下的實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)中，時(shí)間窗為雙邊可容忍時(shí)間窗，允許提前或延后服務(wù)客戶，若不在規(guī)定時(shí)間窗服務(wù)，則按照懲罰函數(shù)的設(shè)置付出相應(yīng)的懲罰成本，進(jìn)而計(jì)算包含車輛固定使用成本、車輛行駛成本和懲罰成本的總成本。本文的GA-ALNS算法對(duì)9組數(shù)據(jù)分別運(yùn)行10次，選成本最小的結(jié)果與何美玲等^［15］的IACO算法公布的最優(yōu)解進(jìn)行比較（表4），其中NC表示客戶數(shù)量，DEV表示二者相比GA-ALNS計(jì)算結(jié)果的優(yōu)化率。

表 4表明二者最優(yōu)解的比較結(jié)果優(yōu)化率都是負(fù)數(shù)，且優(yōu)化效果較為顯著，優(yōu)化效果最多的C201-50實(shí)例優(yōu)化率達(dá)到了38.6%，除優(yōu)化率為1.7%的RC201-100實(shí)例外，其他實(shí)例的優(yōu)化率都在10%～37%，說明不論客戶數(shù)量大小，GA-ALNS算法的計(jì)算結(jié)果都優(yōu)于IACO算法。

表5為IACO^［15］算法、韓亞娟等^［7］的算法和GA-ALNS算法分別對(duì)客戶數(shù)量為25的R101實(shí)例計(jì)算的最優(yōu)結(jié)果比較。其中無懲罰成本包括車輛固定使用成本和車輛行駛距離成本，NV表示車輛數(shù)目。結(jié)果表明，雖然IACO算法最優(yōu)解的無懲罰成本最低，但GA-ALNS算法的最優(yōu)解總成本最低，說明該算法在解決帶可容忍時(shí)間窗的VRP時(shí)有一定優(yōu)勢(shì)。

4 結(jié) 語(yǔ)

本文針對(duì)帶可容忍時(shí)間窗的車輛路徑規(guī)劃問題構(gòu)建了GA-ALNS算法，利用遺傳算法高效構(gòu)建了ALNS算法的初始解，降低了計(jì)算時(shí)間成本；結(jié)合3種破壞算子移除路線中的客戶點(diǎn)，利用3種修復(fù)算子將客戶重新插入回路徑，生成新的解決方案，擴(kuò)大了解空間，增大了搜尋最優(yōu)解的可能性。嵌入模擬退火接受準(zhǔn)則按一定概率接受差解，避免算法陷入局部最優(yōu)，在迭代過程中，自適應(yīng)更新算子得分權(quán)重，更多地使用歷史表現(xiàn)優(yōu)良的算子，最終找到了最佳的路徑規(guī)劃方案。

利用Solomon測(cè)試集驗(yàn)證算法的改進(jìn)效果和可行性、有效性，實(shí)驗(yàn)結(jié)果表明：本文算法在硬時(shí)間窗下能得到與已知最優(yōu)解相同或十分接近的解；在單邊容忍時(shí)間窗模型下，不論客戶數(shù)量多少，同基礎(chǔ)ALNS算法相比，GA-ALNS算法都能得到更好解，顯著降低了配送總成本，改進(jìn)效果顯著；在雙邊容忍時(shí)間窗模型下，與IACO算法^［15］最優(yōu)解進(jìn)行比較，9組數(shù)據(jù)運(yùn)行結(jié)果都能得到總成本更小的解；IACO^［15］算法、韓亞娟等^［7］的算法和GA-ALNS算法分別對(duì)客戶數(shù)量為25的R101實(shí)例計(jì)算，GA-ALNS算法也得到花費(fèi)總成本最低的解決方案，這表明該算法在解決帶容忍度時(shí)間窗的車輛路徑規(guī)劃問題時(shí)有一定優(yōu)勢(shì)。

參考文獻(xiàn)：

［1］KRAJCINOVIC D，F(xiàn)ONSEKA G U.The continuous damage theory of brittle materials［J］.J Appl Mech，1981，48（4）：809-824.

SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints［J］.Oper Res，1987，35（2）：254-265.

［2］HE Q，IRNICH S，SONG Y J.Branch-Cut-and-Price for the vehicle routing problem with time windows and convex node costs［J］.Transport Sci，2019，53（5）：1409-1426.

［3］SAKSURIYA P，LIKASIRI C.Hybrid Heuristic for vehicle routing problem with time windows and compatibility constraints in home healthcare system［J］.Appl Sci，2022，12（13）：6486.

［4］SHEN Y，LIU M D，YANG J，et al.A hybrid swarm intelligence algorithm for vehicle routing problem with time windows［J］.IEEE Access，2020，8：93882-93893.

［5］YASSEN E T，AYOB M，NAZRI M Z A，et al.A hybrid meta-Heuristic algorithm for vehicle routing problem with time windows［J］.Int J Artif Intell Tools，2015，24（6）：1550021.

［6］MARINAKIS Y，MARINAKI M，MIGDALAS A.A multi-adaptive particle swarm optimization for the vehicle routing problem with time windows［J］.Inf Sci，2019，481：311-329.

［7］韓亞娟，彭運(yùn)芳，魏航，等.超啟發(fā)式遺傳算法求解帶軟時(shí)間窗的車輛路徑問題［J］，計(jì)算機(jī)集成制造系統(tǒng)，2019，25（10）：2571-2579.

［8］劉爍佳，李學(xué)強(qiáng).基于啟發(fā)式帶時(shí)間窗的車輛路徑規(guī)劃問題求解［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2022，31（11）：275-281.

［9］ROPKE S，PISINGER D.An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows［J］.Transport Sci，2006，40（4）：455-472.

［10］KREBS C，EHMKE J F，Koch H.Effective loading in combined vehicle routing and container loading problems［J］.Comput Oper Res，2023，149：105988.

［11］GU W J，CATTARUZZA D，OGIER M，et al.Adaptive large neighborhood search for the commodity constrained split delivery VRP［J］.Comput Oper Res，2019，112：104761.

［12］LI W L，LI K P，RAM KUMAR P N，et al.Simultaneous product and service delivery vehicle routing problem with time windows and order release dates［J］.Appl Math Model，2021，89：669-687.

［13］LIANG Y J，WANG X，LUO Z X，et al.Integrated optimisation of loading schedules and delivery routes［J］.Int J Prod Res，2022，61（2）：1-18.

［14］CHEN C，DEMIR E，HUANG Y.An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots［J］.Eur J Oper Res，2021，294（3）：1164-1180.

［15］何美玲，魏志秀，武曉暉，等.基于改進(jìn)的蟻群算法求解帶軟時(shí)間窗的車輛路徑問題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2023，29（3）：1029-1039.

【責(zé)任編輯：溫學(xué)兵】