無(wú)人靶車路徑規(guī)劃及其算法研究

魏振亞 崔國(guó)梁 寧濤 丁雨康

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

關(guān)鍵詞：無(wú)人靶車 變鄰域搜索算法 染色體 算法研究

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

無(wú)人靶車路徑問(wèn)題（Unmanned Target Vehicle Routing Problem，UTVRP）是經(jīng)典車輛路徑問(wèn)題（Vehicle Routing Problem，VRP）[1]的變體。無(wú)人靶車路徑問(wèn)題與傳統(tǒng)的車輛路徑問(wèn)題的主要的聯(lián)系是將車輛路徑問(wèn)題的思想運(yùn)用到無(wú)人靶車路徑規(guī)劃上。根據(jù)全球能源部門(mén)的相關(guān)文件表明[2]應(yīng)對(duì)氣候變化，設(shè)定零排放目標(biāo)。因此合理優(yōu)化靶車路徑對(duì)環(huán)境具有重要意義。

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

UTVRP是一個(gè)NP-hard問(wèn)題，難在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解。當(dāng)前，該問(wèn)題的求解算法可以分為精確算法傳統(tǒng)啟發(fā)式算法和元啟發(fā)式算法三種。精確算法是利用數(shù)學(xué)方法或數(shù)據(jù)結(jié)構(gòu)方法求得問(wèn)題的最優(yōu)解，精確算法可以為問(wèn)題到最優(yōu)解，但是在大規(guī)模問(wèn)題上會(huì)存迭代時(shí)間過(guò)長(zhǎng)的問(wèn)題。傳統(tǒng)啟發(fā)式算法從一個(gè)解出發(fā)，在其鄰域空間內(nèi)不斷搜索最優(yōu)解，但是傳統(tǒng)的啟發(fā)式算法容易陷入局部最優(yōu)。元啟發(fā)式算法在處理各類路由問(wèn)題上表現(xiàn)出顯著的效果。元啟發(fā)式算法分為模擬退火算法[6-7]、蟻群算法[8-9]、變鄰域搜索算法[10-12]、遺傳算法[13-16]等。

本文提出無(wú)人靶車路徑問(wèn)題（Unmanned Target Vehicle Routing Problem，UTVRP），此問(wèn)題以靶車行駛成本最小為優(yōu)化目標(biāo)，接著提出一種帶成本最優(yōu)法的混合變鄰域搜索算法來(lái)求解UTVRP。以下是本文的具體工作：第一部分將UTVRP建立混合整數(shù)規(guī)劃模型，第二部分對(duì)UTVRP進(jìn)行染色體編碼，第三部分進(jìn)行算法設(shè)計(jì)以及求解，第四部分為分析總結(jié)。

1無(wú)人靶車混合整數(shù)模型

UTVRP描述為一個(gè)靶車車廠擁有多臺(tái)靶車，它可以移動(dòng)到多個(gè)目標(biāo)點(diǎn)。其中該問(wèn)題的目標(biāo)是實(shí)現(xiàn)所有靶車到達(dá)目標(biāo)點(diǎn)路徑最短即成本最小。為了明確研究適用的范圍，做出以下假設(shè)：（1）所有靶車需從靶車車廠出發(fā)完成任務(wù)后返回靶車車廠；（2）每個(gè)目標(biāo)點(diǎn)僅可以達(dá)到一次；（3）靶車總成本為靶車行駛距離。

定定義一個(gè)靶車車廠擁有臺(tái)靶車，靶車集合為，其中為靶車編號(hào)。目標(biāo)點(diǎn)集合為，為目標(biāo)點(diǎn)個(gè)數(shù)。此外，靶車路徑可定義為無(wú)向圖，為節(jié)點(diǎn)集合其中為靶車車廠編號(hào)。為邊的集合。UTVRP的混合整數(shù)模型如下所示。

UTVRP目標(biāo)函數(shù)如公式（1）所示，其中F為目標(biāo)問(wèn)題成本即靶車運(yùn)行的總距離，另外目標(biāo)點(diǎn)之間的距離為。為決策變量，時(shí)，靶車通過(guò)點(diǎn)，否則。

每個(gè)目標(biāo)點(diǎn)只可以到達(dá)一次，公式為

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

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

式中，，為正整數(shù)集，對(duì)每個(gè)節(jié)點(diǎn)引入決策變量建立MTZ[17]約束，取值范圍為。另外為極大數(shù)，有實(shí)驗(yàn)表明M取緊貼的上界，效果更好，因此本文取，n為目標(biāo)點(diǎn)個(gè)數(shù)，因此我們將約束拉緊為

決策變量的約束為

2染色體編碼方案

解的編碼是求解UTVRP的關(guān)鍵的工作。該方案將添加若干個(gè)虛擬目標(biāo)點(diǎn)用來(lái)分隔靶車的路徑，并將目標(biāo)點(diǎn)和靶車擬合成個(gè)體，圖1中表示了UTVRP問(wèn)題的一個(gè)可能的解，其中插入兩個(gè)虛擬目標(biāo)點(diǎn)即目標(biāo)點(diǎn)12以及目標(biāo)點(diǎn)13用來(lái)分配目標(biāo)點(diǎn)，同時(shí)加入靶車車廠0。這樣的自然數(shù)序列構(gòu)成了一個(gè)解并且可以表述一個(gè)靶車路徑分配方案。

那么圖1解對(duì)應(yīng)的目標(biāo)點(diǎn)分配方案為：靶車1的訪問(wèn)順序?yàn)椋话熊?的訪問(wèn)順序?yàn)?；靶?的訪問(wèn)順序?yàn)?。

3算法步驟

3.1成本最優(yōu)法

成本最優(yōu)法的思想是以成本最小的方式去構(gòu)建目標(biāo)問(wèn)題的可行解，并且在構(gòu)建初始解的同時(shí)不違背目標(biāo)問(wèn)題的約束，已有實(shí)驗(yàn)表明[18]成本最優(yōu)法的算法復(fù)雜度為。為了提高算法求解效率，本文采用成本最優(yōu)法生成初始解，具體步驟如下。

步驟1：讀取當(dāng)前數(shù)據(jù)點(diǎn)數(shù)據(jù)，記當(dāng)前路徑為。

步驟2：判斷是否訪問(wèn)過(guò)所有目標(biāo)點(diǎn)，如果訪問(wèn)完所有目標(biāo)點(diǎn)則算法結(jié)束，輸入處理后的路徑并計(jì)算當(dāng)前成本。若貨物點(diǎn)未被訪問(wèn)完則算法繼續(xù)，記未被訪問(wèn)的目標(biāo)為。

步驟3：由輪盤(pán)賭隨機(jī)產(chǎn)生基點(diǎn)，加入中并且標(biāo)記已經(jīng)被服務(wù)。

步驟4：挑選為被服務(wù)的目標(biāo)點(diǎn)和，計(jì)算其成本標(biāo)記為和比較、。若則將添加至，反之，將添加至。跳轉(zhuǎn)至步驟2。

3.2變鄰域搜索算法

變鄰域搜索算法的基本思想是通過(guò)在搜索過(guò)程中系統(tǒng)改變鄰域變換結(jié)構(gòu)來(lái)拓寬搜索范圍，來(lái)獲得局部最優(yōu)解，同時(shí)通過(guò)得到的局部最優(yōu)解后重新改變鄰域結(jié)構(gòu)，尋求另一部分的最優(yōu)解。變鄰域搜索算法具有算法迭代速度快和局部搜索能力強(qiáng)的特點(diǎn)。為了提高搜索能力，本文采用單點(diǎn)插入、兩段交換、2-opt來(lái)實(shí)現(xiàn)變鄰域搜索算法。算法的具體步驟如下：

3.2.1 單點(diǎn)插入操作

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

3.2.2兩段交換操作

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

3.2.3 2-opt操作

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

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

本文涉及的所有算法采用Python語(yǔ)言編程，在Windows 10操作系統(tǒng)下，硬件為設(shè)備AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx@2.10 GHz（16.00GB RAM）的機(jī)器上運(yùn)行，實(shí)驗(yàn)數(shù)據(jù)采用Solomon數(shù)據(jù)庫(kù)，實(shí)驗(yàn)仿真結(jié)果如下所示：

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

5結(jié)論

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

參考文獻(xiàn)

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

張雅欣，羅薈霖，王燦.碳中和行動(dòng)的國(guó)際趨勢(shì)分析[J].氣候變化研究進(jìn)展，2021（17）：88-97.

謝高楊，房立清，蘇續(xù)軍，等.無(wú)人靶車在不同車速下的路徑規(guī)劃方法[J].電子測(cè)量與儀器學(xué)報(bào)，2023（2）：39-47.

史發(fā).無(wú)人靶車自動(dòng)導(dǎo)航技術(shù)研究[D].西安：西安工業(yè)大學(xué)，2023.

鄭銳，馮振明，陸明泉.基于遺傳算法的無(wú)人機(jī)航路規(guī)劃優(yōu)化研究[J].計(jì)算機(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.

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

陳迎欣.基于改進(jìn)蟻群算法的車輛路徑優(yōu)化問(wèn)題研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（6）：2031-2034.

王征，張俊，王旭坪.多車場(chǎng)帶時(shí)間窗車輛路徑問(wèn)題的變鄰域搜索算法[J].中國(guó)管理科學(xué)，2011，19（2）：99-109.

陳萍，黃厚寬，董興業(yè).求解多車型車輛路徑問(wèn)題的變鄰域搜索算法[J].系統(tǒng)仿真學(xué)報(bào)，2011，23（9）：1945-1950.

趙燦華，侍洪波.基于自適應(yīng)變鄰域搜索的大規(guī)模電動(dòng)車輛路徑優(yōu)化[J].華東理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，46（5）：694-701.

張麗萍，柴躍廷.車輛路徑問(wèn)題的改進(jìn)遺傳算法[J].系統(tǒng)工程理論與實(shí)踐，2002（8）：79-84.

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

鄒彤，李寧，孫德寶，等.多車場(chǎng)車輛路徑問(wèn)題的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2004，40（21）：82-83.

常見(jiàn)，任雁.基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃[J].組合機(jī)床與自動(dòng)化加工技術(shù)，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.

饒衛(wèi)振，金淳.求解大規(guī)模CVRP問(wèn)題的快速貪婪算法[J].管理工程學(xué)報(bào)，2014，28（2）：45-54.