深度混合型鄰域搜索模型求解CVRP 問題

楊笑笑,陳智斌

（昆明理工大學(xué)理學(xué)院，昆明，650000）

車輛路徑問題（Vehicle Routing Problem，VRP）是組合最優(yōu)化問題中的經(jīng)典問題，帶容量的車輛路徑問題（Capacitated Vehicle Routing Problem，CVRP）是VRP 的主要變體之一，在智能交通、物流領(lǐng)域等有廣泛應(yīng)用［1］.CVRP 考慮的是帶容量的車隊(duì)為一系列客戶提供服務(wù)的最佳路線，要求車隊(duì)將貨物從倉庫運(yùn)輸?shù)街付蛻酎c(diǎn)，每個(gè)客戶只允許被訪問一次，其中車輛是同質(zhì)的且只能從倉庫出發(fā)，完成任務(wù)后需返回倉庫，目標(biāo)是使車隊(duì)完成所有任務(wù)的總路線最短［2］.先前求解組合最優(yōu)化問題的方法主要依賴傳統(tǒng)算法［3］，例如利用精確算法、近似算法或啟發(fā)式算法進(jìn)行求解.針對CVRP 問題的特點(diǎn)，國內(nèi)外學(xué)者設(shè)計(jì)了各種優(yōu)化算法對其進(jìn)行求解，其中應(yīng)用較多的是智能算法，如遺傳算法、鄰域搜索等.

高效的算法可以快速合理地規(guī)劃路線，減少路徑花費(fèi).在實(shí)際應(yīng)用中具有挑戰(zhàn)性的問題大多數(shù)是NP 難的，傳統(tǒng)算法在處理這類任務(wù)時(shí)會受到特定的限制（例如計(jì)算時(shí)間長、精度低等）.強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）在處理自然語言處理問題上的最新進(jìn)展［4］表明其在處理NP難問題上具有很大的潛力.Kool et al［5］基于注意力機(jī)制（Attention Mechanism，AM）提出的Transformer 模型是首次解決旅行商問題（Travelling Salesman Problem，TSP）、CVRP 和其他路徑問題的模型，模型將輸入元素分為靜態(tài)、動態(tài)兩種類型，利用嵌入的編碼過程對靜態(tài)和動態(tài)元素進(jìn)行向量表示，解碼階段將靜態(tài)元素向量輸入解碼中獲得隱含層向量并與動態(tài)向量結(jié)合，通過AM 獲得下一個(gè)決策點(diǎn)的概率分布.AM 模型的提出為后續(xù)深度強(qiáng)化學(xué)習(xí)（Deep Reinforcement Learning，DRL）求解路徑問題奠定了基礎(chǔ)，為組合最優(yōu)化問題的求解提供了新思路［6］.DRL 得到的策略有希望比人工設(shè)計(jì)的更高效，對于類似的問題能同樣用基于學(xué)習(xí)的框架去求解，不需要人工重新設(shè)計(jì)算法.

基于DRL 的方法通過歸一化的AM 獲取隱藏層信息，但是AM 模塊的性能受到CVRP 中動態(tài)和隨機(jī)因素的影響，導(dǎo)致先前工作中的AM 模塊未能充分考慮多重頭注意力機(jī)制（Multi-attention Mechanism，MHA）中查詢向量Q和鍵向量K之間的相關(guān)性，導(dǎo)致在沒有相關(guān)性的前提下也會輸出關(guān)聯(lián)值.同時(shí)，混合模型通常利用多個(gè)網(wǎng)絡(luò)進(jìn)行編碼和解碼，結(jié)合了來自不同模塊的優(yōu)點(diǎn)，但是向量編碼及傳輸過程過于繁雜，可能出現(xiàn)信息解碼錯(cuò)誤等情況.

自適應(yīng)大鄰域搜索（Adaptive Large Neighborhood Search，ALNS）是受大鄰域搜索（Large Neighborhood Search，LNS）發(fā)展啟發(fā)而來的，在LNS 的基礎(chǔ)上，允許在同一個(gè)搜索中使用多個(gè)破壞算子和修復(fù)算子來獲得當(dāng)前解的鄰域，根據(jù)生成的解的質(zhì)量，選擇表現(xiàn)好的破壞算子和修復(fù)算子，再次生成鄰域進(jìn)行搜索.鄰域搜索算法的關(guān)鍵是鄰域結(jié)構(gòu)的選擇，但每次迭代搜索的時(shí)間較長，缺少在解空間內(nèi)自主搜索的能力.

現(xiàn)實(shí)中很多問題本質(zhì)上是組合優(yōu)化問題，因此，人們一直在修改ALNS 來有效地求解組合優(yōu)化問題，例如CVRP 問題.針對上述問題，本文提出深度混合型鄰域搜索（Deep Hybrid Neighborhood Search，DHNS）算法模型，即帶有DRL 的ALNS 算法的修復(fù)解的更新，同時(shí)，將AOA（Attention on Attention）［7］加入編碼和解碼過程.在編碼過程中，AOA 可以提取節(jié)點(diǎn)的特征，并對節(jié)點(diǎn)間的關(guān)系進(jìn)行建模；在解碼過程中，AOA 負(fù)責(zé)篩選有價(jià)值的信息，過濾不相關(guān)或誤導(dǎo)性信息，進(jìn)一步確定注意力結(jié)果和查詢之間的相關(guān)性.實(shí)驗(yàn)結(jié)果表明AOA 模塊對于改善模型性能是有效的，優(yōu)于之前基于DRL 的所有模型.

本文的主要創(chuàng)新如下.

（1）為了提取豐富的節(jié)點(diǎn)特征向量，在傳統(tǒng)編碼結(jié)構(gòu)上，提出一種Transformer［8］和指針網(wǎng)絡(luò)（Pointer Network，PN）［9］混合編碼結(jié)構(gòu)，并在AM上改進(jìn)同時(shí)具有MHA 和AOA 的編碼和解碼結(jié)構(gòu).MHA 主要用于信息提取，AOA 負(fù)責(zé)提高解碼器的準(zhǔn)確性.

（2）設(shè)計(jì)了一個(gè)依賴于DRL 框架的ALNS，以探索解空間中鄰域的關(guān)系，修復(fù)解決方案的任務(wù)留給通過DRL 訓(xùn)練的新型網(wǎng)絡(luò)模型.將DRL集成到ALNS 中可以提高算法在解空間中的搜索范圍，并提供啟發(fā)式信息的指導(dǎo).

1 相關(guān)工作

近年來，DRL 成為一種解決路徑問題的新方法，目前基于DRL 求解VRP 的框架主要是編碼和解碼結(jié)構(gòu)，由Nazari et al［10］首次提出，強(qiáng)調(diào)路徑問題與DRL 的結(jié)合，這種編碼-解碼體系訓(xùn)練的模型效果與傳統(tǒng)算法相比有很大的優(yōu)勢.在求解VRP 的模型框架中，首先將問題轉(zhuǎn)化為圖，通過網(wǎng)絡(luò)模型編碼為帶有節(jié)點(diǎn)信息的特征向量，然后通過解碼器將其解碼為城市輸出序列.由于編碼器-解碼器的通用架構(gòu)是循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network，RNN），但是RNN 存在長距離依賴問題，會導(dǎo)致梯度消失和梯度爆炸.為了避免上述問題，Bresson and Laurent［11］提出一種基于Transformer模型的求解方法，在編碼-解碼中添加AM，為每個(gè)查詢輸出一個(gè)加權(quán)平均值，使模型能夠關(guān)注更多有用的信息，有效緩解了梯度爆炸，降低計(jì)算成本.在此基礎(chǔ)上，王揚(yáng)和陳智斌［12］提出動態(tài)圖Transformer（Dynamic Graph Transformer Model，DGTM）模型求解CVRP，并使用REINFORCE 算法提高模型的訓(xùn)練效率，實(shí)驗(yàn)結(jié)果表明模型整體性能優(yōu)于專業(yè)求解器，提高了CVRP 問題求解速度，且具有較好的泛化性能.

為提高模型搜索效率，Kwon et al［13］提出一種具有多重策略優(yōu)化（Policy Optimization with Multiple Optimal，POMO）的網(wǎng)絡(luò)框架，使用DRL 來訓(xùn)練MHA 的多個(gè)初始節(jié)點(diǎn)嵌入，POMO 的低方差基線使RL 模型訓(xùn)練快速且穩(wěn)定，且對局部最小值的抵抗力最高.實(shí)驗(yàn)結(jié)果表明模型性能顯著提高，同時(shí)模型推理時(shí)間減少一個(gè)數(shù)量級以上.為提升智能體的選擇效率，Wu et al［14］通過DRL框架改進(jìn)啟發(fā)式算法來求解CVRP，其中策略網(wǎng)絡(luò)用于指導(dǎo)下一個(gè)解決方案的選擇，并利用行動者-評論家（Actor-critic，AC）算法訓(xùn)練策略網(wǎng)絡(luò)，然后通過啟發(fā)式算法來提高解的質(zhì)量，該模型學(xué)習(xí)到的策略明顯優(yōu)于傳統(tǒng)的手工規(guī)則.

啟發(fā)式算法通常需要改進(jìn)其在解空間內(nèi)的搜索能力，因此王原等［15］利用深度智慧型蟻群優(yōu)化算法（Deep Intelligent Ant Colony Optimization，DIACO）求解TSP，DRL 結(jié)合蟻群算法提高了DRL 在解空間內(nèi)的搜索能力以及蟻群算法的計(jì)算能力.此外，Ma et al［16］提出雙方面協(xié)作Transformer（Dual-Aspect Collaborative Transformer，DACT）模型來解決具有動態(tài)和周期性變化的CVRP，使用雙向編碼器分別學(xué)習(xí)節(jié)點(diǎn)和位置特征的嵌入，同時(shí)使用課程學(xué)習(xí)訓(xùn)練模型，提高模型的采樣速率.實(shí)驗(yàn)結(jié)果表明，DACT 優(yōu)于傳統(tǒng)的啟發(fā)式算法，且具有更優(yōu)的泛化性能.

為了縮小基于DRL 的方法與最先進(jìn)優(yōu)化方法之間的性能差距，Hottung and Tierney［17］提出了一種新穎的神經(jīng)鄰域搜索（Neural Large Neighborhood Search，NLNS）框架，該框架集成啟發(fā)式算法以生成新的解決方案，學(xué)習(xí)機(jī)制基于具有AM 的神經(jīng)網(wǎng)絡(luò)，并設(shè)計(jì)結(jié)合到大型鄰域搜索設(shè)置中.實(shí)驗(yàn)結(jié)果表明，該模型明顯優(yōu)于僅使用手工啟發(fā)式算法和著名的啟發(fā)式算法，并接近于最先進(jìn)的優(yōu)化方法的性能.但上述方法僅考慮小規(guī)模CVRP，當(dāng)問題規(guī)模變大時(shí)，優(yōu)化效果不理想.

2 模型介紹

2.1 CVRP 問題定義CVRP 考慮帶容量的車隊(duì)為一系列客戶N={1，2，…，n}提供服務(wù)的最佳路線，每個(gè)客戶節(jié)點(diǎn)i的需求為qi，要求車隊(duì)v={1，2，3，…，K}將貨物從倉庫{0}運(yùn)輸?shù)街付蛻酎c(diǎn)，每個(gè)客戶只允許被訪問一次，客戶i與客戶j之間的距離為dij.其中車輛是同質(zhì)的（容量為C）且只能從倉庫出發(fā)，完成任務(wù)后需返回倉庫，目標(biāo)是使車隊(duì)完成所有任務(wù)的總路線最短［2］.如果車輛K直接從客戶i到達(dá)客戶j，則令決策變量xijk=1，否則為0.若客戶節(jié)點(diǎn)i的需求由車輛k滿足，則yik=1，否則為0.因此，CVRP 問題可建模如下.

目標(biāo)函數(shù)（1）表示最小化車輛總行駛距離，約束（2）表示每個(gè)客戶節(jié)點(diǎn)僅能被一輛車訪問一次，約束（3）用來保證運(yùn)輸路線上的客戶總需求不能超過車輛自身承載容量，約束（4）表示若客戶i，j均由車輛k配送，則車輛k必須由某點(diǎn)i到達(dá)j，或者車輛訪問完客戶i后立即訪問節(jié)點(diǎn)j，約束（5）表示訪問某點(diǎn)的車輛數(shù)等于離開該點(diǎn)的車輛數(shù).

2.2 模型總框架DHNS 模型基于PN 和Transformer 混合編碼，PN 表示和提取各種淺層的節(jié)點(diǎn)特征，減少參數(shù)的冗余，在此基礎(chǔ)上利用Transformer 中MHA 機(jī)制從不同維度提取節(jié)點(diǎn)特征信息，最后結(jié)合動態(tài)位置編碼（Dynamic Positional Encoding，DPE）［12］表示隱層嵌入的絕對位置信息.而混合編碼過程程序復(fù)雜，很可能出現(xiàn)解碼失誤的情況.

因此，本文通過MHA 提取節(jié)點(diǎn)特征信息，AOA 通過計(jì)算MHA 中的查詢向量和查詢結(jié)果之間的相關(guān)性，提高解碼器的精確性，結(jié)合DPE進(jìn)一步提取節(jié)點(diǎn)間的相關(guān)性，提高模型在不同規(guī)模問題上的泛化能力.DHNS 模型的總體架構(gòu)和求解思路如圖1 所示，ALNS 的主要思想是通過多組破壞算子OD和修復(fù)算子OR在解空間搜索并改善當(dāng)前解，對性能較好的算子給予更高的權(quán)重.對于給定的初始解，由ALNS 的破壞算子OD對初始解進(jìn)行破壞，然后DRL 自動學(xué)習(xí)修復(fù)解的策略，最后模型在修復(fù)解空間中探索最優(yōu)的解.

圖1 模型架構(gòu)及求解思路Fig.1 Model architecture and solution ideas

2.2.1 破壞算子和修復(fù)算子破壞算子OD主要通過隨機(jī)破壞、點(diǎn)的破壞、路線的破壞對初始解進(jìn)行破壞，其中隨機(jī)破壞是隨機(jī)破壞當(dāng)前解的節(jié)點(diǎn)或邊，基于點(diǎn)的破壞是刪除最接近隨機(jī)選擇的節(jié)點(diǎn)，基于路線的破壞是刪除最接近隨機(jī)選擇的節(jié)點(diǎn)的路線.如果一個(gè)節(jié)點(diǎn)vj從一條路{vi，…，vj，…，vk}移除，得到三條不完整的路.部分解{vi，…，vj-1}包含vj之前的所有節(jié)點(diǎn)，部分解{vj}只包含節(jié)點(diǎn)vj，部分解{vj+1，…，vk}包含vj之后的所有節(jié)點(diǎn).圖2 僅顯示在鄰域中破壞和修復(fù)一個(gè)解決方案的過程，但是在整個(gè)鄰域中還有許多其他可能的修復(fù)解決方案.

圖2 破壞算子和修復(fù)算子的操作過程Fig.2 Operation process of destroying operator and repairing operator

修復(fù)算子OR主要通過DRL 在智能體與環(huán)境之間的交互作用中學(xué)習(xí)修復(fù)的策略，如圖2 所示.破壞算子OD通過隨機(jī)的破壞方法將初始解破壞為七段不完整路徑{(x2，x3)，(x0，x4)，(x0，x16)，(x5，x6)，(x7，x8)，(x10，x11)，(x14，x15)}和四個(gè)獨(dú)立的客戶節(jié)點(diǎn){x1，x9，x12，x13}.模型為被破壞的解的末端添加特征向量xi，并將不完整路徑的末端特征向量作為輸入，通過DRL 模型計(jì)算不完整路徑末端節(jié)點(diǎn)的相關(guān)性，自動學(xué)習(xí)路徑的修復(fù)策略.為了防止不完整的路徑選擇其末端節(jié)點(diǎn)或產(chǎn)生不可行的解決方案（例如路線負(fù)載超過車輛容量限制），通過添加掩碼來禁止該操作.

2.3 編碼器結(jié)構(gòu)模型采用PN 和Transformer混合編碼，結(jié)合兩者的優(yōu)勢增強(qiáng)數(shù)據(jù)特征.如圖3所示，DHNS 模型的編碼器由PN，MHA，AOA，前饋層和歸一化組成.首先，編碼器將輸入序列映射為高維向量，然后利用DPE 提取節(jié)點(diǎn)的特征向量a=[a1，a2，…，an]，ai∈Rd，n為客戶數(shù)目，d為特征向量的維數(shù).MHA 進(jìn)一步促進(jìn)網(wǎng)絡(luò)提取深層次的特征信息，AOA 則是減少在解碼階段進(jìn)行錯(cuò)誤解碼的可能性.因此，特征向量不再是直接傳到解碼器，而是通過AOA 和MHA 來更加精確地表示節(jié)點(diǎn)特征向量ai.編碼部分可表示為：

圖3 DHNS 模型總架構(gòu)Fig.3 DHNS model master architecture

其中，Wo是訓(xùn)練參數(shù)，Ql，Kl和Vl分別是自注意力機(jī)制的查詢向量、鍵向量和值向量.

當(dāng)反向傳播梯度累積時(shí)，模型需要隨時(shí)了解動態(tài)元素的信息變化，因此使用AM 和cos-AM［18］提供雙隱層信息，分別表征動態(tài)信息和靜態(tài)信息.用元組(Xt，ft)表示不完整解在t時(shí)刻的狀態(tài)，對于輸入xt∈Xt，包含上述過程在時(shí)間步長t時(shí)產(chǎn)生的嵌入hi和hi'，hi和hi'通過Embc和注意層轉(zhuǎn)換計(jì)算得到，ft表示相關(guān)嵌入，Embf使用與Embc相同的結(jié)構(gòu)不同的參數(shù)，通過Embf和注意層生成嵌入hf和hf'.所有節(jié)點(diǎn)信息嵌入都被注意層AM 和cos-AM 用來計(jì)算上下文向量c來表示所有相關(guān)嵌入.上下文向量c計(jì)算如下：

AOA 主要生成兩個(gè)信息，即信息向量I和注意力門G，然后對AOA 使用逐元素乘法將注意力門G應(yīng)用到信息向量I來添加另一個(gè)注意力機(jī)制，AOA 可以應(yīng)用于各種注意力機(jī)制.對于傳統(tǒng)的單頭注意力機(jī)制，AOA 有助于確定注意結(jié)果與查詢之間的相關(guān)性.對于MHA，AOA 有助于在不同注意力頭之間建立關(guān)系，過濾所有注意力結(jié)果并僅保留有用的注意力.對于編碼器，AOA 機(jī)制將自我注意應(yīng)用于向量以對節(jié)點(diǎn)之間的關(guān)系進(jìn)行建模，進(jìn)而確定不同向量之間的關(guān)系.對于解碼器，應(yīng)用AOA 過濾掉不相關(guān)或誤導(dǎo)性的注意結(jié)果，并僅保留有用的結(jié)果.

2.3.1 MHAMHA 首先計(jì)算了Q，K的注意分布，并將其附加到V上，此步驟準(zhǔn)確地捕獲輸入序列的特征信息.然后計(jì)算Q和V的相似度并歸一化，根據(jù)相似度和相應(yīng)的V值加權(quán)和獲得最終的注意值，此步驟通過在全局特征中分配不同的權(quán)重給不同的特征向量以提取局部特征，同時(shí)生成包括全局和局部特征在內(nèi)的聯(lián)合特征向量序列.根據(jù)Huang et al［7］研究使用縮放點(diǎn)積方法計(jì)算MHA 中的權(quán)重可以有效地解決梯度消失問題，因此使用如下表達(dá)式來計(jì)算權(quán)重向量：

其中，qi屬于Q的第i個(gè)查詢向量，kj和vj分別屬于K，V的第j個(gè)鍵向量和值向量，fsim是用來計(jì)算kj和qi相似分?jǐn)?shù)的函數(shù)，Hi表示qi和kj的相似性.

2.3.2 AOA模型對AM 有著全局依賴性，因?yàn)檩敵龅慕Y(jié)果取決于AM 的權(quán)重分配，但解碼器對注意力分配的合理性或者與查詢向量的相關(guān)程度一無所知.先前模型的AM 通過對每個(gè)時(shí)間步生成的特征向量做加權(quán)平均值來指導(dǎo)解碼過程.傳統(tǒng)的AM 不管Q，K或V是否相關(guān)，都會為Q生成一組歸一化的權(quán)重，通過給出與任務(wù)相關(guān)的查詢向量q的過程，通過縮放點(diǎn)積方法計(jì)算Q，K的注意分布，并將其附加到值向量V上，從而得到注意值.若二者不相關(guān)，會輸出誤導(dǎo)或錯(cuò)誤的信息.最后的注意力結(jié)果可能不是解碼器期望得到的，而是注意力分配造成的，將導(dǎo)致解碼器被誤導(dǎo)輸出錯(cuò)誤的結(jié)果.

為了避免上述誤導(dǎo)性信息，使用AOA 模塊衡量注意力結(jié)果和查詢之間的相關(guān)性，來解決這種不合理的現(xiàn)象.AOA 通過MHA 中的Q，K和V獲得的權(quán)重結(jié)果執(zhí)行兩個(gè)獨(dú)立的線性變換來生成信息向量I和注意力門G，同時(shí)利用逐元素乘法聚合信息向量I和注意力門G以預(yù)防不合理的現(xiàn)象，從而提高解碼器的準(zhǔn)確性.MHA 尋找節(jié)點(diǎn)間的潛在聯(lián)系，AOA 測量它們之間的關(guān)聯(lián)程度，更新特征向量.AOA 首先使用得到的注意結(jié)果和當(dāng)前上下文向量c生成信息向量I和注意力門G，信息向量I是當(dāng)前上下文向量和注意力結(jié)果v通過線性變換得到并存儲，注意力門G是當(dāng)前上下文向量c與注意力結(jié)果v通過另一個(gè)線性變換得到的.

AOA 機(jī)制通過注意力門G對信息向量I添加另一個(gè)注意力，應(yīng)用逐元素乘法得到最終的信息向量，AOA 可建模表示為：

其中，fatt是注意力模塊，⊙表示逐元素乘法.

2.4 解碼器結(jié)構(gòu)解碼器的輸入是編碼器中所有節(jié)點(diǎn)的隱藏層信息egraph、最后時(shí)間的節(jié)點(diǎn)嵌入elast以及車輛在當(dāng)前時(shí)間t的容量狀態(tài)和位置lt，給定輸入，解碼器采用批次搜索采樣策略，為了防止生成不合理的路線（例如總路線負(fù)載超過車的容量或者重復(fù)訪問一個(gè)客戶），設(shè)置一個(gè)掩碼向量來標(biāo)記已訪問的客戶節(jié)點(diǎn)，確保每個(gè)節(jié)點(diǎn)在旅行路線中只出現(xiàn)一次，同時(shí)節(jié)點(diǎn)在下一個(gè)時(shí)間步長的權(quán)重設(shè)置為負(fù)無窮大.上下文向量Ct在任意時(shí)刻t的表達(dá)式如下：

其中，fconcat是隱藏層的級聯(lián)函數(shù)，在MHA 中使用獲得的上下文向量來獲得權(quán)重向量.

AOA 計(jì)算解碼器中時(shí)間t的所有節(jié)點(diǎn)的上下文向量Ct和隱藏層向量之間的權(quán)重，然后將計(jì)算出的權(quán)重轉(zhuǎn)換為上下文向量并發(fā)送到自我注意層.單個(gè)輸出向量q使用嵌入h0+h0'，…，hn+hn'計(jì)算所有動作的輸出分布，如下所示：

其中，et表示時(shí)刻t的節(jié)點(diǎn)隱藏層，mask是標(biāo)記已訪問節(jié)點(diǎn)的掩碼向量，VB是可訓(xùn)練的參數(shù).

3 訓(xùn)練與推理方法

3.1 模型訓(xùn)練算法在訓(xùn)練階段，需要花費(fèi)大量時(shí)間來訓(xùn)練網(wǎng)絡(luò)參數(shù)，但當(dāng)模型訓(xùn)練完成后，可以在測試階段快速獲得預(yù)測結(jié)果.首先，通過貪婪算法為DHNS 模型提供初始解，DRL 中智能體根據(jù)當(dāng)前環(huán)境狀態(tài)（車的容量或顧客總需求）作出適當(dāng)?shù)臎Q策，結(jié)合獎勵(lì)機(jī)制不斷調(diào)整參數(shù)，直至模型可以修復(fù)得到完整解.

模型基于損失函數(shù)L來衡量模型操作的有效性，同時(shí)使用AC 算法對策略參數(shù)進(jìn)行訓(xùn)練，并利用此算法計(jì)算梯度來最大化預(yù)期獎勵(lì)J：

其中，π0為破壞后的解，πt是智能體執(zhí)行動作a1，a2，a3，…，at-1之后修復(fù)的解，基線b(π0)可以有效地減少方差.

模型采用AC 算法進(jìn)行訓(xùn)練，通過隨機(jī)策略學(xué)習(xí)行為網(wǎng)絡(luò)的參數(shù)，行為網(wǎng)絡(luò)基于概率分布做動作，評判網(wǎng)絡(luò)基于行為網(wǎng)絡(luò)生成的行為評判得分，行為網(wǎng)絡(luò)再根據(jù)評判網(wǎng)絡(luò)的評分調(diào)整行為選擇的概率.解決VRP 問題的傳統(tǒng)策略梯度算法的主要缺點(diǎn)是高維離散空間中不同路徑之間的方差大，訓(xùn)練不穩(wěn)定，但AC 算法可以單步更新，不需要完成整個(gè)動作再更新網(wǎng)絡(luò)參數(shù).傳統(tǒng)策略梯度方法對價(jià)值的估計(jì)雖然是無偏的，但方差較大，AC 算法能夠有效降低方差.為了保證策略梯度方差的穩(wěn)定性，類似于Nazari et al［10］，本文使用評判網(wǎng)絡(luò)為修復(fù)解π0生成一個(gè)值c0作為評判網(wǎng)絡(luò)估算修復(fù)的成本，評判網(wǎng)絡(luò)根據(jù)行為網(wǎng)絡(luò)狀態(tài)預(yù)測獎勵(lì)值b(π0)，并以預(yù)測獎勵(lì)值b(π0)和實(shí)際獎勵(lì)值L(π0，πt)之間的均值誤差作為優(yōu)化目標(biāo).

3.2 模型推理算法基于DRL 策略，為了提高解的精確性，有時(shí)仍需要結(jié)合傳統(tǒng)優(yōu)化算法（例如波束搜索、采樣）進(jìn)一步提高解的質(zhì)量.在推理階段采用批次搜索算法進(jìn)一步提升解的質(zhì)量.首先模型采樣n條不同的路徑作為起始節(jié)點(diǎn)，使用貪婪啟發(fā)式方法為每個(gè)軌跡創(chuàng)建初始解，在構(gòu)建步驟中，所有解決方案都使用成對的破壞和修復(fù)運(yùn)算符進(jìn)行破壞和修復(fù)，最后是為每個(gè)解決方案創(chuàng)建一個(gè)相鄰的解決方案.整個(gè)搜索直到達(dá)到整個(gè)批次的終止標(biāo)準(zhǔn).

4 數(shù)值實(shí)驗(yàn)

所有實(shí)驗(yàn)均基于Pytorch 1.9.0 深度學(xué)習(xí)平臺，Windows 11 操作系統(tǒng)，使用單張Nvidia RTX 3050 GPU 和i5-11300H CPU 運(yùn)行本文模型和其他DRL 模型.實(shí)驗(yàn)中節(jié)點(diǎn)的坐標(biāo)在[0，1]×[0，1]單位平方形中生成，分別在CVRP20，CVRP50 和CVRP100 上進(jìn)行訓(xùn)練和測試，車輛的容量限制分別設(shè)置為D=30，40，50.DHNS 模型在8 G 顯存下運(yùn)行（100 回合）20，50，100 節(jié)點(diǎn)的訓(xùn)練時(shí)間分別為11，40 和160 h.最優(yōu)間隙以LKH3 為基準(zhǔn)，其他結(jié)果均來自于原文獻(xiàn).聚合函數(shù)使用單層的全連接神經(jīng)網(wǎng)絡(luò)，批次大小為256，MHA 中的頭部H=8，前饋輸入層和輸出層的維度都是512維，Adam 優(yōu)化器的學(xué)習(xí)率為0.0001，權(quán)重衰減率為0.95，隱含層設(shè)置為128 維.

4.1 CVRP 的實(shí)驗(yàn)方案及其模型性能對比實(shí)驗(yàn)表1 顯示了DHNS 模型求解的CVRP 性能與以前的關(guān)鍵工作進(jìn)行比較，例如NeuRewriter［19］，NLNS［17］，AM［5］，POMO［13］，DACT［16］，MDAM［20］，DPDP［21］和其他啟發(fā)式方法.由表1可知，DHNS 模型在推理階段快于傳統(tǒng)算法（LKH3 和CW）以及NLNS，RL（BS），DACT 等模型，優(yōu)化效果超越目前基于DRL 的模型和專業(yè)求解器OR-Tools.與DGTM 比較，DHNS 模型的精度較高，但計(jì)算推理時(shí)間比DGTM 長，這是由于DGTM 模型屬于構(gòu)造解的模型，模型推理時(shí)間較短，而本文模型是改善解的模型，結(jié)合傳統(tǒng)啟發(fā)式算法進(jìn)行搜索，導(dǎo)致推理時(shí)間較長，但是解的精度得到保證.進(jìn)一步分析，模型在CVRP20，CVRP50 和CVRP100 的間隙明顯優(yōu)于目前基于DRL 的方法，與DGTM 相比，CVRP20，CVRP50和CVRP100 的最優(yōu)間隙分別由原來的0.13%，0.15%和0.19%降低到0.06%，0.09%和0.12%，超越目前基于DRL 的方法.DRL 有希望設(shè)計(jì)出比啟發(fā)式規(guī)則更好的策略，打破人為設(shè)定的限制，智能體自主探索解空間中的最優(yōu)解.DRL 充分利用同類型問題之間的相似特征，避免傳統(tǒng)算法不斷重復(fù)求解的過程和數(shù)據(jù)資源的浪費(fèi).

表1 DHNS 模型在CVRP 問題上的優(yōu)化結(jié)果比較Table1 Comparison of CVRP optimization results of DHNS model

DHNS 模型的關(guān)鍵是AOA 在編碼和解碼階段發(fā)揮著重要的作用，DPE 提取了更多的隱藏和動態(tài)的節(jié)點(diǎn)結(jié)構(gòu)信息以及貪婪算法提供了較好的初始解.DRL 模型能夠自適應(yīng)地為不同的修復(fù)算子分配相應(yīng)的權(quán)重，加速產(chǎn)生更好的解方案.對比ALNS 算法，DRL 能夠進(jìn)一步減少啟發(fā)式信息的指導(dǎo)和時(shí)間成本，能極大地提高算法在解空間的搜索范圍.DRL 根據(jù)算子的歷史表現(xiàn)與使用次數(shù)自動選擇下一次迭代使用的算子，通過算子間在RL 環(huán)境中的相互競爭來生成當(dāng)前解的鄰域結(jié)構(gòu)，這種結(jié)構(gòu)很大概率能夠找到更好的解.實(shí)驗(yàn)結(jié)果表明，與ALNS 結(jié)合的DRL 以及AOA 調(diào)整后的模型優(yōu)化性能很好.

4.2 泛化性能及收斂性分析考慮到問題實(shí)例會根據(jù)模型所作的決策而改變，節(jié)點(diǎn)特征也會發(fā)生變化，使用AC 算法訓(xùn)練模型的策略有利于網(wǎng)絡(luò)學(xué)習(xí)特征.DHNS 模型對求解CVRP 的泛化能力比較如圖4 所示.圖5 和圖6 展示了模型在20節(jié)點(diǎn)和50 節(jié)點(diǎn)的收斂性.結(jié)果表明對于固定的問題大小，DHNS 模型可以很好地推廣和解決任何類似規(guī)模的問題.更重要的是，盡管CVRP20 需要10 h 的訓(xùn)練，但訓(xùn)練過程僅需一次，并且在推理階段僅需花費(fèi)2 min 就可以獲得高質(zhì)量的解決方案，不需要針對不同的問題實(shí)例進(jìn)行再次訓(xùn)練.DHNS 模型具有較好的泛化性能的原因在于DHNS 是基于改善初始解的方式不斷提高解，通過ALNS 擴(kuò)大解的搜索范圍，尋求高質(zhì)量的解決方案，并且通過AOA 防止信息在傳輸過程中出現(xiàn)誤導(dǎo)性信息，更加精確地進(jìn)行信息傳遞，進(jìn)一步提高解的質(zhì)量.

圖4 CVRP 泛化性能的比較Fig.4 Comparison of CVRP generalization performance

圖5 CVRP20 模型收斂圖Fig.5 Diagram of CVRP20 model convergence

圖6 CVRP50 模型收斂圖Fig.6 Diagram of CVRP50 model convergence

4.3 真實(shí)數(shù)據(jù)集實(shí)例測試本文成功地將DHNS 模型從訓(xùn)練模型推廣到現(xiàn)實(shí)世界的數(shù)據(jù)集.表2 是真實(shí)數(shù)據(jù)集CVRPlib 上的22 個(gè)實(shí)例的實(shí)驗(yàn)結(jié)果，表中黑體字表示結(jié)果最優(yōu).由表可見，平均差距進(jìn)一步縮小到2.89%，證明其差距優(yōu)于AM，POMO，Wu et al，DACT 和OR-Tools.在混合隨機(jī)和群集類型以及大多數(shù)隨機(jī)類型的實(shí)例上，DHNS 的性能也優(yōu)于其他基準(zhǔn).鑒于其優(yōu)勢，DHNS 在各種大小和分布的CVRPlib 基準(zhǔn)實(shí)例上的泛化性能方面優(yōu)于現(xiàn)有的基于DRL 的模型.

表2 模型在CVRPlib 基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 2 Experimental results of the model on the CVRPlib benchmark dataset

4.4 AOA 機(jī)制的消融實(shí)驗(yàn)為了進(jìn)一步驗(yàn)證AOA 機(jī)制對DHNS 模型的有效性，設(shè)計(jì)了AOA在編碼和解碼階段的消融實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示，表中黑體字表示結(jié)果最優(yōu).實(shí)驗(yàn)結(jié)果表明，AOA 可以有效提高DHNS 的優(yōu)化性能，解決混合模型中可能出現(xiàn)的解碼錯(cuò)誤，提升解碼效率，顯著降低CVRP 問題的最優(yōu)間隙.其中推理時(shí)間稍長的原因是AOA 增加了網(wǎng)絡(luò)層中的參數(shù).

表3 AOA 機(jī)制在編碼和解碼階段的消融實(shí)驗(yàn)Table 3 Ablation experiment of AOA mechanism in encoding and decoding stage

5 結(jié)論

本文介紹了一種新的求解CVRP 的深度學(xué)習(xí)方法DHNS，利用傳統(tǒng)啟發(fā)式與DRL 相結(jié)合的混合模型，將AOA 添加到編碼器和解碼器中，并使用AC 算法來訓(xùn)練Transformer 網(wǎng)絡(luò)中的參數(shù).在問題規(guī)模中等且解精度高的情況下，DHNS 模型非常可取.在保證解的精度的前提下，模型自動從數(shù)據(jù)中學(xué)習(xí)啟發(fā)式方法并使決策過程自動化.實(shí)驗(yàn)結(jié)果表明，DHNS 模型對100 規(guī)模CVRP的優(yōu)化效果優(yōu)于現(xiàn)有的DRL 模型和部分傳統(tǒng)算法.真實(shí)數(shù)據(jù)集上的測試結(jié)果也顯示出本文模型的優(yōu)越性.

未來的工作會首先考慮進(jìn)一步擴(kuò)展模型以解決VRP 的其他變體或其他組合最優(yōu)化問題以及多目標(biāo)VRP，其次考慮提高基于DRL 方法的解決方案質(zhì)量.未來主要挑戰(zhàn)更有效地處理問題的動態(tài)特征，開發(fā)更好的機(jī)制，使智能體能夠了解在訪問一個(gè)城市后其他城市和環(huán)境的變化以及這種動態(tài)變化如何影響策略.