無人靶車路徑規劃及其算法研究

魏振亞 崔國梁 寧濤 丁雨康

（安徽卡思普智能科技有限公司 安徽滁州 239299）摘要：靶車路徑問題（Target Vehicle Routing Problem，TVRP）是組合優化領域的熱點問題。首次提出了無人靶車路徑問題（Unmanned Target Vehicle Routing Problem，UTVRP），建立了以最小化運輸成本為優化目標的整數規劃模型。接著提出一種帶成本最優法的變鄰域搜索算法（Variable Neighborhood Search with Cost Optimal Method，VNSCOM）。算法的初始階段對目標問題進行單基因染色體編碼操作，首先提出成本最優法對問題的初始解進行構造。接著，在單基因染色體編碼下進行鄰域變化，最后通過大量實驗仿真，驗證了提出算法的有效性。

關鍵詞：無人靶車 變鄰域搜索算法 染色體 算法研究

Research on Path Planning for Unmanned Target Vehicles and Its Algorithm

WEI Zhenya* CUI Guoliang NING Tao DING Yukang

（Anhui Kasper Intelligent Technology Co.， Ltd.， Chuzhou， Anhui Province， 239299 China）

Abstract： The target vehicle routing problem （TVRP） is a hot problem in the field of combinatorial optimization. The unmanned target vehicle routing problem （UTVRP） is proposed for the first time， an integer planning model with the optimization objective of minimizing transportation costs is established， and then a variable neighborhood search with cost ptimal method （VNSCOM） is proposed. In the initial stage of the algorithm， the single-gene chromosome coding operation is performed on the target problem. The cost optimal method is first proposed to construct the initial solution of the problem， then the neighborhood change is performed under single-gene chromosome coding， and finally the effectiveness of the proposed algorithm is verified through a large number of experimental simulations.

Key Words： Unmanned target vehicle; Variable neighborhood search algorithm; Chromosome; Algorithm research

無人靶車路徑問題（Unmanned Target Vehicle Routing Problem，UTVRP）是經典車輛路徑問題（Vehicle Routing Problem，VRP）[1]的變體。無人靶車路徑問題與傳統的車輛路徑問題的主要的聯系是將車輛路徑問題的思想運用到無人靶車路徑規劃上。根據全球能源部門的相關文件表明[2]應對氣候變化，設定零排放目標。因此合理優化靶車路徑對環境具有重要意義。

廣大學者分別從建模和求解方面對UTVRP展開深入研究。謝高楊等人[3]建立了不同車速下的無人靶車的數學模型，改進了A*算法將航向角與圓弧形搜索算法相結合最后應用于不同速度下的無人靶車路徑問題上。史發[4]建立了地圖模型，接著分析了主流算法Dijkstra路徑規劃算法和A*路徑規劃算法的工作原理和流程，最后編寫了代碼進行了兩種算法的仿真。鄭銳等[5]為了提高無人機航路規劃效率和精度，重新設計了遺傳算法，加快了搜索速度，提高了規劃效率。

UTVRP是一個NP-hard問題，難在多項式時間內求得最優解。當前，該問題的求解算法可以分為精確算法傳統啟發式算法和元啟發式算法三種。精確算法是利用數學方法或數據結構方法求得問題的最優解，精確算法可以為問題到最優解，但是在大規模問題上會存迭代時間過長的問題。傳統啟發式算法從一個解出發，在其鄰域空間內不斷搜索最優解，但是傳統的啟發式算法容易陷入局部最優。元啟發式算法在處理各類路由問題上表現出顯著的效果。元啟發式算法分為模擬退火算法[6-7]、蟻群算法[8-9]、變鄰域搜索算法[10-12]、遺傳算法[13-16]等。

本文提出無人靶車路徑問題（Unmanned Target Vehicle Routing Problem，UTVRP），此問題以靶車行駛成本最小為優化目標，接著提出一種帶成本最優法的混合變鄰域搜索算法來求解UTVRP。以下是本文的具體工作：第一部分將UTVRP建立混合整數規劃模型，第二部分對UTVRP進行染色體編碼，第三部分進行算法設計以及求解，第四部分為分析總結。

1無人靶車混合整數模型

UTVRP描述為一個靶車車廠擁有多臺靶車，它可以移動到多個目標點。其中該問題的目標是實現所有靶車到達目標點路徑最短即成本最小。為了明確研究適用的范圍，做出以下假設：（1）所有靶車需從靶車車廠出發完成任務后返回靶車車廠；（2）每個目標點僅可以達到一次；（3）靶車總成本為靶車行駛距離。

定定義一個靶車車廠擁有臺靶車，靶車集合為，其中為靶車編號。目標點集合為，為目標點個數。此外，靶車路徑可定義為無向圖，為節點集合其中為靶車車廠編號。為邊的集合。UTVRP的混合整數模型如下所示。

UTVRP目標函數如公式（1）所示，其中F為目標問題成本即靶車運行的總距離，另外目標點之間的距離為。為決策變量，時，靶車通過點，否則。

每個目標點只可以到達一次，公式為

每輛靶車完成任務后返回靶車車廠，公式為

禁止靶車路徑回路中含有子回路，公式為

式中，，為正整數集，對每個節點引入決策變量建立MTZ[17]約束，取值范圍為。另外為極大數，有實驗表明M取緊貼的上界，效果更好，因此本文取，n為目標點個數，因此我們將約束拉緊為

決策變量的約束為

2染色體編碼方案

解的編碼是求解UTVRP的關鍵的工作。該方案將添加若干個虛擬目標點用來分隔靶車的路徑，并將目標點和靶車擬合成個體，圖1中表示了UTVRP問題的一個可能的解，其中插入兩個虛擬目標點即目標點12以及目標點13用來分配目標點，同時加入靶車車廠0。這樣的自然數序列構成了一個解并且可以表述一個靶車路徑分配方案。

那么圖1解對應的目標點分配方案為：靶車1的訪問順序為；靶車2的訪問順序為；靶車3的訪問順序為1。

3算法步驟

3.1成本最優法

成本最優法的思想是以成本最小的方式去構建目標問題的可行解，并且在構建初始解的同時不違背目標問題的約束，已有實驗表明[18]成本最優法的算法復雜度為。為了提高算法求解效率，本文采用成本最優法生成初始解，具體步驟如下。

步驟1：讀取當前數據點數據，記當前路徑為。

步驟2：判斷是否訪問過所有目標點，如果訪問完所有目標點則算法結束，輸入處理后的路徑并計算當前成本。若貨物點未被訪問完則算法繼續，記未被訪問的目標為。

步驟3：由輪盤賭隨機產生基點，加入中并且標記已經被服務。

步驟4：挑選為被服務的目標點和，計算其成本標記為和比較、。若則將添加至，反之，將添加至。跳轉至步驟2。

3.2變鄰域搜索算法

變鄰域搜索算法的基本思想是通過在搜索過程中系統改變鄰域變換結構來拓寬搜索范圍，來獲得局部最優解，同時通過得到的局部最優解后重新改變鄰域結構，尋求另一部分的最優解。變鄰域搜索算法具有算法迭代速度快和局部搜索能力強的特點。為了提高搜索能力，本文采用單點插入、兩段交換、2-opt來實現變鄰域搜索算法。算法的具體步驟如下：

3.2.1 單點插入操作

單點插入操作作用于相同和不同的靶車之間這兩種情況。同一輛靶車和不同靶車之間所有位置均可插入。圖2和圖3是兩種單點插入情況的示意圖。圖2將目標點4插入到第四個點位，再將目標點7放置第三個點位更新路徑得到新路徑為路徑2。在不同靶車之間將目標點8取出放置第二條路徑的目標點4處，將目標點4放置目標點8處，更新路徑為路徑2，如圖3所示。

3.2.2兩段交換操作

兩段交換操作亦可以作用于相同和不同靶車之間。在相同靶車之間目標點段2、8和7、6交換位置得到新路徑記為路徑2，如圖4所示。不同靶車之間目標點段2、8、7和3、4、9交換的到新路徑記為路徑2如圖5所示。

3.2.3 2-opt操作

2-opt操作將兩條不相鄰的邊斷開新連接得到新路徑，具體操作如圖5所示：將0-2和7-6斷開并重新連接上兩條邊生成新的路徑記為路徑2。

4實驗結果分析

本文涉及的所有算法采用Python語言編程，在Windows 10操作系統下，硬件為設備AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx@2.10 GHz（16.00GB RAM）的機器上運行，實驗數據采用Solomon數據庫，實驗仿真結果如下所示：

本文將一種帶成本最優法的混合變鄰域搜索算法（Variable Neighborhood Search with Cost Optimal Method，VNSCOM）與蟻群算法（Ant Colony Optimization，ACO）進行仿真比較，算法均設定運行20次運行，運行40 s。各算法對比如表1所示。表1中表示靶車行駛的總路徑，為行駛結果的平均值。其中較好的數據均以粗體表示。綜合表1和圖6所示VNSCOM的數據均優于ACO，且平均值亦優于ACO。

5結論

本文提出并研究了一種靶車路徑規劃問題，綜合考慮了靶車行駛成本最小化為優化目標，同時構建了靶車路徑規劃的混合整數模型。接著提出一種帶成本最優法的混合變鄰域搜索算法。算法的初始階段為了加快算法迭代速度使用成本最優法對初始解進行探索，為了求得靶車路徑問題的最優解本文使用不同鄰域變換的搜索算法。通過實驗對比表明：VNSCOM與ACO算法相比較，VSNCOM求得的路徑最短即成本最小。由于本文算法在避障方面沒有合適的方案，所以在后續工作中，還要對避障進行下一步的優化，以便于算法更貼近實際問題。

參考文獻

DANTZIG G B，RAMSER J H.The Truck Dispatching Problem[J].Management science，1959（1）：80-91.

張雅欣，羅薈霖，王燦.碳中和行動的國際趨勢分析[J].氣候變化研究進展，2021（17）：88-97.

謝高楊，房立清，蘇續軍，等.無人靶車在不同車速下的路徑規劃方法[J].電子測量與儀器學報，2023（2）：39-47.

史發.無人靶車自動導航技術研究[D].西安：西安工業大學，2023.

鄭銳，馮振明，陸明泉.基于遺傳算法的無人機航路規劃優化研究[J].計算機仿真，2011（6）：88-91.

LIU G，HU J，YANG Y，et al.Vehicle routing problem in cold chain logistics：a. joint distribution model with carbon trading mechanisms[J].Resources conservation and recycling，2020（156）：104715.

SUZUKI，YOSHINORI.A Dual-Objective Metaheuristic Approach to Solve Practical Pollution Routing Problem[J].International journal of production economics，2016（10）：143-153.

周鮮成，呂陽，賀彩虹，等.考慮時變速度的多車場綠色車輛路徑模型及優化算法[J].控制與決策，2022，37（1）：473-482.

陳迎欣.基于改進蟻群算法的車輛路徑優化問題研究[J].計算機應用研究，2012，29（6）：2031-2034.

王征，張俊，王旭坪.多車場帶時間窗車輛路徑問題的變鄰域搜索算法[J].中國管理科學，2011，19（2）：99-109.

陳萍，黃厚寬，董興業.求解多車型車輛路徑問題的變鄰域搜索算法[J].系統仿真學報，2011，23（9）：1945-1950.

趙燦華，侍洪波.基于自適應變鄰域搜索的大規模電動車輛路徑優化[J].華東理工大學學報（自然科學版），2020，46（5）：694-701.

張麗萍，柴躍廷.車輛路徑問題的改進遺傳算法[J].系統工程理論與實踐，2002（8）：79-84.

趙燕偉，吳斌，蔣麗，等.車輛路徑問題的雙種群遺傳算法求解方法[J].計算機集成制造系統，2004（3）：303-306.

鄒彤，李寧，孫德寶，等.多車場車輛路徑問題的遺傳算法[J].計算機工程與應用，2004，40（21）：82-83.

常見，任雁.基于改進遺傳算法的機器人路徑規劃[J].組合機床與自動化加工技術，2023（2）：23-27.

DESROCHERS M，LAPORTE G.Improvements and extensions to the miller-tucker-zemlin subtour elimination constraints[J].Operations Research Letters，1991，10（1）：27-36.

饒衛振，金淳.求解大規模CVRP問題的快速貪婪算法[J].管理工程學報，2014，28（2）：45-54.