多旅行商模型及其應用研究綜述

張碩航，郭改枝

內蒙古師范大學 計算機科學技術學院，呼和浩特010022

在科學研究和工程實踐中，組合優化問題（combinatorial optimization problem，COP）無處不在，同時隨著近代工業的發展，更好地求解組合優化問題能為企業和個人帶來更加可觀的經濟效益。因此它不僅成為學術界研究熱點，其發展同樣受到社會各界的廣泛關注。目前，在計算機網絡布線、集成電路設計、交通運輸、資源分配等諸多領域都存在著組合優化問題。

盡管該類問題的應用領域廣泛，但在求解過程中當問題規模越來越大時，解決問題的時間成本是巨大的，加之現有的許多方法對解決這一問題都沒有很好的效果，因此組合優化問題也被稱為NP難問題。以旅行商問題和多旅行商問題為代表的便是一類典型的組合優化問題。本文首先以TSP（traveling salesman problem）作為切入點，通過對該單一問題的簡單歸納引出了作為其泛化問題MTSP（multiple traveling salesman problem）的研究，重點關注解決多旅行商的啟發式方法及應用領域兩方面，通過方法與應用的結合對MTSP模型未來的研究方向進行了展望。

1 旅行商問題的產生與發展

第一個旅行商問題于1954年被Dantzig等人用線性規劃解決，當時的城市規模僅有49。但是隨著計算機求解速度的提高和先進算法的不斷引入，目前已知成功解決TSP 的城市數量為24 978 個。可以預見的是，隨著科技的不斷發展，未來可以計算的TSP規模會更大，各時期求解TSP規模的典型實例如圖1所示。

圖1 TSP規模的發展歷程Fig. 1 Development history of TSP scale

表1 TSP的計算量與計算時間Table 1 Calculation amount and calculation time of TSP

同樣，線性規劃作為早期解決TSP 的一種方法，主要采用的是割平面法，雖然線性規劃的求解效率比窮舉法高，但缺點是在求割平面時往往需要人工經驗判斷，這也反映出線性規劃法其實并不適合解決規模較大的多旅行商問題。通過實驗發現人工設計的啟發式算法的一大缺陷是在不同問題集上表現不穩定，因此王原等人提出了深度學習與蟻群算法融合的框架，首先采用基于注意力機制的神經網絡對問題實例進行特征提取，然后采用蟻群算法對問題實例進行求解，兩種算法取長補短，通過在TSPLIB上的實例進行驗證，極大改善了TSP的解。更多關于深度學習方法求解旅行商問題的其他方法可見綜述文獻[9]。

但經典TSP 問題是一種最基礎的求最短路徑規劃問題，它只需要考慮路程最短這一單一條件約束，而生活中大部分實際應用問題卻不能被歸納為TSP問題，例如物流配送、人員調度、巡查救援等一些涉及到多任務分配與優化的場景。多旅行商涉及到的內容更復雜，研究成果也相對較少，但是隨著社會發展的需求變化，對多旅行商問題的研究逐漸成為熱點。

2 多旅行商問題

作為經典組合優化問題TSP的擴展，MTSP抽象模型的研究一開始就側重于優化旅行商的總路程，隨著對該問題研究的深入以及對于實際問題的建模，研究人員發現將MTSP作為一個單目標優化問題已經不能夠滿足于實際需求，在路由的分配過程中，既要考慮總路程最小化，又要考慮各推銷員之間的工作量的平衡；既要考慮盡可能提高公司的收益，又要考慮每個客戶服務的等待時間問題。在理論模型的實際運用的過程中，優化問題往往面臨多個標準的限制，具體的目標依據實際問題而不同。圖2 為=3 的單倉庫多旅行商問題示意圖，（a）為標準多旅行商的路線規劃圖，（b）為考慮任務量均衡的MTSP路線規劃示意圖，其中0表示配送中心，1到9為城市集合。

圖2 MTSP路線規劃圖Fig. 2 MTSP route plan

2.1 多旅行商特征

（1）銷售人員類型：根據應用情況，MTSP中的旅行商可以是銷售人員、車輛、機器人或無人機。

（2）銷售人員的數量嚴格大于1，否則變為TSP問題。

（3）合作型多旅行商：幾個旅行商可以合作完成給定的任務。它們可以是相同的車輛類型，也可以組合使用，例如用于卡車和無人機協同工作向客戶交付包裹的交付應用。

2.2 倉庫特征

（1）單倉庫與多倉庫

在標準MTSP中，通常只考慮一個倉庫并且位置固定；而加入了多個旅行商后，多個站點的存在可以優化遍歷成本。

（2）固定倉庫與移動倉庫

在MTSP中倉庫通常是固定的，然而在某些應用中，倉庫也可以是移動的。例如，移動倉庫可以是無人機或卡車。

（3）封閉路徑與開放路徑

在經典的MTSP 中，旅行商的路徑是封閉的，因為他們必須在同一倉庫位置開始和結束他們的遍歷。但在某些實際應用中，旅行商可以不需要返回倉庫，停留在最后訪問的城市即可。

2.3 多旅行商的城市規格

（1）標準MTSP：在標準MTSP 中，所有旅行商共享相同的工作空間，即他們共享所有城市。

（2）有色MTSP：有色旅行商問題（colored traveling salesman problem，CTSP）是一個廣義的多旅行商問題。該問題中定義了兩種類型的城市：一種是特定旅行商可以訪問的單色專用城市；另一種是所有旅行商都可以訪問的多色共享城市。

2.4 多旅行商的目標函數

MTSP可用于優化單個目標或多個目標，主要目標如表2，其中能量消耗和任務完成時間是高度依賴于行駛距離的。

表2 優化目標的細分Table 2 Segmentation of optimization goals

2.5 問題約束

（1）能量約束

旅行商在移動過程中會消耗能量。當旅行商是卡車等車輛時，其約束唯一取決于油量，但小型無人機或機器人等智能產品的自主性有限，當旅行商是智能產品或下文提到的傳感器節點時，要考慮其續航能力等。

（2）容量約束

在任務期間旅行商可能攜帶包裹或數據。與能量約束相同，車輛容量的約束通常適用于小型車輛，如無人機只能承載小包裹，其數據存儲器存儲也可能是有限的。

（3）時間窗約束

在某些實際問題中，在任務中往往會給旅行商設定最晚到達時間或時間間隔等要求。在無線傳感網等領域中，它可能對應于數據延遲。在這種情況下，對于節點數據的提取、轉移和交付就提出了要求。

2.6 變體的形式化描述

正如前文中所描述，MTSP在不同應用中有不同的主體，但由于多旅行商遍歷的公式會因旅行商是否起終點一致等問題而不同，因此作為考慮約束的多旅行商問題，設定個目標的集合為{,,…,T，個機器人的集合為{,,…,R}，則將四種情況下的多旅行商目標函數建模如下：

（1）單倉庫閉合路徑的MTSP

個推銷員從同一起點出發，最終返回起點。

（2）單倉庫開放路徑的MTSP

在該模型中，旅行商在最后一處訪問城市任務終止，不再回到起點。

（3）多倉庫閉合路徑的MTSP

個推銷員從不同起點出發，遍歷了目標城市后最終返回到各自的起點。

（4）多倉庫開放路徑的MTSP

個旅行商從不同起點出發，任務結束后停留在當前城市，無須返回各自起點。

對MTSP的變體類型及主要特征的歸納如圖3。

圖3 MTSP的主要特征Fig. 3 Main features of MTSP

3 MTSP模型的算法求解

最初在19 世紀學者們大多采用精確算法對MTSP 進行求解，精確算法常見的包括窮舉法、線性規劃法和分支定界法。Ali等人用分支定界法對非對稱MTSP 進行求解，求解規模最多為100 個城市；Gavish等人對分支定界法進行改進，通過限定分支定界的下界，減少了算法運行所需要的時間。該方法的關鍵在于如何選擇合適的約束邊界，不同的約束邊界會形成不同的分支定界方法，因此處理多旅行商問題是不現實的。由于多旅行商問題的解空間會隨問題規模的擴大呈指數方式增長，精確算法對此較難求解，而啟發式算法比盲目搜索更高效，一個經過仔細設計的啟發函數，往往在很快的時間內就可得到一個搜索問題的最優解，對于NP 問題，亦可在多項式時間內得到一個較優解，因此學者們逐漸傾向于采用啟發式算法對MTSP 進行求解。然而隨著MTSP的不斷發展，從原始的優化推銷員路徑優化問題，到處理地面車輛和機器人調度問題，再到現在的無人機協同任務分配。變體的多樣導致求解方法的側重不同，本文將主要圍繞啟發式算法解決MTSP展開綜述。

3.1 基于蟻群算法的方法

蟻群算法（ant colony optimization，ACO）是求解組合優化問題中一種基于種群的元啟發式算法，在種群中，每個個體都是一個人工智能，可以逐漸地、隨機地構造給定優化問題的解。而蟻群算法作為一大經典算法已被廣泛用于路徑問題中，由于其具有的極高求解效率至今仍然是學者們研究的熱點問題。

Xu等人為了使多個無人水下航行器的總行駛距離最小，將該任務分配問題建模為了約束MTSP，然后提出多蟻群系統方法來求解多目標MTSP，最終使得航行器能耗最小化。文獻[14]提出了面向任務的最大-最小蟻群算法，作者使用兩個信息素來實現不同的目標，減輕了蟻群之間的相互糾纏來解決MTSP，目的是最小化總距離最終實現了負載平衡。Chen等人提出并實現了一種雙目標問題的局部搜索方法最小化了多機器人巡邏的總行程。在該文章的實驗中，與四種最經典的算法進行了評估和比較，實驗結果表明該方法在求解質量方面都優于其他比較算法，但該方案比文獻[16]中的模糊邏輯方法（fuzzy logic-multiple traveling salesman problem，FL-MTSP）時間更長，因為FL-MTSP 算法是先將多目標問題分解為單目標問題再提供一個最優解，在執行時間方面較有優勢。Wang等人考慮了現代商業物流的時間限制和車輛的承載能力對物流優化的影響，利用改進信息素模型的蟻群算法求解了具有容量和時間窗約束的MTSP問題，提高了算法的搜索效率同時優化了最短路徑。

3.2 基于遺傳算法的方法

遺傳算法（genetic algorithm，GA）的原理是基于自然選擇和遺傳，從上一代中產生最優解，但利用遺傳算法求解MTSP 時，如何保持良好的個體，保持種群的多樣性一直是一個難題。

文獻[18]為了提高遺傳算法的搜索性能，提出了兩部分染色體編碼方法的遺傳算法來求解MTSP，實驗表明該方法可以有效縮小搜索空間并優化總路程，證明了該交叉方法生成了更好的解。而葉多福等人提出了一種帶復雜突變樹的多染色體遺傳算法，設計了一種多染色體編碼的編碼方式，將可行解的搜索范圍大幅縮小，同時還能根據染色體數量自適應調節旅行商數量，目的是在滿足時間約束的條件下，完成遍歷任務且旅行商數量和旅行時間相對均衡。減少了算法運行時間，優化了旅行商數量。文獻[20]提出了將選擇和變異結合在一起的新的單親遺傳算法（improved partheno genetic algorithm，IPGA），通過考慮機器人的路線和染色體上的斷點，使用序列編碼方法來描述真實種群。將該方法與基于特定TSPLIB基準的粒子群算法（particle swarm optimization，PSO）進行了比較，IPGA 具有更好的性能。Wang 等人針對PGA 種群中個體局部信息可能缺失的缺陷，將繁殖機制集成到了入侵雜草優化算法（invasive weed optimization，IWO）中，得到了改進的帶繁殖機制的單親遺傳算法（reproduction improved partheno genetic algorithm，RIPGA）。利用該改進算法研究了具有多個站點和封閉路徑的多旅行推銷員問題，該算法可以有效地避免局部收斂，且受參數影響小穩定性較好。胡世娟通過在雜草算法中引入繁殖機制產生后代進行遺傳操作，解決了工作量平衡的MTSP，從而改善了快遞員配送環節的任務平衡問題。同時，將混合局部優化算子作為變異算子加入算法中，增強了算法的局部搜索能力，實驗表明旅行商數量越大，算法的優勢越明顯。

但是由于一些實際應用需要優化多個標準，如最小化機器人的能量消耗、任務完成時間等，用于解決MTSP的方法可能需要同時優化多個目標，這類問題被稱為多目標MTSP。Bola?os等人提出了一種基于非支配排序遺傳算法（non-dominated sorting genetic algorithm，NSGA-II）的多目標多旅行商問題求解方法，考慮了MTSP 的兩個目標：總距離的最小化和旅行商工作時間的平衡，但作者并沒有對時間的計算給出解釋。文獻[24]同樣提出了基于NSGA-II算法的多目標優化問題，即部署無線傳感器節點的多機器人軌跡優化問題。在該問題中作者考慮了三個目標：最小化任務時間（即傳感器部署時間）、最小化機器人的使用數量以及平衡機器人巡視時間。

在文獻[25]的研究中，作者首先將無人機作為移動sink點，其次利用遺傳算法確定每架無人機對集群內每個傳感器節點的訪問次數。解決了大規模無線傳感器網絡中使用多個移動接收器進行數據收集的問題，以節省整個網絡的能量并提高數據包的傳輸速率。而文獻[26]的一項研究提出使用無人機作為信息傳送節點，負責在即時延容忍網絡中斷開的節點之間傳送信息。采用遺傳算法在可行時間內求解問題。在遺傳算法中構建集群的節點，使每個無人機對應一個集群，通過無人機路徑的確定使得訪問集群內所有節點，最小化網絡中消息傳遞延遲。

3.3 基于粒子群算法的方法

粒子群優化算法（PSO）是最著名的元啟發式算法之一，與遺傳算法有許多相似之處，每次迭代中，粒子通過跟蹤個體最優位置“PBest”和全局最優位置“GBest”兩個極值來更新自身。

在文獻[27]的研究中，作者擴展了標準PSO以處理多個目標，解決了多機器人協作任務分配問題并將其表述為MTSP，目的是使機器人的總行程和最大旅行成本最小化。在該文的實驗中將提出的方法與著名的現有多目標方法進行了比較，如SPEA2（strength pareto evolutionary algorithm 2）和NSGA-II，并證明了其優越性。其中SPEA2也叫作強度帕累托進化算法，是一種相對較新的技術，用于尋找或逼近多目標優化問題的帕累托最優集。在相同的背景下，文獻[30]也討論了多機器人任務分配問題，并提出了基于動態分布式的PSO，實驗部分將該分布式粒子群算法和GA進行了比較，有很強的競爭性。

3.4 其他方法

Venkatesh 等人使用人工蜂群算法（artificial bee colony，ABC）來求解單倉庫的MTSP，目的是使總行駛距離（MinSum）和最大行駛距離（MinMax）最小。該作者在文獻[32]中還闡述了著色MTSP，并提出了基于ABC的解決方案。關于有色MTSP的進一步研究見文獻[33]，作者對ABC 算法進行了改進，引入了生成鄰域解來求解MTSP。

Venkatachalam 等人提出了基于燃料約束的多無人機路由問題，通過引入兩階段隨機模型來解決不確定情況下多無人機的路線規劃，第一階段目標是最小化所有無人機飛行距離的總和，而第二階段的目標是最小化額外加油停留的預期飛行距離。實驗表明采用的禁忌搜索法在中型和大型測試實例中都提供了高質量的解決方案。

3.5 基于混合算法的方法

一些研究提出了結合不同的元啟發式和技術的混合算法，以更有效地解決多旅行商問題。當合作無人機在危險區域執行多個任務時，優化部署的無人機數量和每架無人機的飛行軌跡，將有助于在最短的時間內完成任務。在此背景下，Jiang 等人在研究中提出了任務分配和路徑規劃問題，在給定的時間約束和任務集下優化無人機的數量。為了解決這一問題，提出了一種結合遺傳算法和聚類算法的協同優化算法。作者首先提出了-means 聚類算法來構建多任務的聚類，每個聚類將分配給一個無人機。其次將同一集群的相鄰任務分組，以減少無人機可訪問的位置數量。在考慮時間約束的情況下，基于遺傳算法求解TSP 優化問題。將協同優化算法與遺傳算法進行比較評價，結果表明所提出的協同優化算法比遺傳算法更有效。文獻[36]將蟻群算法與單親遺傳算法相結合，提出了一種新的大規模MTSP混合算法。該算法首先利用GA來確定旅行商站點的最佳值以及每個旅行商訪問的城市數量，然后利用ACO計算每個旅行商的最短路徑。張富震等人提出了一種基于融合粒子群-魚群優化算法（particle swarm optimization-artificial fish swarm algorithm，PSO-AFSA）的航跡預規劃任務分配策略，先對單無人機進行航跡規劃模擬，再利用匈牙利算法完成各架無人機偵察任務協同分配。該算法能在優化單無人機航跡的同時，實現與任務協同分配緊耦合，使無人機集群總航程的全局總代價最低，提高了任務分配合理性。Decerle等人進一步研究解決了家庭保健問題中護理者的日程安排和路線，并將其制定為帶有時間窗口的多旅行商問題。通過結合蟻群算法和記憶算法的混合方法，平衡了看護人員的工作時間。

表3將求解算法進行了分類，歸納了不同算法求解MTSP模型的最小化目標與具體解決方法的差異。

表3 不同算法下優化目標與解決方法的異同Table 3 Similarities and differences between optimization objectives and solutions under different algorithms

4 MTSP的應用領域

多年來，車輛、移動機器人和無人機作為一類可代替人工的智能手段，它們使許多復雜的任務更加安全和容易。為了實現這些任務，需要在考慮約束的同時優化給定的目標。由于MTSP 不允許重復遍歷和分游等特點，該問題的解決方案可用于解決車輛路由和任務分配等路線規劃的相關問題。根據應用需求，MTSP 的旅行商可以由地面車輛（機器人或貨車）代表，也可以由飛行車輛（無人機）代表，而旅行商要訪問的城市也可以有不同的表示，例如運輸和交付服務中的客戶、無線傳感器網絡數據收集的傳感器節點、軍事任務中的目標、災害中的受困者等。本文將MTSP模型的主要應用領域分為以下五類。

4.1 物流運輸與配送

在如今數字媒體和互聯網+高速發展的背景下，傳統物流也隨之轉型，逐漸成為發展國民經濟中的重要一環。在服務至上的今天，既要縮短商品配送的時間，也要保證服務質量，而如何將二者兼顧，是目前的一大難題。面對運輸帶來的種種困難，學者們選擇利用多旅行商模型來改善物流中出現的許多實際問題，使其節省成本，提高效率，來彌補運輸時的不足。例如貨物分發或包裹遞送或汽車運輸。車輛負責將貨物、包裹或人員從一個地點運送到另一個地點。在這種應用中，應考慮車輛容量和時間約束。

在物流運輸環節，“最后一公里”物流配送具有配送方式苛刻、配送時效要求高、個性化差異化配送需求大、訂單多但規模小等特點，因而面臨許多問題和挑戰。但無論采用哪種配送方式，都需要解決哪個快遞員、以什么順序送達的問題，因此這類問題可以被抽象為MTSP。袁雨果以電商物流的“最后一公里”配送為研究對象，提出了解決多個快遞員的任務分配和路線優化的方法，首先將該問題考慮為任務均衡的MTSP，然后設計了一種改進的遺傳算法求解該問題。而文獻[41]為避免多個快遞員在“最后一公里”的配送任務中出現路程不均衡的現象，將此規劃問題抽象成了MTSP模型，進而提出了一種新穎的回跳重組蟻群算法來優化該模型。在該目標下，不僅最小化了快遞員的總配送距離，還均衡了快遞員之間的配送距離。

然而隨著無人機和移動機器人等新興技術的出現，產生了新的運輸服務，即利用無人機運輸小包裹、移動機器人分揀快遞貨物等來顯著縮短交付時間。如潘成浩等人針對倉儲物流過程中訂單揀選機器人高效的實時路徑規劃問題，建立了以路徑總長度最小為優化數學模型的多旅行商，通過結合改進的自適應遺傳算法實現批量選擇路徑規劃，很好地適應了批量揀選機器人路徑規劃的需求。Murray等人同樣考慮了“最后一英里”的物流交付系統，但不同之處是在該系統中，利用一輛送貨卡車與一組無人機進行協同工作，相互配合，從貨車上便可部署無人機的任務，使距離倉庫較遠的客戶能夠接收無人機的交付。文獻[44]面對該協同任務首先最小化了卡車和無人機到達倉庫的時間，其次開發了一種基于插入啟發式的新算法，用來解決包含100個位置的大型問題。與傳統的單一卡車或無人機交付系統相比有潛在的增益，可見成本得到了極大控制。

4.2 應急與救援

在突發事件中，應急部門需要及時、準確、有效地向受災地區運送救援物資，最大限度地減少生命財產損失。然而大多數災害無法提前預測，救援時間有限。因此，利用數學建模和計算機仿真技術輔助決策者在最短的時間內制定車輛調度方案具有重要的研究意義。

應急救援路徑的選擇主要包含疏散工作和救援物資車輛調度這兩方面，其中疏散工作又包括人員疏散和車輛物資疏散。劉明等人將應急物資分配結構問題看作MTSP，并設計了一種新的混合遺傳算法，優化了各種突發情況下的應急物資分配過程。在突發情況下，救災物資的車輛調度應注重時間因素，只有及時、準確地將所需物資送達需求點，才能最大限度地減少損失。因此姚書婷等人以總配送時間最小的目標建立了一個應急物資運輸的路徑優化模型，同時對該模型加入時間窗約束，以此來確定最佳配送路徑和時間。除了救援物資的車輛調度以外，在室內的緊急救援任務中，急救人員需要快速準確地確定被害者位置，因此需要提前制定搜索計劃規劃其營救路徑。為了及時制定內部巡查路線，并指派救援隊進行初步搜索，文獻[47]將問題描述為MTSP，目標是使得每個救援隊的總路徑最短，縮短了搜尋時間。災情發生后除了人員的地面搜救外，陳昕葉研究了多機器人搜索與救援的任務模式，建立了多機器人搜索和救援任務分配的組合優化數學模型。設計的算法可以滿足在機器人損毀、機器人數量新增或任務新增等動態環境變化的情況下快速適應動態環境的要求。

無人機由于其航空特性和進行大規模檢查的能力，在實時監測洪水、干旱和地震等自然災害方面具有特殊優勢。在完成災情巡查、生命跡象探測等協同任務時，需要對無人機進行任務分配與航跡規劃。基于上述優勢，文獻[49]將緊急救援和救災中無人機的調度優化和路徑優化轉化為多旅行商問題，最后結合遺傳算法最小化了找到目標的時間和建立通信的時間，可以高效地執行搜救任務。

4.3 數據采集與傳輸

近年來，無線傳感器技術以及低功耗無線通信技術受到廣泛的使用與發展。無線傳感器由電池驅動，能量非常有限，但它們的工作時間需要幾個月甚至幾年。而且關鍵路徑上的一些節點耗能過快，整個網絡中的所有節點耗能不均衡，最終導致網絡崩潰，網絡壽命受限。因此如何降低網絡能量消耗，延長網絡生存時間成為無線傳感網研究的熱點，而優化數據傳輸路徑則成為解決問題的一個重要途徑。與傳統的數據路由數據采集技術相比，無線移動節點是無線傳感器網中采集數據的新技術。在無線傳感器網絡中，為了減少能量空洞，文獻[50]通過規劃移動sink點的最短路徑來收集節點數據。此外，利用多個移動機器人作為移動接收器，可以幫助收集傳感器節點提供的數據，這種數據收集策略使得位于固定匯聚附近的傳感器節點的能量耗散最小化，從而增加了網絡壽命。Huang 等人也將移動機器人引入無線傳感器網絡進行數據采集。針對單個機器人提出了一種最短可行路徑規劃算法，不僅在有障礙物的傳感場中訪問傳感器節點，同時能最大限度地減少路徑長度。這種數據收集策略允許將位于固定接收器附近的傳感器節點的能量消耗降至最低，從而延長網絡壽命。Wei 等人針對傳感器節點的數據采集和能量充電聯合問題，提出了一個多目標優化模型，提出的多目標模型優化了移動機器人的總能量效率，降低傳感器節點數據傳輸的平均延遲。在容延遲網絡中，移動機器人可以通過從源節點拾取數據并將其傳送到目的節點來重新建立網絡連接。

4.4 軍事領域

隨著人工智能時代的到來，近些年MTSP的模型還多被用于無人機等智能產品的路徑規劃問題中，其中，多無人機協同任務規劃大致可分為系統資源分配、任務分配、導航規劃、軌跡優化、武器投放規劃等。

在軍事任務中，集群攻擊地面多目標群的研究是實現無人機群作戰的重要內容。而如何在攻擊地面多目標群的過程中找到最優的攻擊路徑是一個難題。徐國訓等人根據機群攻擊多目標群的研究現狀，建立了機群攻擊多目標群的路徑規劃模型，將攻擊地面多目標群過程中的路徑規劃問題轉化為MTSP問題。并提出了一種基于MTSP-GA的模型計算方法，分別得到了單基地起飛和雙基地起飛的最優路徑規劃結果。Zhu 等人旨在研究執行打擊任務的無人機的最優路徑,在無人機路徑規劃中，考慮了時間窗和每個目標的一定環形防御范圍、最佳炸彈和燃料負載等因素，以便更好地為每個無人機分配目標并確定打擊順序。將禁忌搜索算法應用于無人機航路中止和打擊策略的優化，并通過數值實驗驗證了該算法的性能。在日益復雜的戰場環境中，描述協同偵察對于與裝載在不同基地的多架無人駕駛飛行器有關的空中交通至關重要。與所有無人機僅從一個基地起飛的傳統問題相比，文獻[55]是為了解決偵察任務，將最小逗留時間轉化為最短路徑組合優化問題，并將航向角離散化。將圖論應用于分析路徑問題，可以建立具有多種約束條件的全局模型。最后，通過遺傳算法對模型進行求解，可以生成有價值的偵察路徑規劃。并以4 個基地的8 架無人機完成68個目標的偵察任務為例，給出了最優解，說明了所提模塊化和算法的可行性和有效性。

4.5 現代農業

隨著人口的增長，農作物生產的效率和產量變得愈發重要，文獻[56]討論了全覆蓋條件下多收割機的路由問題，田地沿著作物方向被分成幾塊，目的是將多個收割機分配到田地中的各個區域，以便收獲所有作物且路段不被重復遍歷。該問題作為旅行商的一種延伸，不但最小化了行駛距離，還平衡了收割機間的工作量。在精準農業中，無人機可部署于農田噴灑殺蟲劑。在此背景下，文獻[57]研究介紹了任務分配和多架四輪直升機的路徑規劃問題，將其表述為MTSP的優化問題，最終成功實現了在考慮四架直升機電池容量限制的同時有效減少了任務完成時間。為了提高多臂采摘機器人在矮化、密植果園的協同工作效率，李濤等人分析了多臂采摘機器人工作時出現的訪問域重疊的問題，提出了基于遺傳算法的優化求解方法，既保證了各臂能避免沖突，又能在短時間內遍歷所有目標果實，提高了操作效率。盡管地面車輛和無人機都對農民有很大幫助，在智慧農業系統中，采用具有多種傳感器的移動機器人進行宏觀信息感知也是農業可持續發展的關鍵步驟。因此在滿足真實場景要求的區域監控策略中，優化移動機器人的行動是必要的，因此農民需要為每個機器人提供一個優化的路徑，以降低成本和提高產量。Li等人提出了一種基于云的架構，由無線傳感器網絡、移動機器人和云系統組成，以監測溫室區域。首先生成移動機器人訪問的候選區域監測點，然后令機器人到達這些點的移動路徑。通過對不同應用領域的分析歸納，表4將MTSP在不同變體下的分類結合適用場景進行了優劣勢總結。

表4 MTSP不同變體下的分類Table 4 Classification under different variants of MTSP

5 總結與展望

本文首先對MTSP與TSP進行了辨析，以及回答了為何要著重研究MTSP 的現實意義。盡管MTSP與現實生活中的應用非常相關，但目前很多研究仍然只停留在優化數學模型的階段，而沒有考慮特定的應用領域。因此在單一旅行商問題的鋪墊下，引入了多旅行商模型。由于學術研究的最終目標是要解決實際問題，本文并非是單純地總結數學模型與改進方法，而是結合了應用領域來幫助讀者拓寬研究思路。當研究是在特定的背景下進行時，如包裹遞送、數據收集、監測與監控等，則伴隨著MTSP變體的產生。本文在第2 章將不同應用中的變體進行了提煉總結，在不同的應用環境中考慮了不同類型的主體（車輛、機器人和無人機），以及要訪問的倉庫和城市的新特性，同時基于應用需求，在車輛路徑問題中還考慮了車輛容量、能耗、時間窗等約束條件。第3章對求解MTSP 的算法進行了歸納，選取了當前主流研究中具有代表性的幾類啟發式算法以及混合算法。第4章對MTSP在現實中的應用進行了分類，在不同應用中根據主體的不同進行了歸納與概括。

（1）雖然精確的方法可以給出最優的解決方案，但由于NP-hard問題的復雜度高，它們只對非常小的實例有用。目前遺傳算法、蟻群算法、人工蜂群算法和粒子群算法等啟發式算法被廣泛應用于求解MTSP 問題。但由于這類啟發式算法普遍存在易陷入局部最優、早熟收斂、適用范圍局限的缺點，目前對啟發式算法理論方面的研究還處于不斷發展中，新思想和新方法仍不斷出現。通過分析現狀，其發展方向有以下幾個方面：①整理歸納分散的研究成果，建立統一的算法體系結構；②在現有的數學方法（模式定理、編碼策略等）的基礎上尋求新的數學工具；③開發新的混合式算法及開展現有算法改進方面的研究；④研究高效并行的或分布式優化算法。

（2）根據表3 可以看出，遺傳算法在求解多旅行商問題中占據了絕對的主導地位，但分析文獻后不難發現，遺傳算法大部分采用的解決方案都是將MTSP轉化為TSP，研究的焦點集中在如何用染色體編碼表達MTSP，并且在改變染色體編碼方式上對遺傳算法進行改進。盡管遺傳算法如此強大，但由于改進方法的局限性使得其發揮的空間愈發有限。因為啟發式算法的諸多局限，近些年也有少量文獻提出利用神經網絡模型求解MTSP 的方法。由于神經網絡是并行計算的，其計算量不隨維數的增加而發生指數性“爆炸”，對于優化問題的高速計算特別有效。可以預見，隨著神經網絡等智能算法的深入研究，MTSP 這類NP-hard 問題可求解的規模會越來越大，例如可以利用人工神經網絡模型解決物流配送環節中的復雜路線交叉和路徑重復問題；利用機器學習預測物流時效性和利用深度學習解決智能體避障的路徑規劃問題等。

（3）通過對應用領域的細分可以看出，MTSP 模型的變體在物流行業和應急救援兩方面仍然以車輛為主，如快遞包裹的運輸、傷員或物資的轉移等傳統場景中，地面車輛由于其自身不可替代的優勢更適合執行該類任務，加之對于車輛的容量和成本等約束最熟悉也最容易掌握，因此利用MTSP模型解決車輛路由調度問題有極高的研究價值。

而機器人由于其具有可移動性，可將其用在WSN（wireless sensor networks）中執行數據的收集轉發任務，利用MTSP模型規劃多機器人的任務分配及路徑規劃可以有效降低網絡能量消耗，延長網絡壽命。同時，機器人現已可以代替人工執行重復性和高危險性的工作，在物流環節、農業自動化和搜救工作中都有貢獻。無人機作為一種新興產品以其獨有的空中特性，在災害巡查和軍事領域都被廣泛應用，執行巡查或是空中作戰任務時利用MTSP 模型解決多目標的任務分配和路線規劃是提升效率的關鍵。與車輛不同，不論機器人還是無人機，這類變體都對能量有著嚴格的限制，但目前卻沒有標準的能量消耗模型，因而在未來的研究中，可以建立多旅行的Benchmark 基準函數，通過能量消耗模型延長智能體的續航能力。

（4）隨著工業4.0 時代的到來，智能產品對于生產系統的要求迫使新一代的工作系統必須適用柔性生產，但由于生產過程復雜，且機器人與人類的擅長點不同，很多工作單靠機器人或者人來完成結果都不理想。機器的優勢在于持久性長，精確度高，而人的優勢是認知能力強，能夠對于突發的情況進行控制和下決策，因此在裝配高精度的重型零部件時，人機協同的優勢得以凸顯。同時工業4.0 時代將是一個物流系統更加高效、供應鏈更加完善的時代，利用MTSP模型提高供應鏈中的運輸和配送效率，是趨勢也是必然。

（5）可以預見，由于變體的多樣性，今后對MTSP可應用領域的探索會延伸向更多涉及路徑優化或遍歷次序的實際問題中。比如將無人機的路徑規劃應用于海上巡邏預警、設計風力發電機等新能源設備的架構布局方案、躲避障礙避免碰撞的更成熟的無人駕駛技術等。

6 結束語

多旅行商問題作為TSP問題的一類泛化問題，其相關研究已經逐步從解決單純的數學問題進化成為解決一類問題中必不可少的一部分，也逐步迎來更多新的研究方向。同時，有關MTSP的研究一直以來都有著較大的現實意義和經濟效益，備受應用者與研究者的關注。本文通過算法和領域兩種角度對MTSP 模型進行了綜述，除此之外，通過總結文獻并分析文獻展望了日后發展趨勢。關于探求如何求解NP-hard問題一直以來都有各類專家學者不斷探尋，MTSP作為其經典模型，更加值得深入研究來發掘其蘊含的價值。