对多旅行商问题：应用、方法和分类进行了全面的综述
摘要：
多旅行商問(wèn)題( MTSP )是最有趣的組合優(yōu)化問(wèn)題之一,因?yàn)樗粡V泛應(yīng)用于機(jī)器人、交通、網(wǎng)絡(luò)等實(shí)際應(yīng)用中。盡管這一優(yōu)化問(wèn)題的重要性不言而喻,但目前還沒(méi)有專(zhuān)門(mén)考察近期MTSP貢獻(xiàn)的調(diào)查。本文旨在通過(guò)對(duì)現(xiàn)有MTSP研究的全面回顧,填補(bǔ)這一空白。在本次調(diào)查中,我們重點(diǎn)關(guān)注MTSP近期對(duì)經(jīng)典車(chē)輛/機(jī)器人和無(wú)人機(jī)的貢獻(xiàn)。重點(diǎn)介紹了求解MTSP的方法及其應(yīng)用領(lǐng)域。我們對(duì)MTSP變體進(jìn)行了分析,提出了一個(gè)分類(lèi)學(xué)和近期研究的分類(lèi)。
1、介紹和動(dòng)機(jī)
多旅行推銷(xiāo)員問(wèn)題（MTSP）是眾所周知的旅行推銷(xiāo)員問(wèn)題的推廣，即多個(gè)推銷(xiāo)員只訪問(wèn)一次給定數(shù)量的城市，并以最小的旅行成本返回到初始位置。MTSP與其他優(yōu)化問(wèn)題高度相關(guān)，如車(chē)輛路徑問(wèn)題[1]和任務(wù)分配問(wèn)題[2]。事實(shí)上，mtsp是對(duì)VRP的簡(jiǎn)易版本，既沒(méi)有考慮車(chē)輛容量也沒(méi)有考慮客戶(hù)需求。MTSP在任務(wù)分配問(wèn)題上也有一些共同特點(diǎn)，但MTSP不允許多次訪問(wèn)和分團(tuán)訪問(wèn)。因此，可以使用MTSP的解決方案來(lái)解決VRP或任務(wù)分配優(yōu)化問(wèn)題。
MTSP是最重要的優(yōu)化問(wèn)題之一，它適用于現(xiàn)實(shí)生活中的所有場(chǎng)景。根據(jù)應(yīng)用要求，MTSP中的銷(xiāo)售人員可以用地面車(chē)輛來(lái)表示，如機(jī)器人，或者用無(wú)人駕駛飛行器（UAVs）等飛行器，也稱(chēng)為無(wú)人機(jī)。而銷(xiāo)售人員要訪問(wèn)的城市可以有不同的表現(xiàn)形式，如運(yùn)輸和送貨服務(wù)中的客戶(hù)、無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集的傳感器節(jié)點(diǎn)、軍事應(yīng)用中的目標(biāo)、緊急任務(wù)中的受害者和災(zāi)害管理應(yīng)用中的關(guān)鍵地點(diǎn)。
考慮到這種優(yōu)化問(wèn)題的重要性，我們?cè)诒菊{(diào)查中專(zhuān)門(mén)回顧、分析和討論最近對(duì)MTSP的貢獻(xiàn)，同時(shí)強(qiáng)調(diào)應(yīng)用領(lǐng)域和方法，解決經(jīng)典車(chē)輛（即地面機(jī)器人、車(chē)輛、卡車(chē)）和飛行車(chē)輛（即無(wú)人機(jī)和無(wú)人機(jī)）的問(wèn)題。
在經(jīng)典車(chē)輛的背景下，文獻(xiàn)中提出了幾項(xiàng)關(guān)于車(chē)輛路線問(wèn)題[3-6]和旅行推銷(xiāo)員問(wèn)題[7,8]的調(diào)查，以了解這些優(yōu)化問(wèn)題的不同形式以及解決這些問(wèn)題的方法。僅舉幾個(gè)例子，作者在[7]中介紹了一項(xiàng)關(guān)于機(jī)器人系統(tǒng)路由問(wèn)題的調(diào)查。本文討論了一些基于TSP和VRP的路由解決方案及其擴(kuò)展，以滿(mǎn)足機(jī)器人系統(tǒng)的約束。這些解決方案包括Dubins TSP（DTSP），這是TSP的推廣，其中路徑由Dubins曲線組成；TSP with Neighborhoods（TSPN），其中一個(gè)社區(qū)與每個(gè)城市相關(guān)聯(lián)，銷(xiāo)售人員需要訪問(wèn)任何社區(qū)；多重旅行商問(wèn)題（MTSP），最后是廣義非對(duì)稱(chēng)TSP（GATSP）。
[8]中的研究介紹了多目標(biāo)旅行推銷(xiāo)員問(wèn)題（MOTSP）的進(jìn)化算法的比較分析。作者只關(guān)注了五種進(jìn)化算法，即NSGA-II、NSGA-III、SPEA-2、MOEA/D和VEGA，以確定最適合MOTSP問(wèn)題的算法。
盡管有幾項(xiàng)研究引用了MTSP，但它只在某些章節(jié)中提到，而不是上述任何調(diào)查的主題。事實(shí)上，Bektas[9]提出的關(guān)于MTSP的唯一調(diào)查可以追溯到2006年，該調(diào)查審查了MTSP及其應(yīng)用，強(qiáng)調(diào)了一些公式，并描述了一些精確和啟發(fā)式的解決方案。
因此，缺乏專(zhuān)門(mén)針對(duì)MTSP的分析研究。為了填補(bǔ)這一空白，本調(diào)查致力于審查最近的貢獻(xiàn)，這些貢獻(xiàn)集中在MTSP及其變體或使用MTSP來(lái)解決現(xiàn)實(shí)問(wèn)題上。
在飛行器的背景下，[10]中的研究提出了一項(xiàng)關(guān)注無(wú)人機(jī)優(yōu)化問(wèn)題的調(diào)查，并為無(wú)人機(jī)提出了TSP和VRP的不同變體。[11]中介紹了另一項(xiàng)有趣的研究，其中作者回顧了無(wú)人機(jī)軌跡優(yōu)化和無(wú)人機(jī)路由的貢獻(xiàn)。他們還提供了無(wú)人機(jī)路由和軌跡優(yōu)化問(wèn)題（UAVRTOP）的正式定義，該問(wèn)題考慮了無(wú)人機(jī)的運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)約束。Bothsurvey[10，11]提出了路由問(wèn)題及其變體、使用的方法和應(yīng)用等方面的最新研究的分類(lèi)法。因此，讀者可以大致了解無(wú)人機(jī)現(xiàn)有的各種路線問(wèn)題和目標(biāo)優(yōu)化。
讀者也可以參考調(diào)查報(bào)告[12]，它可以提供一個(gè)快速進(jìn)入民用無(wú)人機(jī)運(yùn)行規(guī)劃主題的起點(diǎn)。在這項(xiàng)調(diào)查中，作者總結(jié)了與無(wú)人機(jī)運(yùn)行規(guī)劃有關(guān)的重要無(wú)人機(jī)特征，描述了無(wú)人機(jī)運(yùn)行的規(guī)劃問(wèn)題，以及無(wú)人機(jī)組合和其他車(chē)輛運(yùn)行的規(guī)劃問(wèn)題。他們最終確定了一些新的無(wú)人機(jī)優(yōu)化問(wèn)題，并討論了眾所周知的優(yōu)化問(wèn)題（如TSP）的模型擴(kuò)展。然而，所有這些調(diào)查[1012]都只限于無(wú)人機(jī)的背景。
在我們的論文中，我們提出了一個(gè)不同的調(diào)查，它是對(duì)MTSP的補(bǔ)充，也是對(duì)上述調(diào)查的補(bǔ)充。
更確切地說(shuō)，我們的調(diào)查提出了以下貢獻(xiàn)：
?介紹MTSP最重要的實(shí)際應(yīng)用。
?分析MTSP現(xiàn)有的各種變體及其正式說(shuō)明。
?全面回顧了最近對(duì)地面和飛行飛行器的貢獻(xiàn)，同時(shí)強(qiáng)調(diào)了應(yīng)用領(lǐng)域，并提出了解決每個(gè)貢獻(xiàn)的MTSP的方法。
?MTSP的分類(lèi)法和最新貢獻(xiàn)分類(lèi)，有助于讀者進(jìn)行研究，并為未來(lái)的研究方向提供指導(dǎo)。
本文獻(xiàn)綜述的其余部分組織如下。首先，我們?cè)诘?節(jié)中提到了MTSP的不同現(xiàn)實(shí)應(yīng)用。這促使讀者對(duì)優(yōu)化問(wèn)題進(jìn)行審查，因?yàn)槲覀儽砻魉挥脕?lái)模擬幾個(gè)現(xiàn)實(shí)生活中的應(yīng)用。然后，我們?cè)诘?節(jié)中概述了MTSP，分析了現(xiàn)有的主要MTSP變體，并對(duì)它們進(jìn)行了正式的描述。之后，第4節(jié)專(zhuān)門(mén)回顧了第4.1節(jié)中提出的解決地面車(chē)輛和機(jī)器人的現(xiàn)有方案，以及第4.2節(jié)中對(duì)飛行器的解決方案。在第5節(jié)中，我們提出了對(duì)所審查的MTSP研究的分類(lèi)、分類(lèi)和分析。然后，在第6節(jié)中，我們討論了這些回顧的貢獻(xiàn)并給出了一些未來(lái)的方向。最后，我們?cè)诘?節(jié)中總結(jié)了本調(diào)查。圖1介紹了本論文的結(jié)構(gòu)圖。
2.MTSP的應(yīng)用領(lǐng)域
多年來(lái)，無(wú)人駕駛的移動(dòng)機(jī)器人、車(chē)輛和無(wú)人機(jī)一直被認(rèn)為是一種新興技術(shù)，它使許多復(fù)雜的飛行變得安全和容易。為了實(shí)現(xiàn)它們的任務(wù)，重要的是為每輛車(chē)確定一條路徑，該路徑在考慮一些約束的同時(shí)優(yōu)化給定的目標(biāo)。MTSP已在不同的實(shí)際應(yīng)用中采用，以獲得優(yōu)化的多條車(chē)輛路線。mtsp的主要應(yīng)用如圖2所示，如下所示：
運(yùn)輸和交付。
例如貨物配送或包裹遞送，或者公共汽車(chē)運(yùn)輸。車(chē)輛負(fù)責(zé)將貨物、包裹或人員從指定地點(diǎn)運(yùn)送到另一地點(diǎn)。在這種應(yīng)用中，應(yīng)考慮車(chē)輛容量和時(shí)間限制。此外，卡車(chē)車(chē)隊(duì)可以有效運(yùn)輸貴重貨物，而無(wú)人機(jī)可以在很短的時(shí)間內(nèi)運(yùn)送小包裹[13-17]。隨著無(wú)人機(jī)技術(shù)的出現(xiàn)，一種新的運(yùn)輸服務(wù)被提出，即無(wú)人機(jī)與卡車(chē)協(xié)同工作，將包裹遞送給客戶(hù)，以顯著縮短遞送時(shí)間。
WSN數(shù)據(jù)收集和網(wǎng)絡(luò)連接。
在無(wú)線傳感器網(wǎng)絡(luò)中，可以部署額外的傳感器節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)所收集的數(shù)據(jù)，直到數(shù)據(jù)到達(dá)匯點(diǎn)。然而，可以使用多個(gè)移動(dòng)機(jī)器人作為移動(dòng)接收器，從而幫助收集傳感器節(jié)點(diǎn)提供的數(shù)據(jù)。這種數(shù)據(jù)收集策略可以最大限度地減少位于固定匯點(diǎn)附近的傳感器節(jié)點(diǎn)的能量消耗，從而延長(zhǎng)網(wǎng)絡(luò)壽命[18-22]。作者在[22]中針對(duì)傳感器節(jié)點(diǎn)的數(shù)據(jù)收集和能量充電的聯(lián)合問(wèn)題提出了一個(gè)多目標(biāo)優(yōu)化模型。所提出的多目標(biāo)模型試圖優(yōu)化移動(dòng)機(jī)器人的總能量效率，并減少傳感器節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)钠骄舆t。在延遲容忍網(wǎng)絡(luò)中，移動(dòng)機(jī)器人可以通過(guò)從源節(jié)點(diǎn)獲取數(shù)據(jù)，然后將其傳遞到目的節(jié)點(diǎn)來(lái)重新建立網(wǎng)絡(luò)連接。在這樣的應(yīng)用中，可以使用一組無(wú)人機(jī)來(lái)代替地面機(jī)器人。其想法是，這些無(wú)人駕駛飛行器飛越斷開(kāi)連接的地面節(jié)點(diǎn)，負(fù)責(zé)收集數(shù)據(jù)，并充當(dāng)中繼[18，23，24]。應(yīng)考慮對(duì)存儲(chǔ)容量和數(shù)據(jù)延遲的限制。
搜救。
當(dāng)人類(lèi)生命處于危險(xiǎn)之中時(shí)，優(yōu)化搜救行動(dòng)中的每一秒至關(guān)重要[25，26]。在這樣的應(yīng)用中，確定要訪問(wèn)的位置，然后優(yōu)化要遵循的路線。隨著無(wú)人機(jī)技術(shù)的出現(xiàn)，無(wú)人機(jī)在搜救行動(dòng)中變得非常實(shí)用和有用[26]。
精準(zhǔn)農(nóng)業(yè)。
移動(dòng)機(jī)器人廣泛應(yīng)用于精準(zhǔn)農(nóng)業(yè)，例如確保作物監(jiān)測(cè)或灌溉管理。農(nóng)民需要為每個(gè)機(jī)器人提供一條優(yōu)化的路徑，以降低成本并提高產(chǎn)量。地面車(chē)輛和無(wú)人機(jī)對(duì)農(nóng)民都有很大幫助[27-29]。作者在[29]中提出了一種基于云的架構(gòu)，該架構(gòu)由WSN、移動(dòng)機(jī)器人和云系統(tǒng)組成，用于監(jiān)測(cè)溫室區(qū)域。作者首先生成了移動(dòng)機(jī)器人要訪問(wèn)的候選區(qū)域監(jiān)測(cè)點(diǎn)。然后，他們生成移動(dòng)機(jī)器人到達(dá)這些點(diǎn)的移動(dòng)路徑。為了計(jì)算機(jī)器人的最優(yōu)路徑，使用了TSP和MTSP問(wèn)題。
災(zāi)害管理。
在森林火災(zāi)、地震或工業(yè)事故后，移動(dòng)機(jī)器人可以幫助救援隊(duì)執(zhí)行任務(wù)[30，31]。例如，無(wú)人機(jī)的路線應(yīng)在關(guān)鍵地點(diǎn)進(jìn)行優(yōu)化[32]，例如在消防行動(dòng)期間。作者在[30]中提出了一種基于云的災(zāi)難管理系統(tǒng)。該系統(tǒng)由部署在將被監(jiān)測(cè)的感興趣區(qū)域的WSN組成，在發(fā)生災(zāi)難時(shí)，傳感器節(jié)點(diǎn)將向位于云側(cè)的中心站報(bào)告該信息。優(yōu)化的救援計(jì)劃被建模為MTSP，然后使用層次分析過(guò)程MTSP（AHP-MTSP）（the Analytical Hierarchy Process MTSP (AHP-MTSP)）方法生成。
監(jiān)測(cè)和監(jiān)督。
大面積區(qū)域可以由移動(dòng)機(jī)器人代替?zhèn)鞲衅鞴?jié)點(diǎn)進(jìn)行監(jiān)測(cè)。無(wú)人機(jī)已被廣泛應(yīng)用于監(jiān)控和監(jiān)視應(yīng)用中。在這種應(yīng)用中使用的大多數(shù)飛行器都是小型無(wú)人機(jī)平臺(tái)。然而，這些無(wú)人機(jī)的能量有限。在這種情況下，無(wú)人機(jī)巡視不得超過(guò)其最大能量，或者無(wú)人機(jī)可能在其監(jiān)測(cè)任務(wù)期間進(jìn)行一次或多次加油停留[33]。
多機(jī)器人任務(wù)分配和調(diào)度。
在機(jī)器人社區(qū)，一些工作已經(jīng)將多機(jī)器人任務(wù)分配（MRTA）（the Multi-Robot Task Allocation）問(wèn)題建模為MTSP。一般來(lái)說(shuō)，MRTA包括為每個(gè)機(jī)器人分配一組任務(wù)，同時(shí)優(yōu)化一些給定的指標(biāo)[9，34-38]。
合作任務(wù)。
當(dāng)一群車(chē)輛/機(jī)器人協(xié)同完成給定的任務(wù)時(shí)，例如軍事應(yīng)用中的目標(biāo)攻擊[32]。在合作任務(wù)中，車(chē)輛路線的計(jì)算應(yīng)考慮其他車(chē)輛的路線以及防撞。必須優(yōu)化這些運(yùn)載工具的軌跡，以便每輛運(yùn)載工具都能有效、安全、成功地執(zhí)行任務(wù)。請(qǐng)注意，在協(xié)作任務(wù)中，不同的機(jī)器人可能會(huì)多次訪問(wèn)一個(gè)引用。上述一些應(yīng)用可能需要協(xié)作機(jī)器人，如災(zāi)害管理[32]或使用卡車(chē)和無(wú)人機(jī)的包裹遞送[13-15]。
3.MTSP的定義和變體
MTSP被廣泛研究，最初的定義是，給定一組城市、一個(gè)停車(chē)場(chǎng)、m個(gè)推銷(xiāo)員和一個(gè)成本函數(shù)（如時(shí)間或距離），MTSP旨在為m個(gè)推銷(xiāo)員確定一組路線，使m條路線的總成本最小化，這樣，每條路線都在停車(chē)場(chǎng)開(kāi)始和結(jié)束，每個(gè)城市只由一個(gè)推銷(xiāo)員訪問(wèn)一次。
MTSP已被應(yīng)用于不同的應(yīng)用領(lǐng)域，這產(chǎn)生了該優(yōu)化問(wèn)題的新變體。在本節(jié)中，我們分析了MTSP的不同變體，然后對(duì)主要變體進(jìn)行了正式描述。
3.1變異分析
在本文中，我們擴(kuò)展了[9]中提出的MTSP變體，并根據(jù)最近對(duì)MTSP的貢獻(xiàn)對(duì)更多指標(biāo)進(jìn)行了分析。MTSP的新變體是考慮到銷(xiāo)售人員、倉(cāng)庫(kù)、城市以及問(wèn)題約束和目標(biāo)的不同特征的結(jié)果。
銷(xiāo)售人員特點(diǎn)：
?推銷(xiāo)員的類(lèi)型：根據(jù)應(yīng)用，MTSP中的旅行推銷(xiāo)員可以是推銷(xiāo)員、車(chē)輛、機(jī)器人或無(wú)人機(jī)（UAV），也稱(chēng)為無(wú)人機(jī)。注：在下文中，我們對(duì)銷(xiāo)售人員、車(chē)輛和機(jī)器人這三個(gè)術(shù)語(yǔ)的使用漠不關(guān)心。此外，無(wú)人機(jī)、無(wú)人機(jī)和飛行車(chē)輛這一術(shù)語(yǔ)的使用并不重要。
?銷(xiāo)售人員的數(shù)量m嚴(yán)格大于1；否則，問(wèn)題與TSP相同。m可以是固定的或者由MTSP確定。
?合作銷(xiāo)售人員：幾個(gè)銷(xiāo)售人員可能會(huì)合作完成給定的任務(wù)。它們可以是相同的車(chē)輛類(lèi)型，也可以組合在一起，例如用于卡車(chē)和無(wú)人機(jī)協(xié)同工作向客戶(hù)遞送包裹的遞送應(yīng)用。
倉(cāng)庫(kù)：
?單個(gè)倉(cāng)庫(kù)與多個(gè)倉(cāng)庫(kù)：在MTSP的標(biāo)準(zhǔn)版本中，只應(yīng)考慮一個(gè)倉(cāng)庫(kù)，其位置是固定的。由于使用了幾個(gè)推銷(xiāo)員，多個(gè)倉(cāng)庫(kù)的存在可以?xún)?yōu)化旅游成本。在這種MTSP的變體中，銷(xiāo)售人員可以從一個(gè)倉(cāng)庫(kù)開(kāi)始旅行，并在完成任務(wù)時(shí)加入另一個(gè)倉(cāng)庫(kù)。
?固定倉(cāng)庫(kù)與移動(dòng)倉(cāng)庫(kù)：一般來(lái)說(shuō)，在MTSP中，倉(cāng)庫(kù)是固定的。然而，在一些應(yīng)用中，倉(cāng)庫(kù)也可以是移動(dòng)的。例如，移動(dòng)倉(cāng)庫(kù)可以是無(wú)人機(jī)開(kāi)始和結(jié)束其旅程的卡車(chē)。
?封閉路徑與開(kāi)放路徑：在經(jīng)典的MTSP中，銷(xiāo)售人員的路徑是封閉的，因?yàn)樗麄儽仨殢耐粋€(gè)倉(cāng)庫(kù)位置開(kāi)始和結(jié)束他們的旅程。然而，在某些應(yīng)用程序中，銷(xiāo)售人員不需要返回倉(cāng)庫(kù)，可以留在最后訪問(wèn)的城市。此外，如果考慮多個(gè)倉(cāng)庫(kù)，則銷(xiāo)售人員可以加入任何可能與其初始倉(cāng)庫(kù)不同的現(xiàn)有倉(cāng)庫(kù)。
?加油點(diǎn)：當(dāng)允許加油時(shí)，可以在倉(cāng)庫(kù)或一些額外的加油位置進(jìn)行。
城市規(guī)格：
?標(biāo)準(zhǔn)MTSP：在標(biāo)準(zhǔn)MTSP中，所有銷(xiāo)售人員共享相同的工作空間，即他們共享所有城市。
?有色MTSP：[39]引入的一種新變體，稱(chēng)為有色旅行推銷(xiāo)員問(wèn)題（CTSP），其中有兩組城市。一組由所有銷(xiāo)售人員共享，一組由特定銷(xiāo)售人員訪問(wèn)的城市。
目標(biāo)函數(shù)：
?單一目標(biāo)與多目標(biāo)：MTSP可用于優(yōu)化單一目標(biāo)或多個(gè)目標(biāo)。此外，文獻(xiàn)中提到的主要目標(biāo)是：
-最大限度地減少所有旅行的（累計(jì)）距離或時(shí)間方面的總成本。
–最大限度地降低銷(xiāo)售人員的旅行成本。
–最大限度地縮短任務(wù)時(shí)間。
–最大限度地減少能源消耗。
–最大限度地減少銷(xiāo)售人員的數(shù)量。
–最大限度地減少額外成本，例如與加油站相關(guān)的成本。
值得注意的是，能源消耗和任務(wù)完成時(shí)間高度依賴(lài)于行駛的距離，因此，文獻(xiàn)中考慮的主要目標(biāo)是：行駛的總距離，機(jī)器人的最大行程，以及機(jī)器人行程長(zhǎng)度之間的平衡。
問(wèn)題限制：
?能量限制：銷(xiāo)售人員在移動(dòng)時(shí)消耗能量。卡車(chē)等車(chē)輛的能耗沒(méi)有任何限制，而小型無(wú)人機(jī)等其他車(chē)輛的自主性有限。因此，如果車(chē)輛在執(zhí)行任務(wù)期間無(wú)法進(jìn)行加油，則計(jì)算的行程將受到該車(chē)輛有限航程的限制。
?容量限制：在執(zhí)行任務(wù)期間，銷(xiāo)售人員可能攜帶包裹或數(shù)據(jù)。與能量約束相同，車(chē)輛容量約束通常考慮無(wú)人機(jī)等小型車(chē)輛，這些車(chē)輛只能攜帶小包裹，并且可能具有有限的數(shù)據(jù)存儲(chǔ)器存儲(chǔ)。
?時(shí)間窗口限制：它對(duì)應(yīng)于銷(xiāo)售人員需要訪問(wèn)給定目標(biāo)的時(shí)間間隔。在某些應(yīng)用程序中，它可能對(duì)應(yīng)于數(shù)據(jù)延遲，即銷(xiāo)售人員必須從一個(gè)站點(diǎn)獲取數(shù)據(jù)，攜帶數(shù)據(jù)，然后將數(shù)據(jù)交付到另一個(gè)站點(diǎn)。
3.2 變體的形式描述
如前所述，MTSP有幾種變體。在本節(jié)中，我們將對(duì)主要內(nèi)容進(jìn)行正式描述。為此，我們考慮一組n個(gè)目標(biāo)，即{T1，…，Tn}和一組m個(gè)機(jī)器人{(lán)R1，…，Rm}。機(jī)器人的任務(wù)是以最佳成本協(xié)同訪問(wèn)這些目標(biāo)。
根據(jù)目標(biāo)函數(shù)，MTSP一般有兩個(gè)主要提法，它們是[31]：
1.MinSum MTSP：
在該 MTSP變體中，目標(biāo)函數(shù)包括最小化所有機(jī)器人的旅行成本之和。從形式上講，MinSum變量被建模為：
?2. MinMax MTSP
在這個(gè)變體中，目標(biāo)函數(shù)在于最小化所有機(jī)器人的旅行中的最長(zhǎng)旅行成本（例如距離或時(shí)間）。這一目標(biāo)在以任務(wù)完成時(shí)間為重點(diǎn)的研究中得到了高度采納。從形式上講，這種變體被建模為：
當(dāng)總行程距離或機(jī)器人的能量消耗應(yīng)最小化時(shí)，最常使用MinSum，而當(dāng)任務(wù)完成時(shí)間必須最小化時(shí)，最多使用MinMax。其他目標(biāo)函數(shù)可以作為上述目標(biāo)函數(shù)的線性組合導(dǎo)出[40]。
此外，無(wú)論機(jī)器人是從單個(gè)倉(cāng)庫(kù)開(kāi)始還是最初位于不同的倉(cāng)庫(kù)，以及機(jī)器人是需要返回到其初始倉(cāng)庫(kù)（封閉路徑變體）還是可以停在最后訪問(wèn)的目標(biāo)（開(kāi)放路徑變體），機(jī)器人的旅行成本C（tour RI）公式都會(huì)發(fā)生變化。
更準(zhǔn)確地說(shuō)，設(shè)C（Ti，Tj）是從目標(biāo)Ti行進(jìn)到目標(biāo)Tj的成本，并且C（Tour R i）是機(jī)器人R i的行進(jìn)成本，每個(gè)變體中的機(jī)器人行進(jìn)成本可以建模如下：
Single depot, closed path MTSP. 單一倉(cāng)庫(kù)，封閉路徑MTSP：在這個(gè)變體中，所有機(jī)器人都從同一個(gè)倉(cāng)庫(kù)開(kāi)始，一旦完成任務(wù)，它們就會(huì)返回。因此，機(jī)器人Ri從倉(cāng)庫(kù)D開(kāi)始其巡視，然后按順序訪問(wèn)r個(gè)指定目標(biāo)的列表{T i 1，…，T i r}，并最終返回D。機(jī)器人Ri的巡視成本等于：
Single depot,open path MTSP :I單一倉(cāng)庫(kù)，開(kāi)放路徑MTSP：在這個(gè)變體中，機(jī)器人位于最后一個(gè)訪問(wèn)目標(biāo)的頂部。機(jī)器人R i的游覽成本等于：
?
Multiple depots, closed path MTSP :多個(gè)倉(cāng)庫(kù)，封閉路徑mtsp：在這個(gè)變體中，m個(gè)機(jī)器人最初位于m個(gè)不同的倉(cāng)庫(kù)，稱(chēng)為{D1，…，Dm}。因此，機(jī)器人R i的游覽成本等于：
?
Multiple depots, open path MTSP : 多個(gè)倉(cāng)庫(kù)，開(kāi)放路徑MTSP：在多個(gè)倉(cāng)庫(kù)MTSP的開(kāi)放路徑變體中，機(jī)器人不必返回其初始倉(cāng)庫(kù)，因此，機(jī)器人R i的旅行成本等于：
?
關(guān)于MTSP的正式描述和MTSP可能的表述的更多細(xì)節(jié)，我們請(qǐng)讀者參閱[31]和[9]。在下文中，我們確定了兩大類(lèi)MTSP，即：（1）銷(xiāo)售人員、車(chē)輛和機(jī)器人的MTSP和（2）無(wú)人機(jī)的MTSP。事實(shí)上，基于無(wú)人機(jī)的優(yōu)化問(wèn)題與傳統(tǒng)的車(chē)輛和機(jī)器人具有不同的特征和約束。
開(kāi)始沒(méi)好好看
4 MTSP方法
顧名思義，MTSP最初是為了優(yōu)化旅行推銷(xiāo)員問(wèn)題而設(shè)計(jì)的。然后，它被推廣到地面車(chē)輛機(jī)器人的處理優(yōu)化任務(wù)中。然而，最近十年，無(wú)人機(jī)、新飛車(chē)輛已經(jīng)出現(xiàn)。首先使用的是無(wú)人機(jī)的危險(xiǎn)軍事任務(wù)的安全駕駛。隨后，這些簡(jiǎn)單的車(chē)輛引起了人們對(duì)各種民用應(yīng)用的極大興趣，它們的使用也在繼續(xù)增長(zhǎng)。在文獻(xiàn)中，最近的一些研究提出了不同的方法來(lái)解決MTSP。大多數(shù)為飛行器提出的方法都擴(kuò)展了那些應(yīng)用于地面車(chē)輛的方法，同時(shí)考慮了無(wú)人機(jī)的限制，如能源消耗或其有限的承載能力。
在本節(jié)中，我們建議研究和分析應(yīng)用于分別解決地面車(chē)輛（包括銷(xiāo)售人員和機(jī)器人）和飛行車(chē)輛的MTSP的不同方法，以幫助讀者理解每種類(lèi)型的車(chē)輛的問(wèn)題，并指導(dǎo)他/她選擇最合適的方法來(lái)解決他/她的優(yōu)化問(wèn)題。這些方法如圖3所示。
?
?4.1 地面車(chē)輛和機(jī)器人的MTSP
本節(jié)專(zhuān)門(mén)回顧現(xiàn)有的專(zhuān)注于地面車(chē)輛、機(jī)器人或銷(xiāo)售人員在一般情況下的MTSP的貢獻(xiàn)。我們根據(jù)所使用的優(yōu)化方法對(duì)這些解決方案進(jìn)行了分類(lèi)，如圖3所示。它們?nèi)缦?/p>
4.1.1 確定性方法
也被稱(chēng)為精確方法，能夠達(dá)到給定優(yōu)化問(wèn)題的最優(yōu)解。一般來(lái)說(shuō)，由于計(jì)算的復(fù)雜性，這些方法非常耗時(shí)。因此，只有少數(shù)論文采用了精確的方法。作者在[41]中，將多倉(cāng)庫(kù)多旅行推銷(xiāo)員問(wèn)題（MDMTSP）轉(zhuǎn)化為單倉(cāng)庫(kù)非對(duì)稱(chēng)TSP問(wèn)題。在本文中，目標(biāo)之間的旅行成本必須滿(mǎn)足三角形不等式。為了將問(wèn)題從一個(gè)多倉(cāng)庫(kù)轉(zhuǎn)化為一個(gè)單一的倉(cāng)庫(kù)MTSP，增加了一組額外的節(jié)點(diǎn)，使每個(gè)新節(jié)點(diǎn)都被視為一個(gè)倉(cāng)庫(kù)。一旦轉(zhuǎn)換完成，就應(yīng)用標(biāo)準(zhǔn)的TSP精確方法來(lái)解決這個(gè)問(wèn)題。
在[42]中也使用精確算法解決了帶有異質(zhì)車(chē)輛的MDMTSP。作者首先介紹了整數(shù)線性規(guī)劃（ILP）的表述。那么，他們提出了一種定制的分支切割算法，該算法在100個(gè)目標(biāo)和5輛車(chē)的300次實(shí)例中達(dá)到了最優(yōu)解。
另一項(xiàng)研究[43]使用約束編程（CP）來(lái)制定和優(yōu)化解決MTSP，通過(guò)應(yīng)用全局約束、區(qū)間變量和域過(guò)濾算法。然而，由于解決51個(gè)城市和3個(gè)銷(xiāo)售人員的實(shí)例的執(zhí)行時(shí)間超過(guò)2小時(shí)，因此所提出的方法很耗時(shí)。
4.1.2 基于元啟發(fā)式的方法
文獻(xiàn)中最常用的元啟發(fā)式算法；遺傳算法（GA）、蟻群優(yōu)化（ACO）、實(shí)用蜂群優(yōu)化（PSO）和人工蜂群（ABC）技術(shù)。
基于GA的方法。
GA技術(shù)的原理是基于自然選擇和遺傳學(xué)來(lái)生成上一代的最佳解決方案。這個(gè)過(guò)程從一個(gè)初始隨機(jī)解（代）開(kāi)始。然后，計(jì)算一個(gè)健身函數(shù)來(lái)評(píng)估每個(gè)迭代中的解決方案的性能。之后，該過(guò)程選擇兩個(gè)父代解決方案，并計(jì)算交叉/變異操作，以產(chǎn)生兩個(gè)新的解決方案，這些解決方案將在下一代中插入。如果計(jì)算出的子代解決方案有更好的適配值，它們將取代父代解決方案。這個(gè)選擇、交叉和變異的過(guò)程不斷重復(fù)，直到新一代達(dá)到種群規(guī)模。這就完成了一次迭代（生成）。該算法一直持續(xù)到達(dá)到一定的代數(shù)（由用戶(hù)決定）或解決方案的質(zhì)量不再提高為止?
在GA方法中，解決方案被表示為染色體。有不同的染色體表示技術(shù)。文獻(xiàn)中使用的主要方法如圖4所示。
作者在[45]中提出了一個(gè)兩部分的染色體編碼（圖4d），并開(kāi)發(fā)了一種新的交叉方法。提出的交叉方法與現(xiàn)有的交叉方法進(jìn)行了比較，如有序交叉算子（ORX）、循環(huán)交叉算子（CX）和部分匹配交叉算子（PMX）。考慮到目標(biāo)被優(yōu)化，包括總行程和最大行程長(zhǎng)度。性能評(píng)估證明了所提出的交叉方法在產(chǎn)生更好的解決方案質(zhì)量方面的效率。
?[46]中的作者旨在建立一個(gè)遺傳算法解決方案來(lái)解決MTSP。他們首先比較了六種不同的交叉運(yùn)算符，即循環(huán)交叉（CX）、部分匹配交叉、順序交叉（OX）、邊緣重組交叉（ERX）、交替位置交叉（AEX）、順序結(jié)構(gòu)交叉（SCX）。不同規(guī)模的實(shí)驗(yàn)分析TSPLIBbenchmarkinstances[47]顯示了交叉方法的性能。此外，實(shí)驗(yàn)研究表明，順序構(gòu)造交叉法的性能優(yōu)于其他交叉法。
最近，一些研究集中在Partheno遺傳算法（PGA）上[44,48]。[48]中的研究介紹了兩種partheno遺傳算法。第一個(gè)是帶有輪盤(pán)賭和精英選擇的PGA，并提出了四種新的變異操作類(lèi)型。第二種被稱(chēng)為IPGA，它建議將選擇和突變結(jié)合起來(lái)，使用更廣泛的突變算子。作者使用了一種序列編碼方法來(lái)描述該種群，該方法考慮了機(jī)器人在染色體中的路由和斷點(diǎn)（圖4c）。這個(gè)染色體被分割開(kāi)來(lái)：第一部分代表機(jī)器人的路徑，第二部分對(duì)應(yīng)于斷點(diǎn)部分。仿真結(jié)果顯示，IPGA的性能最好。
作者在[44]中研究了PGA在解決MDMTSP方面的優(yōu)點(diǎn)和缺點(diǎn)，并報(bào)告了由于缺乏群體中個(gè)體的局部信息而導(dǎo)致的缺陷。為了解決這個(gè)缺陷，作者提議將繁殖機(jī)制整合到入侵性雜草算法（IWO）中。由此產(chǎn)生的算法，稱(chēng)為RIPGA，用于改進(jìn)的具有復(fù)制機(jī)制的Partheno-Genetic算法，與GA解決方案進(jìn)行了比較，以證明其在避免局部融合方面的效率。
一些實(shí)際應(yīng)用需要對(duì)更多的標(biāo)準(zhǔn)進(jìn)行優(yōu)化，如最小化機(jī)器人的能源消耗、任務(wù)完成時(shí)間等。因此，方法解決MTSP可能需要同時(shí)優(yōu)化幾個(gè)目標(biāo)。這種問(wèn)題被稱(chēng)為 "多目標(biāo)MTSP（MOMTSP）。事實(shí)上，作者在[49]中使用了非支配排序遺傳算法（NSGA-II）來(lái)提供多目標(biāo)MTSP的解決方案。該方案旨在優(yōu)化兩個(gè)目標(biāo)，即：最小化總行程和平衡銷(xiāo)售人員之間的旅行時(shí)間。該解決方案計(jì)算出一組非主導(dǎo)的解決方案。然而，作者并沒(méi)有解釋如何計(jì)算旅行時(shí)間。
[50]中的另一項(xiàng)研究提出了一個(gè)多目標(biāo)優(yōu)化問(wèn)題，稱(chēng)為多機(jī)器人部署無(wú)線傳感器節(jié)點(diǎn)問(wèn)題（MRDS），其中多個(gè)機(jī)器人必須在給定的位置部署傳感器節(jié)點(diǎn)。在MRDS中考慮了三個(gè)目標(biāo)；最小化任務(wù)時(shí)間（即傳感器部署時(shí)間），最小化使用的機(jī)器人數(shù)量，以及平衡機(jī)器人的行程時(shí)間。作者解決了基于NSGA-II算法的MRDS問(wèn)題。
基于PSO的方法。
粒子群優(yōu)化方法是最著名的元啟發(fā)式方法之一，與遺傳算法有許多相似之處。PSO首先啟動(dòng)一個(gè)隨機(jī)解決方案的群體，然后更新生成，直到達(dá)到一個(gè)最佳狀態(tài)。然而，與遺傳算法不同，PSO不使用交叉或變異操作來(lái)進(jìn)化群體。在PSO中，可能的解決方案，被稱(chēng)為粒子，以其速度為特征，按照當(dāng)前的最佳粒子在問(wèn)題空間中移動(dòng)。
粒子群優(yōu)化方法被應(yīng)用于[51]中提出的研究中。在這項(xiàng)研究中，作者解決了多機(jī)器人合作任務(wù)分配的問(wèn)題，并將其表述為MTSP。該解決方案的目的是使機(jī)器人的總行駛距離和最大旅游成本最小。作者擴(kuò)展了標(biāo)準(zhǔn)的PSO來(lái)處理幾個(gè)目標(biāo)。為此，作者提出了兩種策略，即刪除劣質(zhì)解決方案的帕累托前沿細(xì)化策略，以及基于概率的領(lǐng)導(dǎo)者選擇策略。作者將所提出的方法與眾所周知的多目標(biāo)方法進(jìn)行了比較，如OMOPSO[52]、SPEA2[53]、NSGA-II[54]和SMPSO[55]，并證明了其優(yōu)越性。
在同樣的背景下，作者在[56]中也討論了MRTA問(wèn)題，并提出了動(dòng)態(tài)和分布式PSO的DDPSO。解決方案由兩個(gè)階段組成。在第一個(gè)例子中，它將任務(wù)分組到集群中。然后，在第二階段，它將集群分配給機(jī)器人。將所提出的解決方案與分布式粒子群算法和遺傳算法進(jìn)行了比較。
基于ACO的方法。
蟻群優(yōu)化方法是一種基于種群的元啟發(fā)式方法，用于解決組合優(yōu)化問(wèn)題。ACO的靈感來(lái)自于真實(shí)蟻群的能力，即通過(guò)使用化學(xué)信息素軌跡在蟻群之間進(jìn)行交流來(lái)有效地組織蟻群的食物尋找行為。在群體中，每個(gè)個(gè)體都是一個(gè)人工代理，它逐步和隨機(jī)地構(gòu)建一個(gè)給定優(yōu)化問(wèn)題的解決方案。在下文中，我們回顧了基于ACO方法解決MTSP的貢獻(xiàn)。
作者在[57]中對(duì)任務(wù)分配問(wèn)題進(jìn)行了建模，該問(wèn)題是在水下車(chē)輛安全約束的MTSP下進(jìn)行的。該解決方案旨在最小化總行駛距離和總轉(zhuǎn)彎角度，從而使車(chē)輛能耗最小化。此外，解決方案迫使每輛車(chē)的目標(biāo)數(shù)不能超過(guò)1。建議的解決方案包括兩個(gè)步驟。首先，該解決方案決定了分配給每輛車(chē)的目標(biāo)數(shù)量。然后，使用所提出的多蟻群系統(tǒng)（MACS）方法來(lái)解決多目標(biāo)MTSP。實(shí)驗(yàn)結(jié)果證明，所提出的多ACS優(yōu)于經(jīng)典的ACS。
在[58]中，作者們解決了ACO解決多目標(biāo)單倉(cāng)庫(kù)MTSP的問(wèn)題。
在[59]中，作者提出了面向任務(wù)的蟻隊(duì)ACO（MOAT-ACO）算法。MOATACO算法的目的是最小化總距離并實(shí)現(xiàn)負(fù)載平衡。在這個(gè)解決方案中，作者賦予蟻群以方向性意識(shí)和忠誠(chéng)度特征，并提出了一個(gè)任務(wù)信息素來(lái)模仿生物本能。因此，這緩解了蟻群之間的糾纏，從而使其中一個(gè)目標(biāo)最小化，即總距離。為了達(dá)到第二個(gè)目標(biāo)，即負(fù)載平衡（旅游之間的負(fù)載平衡），引入了一個(gè)蟻群發(fā)射規(guī)則，允許最慢的蟻群加入更難工作的蟻群。
作者在[60]中解決了MRTA問(wèn)題，并提出了一種基于ACO的多目標(biāo)MTSP算法。ACO方法與序列變量鄰域下降相結(jié)合，以進(jìn)一步改進(jìn)局部Pareto集解。該解決方案旨在同時(shí)最小化總行程和最大行程，并與NSGA-II、MOEA/D-ACO[61]和FL-MTSP[62]進(jìn)行了比較。盡管該解決方案在解決方案質(zhì)量方面優(yōu)于這些方法，但它低于FL-MTSP。作者在[63]中討論了具有時(shí)間窗口的mstp，并通過(guò)將ACO與最小生成1-樹(shù)集成來(lái)提供最優(yōu)解決方案，提出了一種混合解決方案。
基于ABC的方法。
與ACO方法一樣，人工蜂群是一種專(zhuān)注于蜜蜂群智能食品搜索行為的優(yōu)化方法。ABC也是一種基于種群的方法，其中食物源的位置（即種群）是優(yōu)化問(wèn)題的潛在解決方案，來(lái)自食物源的甘油數(shù)量代表相關(guān)解決方案的適用性。Venkatesh等人。[64]使用ABC算法解決單一倉(cāng)庫(kù)的MTSP，旨在最小化總行駛距離（MinSum）和最大行駛距離（MinMax）。作者還提出使用局部搜索來(lái)改善獲得的結(jié)果。同一作者在[65]中討論了彩色MTSP，還提出了一個(gè)基于ABC的解決方案。作者修改了ABC算法并引入了生成鄰域解決方案（GNS）來(lái)解決MTSP。
混合方法
在文獻(xiàn)中，一些研究提出了混合算法，結(jié)合不同的元啟發(fā)法和技術(shù)來(lái)更有效地解決多旅行推銷(xiāo)員問(wèn)題。
例如，[61]中的研究提出了一種混合方法，將ACO算法與基于分解的多目標(biāo)進(jìn)化算法（MOEA/D）相結(jié)合，以解決多目標(biāo)MTSP。該解決方案的想法是將多目標(biāo)MTSP分為幾個(gè)單目標(biāo)子問(wèn)題。然后，每個(gè)單目標(biāo)子問(wèn)題被分配給一只蟻。蟻群被組織成一組，每只都有幾只相鄰的蟻。每組都與一個(gè)信息素矩陣和每個(gè)啟發(fā)式知識(shí)矩陣相關(guān)聯(lián)。此外，每只蟻?zhàn)佣钾?fù)責(zé)尋求其分配的子問(wèn)題的最優(yōu)解。出于這個(gè)原因，蟻群利用其啟發(fā)式知識(shí)矩陣、其群體信息素矩陣和其當(dāng)前的解決方案。圍繞這種方法的關(guān)鍵問(wèn)題是時(shí)間融合的模糊性和實(shí)施的難度。
[67]中提出了一種新的用于大規(guī)模MTSP的混合算法。所提出的解決方案，稱(chēng)為AC-PGA for Ant ColonyPGA，是通過(guò)整合PGA和ACO獲得的。更確切地說(shuō)，該算法首先利用PGA來(lái)確定銷(xiāo)售員倉(cāng)庫(kù)的最佳值和每個(gè)銷(xiāo)售員要訪問(wèn)的城市數(shù)量。然后，它利用ACO來(lái)計(jì)算每個(gè)銷(xiāo)售員的最短路徑。
進(jìn)一步的研究[68]解決了家庭保健問(wèn)題中護(hù)理人員的調(diào)度和路由問(wèn)題，并將其表述為帶有時(shí)間窗口的MTSP。他們提出了一種結(jié)合ACO和記憶算法的混合方法[69]。該解決方案的目的是最小化總的旅行時(shí)間，并平衡護(hù)理人員（銷(xiāo)售人員）的工作時(shí)間。
4.1.3. 基于市場(chǎng)的方法
基于市場(chǎng)的方法，也被稱(chēng)為基于拍賣(mài)的方法，可以是集中式的中央拍賣(mài)者，接收出價(jià)并將城市分配給成本最低的銷(xiāo)售人員，或者分布在不同的銷(xiāo)售人員之間共享競(jìng)價(jià)過(guò)程。
作者在[70]中提出了一種基于市場(chǎng)的分布式動(dòng)態(tài)MTSP算法，其中銷(xiāo)售人員是機(jī)器人。因此，該問(wèn)題被稱(chēng)為多個(gè)行走機(jī)器人問(wèn)題（MTRP）。在這個(gè)解決方案中，每個(gè)機(jī)器人以漸進(jìn)和分布式的方式選擇自己的目標(biāo)，如下所示。首先，每個(gè)機(jī)器人使用最短距離作為成本函數(shù)來(lái)選擇合適的目標(biāo)。然后，它宣布對(duì)其目標(biāo)參觀時(shí)間表進(jìn)行單項(xiàng)拍賣(mài)。選擇最佳的機(jī)器人覓食任務(wù)要?dú)w功于一種稱(chēng)為DNP（用于合同網(wǎng)協(xié)議）的基于構(gòu)造的協(xié)議。Webots仿真結(jié)果表明，所提出的解決方案在可擴(kuò)展性、總路徑長(zhǎng)度和通信開(kāi)銷(xiāo)方面都很有效。
在[71]中，多機(jī)器人任務(wù)分配問(wèn)題（MRTA）被公式化為MSTP，并使用帶有動(dòng)作過(guò)程的K-均值聚類(lèi)技術(shù)進(jìn)行求解。該解決方案可以縮短總距離四個(gè)波長(zhǎng)，并平衡機(jī)器人的長(zhǎng)度。首先，使用K-means算法形成n組任務(wù)，其中n是機(jī)器人的數(shù)量。然后，每個(gè)機(jī)器人計(jì)算訪問(wèn)在前一步驟中形成的每個(gè)集群的成本。最后，在拍賣(mài)步驟中，機(jī)器人在集群上出價(jià)，每個(gè)集群以最低的成本分配給機(jī)器人。然而，該算法的復(fù)雜性相當(dāng)高，因?yàn)樗紤]了集群機(jī)器人分配的所有可能組合。因此，這種方法可能不適合解決大規(guī)模實(shí)例。
受基于共識(shí)的捆綁算法（CBBA）[72]和基于市場(chǎng)的前瞻代理方法（MALA）[73]的啟發(fā)，[74]的作者為MTSP引入了一個(gè)基于市場(chǎng)的解決方案。解決方案是一個(gè)重復(fù)的市場(chǎng)程序，機(jī)器人執(zhí)行以下步驟：市場(chǎng)拍賣(mài)、代理人之間的交易、代理人轉(zhuǎn)換和代理人放棄步驟。每個(gè)機(jī)器人根據(jù)目標(biāo)成本，在市場(chǎng)拍賣(mài)階段選擇最佳任務(wù)。機(jī)器人在代理與代理之間的交易步驟中任意檢查其他機(jī)器人的任務(wù)，以驗(yàn)證它們是否能以較低的價(jià)格執(zhí)行這些任務(wù)中的任何一個(gè)。在代理切換階段，該算法試圖探索不在最小位置的解決方案。該算法在anumberofiterations之后沒(méi)有性能改進(jìn)。
Cheikhrouhouetal.proposeda-based method，稱(chēng)為Move-and-Improve，見(jiàn)[75,76]。建議的解決方案涉及機(jī)器人在分配目標(biāo)和逐步消除可能的重疊方面的合作。這個(gè)概念很簡(jiǎn)單：機(jī)器人在與鄰居交流時(shí)，每一步都會(huì)移動(dòng)并試圖優(yōu)化其解決方案。移動(dòng)和改進(jìn)方法包括四個(gè)主要階段：（1）初始目標(biāo)分配，（2）旅游建設(shè)，（3）沖突目標(biāo)的談判，（4）解決方案改進(jìn)。使用MATLAB和Webots模擬器對(duì)移動(dòng)和改進(jìn)進(jìn)行了模擬，并使用機(jī)器人操作系統(tǒng)（ROS）部署在真實(shí)的機(jī)器人上。
另一個(gè)基于聚類(lèi)市場(chǎng)的算法（CM-MTSP）[77]被提出來(lái)用于多目標(biāo)MTSP。解決方案包括三個(gè)步驟，即：聚類(lèi)、拍賣(mài)和改進(jìn)。在聚類(lèi)步驟中，一個(gè)中央服務(wù)器使用k-means將目標(biāo)分組為集群。然后，服務(wù)器逐一宣布已經(jīng)形成的集群，機(jī)器人通過(guò)計(jì)算成本對(duì)每個(gè)集群進(jìn)行投標(biāo)，并將其發(fā)送給服務(wù)器。服務(wù)器最后將集群分配給成本最低的機(jī)器人。改進(jìn)步驟的目的是優(yōu)化另一個(gè)目標(biāo)，即最大旅行和任務(wù)完成時(shí)間。這種改進(jìn)是通過(guò)機(jī)器人之間的集群排列來(lái)實(shí)現(xiàn)的。在這個(gè)算法中，作者給每個(gè)機(jī)器人分配了一個(gè)集群。然而，改變聚類(lèi)的數(shù)量可能會(huì)帶來(lái)更好的結(jié)果。此外，作者以同時(shí)處理多目標(biāo)問(wèn)題的方式處理，不一定能得到最好的結(jié)果。
4.1.4. 其他方法
在下文中，我們將回顧一些MTSP的貢獻(xiàn)，這些貢獻(xiàn)采用了不同的技術(shù)，如概率論、游戲理論、模糊邏輯、分析層次過(guò)程等。
TosolvetheMDMTSP,作者在[78]中介紹了使用概率集合的Damethod，其中車(chē)輛被表示為自主代理，車(chē)輛作為一種策略進(jìn)行路由
Khoufi等人。[79]提出了一個(gè)多目標(biāo)優(yōu)化問(wèn)題，以確定負(fù)責(zé)從無(wú)線傳感器節(jié)點(diǎn)收集數(shù)據(jù)的機(jī)器人之旅，并將這些數(shù)據(jù)傳遞給倉(cāng)庫(kù)。建議的優(yōu)化問(wèn)題應(yīng)滿(mǎn)足一些約束條件，如數(shù)據(jù)交付延遲、機(jī)器人能量和有限的機(jī)器人數(shù)量。這個(gè)優(yōu)化問(wèn)題是基于博論方法解決的。所提出的理論游戲是一個(gè)聯(lián)盟形成游戲，它優(yōu)化了最大旅行時(shí)間、機(jī)器人的數(shù)量，并平衡了機(jī)器人的旅行。
Todressthemulti-objectiveMTSP,afuzzylogic-basedsolution（FL-MTSP）是由Trigui等人提出的。[62]。該解決方案考慮了兩個(gè)目標(biāo)，MinSum和MinMax。FL-MTSP解決方案與基于GA的解決方案[34]進(jìn)行了比較，以證明其效率。
最近，Cheikhrouhou等人[31,80]提出了AHP-MTSP，一種基于分析層次過(guò)程（AHP）的方法。AHP-MTSP首先為每個(gè)考慮的目標(biāo)計(jì)算一個(gè)權(quán)重。這些權(quán)重是根據(jù)用戶(hù)的偏好并使用AHP方法[81]計(jì)算的。然后，不同的目標(biāo)被匯總成一個(gè)單一的函數(shù)，作為不同加權(quán)目標(biāo)的總和。AHP-MTSP與包括FL-MTSP[62]和CM-MTSP[77]在內(nèi)的幾種方法的比較證明了其優(yōu)越性。
受[45]工作的啟發(fā)，[82]中的作者提出了一種ModifiedTwo-PartWolfPackSearch(MTWPS)方法，該方法由兩部分染色體編碼方法和轉(zhuǎn)置和擴(kuò)展操作來(lái)解決MTSP.該解決方案旨在最小化總行程和最大行程。
Venkatesh等人。[64]提出了一種基于入侵性雜草優(yōu)化算法的元啟發(fā)式方法。為了進(jìn)一步改進(jìn)解決方案，還使用了局部搜索方法。
表1總結(jié)了為地面車(chē)輛和機(jī)器人提出的不同討論的MTSP解決方案。
4.2.無(wú)人機(jī)MTSP
在本節(jié)中，我們回顧了最近在無(wú)人機(jī)背景下使用MTSP的研究，并根據(jù)所采用的方法對(duì)這些MTSP解決方案進(jìn)行了分類(lèi)，同時(shí)強(qiáng)調(diào)了它們的應(yīng)用領(lǐng)域。表2總結(jié)了為無(wú)人機(jī)提出的不同審查MTSP解決方案。
?4.2.1. 確定性的方法
在運(yùn)輸和配送應(yīng)用中，[87]中的作者首次正式定義了將飛行器與卡車(chē)結(jié)合起來(lái)進(jìn)行包裹配送的問(wèn)題。然后，他們擴(kuò)展了[13]中的研究，引入了多飛行伙伴旅行推銷(xiāo)員問(wèn)題（mFSTSP），即部署卡車(chē)和無(wú)人機(jī)車(chē)隊(duì)向客戶(hù)運(yùn)送小包裹。這個(gè)問(wèn)題被公式化為混合整數(shù)線性規(guī)劃（MILP），并通過(guò)Gurobi解決小尺寸問(wèn)題。
在這一背景下，[14]中的作者基于[87]中的研究，提出了無(wú)人機(jī)的多重旅行推銷(xiāo)員問(wèn)題（MTSPD），該問(wèn)題基于無(wú)人機(jī)和卡車(chē)在最后一英里的交付。擬議模式是MTSP的一個(gè)變體。在這個(gè)優(yōu)化問(wèn)題中，多架無(wú)人機(jī)和多輛卡車(chē)一起執(zhí)行交付。MTSPD的目標(biāo)是在將所有包裹交付給客戶(hù)后，將車(chē)輛、卡車(chē)和無(wú)人機(jī)在倉(cāng)庫(kù)的到達(dá)時(shí)間降至最低。為了求解MTSPD，作者提出了混合整數(shù)規(guī)劃（MIP）公式，并使用IBM-CPLEX[88]獲得了解決方案。
由于計(jì)算的復(fù)雜性，[13]和[14]中引入的優(yōu)化問(wèn)題只對(duì)小實(shí)例進(jìn)行了優(yōu)化解決。然而，這兩項(xiàng)研究都應(yīng)用啟發(fā)式方法來(lái)解決他們?cè)谥行秃痛笮蛯?shí)例中的問(wèn)題。我們?cè)谙乱还?jié)中回顧了這些啟發(fā)式方法。
[15]中的另一項(xiàng)研究擴(kuò)展了[87]中提出的多個(gè)四級(jí)alesman問(wèn)題的問(wèn)題。在該研究中，當(dāng)一個(gè)客戶(hù)和另一個(gè)客戶(hù)將包裹送到另一個(gè)顧客那里以提取新包裹或直接返回到倉(cāng)庫(kù)以開(kāi)始新的交付時(shí)，地址負(fù)責(zé)丟棄包裹。該問(wèn)題被建模為一個(gè)不相關(guān)的并行機(jī)調(diào)度（PMS），并將多個(gè)倉(cāng)庫(kù)與多輛卡車(chē)和無(wú)人機(jī)進(jìn)行了集成，受時(shí)間窗口、接送同步和多次訪問(wèn)的限制。為了解決這個(gè)問(wèn)題，提出了一種新的約束規(guī)劃方法，以最小化滿(mǎn)足所有交付任務(wù)所需的最大時(shí)間。
在攻擊多個(gè)目標(biāo)的背景下，[32]研究了多個(gè)無(wú)人作戰(zhàn)飛行器（UCAV）的合作軌跡規(guī)劃綜合目標(biāo)分配問(wèn)題。該問(wèn)題被表述為動(dòng)態(tài)約束、多倉(cāng)庫(kù)、多旅行問(wèn)題與鄰域（DC_MDMTSPN），它是MTSP的一個(gè)變種。所提出的問(wèn)題考慮到了戰(zhàn)場(chǎng)環(huán)境約束（如威脅規(guī)避）和UCAV動(dòng)力學(xué)模型（如避免相互碰撞），并基于兩階段的方法進(jìn)行解決。在第一階段，作者構(gòu)建了有向圖，然后將原始問(wèn)題轉(zhuǎn)化為非對(duì)稱(chēng)TSP（ATSP）。在第二階段，他們使用Lin? Kernighan啟發(fā)式（LKH）搜索算法來(lái)解決ATSP。
[83]中的研究介紹了異構(gòu)多無(wú)人機(jī)任務(wù)分配問(wèn)題的問(wèn)題表述為多個(gè)旅行推銷(xiāo)員問(wèn)題。作者提出了一種新的基于數(shù)字圖的無(wú)死鎖算法，以及一種修正的兩部分Wolf Pack Search算法來(lái)有效解決確定性的離線問(wèn)題。
4.2.2. 基于元啟發(fā)式的方法
元啟發(fā)式已經(jīng)被應(yīng)用于解決許多NP-hard優(yōu)化問(wèn)題。在這一節(jié)中，我們對(duì)基于MTSP的啟發(fā)式算法如遺傳算法和Tabu搜索的貢獻(xiàn)進(jìn)行了回顧。請(qǐng)注意，許多研究提出了組合啟發(fā)式方法，其中問(wèn)題的解決遵循幾個(gè)階段，并基于不同的技術(shù)（如聚類(lèi)、元啟發(fā)式）來(lái)降低問(wèn)題的復(fù)雜性。
基于遺傳算法的方法。
在最后一英里交付的背包和背包的背景下，作者在[14]中為小型實(shí)例優(yōu)化求解了MTSPD，并提出了一種新的啟發(fā)式算法，稱(chēng)為自適應(yīng)插入算法（ADI）來(lái)求解大型實(shí)例。ADI的原理是首先構(gòu)建一個(gè)初始解決方案，然后通過(guò)應(yīng)用移除和插入運(yùn)算符來(lái)構(gòu)建MTSPD解決方案來(lái)改進(jìn)它。為了執(zhí)行ADI的第二階段，作者基于遺傳算法、組合K?means/Nearest Neighbor和隨機(jī)聚類(lèi)/Tour。仿真結(jié)果表明，在小規(guī)模實(shí)例中，求解器和遺傳元啟發(fā)式算法GA?ADI都達(dá)到了最優(yōu)解。請(qǐng)注意，GA-ADI解決MTSPD問(wèn)題的速度明顯快于求解器IBM-CPLEX[88]。然而，在大型情況下，作者只使用了GA?ADI啟發(fā)式算法，他們證明了使用多架無(wú)人機(jī)來(lái)縮短交付時(shí)間的效率。
作者在[23]中提出了一項(xiàng)將無(wú)人機(jī)作為DTN中繼的研究，并引入了一個(gè)名為Deadline Triggered Pigeon with Traveling Salesman Problem with Deadline（DTP-TSP-D）的主動(dòng)方案。在這個(gè)問(wèn)題中，無(wú)人機(jī)可以與一個(gè)或一個(gè)集群的節(jié)點(diǎn)進(jìn)行通信，從一個(gè)地面節(jié)點(diǎn)拾取數(shù)據(jù)，同時(shí)考慮它從一個(gè)地方向另一個(gè)地方傳遞信息的能力，然后懸停，直到被觸發(fā)傳遞指向其他地面節(jié)點(diǎn)的信息。一個(gè)遺傳算法被用來(lái)確定在交付時(shí)間方面優(yōu)化的無(wú)人機(jī)之旅。
[24]中的一項(xiàng)類(lèi)似研究提出，使用無(wú)人機(jī)作為消息渡輪節(jié)點(diǎn)，負(fù)責(zé)在DTN網(wǎng)絡(luò)中斷開(kāi)連接的節(jié)點(diǎn)之間傳輸消息。作者介紹了一個(gè)多消息擺渡無(wú)人機(jī)優(yōu)化問(wèn)題，該問(wèn)題是中期戰(zhàn)略計(jì)劃的一個(gè)變體，使得最優(yōu)路徑規(guī)劃最小化了消息傳遞延遲。為了保持最優(yōu)路徑規(guī)劃解，采用遺傳算法在可行的時(shí)間內(nèi)求解該問(wèn)題。在遺傳算法中，建立節(jié)點(diǎn)集群，每個(gè)集群將被分配給一個(gè)UAV，然后UAV訪問(wèn)集群中所有節(jié)點(diǎn)的路徑是根據(jù)節(jié)點(diǎn)之間的流量和節(jié)點(diǎn)中的消息負(fù)載來(lái)確定的，以?xún)?yōu)化網(wǎng)絡(luò)中的消息傳遞。在小型網(wǎng)絡(luò)中，該遺傳算法提供了與使用窮舉搜索方法獲得的算法一樣好的解決方案，但運(yùn)行時(shí)間更短。此外，所提出的優(yōu)化問(wèn)題在DTN中的消息傳遞延遲方面優(yōu)于傳統(tǒng)的MTSP解決方案。
[18]中的研究，解決了在大規(guī)模WSN中使用多個(gè)移動(dòng)匯的數(shù)據(jù)收集問(wèn)題，以節(jié)省整個(gè)網(wǎng)絡(luò)的能量并提高數(shù)據(jù)包交付率。為了解決這個(gè)問(wèn)題，作者提出了一個(gè)兩階段的啟發(fā)式方法。在第一階段，形成k個(gè)傳感器節(jié)點(diǎn)集群，其中k是UAVsactingasmobilesinks的數(shù)量。在第二階段，根據(jù)平滑路徑構(gòu)建（SPC）算法確定每個(gè)無(wú)人機(jī)的路徑。在SPC中，遺傳算法被用來(lái)確定每個(gè)無(wú)人機(jī)正好訪問(wèn)集群內(nèi)每個(gè)傳感器節(jié)點(diǎn)一次的行程。然后，根據(jù)無(wú)人機(jī)轉(zhuǎn)彎約束計(jì)算出平滑的行程。
當(dāng)合作的無(wú)人機(jī)在危險(xiǎn)地區(qū)運(yùn)行以執(zhí)行多項(xiàng)任務(wù)時(shí)，優(yōu)化部署的無(wú)人機(jī)數(shù)量以及每個(gè)無(wú)人機(jī)的軌跡，將有助于在最短的時(shí)間內(nèi)完成任務(wù)。在這種情況下，[84]的研究提出了針對(duì)多任務(wù)、任務(wù)分配和路徑規(guī)劃問(wèn)題的Multi?無(wú)人機(jī)，這是MTSP的一個(gè)變種，在給定的時(shí)間約束和任務(wù)集下優(yōu)化無(wú)人機(jī)的數(shù)量。本文介紹了解決該問(wèn)題的方法、協(xié)調(diào)優(yōu)化算法、組合遺傳算法和集群算法。作者首先提出了K-means聚類(lèi)算法來(lái)建立多個(gè)任務(wù)的聚類(lèi)，其中每個(gè)聚類(lèi)將被分配給一個(gè)無(wú)人機(jī)。第二，相鄰任務(wù)的sameclusterare分組，以減少無(wú)人機(jī)要訪問(wèn)的地點(diǎn)的數(shù)量。之后，一個(gè)基于遺傳算法的TSP優(yōu)化問(wèn)題將被解決，同時(shí)考慮時(shí)間約束。協(xié)調(diào)優(yōu)化算法和GA之間的比較表明，所提出的協(xié)調(diào)優(yōu)化算法比GA更有效。
在無(wú)人機(jī)負(fù)責(zé)覆蓋多個(gè)區(qū)域的監(jiān)測(cè)應(yīng)用方面，[85]的研究提出了覆蓋路徑規(guī)劃的能量受限的多重旅行推銷(xiāo)員問(wèn)題（EMTSP-CPP）。為了解決這個(gè)問(wèn)題，作者引入了遺傳算法的修改版本，同時(shí)考慮了新的個(gè)體（染色體）代表，以及新版本的交叉和變異操作，最后是一個(gè)約束意識(shí)的功能函數(shù)。作者證明，與其他方法相比，修改后的遺傳算法具有更好的性能。
在[26]中，提出了一個(gè)用于搜索和救援的多目標(biāo)無(wú)人機(jī)路徑規(guī)劃。所提出的解決方案是基于遺傳算法的，目的是使完成時(shí)間最小化。該解決方案將環(huán)境劃分為若干單元，然后使用MTSP來(lái)保證每個(gè)單元正好被一個(gè)無(wú)人機(jī)搜索到。
在精準(zhǔn)農(nóng)業(yè)中，無(wú)人機(jī)可以被部署到用殺蟲(chóng)劑噴灑田地。在這種情況下，[86]的研究介紹了多四旋翼飛機(jī)的任務(wù)分配和路徑規(guī)劃問(wèn)題，這是無(wú)人機(jī)的一種特殊類(lèi)型。所提出的問(wèn)題被表述為MTSP優(yōu)化，目標(biāo)是減少任務(wù)完成時(shí)間，同時(shí)考慮到對(duì)四旋翼飛機(jī)電池容量限制的約束。為了解決這個(gè)問(wèn)題，作者提出了一種分層的方法，其中采用了內(nèi)外循環(huán)結(jié)構(gòu)。事實(shí)上，內(nèi)循環(huán)是基于遺傳算法的，而outerloopusesanonlinearproming方法是基于內(nèi)循環(huán)獲得的最佳結(jié)果。基于與傳統(tǒng)方法的性能比較，說(shuō)明了所提方法的效率。
基于TS的方法。
塔布搜索法是一種基于局部搜索方法的元啟發(fā)式方法，用于數(shù)學(xué)優(yōu)化。局部搜索方法往往會(huì)卡在次優(yōu)解中。因此，Tabu搜索通過(guò)探索超越局部最優(yōu)的解空間來(lái)提高這些方法的性能。
在監(jiān)測(cè)和監(jiān)視應(yīng)用領(lǐng)域，[33]的研究提出了兩階段燃料約束的多重UAV路由問(wèn)題（FCMURP）。在FCMURP中，考慮了multipledepots，它們也代表了加油點(diǎn)。然而，只有一個(gè)倉(cāng)庫(kù)，每個(gè)無(wú)人機(jī)之旅從那里開(kāi)始和結(jié)束。兩階段的FCMURP工作原理如下。在第一階段，采用MTSP為每個(gè)無(wú)人機(jī)建立一個(gè)旅游。然而，如果任何無(wú)人機(jī)沒(méi)有足夠的能量來(lái)完成其行程，它可以在任何倉(cāng)庫(kù)進(jìn)行加油站。在第二階段，額外的加油站被添加到第一階段的旅游中，以確保實(shí)現(xiàn)能源消耗的可行性。在FCMURP的第一階段，目標(biāo)是最小化所有無(wú)人機(jī)的飛行距離之和，而第二階段的目標(biāo)是最小化額外加油站的預(yù)期飛行距離。為了解決FCMURP，作者提出了SampleAverageApproximation（SAA）方法。在小的實(shí)例中，SAA方法對(duì)兩階段模型的最優(yōu)解也是趨同的，然而，在大中型實(shí)例中，SAA需要這么多時(shí)間來(lái)趨同。為了應(yīng)對(duì)這個(gè)問(wèn)題，作者提出基于Tabu搜索的啟發(fā)式方法來(lái)解決FCMURP，他們表明這種啟發(fā)式方法提供了高質(zhì)量的解決方案。
4.2.3其他方式
在卡車(chē)和無(wú)人機(jī)送貨應(yīng)用中，作者在[13]中提出了三個(gè)階段的啟發(fā)式方法來(lái)解決多個(gè)反射側(cè)邊旅行推銷(xiāo)員問(wèn)題（mFSTSP），涉及100個(gè)客戶(hù)和4個(gè)地區(qū)。在第一階段，一些客戶(hù)被選擇由卡車(chē)服務(wù)，另一些客戶(hù)將由無(wú)人機(jī)服務(wù)。然后，基于旅行推銷(xiāo)員優(yōu)化問(wèn)題確定卡車(chē)之旅。在第二階段，將每個(gè)客戶(hù)分配給特定的無(wú)人機(jī)，并識(shí)別卡車(chē)之旅和無(wú)人機(jī)之旅。在第三階段，作者求解MILP以確定卡車(chē)和無(wú)人機(jī)計(jì)劃運(yùn)行的確切時(shí)間。異構(gòu)無(wú)人機(jī)的飛行續(xù)航能力被建模為電池大小、有效載荷、飛行距離和飛行階段的函數(shù)。最后，執(zhí)行局部搜索過(guò)程來(lái)提高求解質(zhì)量。作者表明，對(duì)于實(shí)際大小的問(wèn)題，三階段啟發(fā)式算法提供了具有合理執(zhí)行時(shí)間的高質(zhì)量解。
在任務(wù)分配和調(diào)度的背景下，作者在[83]中把多無(wú)人機(jī)任務(wù)分配問(wèn)題表述為MTSP。所提出的問(wèn)題考慮了各種情況，包括多個(gè)連續(xù)任務(wù)、異質(zhì)無(wú)人機(jī)、時(shí)間敏感和不確定性。為了解決這個(gè)參數(shù)不確定的問(wèn)題，引入了幾種方法，如穩(wěn)健優(yōu)化方法、對(duì)偶性理論和一種新的組合算法，包括經(jīng)典的內(nèi)部點(diǎn)方法和改進(jìn)的兩部分狼群搜索算法。作者還提出了一種在線分層規(guī)劃算法來(lái)解決具有時(shí)間敏感不確定性的在線問(wèn)題。最后，他們進(jìn)行了幾次數(shù)值模擬和物理實(shí)驗(yàn)，以檢查所提出的算法的效率。表2總結(jié)了現(xiàn)有的無(wú)人機(jī)MTSP的解決方案。
5.分類(lèi)法、分類(lèi)和分析
在這一節(jié)中，我們首先提供了一個(gè)MTSP的擴(kuò)展分類(lèi)法，它是基于MTSP的變體、應(yīng)用的優(yōu)化方法和提出解決方案的應(yīng)用領(lǐng)域。之后，根據(jù)這個(gè)提議的分類(lèi)法，對(duì)之前審查的解決方案進(jìn)行了分類(lèi)。這個(gè)分類(lèi)法對(duì)現(xiàn)有的MTSP研究進(jìn)行了概述，可以幫助讀者為特定的應(yīng)用選擇合適的MTSP變體，以及用于解決問(wèn)題的方法。最后，我們根據(jù)我們的分類(lèi)中提供的指標(biāo)，通過(guò)對(duì)所審查的論文進(jìn)行分析研究來(lái)結(jié)束本節(jié)。
5.1.MTSP的擴(kuò)展分類(lèi)法
在下文中，我們提出并擴(kuò)展了mtsp。首先，我們首先根據(jù)三個(gè)標(biāo)準(zhǔn)列舉該分類(lèi)法中考慮的屬性，即：mtsp的變體、方法和應(yīng)用領(lǐng)域。我們?yōu)榍懊娴?節(jié)所述的mtsp劃變體選擇了最常見(jiàn)的屬性。我們還選擇了用于解決mtsp的不同方法（第4節(jié)中引用）。此外，上文第2節(jié)詳細(xì)介紹了mtsp的不同應(yīng)用領(lǐng)域。
MTSP變體
銷(xiāo)售員：
? 1- 銷(xiāo)售員
? 2- 機(jī)器人
? 3- 車(chē)輛
? 4- 無(wú)人機(jī)
目的地：
? 5- 單一
? 6- 多個(gè)
? 7- 加油點(diǎn)
城市：
? 8- 標(biāo)準(zhǔn)MTSP
? 9- 彩色TSP
?問(wèn)題 約束條件：
? 10 能量
? 11-容量
? 12-時(shí)間窗口
問(wèn)題 目標(biāo)：
? 13-單目標(biāo)優(yōu)化問(wèn)題
? 14-多目標(biāo)優(yōu)化問(wèn)題
?方法 實(shí)現(xiàn)
15-精確算法
?16-遺傳算法（GA）
17-粒子群優(yōu)化（PSO）
?18-蟻群優(yōu)化（ACO）
19-人工蜂群（ABC） ?
20-Tabu搜索(TS)
21-聚類(lèi)算法(如K?表示，最近的鄰居)
22-基于市場(chǎng)的聚類(lèi) 23-其他 ? a-模糊邏輯 ? b-游戲理論 ? c-ADI啟發(fā)式 ? d-三階段啟發(fā)式 ? e-樣本平均近似(SAA) ? f- Lin? Kernighan啟發(fā)式(LKH) ? g-主動(dòng)方案 ? h-Prob
應(yīng)用 24-運(yùn)輸和運(yùn)送 25-數(shù)據(jù)收集 26-搜索和救援 27-精準(zhǔn)農(nóng)業(yè) 28-災(zāi)害管理 29-監(jiān)測(cè)和監(jiān)視 30-多機(jī)器人任務(wù)分配和調(diào)度 31-合作任務(wù)管理 32-一般情況
5.2.審查的MTSP解決方案的分類(lèi)
我們根據(jù)之前提出的分類(lèi)法對(duì)調(diào)查中審查的現(xiàn)有研究進(jìn)行分類(lèi)，如表3所示。在下文中，我們將對(duì)這些分類(lèi)的解決方案進(jìn)行詳細(xì)分析。
5.3.對(duì)審查的MTSP解決方案的分析
為了更好地理解和分析表3中提出的分類(lèi)，我們?cè)趫D中提出。5、我們調(diào)查中引用的論文在車(chē)輛類(lèi)型、應(yīng)用方法、應(yīng)用領(lǐng)域和出版年份方面的統(tǒng)計(jì)研究。
我們可以看到，71%的專(zhuān)注于MTSP的研究是在地面車(chē)輛的背景下進(jìn)行的，而飛行車(chē)輛的這一比例為29%，如圖所示。第5a段。這可以通過(guò)以下事實(shí)來(lái)解釋：地面車(chē)輛的MTSP研究自2007年以來(lái)一直在發(fā)表，然而，我們調(diào)查中引用的最古老的關(guān)于無(wú)人機(jī)的論文發(fā)表于2015年，如圖所示。5b。地面飛行器和機(jī)器人的MTSP比無(wú)人機(jī)的MTSP研究得更多，因?yàn)檫@種飛行飛行器被認(rèn)為是一種新興技術(shù)，在民用領(lǐng)域的使用相對(duì)較新。
此外，如圖所示。5c所示，GA方法是兩類(lèi)車(chē)輛中使用最多的方法（36%的論文使用了GA）。第二種最常用的方法是精確方法和ACO方法（被18%的論文使用）。然后，它是基于市場(chǎng)的方法（被11%的論文使用）。
此外，如表3所示，對(duì)于地面車(chē)輛，大多數(shù)論文考慮了多個(gè)倉(cāng)庫(kù)的變體，然而，對(duì)于無(wú)人機(jī)，大多數(shù)論文考慮了MTSP的單一倉(cāng)庫(kù)變體。事實(shí)上，使用的倉(cāng)庫(kù)數(shù)量取決于應(yīng)用領(lǐng)域，也取決于車(chē)輛的類(lèi)型。例如，與地面車(chē)輛相比，無(wú)人機(jī)的自主性有限，這些無(wú)人機(jī)一般部署在非延伸區(qū)域。這就證明了需要一個(gè)單一的倉(cāng)庫(kù)來(lái)給無(wú)人機(jī)充電和發(fā)射。此外，這個(gè)單一的pot可以是移動(dòng)的，以?xún)?yōu)化預(yù)定的時(shí)間和無(wú)人機(jī)的能量，例如，通過(guò)使用卡車(chē)和無(wú)人機(jī)的最后一英里交付，如[13,14]中提出的。
此外，一些論文如[32,33]考慮了無(wú)人機(jī)路徑上的加油點(diǎn)。
無(wú)人機(jī)解決方案的另一個(gè)特點(diǎn)是，它們考慮了更多的約束條件，如[13,33,85,86]中的能量約束和[15,23,83,84]中的時(shí)間窗口約束。這是因?yàn)闊o(wú)人機(jī)比地面車(chē)輛有更多的受限資源（即特別是在能源方面），這是有道理的。對(duì)于地面車(chē)輛，能量被認(rèn)為是一個(gè)優(yōu)化目標(biāo)（即要最小化），而不是一個(gè)約束條件。此外，與地面車(chē)輛背景相反，MTSP的單一目標(biāo)以及多目標(biāo)變體被公平考慮，在無(wú)人機(jī)背景中，多目標(biāo)變體很少被考慮（只有參考文獻(xiàn)。[26]）。事實(shí)上，無(wú)人機(jī)解決方案中考慮最多的目標(biāo)是最小化任務(wù)時(shí)間。
就所使用的方法而言，如圖6所示，在所有類(lèi)型的車(chē)輛中，最常用的是遺傳算法方法。地面車(chē)輛第二常用的方法是ACO元啟發(fā)式。然后是基于市場(chǎng)的方法。值得注意的是，在幾篇論文中，GA方法與其他技術(shù)相結(jié)合，如[61，67]中的GA+ACO，或[68]中的GA+模因算法。此外，對(duì)于無(wú)人機(jī)環(huán)境，遺傳算法方法被廣泛用于聚類(lèi)技術(shù)，如[14，18，23，24，84]。此外，我們從表3中注意到，為無(wú)人機(jī)背景提出的中期戰(zhàn)略計(jì)劃解決方案更為復(fù)雜，基于多種方法的整合。事實(shí)上，正如一些論文所建議的那樣，無(wú)人機(jī)受到其能量和負(fù)載/承載能力的限制，可以與卡車(chē)協(xié)同運(yùn)行。因此，優(yōu)化問(wèn)題變得復(fù)雜。為了在考慮無(wú)人機(jī)的約束和應(yīng)用要求的同時(shí)優(yōu)化預(yù)期時(shí)間，許多研究提出分幾個(gè)步驟解決優(yōu)化問(wèn)題，以降低問(wèn)題的復(fù)雜性。為了做到這一點(diǎn)，這些研究針對(duì)這些不同階段應(yīng)用或組合了幾種方法。
在應(yīng)用領(lǐng)域方面（圖5d），大多數(shù)為地面車(chē)輛提出的論文考慮了一般情況，不限于特定的應(yīng)用領(lǐng)域，除了一些論文，如[38,51,57,60,71]，這是為MRTA問(wèn)題提出的。然而，無(wú)人機(jī)解決方案呈現(xiàn)出應(yīng)用的多樣性領(lǐng)域（表3）。
6.討論和未來(lái)方向
前兩節(jié)專(zhuān)門(mén)回顧了為MTSP提出的貢獻(xiàn)。事實(shí)上，我們已經(jīng)概述了文獻(xiàn)中提出的解決MTSP的不同方法，同時(shí)強(qiáng)調(diào)了應(yīng)用領(lǐng)域。
盡管MTSP與現(xiàn)實(shí)生活中的應(yīng)用非常相關(guān)，但我們指出，一些研究已經(jīng)解決了一般情況下的MTSP，而沒(méi)有考慮具體的應(yīng)用。然而，當(dāng)研究在一個(gè)特定的背景下，如包裹運(yùn)送、數(shù)據(jù)收集、監(jiān)測(cè)和監(jiān)視等，MTSP的新變體被提出。這些變體考慮了不同類(lèi)型的車(chē)輛（如機(jī)器人、車(chē)輛、卡車(chē)和無(wú)人機(jī)），以及倉(cāng)庫(kù)和要訪問(wèn)的城市的新特征。
例如，無(wú)人機(jī)的特點(diǎn)是成本低、機(jī)動(dòng)性強(qiáng)，可以很容易地被部署來(lái)執(zhí)行搜救任務(wù)或監(jiān)測(cè)特定區(qū)域。然而，在交通領(lǐng)域，地面車(chē)輛和卡車(chē)的使用是因?yàn)樗鼈冇泻艽蟮淖灾餍院脱b載能力。應(yīng)該注意的是，一些研究是基于異質(zhì)車(chē)輛的，并提出了卡車(chē)和無(wú)人機(jī)一起用于完成特定任務(wù)的解決方案。
根據(jù)應(yīng)用要求，在MTSP中還考慮了額外的約束條件，如車(chē)輛容量、能源消耗和時(shí)間窗口，這些都是常用的車(chē)輛路由問(wèn)題。即使MTSP在考慮這些約束條件時(shí)變得與VRP相似，在我們的調(diào)查中，我們只審查了問(wèn)題被表述為MTSP的論文。
在最近的研究中，已經(jīng)提出了幾種精確和啟發(fā)式的方法，可以直接解決MTSP，也可以在轉(zhuǎn)換為T(mén)SP后解決。
盡管精確的方法給出了最優(yōu)解，但由于問(wèn)題的NP-hardness，它們只對(duì)非常小的實(shí)例有用。元啟發(fā)式方法，包括遺傳算法（GA）、蟻群優(yōu)化（ACO）、人工蜂群（ABC）和粒子群優(yōu)化（PSO），已經(jīng)被廣泛探索，以有效解決MTSP。然而，當(dāng)問(wèn)題擴(kuò)大時(shí)，執(zhí)行時(shí)間非常長(zhǎng)，使其不適合實(shí)時(shí)應(yīng)用。我們指出，遺傳算法是最廣泛使用的元啟發(fā)式算法，然而，近年來(lái)，有一種趨勢(shì)是應(yīng)用ACO算法。
此外，一些研究提出了基于混合算法的MTSP解決方案，該算法結(jié)合了元啟發(fā)式的使用和例如局部搜索或聚類(lèi)算法。然后在不同的階段解決該問(wèn)題，這樣，計(jì)算復(fù)雜度就會(huì)降低，融合時(shí)間就會(huì)變得合理。
基于市場(chǎng)的方法也被用來(lái)解決MTSP，因?yàn)樗梢杂行У亟鉀Q動(dòng)態(tài)的系統(tǒng)變化，并且不需要事先了解所有的系統(tǒng)狀態(tài)來(lái)提供一個(gè)解決方案。
車(chē)輛完成特定任務(wù)所遵循的路徑必須滿(mǎn)足兩個(gè)重要條件。一方面，車(chē)輛軌跡必須是可行的，因此需要考慮到車(chē)輛的約束條件，如耐力、運(yùn)動(dòng)學(xué)（如速度和加速度）和系統(tǒng)動(dòng)力學(xué)。另一方面，必須通過(guò)避免與障礙物的碰撞以及車(chē)輛之間的碰撞來(lái)確保車(chē)輛的安全。
為了簡(jiǎn)單起見(jiàn)，許多研究沒(méi)有考慮這些車(chē)輛特征和建議的優(yōu)化問(wèn)題，以放松這些約束。只有少數(shù)關(guān)于無(wú)人機(jī)應(yīng)用的貢獻(xiàn)在問(wèn)題模型中加入了車(chē)輛約束[11]或在解決方案中考慮了避免碰撞[32]。
未來(lái)對(duì)MTSP優(yōu)化問(wèn)題的研究需要更加關(guān)注車(chē)輛特性和約束條件，以便為現(xiàn)實(shí)生活中的應(yīng)用提供有效的解決方案。
與車(chē)輛和卡車(chē)不同，地面機(jī)器人和無(wú)人機(jī)的能量可能有限。一些研究集中在無(wú)人機(jī)的續(xù)航能力上，然而，在未來(lái)的貢獻(xiàn)中需要提出一個(gè)機(jī)器人和無(wú)人機(jī)的能耗模型。
至于經(jīng)典的MTSP，關(guān)于無(wú)人機(jī)MTSP的研究可以為數(shù)據(jù)基準(zhǔn)[89]提供解決方案，以便在為解決MTSP而提出的不同方法之間進(jìn)行比較，并將研究工作推向這個(gè)方向。
7.結(jié)論
多重旅行推銷(xiāo)員問(wèn)題是最有趣的組合優(yōu)化問(wèn)題之一，因?yàn)樗軌蛎枋龊椭贫ìF(xiàn)實(shí)生活中的應(yīng)用。事實(shí)上，這項(xiàng)調(diào)查表明，MTSP在多個(gè)領(lǐng)域都使用了公式化的優(yōu)化問(wèn)題，包括運(yùn)輸和交付、數(shù)據(jù)收集、搜索和救援、多機(jī)器人任務(wù)分配和調(diào)度等。雖然MTSP很重要，但目前還缺乏描述現(xiàn)有解決方案的調(diào)查。本文旨在通過(guò)對(duì)MTSP的現(xiàn)有和最近的解決方案進(jìn)行全面回顧來(lái)填補(bǔ)這一空白。我們將現(xiàn)有的解決方案分為兩大類(lèi)：（1）車(chē)輛和機(jī)器人的MTSP；（2）無(wú)人機(jī)或無(wú)人機(jī)的MTSP。此外，每個(gè)類(lèi)別的解決方案都根據(jù)所使用的優(yōu)化方法進(jìn)行分類(lèi)，如精確的、元啟發(fā)式的、基于市場(chǎng)的等。本文還根據(jù)幾個(gè)標(biāo)準(zhǔn)提出了所研究的解決方案的分類(lèi)法，包括MTSP的變體、方法、應(yīng)用等。最后，值得注意的是，MTSP仍然是一個(gè)有前途的研究領(lǐng)域，特別是對(duì)于基于無(wú)人機(jī)的應(yīng)用，新的優(yōu)化問(wèn)題正在出現(xiàn)。
總結(jié)
以上是生活随笔為你收集整理的对多旅行商问题：应用、方法和分类进行了全面的综述的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： Python+Opencv图像处理--基
- 下一篇： Sql(presto语法） 实现行转列和