足夠接近的旅行商問題研究綜述

摘要： 考慮組合優化問題中的經典問題旅行商問題（traveling salesman problem， TSP）的變體——足夠接近的旅行商問題（close-enough traveling salesman probl

em， CETSP）. 首先， 綜合介紹TSP和CETSP的歷史、 求解方法和算法， 包括精確算法（如分支定界法、 線性規劃）和啟發式算法（如粒子群優化、 貪心算法等）.

TSP要求在給定城市列表和距離的條件下， 找到訪問每座城市一次并回到起點的最短路徑. CETSP是TSP的推廣， 允許在每個目標的鄰域內選擇任意點進行訪問， 而非精確位

置， 適用于可容忍誤差的實際應用， 如物流配送、 智能交通、 無線傳感器網絡等. CETSP具有更高的靈活性和適應性， 可大幅度減少計算資源和時間消耗， 特別在大規模問題中有更大優勢. 其次， 介紹CE

TSP在實際應用中的潛力， 尤其在物流、 工業制造、 交通規劃、 信息通訊等領域， 為提高效率、 降低成本、 推動智能化決策提供了有效解決方案. 最后， 指出了CETSP的一些未來研究方向.

關鍵詞： 足夠接近的旅行商問題； 啟發式算法； 路徑規劃； 模型應用

中圖分類號： TP301.6" 文獻標志碼： A" 文章編號： 1671-5489（2025）01-0114-10

Research" Review of" Close Enough Traveling Salesman Problem

SHI Fengyuan1， OUYANG Dantong1，2， ZHANG Liming1，2

（1. College of Computer Science and Technology， Jilin University， Changchun 130012， China;

2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education，Jilin University， Changchun 130012， China）

收稿日期： 2024-12-05.

第一作者簡介： 史豐源（2000—）， 男， 漢族， 碩士研究生， 從事基于模型診斷的研究， E-mail： Shify23@mails.jlu.edu.cn.

通信作者簡介： 歐陽丹彤（1968—）， 女， 滿族， 博士， 教授， 博士生導師， 從事人工智能和基于模型診斷的研究， E-mail： ouyd@jlu.edu.cn.

基金項目： 國家自然科學基金（批準號： 62076108; 61872159; 61672261）.

Abstract： We consider a variant of the classic problem of" the traveling salesman problem （TSP） in combinatorial optimization problem：

the close enough traveling salesman problem （CETSP）.

Firstly， we comprehensively introduce the history， solving methods， and algorithms for both TSP and CETSP， including exact algorithms （such as branch and bound method，

linear programming） and heuristic algorithms （such as particle swarm optimization， greedy algorithms， etc.）.

The TSP requires finding the shortest path to visit each city" once and return to the starting point given a list of cities and distances.

CETSP is a generalization of TSP， allowing the visiting point for each target to be chosen from within a specified neighborhood， rather than" exact location.

It is" suitable for practical applications that can" tolerate errors， such as logistics distribution， intelligent transportation， and wireless sensor networks， etc.

CETSP has higher flexibility and adaptability， which can significantly reduce computational resources and time consumption， particularly for large-scale problems with

greater advantages. Secondly， we introduce" the potential" of CETSP in practical applications， especially in logistics， industrial manufacturing， traffic planning， information and comm

unication， offering effective solutions for improving efficiency， reducing costs， and promoting intelligent decision-making. Finally， we have identified some future research directions for CETSP.

Keywords： close enough traveling salesman problem; heuristic algorithm; path planning; model application

組合優化問題（combinatorial optimization problem， COP）［1］是在有限數目可行解的集合中找出最優解的一類優化問題， 其廣泛應用于物流、 電信、 交通、 軍事等領域.

雖然不同組合優化問題的應用背景不同， 但絕大多數組合優化問題通過數學建模后都可以抽象為混合整數規劃問題， 因此， 如何高效地求解組合優化問題是學術界研究的一個重要課題.

雖然這類問題的應用廣泛， 但在求解過程中， 隨著問題的規模越來越大， 同時產生了巨大的時間成本， 而且現有的許多方法對解決這類問題都沒有很好的綜

合效果， 因此組合優化問題是NP-難［2］問題. 旅行商問題（traveling salesman problem， TSP）［3］是一個經典的組合優化問題. 本文以旅行商問題作為切

入點， 通過對該問題的簡單歸納引申出TSP問題的變體問題足夠接近的旅行商問題（close-enough traveling salesman problem， CETSP）， 綜合介紹足夠接近的旅行

商問題的啟發式解決方法及其應用， 并對CETSP模型未來的研究方向進行了展望.

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

TSP是一個組合優化問題， 可描述為給定一系列城市和每對城市之間的距離， 求解訪問每座城市一次并回到起始城市的最短路徑. TSP作為一個被廣

泛認可的數學和運籌學問題， 隨著計算機科學和運籌學的發展而備受關注." TSP問題最初來源于實際生活中的旅行商行走問題， 即如何規劃一條最短

的路線， 使旅行商能訪問每座城市一次并返回出發點. 該問題在物流、 配送、 路線規劃等領域應用廣泛. 在20世紀50年代， TSP問題首次被正式定義［4］， 并且很快被證明是NP-難問題，

即沒有已知的多項式時間算法可解決所有實例. 經過多年的發展， 目前該問題的求解算法已有很多， 主要分為找出最優解的精確算法和基于經驗或直

觀規則構建解， 不保證找到最優解， 但能在合理時間內得到較好的可行解啟發式算法［5］.

精確算法旨在找到TSP的最優解. 暴力搜索法通過列舉所有可能的城市排列順序， 計算每種排列的路徑總長度， 從而找出最短路徑， 適用于城市數量較少的小規模問題， 但計算復雜度

極高， 為O（n！）， 其中n表示城市數量. 隨著城市數量的增加， 計算時間呈指數級增長， 在這種數據量下應用精確算法變得不切實際.

動態規劃法［6］將問題分解為多個子問題， 利用子問題的重疊性， 通過遞歸關系求解， 在城市數量相對較少時能有效減少計算量， 但空間復雜度較高， 需存儲大量中間結果， 對大規模問題可能面臨內存限制.

分支定界法基于樹狀搜索結構， 對解空間進行系統性搜索， 通過計算下界（如使用最小生成樹等方法估計路徑長度下限）剪枝不必要的分支， 適用于中等規模問題， 但對復雜問題

實例， 下界估計可能不夠精確， 導致搜索空間大、 計算時間長.

線性規劃與割平面法將 TSP 問題轉化為線性規劃問題， 通過添加約束條件（割平面）逐步逼近整數最優解， 對一些特殊結構的TSP問題或結合其他優化技術時， 能有效找到最優

解或高質量近似解， 但割平面的生成和選擇需要技巧和計算資源， 大規模問題可能需要復雜算法和求解線性規劃模型.

但經典TSP是一種基礎的求最短路徑規劃問題， 它只需考慮總路程最短這一單一條件約束，" 而大部分實際應用問題卻不能被簡單的直接歸納為 TSP 問題， 例如配送無人機、

無線傳感器網絡中的數據采集、 通信網絡中的信號覆蓋等. 在這些場景中， 銷售員（如無人機或信號設備）不需要精確到達每個點， 只需覆蓋一個范圍， 因此研究CETSP有助于為

這些問題找到更高效的解決方案. CETSP的研究有助于在一些受限條件（如有限的燃料、 時間或資源）下規劃更短的路徑， 減少銷售員的行程時間或成本. 在物流、 通信、 地理數據收集等領域有廣泛應用.

2 足夠接近的旅行商問題

作為TSP的變體， CETSP首次由Gulczynski等［7］提出， CETSP模型相比于傳統TSP更貼近一些實際問題， 如機器人路徑規

劃［8］等. CETSP是TSP的一種實用推廣， 其目標是只要到達一個區域（鄰域）而不是精確位置. 約束條件中額外的自由度允許通過確定訪問鄰近區域的合適位置節省總的旅行成本.

2.1 問題描述

在歐氏平面上給定n個目標的集合V={p1，p2，…，pn}和初始倉庫p0， 每個目標V有一個半徑為r的圓盤鄰域N. 目標是找到最短的Hamilton環S={p0，p

1，…，pn，p0}， Hamilton環在倉庫p0處開始和結束， pi為通過每個目標vi盤鄰域Ni中的點. 定義d（x，y）為點x和點y之間的距離， f（S）為所求的最終距離， 則CETSP的定義如下：

CETSP： min f（S）=∑N-1i=0d（pi，pi+1）+d（pN，p0），s.t. S={p0，p1，…，pN，p0}， pi∈Ni， i=1，2，…，N.

2.2 問題特點

在傳統TSP中， 推銷員必須精確訪問目標， 而在CETSP中， 允許在目標城市的鄰域范圍內選擇一個合適位置進行訪問. 路徑只需覆蓋目標城市所在區域而不是精確坐標， 因此路徑

優化考慮的是通過區域而不是點. TSP路徑優化的目標是最短距離， 而CETSP路徑優化的目標是足夠接近的最短距離， 路徑不必經過精確位置. 這種優化目標相比于傳統TSP更靈活，

適用性更強， 且能容忍一定誤差， 減少計算的復雜度.

標準CETSP模型是圓形的覆蓋區域， 但其也適應不同形狀的覆蓋區域， 如橢圓形、 多邊形等， 這取決于實際問題的需求. 在三維空間中， 覆蓋區域可以是球體或其他三維形狀.

例如， 在無人機執行任務時， 其信號覆蓋范圍可能是一個不規則的三維空間區域， CETSP可以對這種情況進行建模.

CETSP和TSP的特殊性導致其可以獲得較短的路徑， 在許多實際應用中更有效. 圖1為TSP訪問和CETSP訪問示意圖， 其中黑色三角形表示倉庫， 黑色節點是目標及其

圓盤鄰域. 由圖1可見， CETSP巡視明顯短于TSP巡視， 并且CETSP更符合實際情況. CETSP可以視為TSP的推廣， 如果

所有圓盤鄰域的半徑都為0， 則CETSP即簡化為標準TSP. CETSP是一個NP-難問題， 在計算上很難求解.

2.3 應用場景

與傳統的TSP適用于對路徑精度要求非常高的場景不同， CETSP適用于可以容忍誤差的實際問題， 尤其是在路徑規劃時間和計算資源有限的情況下. 例如在大規模物流配送中

， 當城市數量龐大時， 完全精確的路徑優化不現實， 而CETSP模型可提供足夠接近的路徑解決方案; 在無人駕駛和智能交通中， 若處于動態變化的交通環境中， 則可能不需要絕對最

優的路徑， 而是一個足夠好的解， 能在合理的時間內快速生成. 相比于TSP的求解必須遵循嚴格的最優標準， 路徑誤差不可容忍， 計算結果的靈活性較低， C

ETSP則提供了一定的靈活性， 允許在一些約束條件下進行權衡， 如時間、 計算資源、 路徑長度等， 允許在給定的誤差范圍內找到一個接近最優的解. 這種容錯性使CETSP在一些現實場景下更具實用性.

3 CETSP模型的求解算法

在CETSP的研究中， 基于TSP， Cariou等［9］開發了幾種啟發式算法， 主要采用三階段啟發式方法進行求解. Mennell［10］提出了一種

三階段Steiner區域啟發式算法， 降低了解決問題的復雜性， 并使用二階錐規劃（SOCP）［11］改進路徑質量. Behdani等［12］提出了一種基于混合整數規劃（MIP）［13］的精確算法， 為CETSP

提供了可行的最優解， 但在處理大規模問題上性能欠佳. 之后研究者們引入了基于分支限界［14］和SOCP的精確算法［15］， 這些方法能在有限步內達到某些最優解， 但同樣難

以處理更大規模的問題. Carrabs等［16］結合離散化技術和MIP的方法， 提出了一種新型啟發式算法， 解決CETSP問題. Yang等［1

7］結合粒子群優化和遺傳算法提出了混合算法， 相比于MIP方法可更有效地處理CETSP實例. Wang等［18］開發了一種快速的三步啟發式算法（SZVNS）， 該

算法利用變量鄰域搜索策略. Carrabs等［19］提出的（lb/ub）Alg方法引入了新的離散化策略， 并結合了Carousel貪婪算法， 提高了搜索效率. Di

Placido等［20］提出了一種有效的遺傳算法， 表明該領域的元啟發式方法仍有潛力， 并獲得了更多的更優解.

由于CETSP的解空間在問題規模擴大的過程中會呈現指數式增長， 精確算法難以求解， 啟發式算法相比于盲目搜索則會更有效， 因為啟發函數經過設計修改， 一般可以在較短的時

間內得到一個搜索問題的最優解， 對于NP-難問題， 使用啟發式算法也可以在多項式時間內得到一個當前的最優解， 所以目前人們更多使用啟發式算法對 CETSP 進行求解. 隨

著問題的發展， 無論是從原始的優化推銷員路徑問題、 機器人調度問題， 還是到現在的無人機協同任務分配、 無線傳感器網絡中的數據采集、 通信網絡中的信號覆蓋等問題中， 雖

然由于問題變體的多樣性導致求解的側重點不同， 但都可以使用啟發式算法對其進行求解. 本文主要圍繞啟發式算法解決CETSP展開綜述.

3.1 基于離散化的啟發式算法

離散化的啟發式算法主要是指在解決優化問題時， 特別是在處理連續變量需要被轉化為離散變量的場景中， 采用的一些基于經驗和直觀構造的算法. 這些方法在可接受的計算時間和空

間花費下， 為組合優化問題提供可行解， 雖然這些解可能不是最優的， 但在實際應用中通常能在合理的時間內得到較好的方案.

Carrabs等［21］提出了周邊離散化方案（PDS）和內部離散化方案（IDS）， 將CETSP轉化為廣義旅行商問題（GTSP）， 然后通過混合整數規劃（MIP）模

型求解. 之后， 他們進一步改進了內部離散化方案， 結合SOCP進一步優化解的質量.

PDS方案其核心在于通過合理選擇離散化點逼近最優解. PDS方案將每個鄰域N（v）的圓周Cv等分為k份， 把離散化點放置在這些圓形弧的端點. 例如， 當k=3時， α=2Π/k=120

°， 離散化點均勻分布在圓周上. 在最差情況下， 即當最優路徑T的轉向點p1位于圓周上Cv某圓形弧d1，d2的中點時， 產生最大離散化誤差.

IDS方案核心也是選擇離散化點逼近最優解. IDS方案同樣將每個鄰域N（v）的圓周Cv等分為k份， 但把離散化點放置在每個弧對應的弦ab的中點. 如k=3或k=4時， 離散化點

的分布位置會相應改變.

這些離散化的啟發式方法通過不同的離散化策略， 在降低離散化誤差方面逐步改進， 為計算 CETSP 的最優解上下界提供了更有效的方法， 有助于在實際應用中更快、 更準確地找到接

近最優的旅行路線. 這種離散化方案簡單易行， 適用于大規模問題， 并且改進后的方案能顯著提高解的質量. 但離散化的粒度會影響解的質量和計算效率， 需要結合其他優化技術（如SOCP）才能獲得更好的結果.

3.2 基于Steiner-zone的啟發式算法

Behdani等［12］首次嘗試精確求解CETSP， 提出了離散化方案： 兩階段MIP、 Benders分解和迭代算法， 但未找到最優解. Mennel等［22］提出了一種啟發式算法，

雖然找到了接近最優的解， 但運行時間較長. Wang等［18］在上述方法的基礎上， 提出了一種快速三階段啟發式算法（SZVNS）， 可在較短時間為CETSP提供高質量解.

SZVNS通過減少問題規模、 構建初始解并優化解的方式高效解決CETSP. 利用Steiner區域（Steiner-zone）［22-23］化簡問題， 將CETSP轉化為標準TSP， 并通過可變鄰域搜索（

VNS）進一步優化， 按順序分為數據清理、 構造初始解和解的優化三個階段.

數據清理階段的目的是減少問題規模， 縮短運行時間. 由于并非所有客戶都需要顯式考慮， 例如， 如果一個客戶的服務區域完全被另一個客戶的服務區域覆蓋， 則可以將該客戶

從問題中移除. 通過這種修剪操作， 減少需要處理的客戶數量， 從而降低計算復雜度.

構造初始解的過程需要用到Steiner-zone， 是指多個客戶服務區域（圓盤）的重疊部分. 如果一個路徑經過某個 Steiner-zone， 則該區域內所有客戶都被服務. Steiner

-zone的“度”定義為其包含的圓盤數量. 度越高， 路徑經過該區域時服務的客戶越多， 但區域面積通常較小， 限制了選擇 Steiner點的靈活性.

在解決Steiner-zone的掃描問題中， Wang等［18］開發了一種基于掃描線的算法. 這種算法通過水平掃描線逐步檢查客戶圓盤的重疊情況. 使用數據結構（如紅黑樹）快速存儲和檢索當

前掃描線上的區間. 僅檢查可能形成Steiner區域的子集， 跳過無意義的子集. 為避免極端情況下的指數復雜度， 限制Steiner區域的最大度數為3.

在識別所有Steiner區域后， 通過求解集合覆蓋問題（set covering problem， SCP）， 選擇最少數量的Steiner區域覆蓋所有客戶. 從選定的Steiner區域中選擇Steiner點， 構造一條可

行路徑. 使用3種規則選擇Steiner點， 生成3條可行路徑， 并保留其中最優的一條作為初始解. 再在初始解的基礎上， 通過多種鄰域操作進一步優化路徑長度.

這種三階段啟發式算法通過數據清理和掃描線算法顯著減少了問題規模， 適用于不同客戶的半徑分布（均勻或非均勻）， 能快速生成高質量的初始解， 并提升解的精度. 但在

計算過程中復雜度較高， 尤其是在處理復雜實例時， 由于對初始解的質量依賴較大， 且Steiner區域最大度數限制為3， 可能會錯過一些高質量解.

3.3 基于粒子群優化算法的方法

粒子群優化（PSO）算法［24］通常由多個簡單個體（稱為粒子或個體）組成， 這些個體通過局部的感知和信息交換， 協同工作， 尋找問題的最優解. 粒子群優化算法

的核心思想是個體通過局部的信息交流（如通過位置、 速度等方式）協調行動， 以實現全局目標的最優化.

Di Placido等［20］提出了將PSO框架下的遺傳算法（GA）利用種群進化的方式優化路徑. GA［25］進一步改進了遺傳操作（如多步交叉和變異）

， 并結合K-means聚類［26］初始化種群. GA的核心操作包括選擇、 交叉和變異， 并結合局部搜索和數學優化方法進一步改進解.

與大部分算法相同［27-28］， 為減少問題規模， GA同樣在正式求解前需進行預處理， 移除在覆蓋其他目標時會被自動覆蓋的目標節點. 主要包括以下兩部分： 如果一個目標節點的鄰域

完全包含在另一個目標節點的鄰域中， 則可以移除前者； 如果一個目標節點的鄰域與其他多個目標節點的鄰域重疊， 并且這些重疊區域已經被覆蓋， 則可以移除該目標節點. 通過這些

預處理步驟， 可顯著減少問題規模， 提高算法效率.

遺傳算法的主要步驟包括種群初始化、 適應度函數優化、 選擇、 交叉、 變異和改進［29］. 初始種群由隨機生成的染色體組成， 每個染色體表示一個可行解（即訪問順序）. 染色體中

的基因表示目標節點的訪問順序. 適應度函數用于評估每個染色體的質量， 目標是最小化路徑長度. 路徑長度的計算考慮了目標節點的鄰域覆蓋特性. 使用基于適應度的選擇機制（如

輪盤賭選擇或錦標賽選擇）從種群中挑選染色體， 優質解有更高的被選擇概率. 采用部分匹配交叉或順序交叉等方法生成新染色體. 交叉操作通過交換父代染色體的部分基因， 產生新

的解. 隨機改變染色體中的基因順序， 以增加種群的多樣性， 避免陷入局部最優. 變異操作可能包括交換兩個基因的位置或隨機調整訪問順序. 每次生成或修改染色體后， 調用改進操

作對解進行局部優化. 最后對解進行優化， 包括2-opt局部搜索、 SOCP和3Alg算法3種. 2-opt局部搜索是交換兩個節點順序以優化路徑順序， 減少路徑長度. SOCP是在固定訪問順

序的情況下， 通過數學優化調整路徑中的轉折點位置， 進一步縮短路徑. 3Alg算法是基于貪心策略調整轉折點位置， 作為SOCP的快速替代方法. 由于SOCP求解耗時較長， 算法僅對種群中的

隨機個體應用SOCP， 剩余節點使用3Alg算法.

這種算法由于結合了局部搜索（2-opt）與數學優化（SOCP和3Alg）的方法， 使得遺傳算法具有記憶性， 即在全局搜索的同時進行局部優化， 為CETSP提供了最優解， 在理論和實際

應用中效果較好， 為類似問題的求解提供了重要參考.

3.4 基于貪心算法的啟發式方法

在經典TSP的背景下， 傳統貪心算法是一種常用的求解近似解的方法， 其基本思想是在每步選擇中都采取當前狀態下最優（即最有利）的選擇， 而不考慮整體的最優解. 貪心算法簡

單直觀， 易于實現， 計算速度相對較快. 在處理小規模問題或對解的精度要求不高的情況下， 能快速得到一個可行的旅行路線. 但貪心算法并不能總是得到全局最優解， 它易陷

入局部最優解. 由于它只考慮當前的最優選擇， 而未考慮后續步驟的影響， 可能會錯過全局最優的路徑. 特別是在復雜的旅行商問題中， 城市之間的距離關系復雜， 貪心算法得到的

解可能與最優解相差較大.

在實際應用中， 傳統貪心算法雖然不能保證得到最優解， 但仍具有一定的實用價值. 例如， 在對實時性要求較高的場景中， 需要快速得到一個可行的旅行路線， 貪心算

法可作為一種初步的解決方案， 然后在此基礎上進一步優化或調整.

CG（carousel greedy）算法［19］結合離散化方案， 通過貪心策略［30］快速生成可行解， 并在后續階段優化路徑. CG算法的設計理念是設計一種通用

的啟發式框架， 能在保持貪心算法速度和簡單性的同時， 提升其解的質量. CG算法在計算成本可控的情況下，

擴展解空間， 比傳統貪心算法的準確性更高， 并具有比元啟發式算法（如模擬退火、 禁忌搜索等）更簡單的結構.

CG算法是一種構造性啟發式算法， 通過引入兩個參數（α和β）， 在構造解的過程中動態調整部分解， 從而探索更多可能的解， 并通過多次迭代調整， CG算法可修正傳統貪心算法

中早期選擇的錯誤. 與元啟發式算法不同， CG算法只生成一個最終可行解， 而不是在多個解之間迭代優化. 通過多次調整部分解， CG算法能修正早期選擇中的錯誤.

CG算法的執行過程可分為3個階段： 首先， 使用傳統貪心算法生成一個初始部分解; 其次， 通過多次迭代調整部分解， 延長解的構造過程， 在每次迭代中， 都移除部分解中的某些元素（由參數

β 控制）， 并使用貪心算法重新選擇元素， 迭代次數由參數α控制； 最后， 在上個階段的基礎上， 使用貪心算法完成剩余部分解的構造， 生成最終的可行解.

CG算法的時間復雜度可表示為T（CG）=（1+α）O（1）， 其中O（1）為原始貪心算法的復雜度. 由于α和β的值較小， CG算法的運行時間通常只比傳統貪心算法增加5～10倍， 但卻顯著

提升了解的質量. 與其他元啟發式算法（如模擬退火、 禁忌搜索、 蟻群優化算法）相比， CG算法的運行時間較少， 尤其適合處理大規模問題. 文獻［19］還將CG算法應用于多個經典的組

合優化問題中， 如最小標號生成樹， 最小頂點覆蓋問題等.

實驗結果表明， CG算法在解的質量上優于傳統貪心算法， 并在某些情況下接近甚至超過元啟發式算

法， 且CG算法的運行時間顯著低于元啟發式算法， 尤其在大規模問題上表現出色. 但由于貪心策略可能導致局部最優， 在復雜實例的實驗上可能導致適應性較差.

3.5 基于分支界定算法的方法

分支定界算法（branch-and-bound， BB）［14］是一種用于求解組合優化問題的通用方法， 其核心思想是將問題的解空間劃分為多個子空間（分支）， 再為每個子問題計算一個

上界或下界， 以估計子問題的最優解（定界）. 根據這個界限判斷是否繼續深入搜索或剪枝. 如果子問題的界限無法比當前最優解更好（即該解不可能超過或達到當前的最優解），

則停止進一步搜索， 排除不可能包含最優解的子空間， 從而縮小搜索范圍， 可高效找到最優解.

分支界定算法是一種靈活且強大的優化算法， 尤其適用于求解具有組合性質的最優化問題. 通過合理的界定和剪枝策略， 可有效減少搜索空間， 提高計算效率. 但其性能依

賴于問題的規模和分支界定的設計， 在處理大規模問題時仍會面臨時間和空間復雜度過高的問題.

文獻［31］對分支界定算法進行改進以解決CETSP問題. 先選擇一個包含倉庫的3個頂點作為初始部分序列， 再使用SOCP［32］解決基于初始部分序列

的最優旅行路徑問題， 得到路徑長度的下界. 確定初始部分序列的旅行路徑是否覆蓋了所有頂點， 如果所有頂點都被覆蓋， 則找到了一個可行解， 算法終止， 如果未

覆蓋所有頂點， 則將當前路徑長度作為下界， 并將其加入搜索樹作為根節點.

從解的搜索樹中選擇一個部分序列進行探索， 選擇一個未被覆蓋的頂點作為分支頂點， 并在序列的所有可能位置插入該頂點， 生成新的部分序列. 對每個新生成的部分序列， 解決相

應的SOCP問題以獲得旅行路徑長度. 如果新序列的路徑長度小于當前已知的最佳解， 則更新最佳解； 如果新序列的路徑長度大于或等于當前最佳解， 則根據算法的剪枝策略， 可將該

序列從搜索樹中移除. 在搜索中使用循環最佳優先搜索（CBFS-CV）策略選擇下一個要探索的節點， CBFS-CV策略通過維護一組有序且標記的輪廓， 以指導搜索過程，

每個輪廓包含一組未探索的搜索樹節點. 由于通過假設遠離插入位置的頂點覆蓋狀態不會改變， 所以可以減少頂點覆蓋檢查的數量， 從而減少不必要的計算. 基于

上一步的可行解構建一個傳統的TSP問題， 并使用Concorde TSP求解器找到更好的可行解， 基于該可行解構造一個新的SOCP問題. 整個過程中使用探針方法減少需要存儲的未

探索節點的數量， 通過在短暫的搜索中探索子樹， 并在必要時將未探索的節點重新插入搜索樹. 持續搜索直到到達預設的時間和空間限制， 得到目前的最優解.

4 CETSP應用領域

4.1 物流配送

在城市物流配送中， 快遞公司需要安排車輛為多個客戶送貨， CETSP模型可考慮將每個客戶地址周圍的一定區域（例如以客戶地址為圓心的圓形區域）作為貨物可送達的范圍， 而無

需精確到客戶門口的具體位置. 這樣可以在保證客戶能收到貨物的前提下， 優化車輛的行駛路線， 減少總行駛里程， 降低運輸成本， 提高配送效率［33］. 例如， 對一個擁有多個小區

客戶的快遞配送區域， 車輛可以在小區門口附近（覆蓋區域內）完成貨物交接， 而不必進入每個小區內部的具體地址.

對電商企業的倉儲中心到多個零售點的貨物運輸， CETSP模型有助于確定最佳的配送順序和路徑， 使貨物能及時、 高效地到達各零售點， 同時減少車輛的空載里程和能源消耗.

在冷鏈物流網絡中， 涉及到易腐貨物的運輸， 如生鮮食品、 藥品等. CETSP模型可用于構建具有無人機運輸功能的新型預冷站， 解決根據各產地日產量的運輸方式選擇及新型預冷站當

日無人機和卡車的運輸能力分配等問題. 例如， 在水果產地， 根據果園的分布情況（視為客戶點）， 利用CETSP模型確定無人機和卡車的最優運輸路線， 將采摘的水果快速運輸到預冷

站， 保證水果的新鮮度， 同時提高冷鏈物流網絡的運行效率， 減少資源浪費.

4.2 工業制造

在電子電路設計中， 需要在電路板上布置各種電子元件并連接它們的線路. CETSP模型可以確定線路的最佳布局， 將電子元件視為客戶點， 線路需要經過元件周圍的一定區域（覆

蓋區域）. 通過優化線路路徑， 減少線路長度， 不僅可以降低生產成本（減少材料使用）， 還能減少信號傳輸延遲和干擾， 提高電路的性能和可靠性. 例如， 在高密度電路板設計中，

CETSP模型可以幫助工程師在有限的空間內規劃出最短且干擾最小的線路連接方案.

在工廠中， 有大量的生產設備需要定期巡檢維護. 將每臺設備視為一個客戶點， 設備周圍的可操作區域視為覆蓋區域， CETSP模型可用于規劃巡檢人員或巡檢機器人的最優巡檢路徑.

從而確保設備得到及時檢查， 同時減少巡檢時間和人力成本， 提高生產設備的維護效率， 保障生產線的正常運行.

4.3 交通規劃

在城市公共交通系統中， 公交車或地鐵的線路規劃可以借助CETSP模型. 以公交站點為客戶點， 站點周圍一定范圍為覆蓋區域， 優化公交車輛的行駛路線， 使乘客能在站點附近方便

地上下車， 同時提高公交車輛的運行效率， 減少乘客的候車時間和出行成本. 例如， 在設計新的公交線路時， 考慮如何以最短的路徑連接多個站點覆蓋區域， 滿足居民的出行需求.

對于智能交通系統中的出租車調度， CETSP模型可以幫助確定出租車在接送乘客時的最優行駛路徑， 提高出租車的運營效率， 減少空駛里程， 降低能源消耗， 同時也為乘客提供更快捷的服務.

在規劃智能交通基礎設施（如交通傳感器、 攝像頭等）的布局時， CETSP模型可用于確定這些設備的最佳安裝位置. 將需要監測或控制的交通路段視為客戶點， 設備的有效監測范圍作

為覆蓋區域， 通過優化設備布局， 以最少的設備數量實現對交通狀況的全面監測和有效控制， 提高智能交通系統的性能.

4.4 信息通訊

在無線網絡建設中， 基站的布局對信號覆蓋和通信質量至關重要. 將需要覆蓋的區域劃分為多個客戶點及其覆蓋區域， CETSP模型可用于確定基站的最佳位置， 使基站能以最少的

數量實現對目標區域的有效覆蓋， 同時減少信號干擾， 提高網絡通信質量， 降低建設成本. 例如， 在城市中規劃移動通信基站的布局， 確保各區域都能獲得良好的信號服務.

在無線傳感器網絡中， 傳感器節點分布在監測區域內［34］， 數據采集設備（如移動數據采集器或無人機）需要定期收集傳感器數據. 將傳感器節點視為客戶點， 數據采集設備能與傳感器

通信的有效范圍作為覆蓋區域， CETSP模型可以幫助規劃數據采集設備的最優路徑， 提高數據采集效率， 延長傳感器網絡的使用壽命， 降低數據采集成本. 例如， 在環境監測傳感器網

絡中， 無人機按CETSP模型規劃的路徑采集各傳感器節點的數據， 實現對環境參數的實時監測.

隨著技術的不斷進步和發展， CETSP模型的應用領域還將不斷拓展， 為解決各種實際優化問題提供更有效的解決方案.

5 未來研究方向

CETSP是TSP的一種變體和推廣， TSP是經典的組合優化問題， 而CETSP在TSP的基礎上擴展了訪問區域， 將訪問目標從精確位置擴展到一定的鄰域范圍， 提升了解決問題的靈活性. 這種

拓展豐富了組合優化問題的類型， 為理論研究提供了新的方向和思路. 作為NP-難問題， CETSP的研究有助于推動NP-難問題的研究與發展， 其復雜的解空間結構和較高的求解難度，

促使人們需要不斷探索新的算法和理論. 在算法研究中， CETSP的求解推動了多種算法的發展和改進， 但這些算法仍存在不足.

在離散化啟發式算法中， PDS和IDS的提出為將連續的鄰域求解問題轉化為離散的廣義旅行商問題提供了方法， 但離散化誤差仍不可避免. 尤其在目標點鄰域較大或形狀復雜

的情況下， 離散化點的分布可能無法完全覆蓋鄰域的邊界， 導致誤差累積. 由于改進離散化方案是針對圓形鄰域設計， 因此如果鄰域形狀較復雜， 則離散化方案可能需要重新設計

. 這種算法主要關注優化路徑長度， 未來研究還可以考慮其他可能的優化目標， 如路徑平滑性等.

三段式啟發式算法（如SZVNS）結合了數據清理、 初始解構建和解的優化等方法， 利用Steiner-zone化簡問題， 這種多階段的算法設計理念和對Steiner-zone的利用， 豐富了啟發式算

法的設計方案. 但該方案仍需進行優化， 例如， 由于剪枝算法的原理導致當客戶半徑均勻的

情況下， 沒有客戶可以被修剪， 此時數據清理的效果較差. 未來研究可以考慮與機器學習技術相結合， 使用強化學習優化耗時較長的VNS搜索策略， 動態調整搜索順序或操作參數.

基于粒子群的優化算法在CETSP求解中通過結合局部搜索和數學優化方法， 展示了如何在復雜的組合優化問題中利用種群進化和局部改進提高解的質量， 推動了遺傳

算法等粒子群優化算法的進一步發展. 在現有研究中， 雖然GA在大多數實例上可以找到高質量的解， 但在某些情況下， 其計算時間明顯高于其他啟發式算法， 如在變動重疊率實例中，

GA的計算時間長于SZVNS， 未來研究仍應在改進算法效率方面進行探索.

基于貪心算法的啟發式方法（如CG算法）， 通過引入參數動態調整部分解， 拓展了解空間， 為貪心算法在復雜問題中的有效應用提供了新的范例， 也啟發了更多對傳統簡單算法進行

改進以適應復雜組合優化問題的研究. 然而對于CG算法中的兩個關鍵參數α和β， 目前雖然有對其使用的推薦范圍， 但仍需針對具體問題進行調優， 缺乏自動化， 且不同問題的

最佳參數組合差異較大， 增加了算法的使用難度. 未來研究可以考慮引入自動化參數調優技術， 以減少人工干預提高適用性. 由于CG算法的設計目標是生成單一解， 因此會限制解空間

的探索深度， 尤其是在解空間復雜和局部最優較多的問題中， 可以擴展CG的框架， 生成多個可行解， 如在每次迭代中記錄多個部分解， 并對這些部分解進行進一步優化.

目前對CETSP的研究取得了許多成果， 但不同算法仍在不同方面（如計算效率、 調整局部最優、 種群多樣性維護和實際應用普適性等）存在不足. 未來研究仍可針對

這些問題進行改進， 通過進一步優化不同算法的各組件和機制， 提高其在不同問題實例上的性能和應用廣泛性. 未來研究可以測試不同算法在不同問題規模、 復雜度和多樣性

上的性能， 以評估其魯棒性和適應性， 也可以考慮加入一些抗噪聲的機制， 以應對實際應用中的不確定性.

CETSP研究推動了智能化決策與自動化操作的發展， 在面對大規模、 復雜的任務分配和路徑規劃時， CETSP為相關算法和智能系統提供了有效的模型基礎， 使無人機、 機器人等自動化

設備能根據該模型更智能地規劃任務路線， 提高自動化作業的效率和精準度， 為實現智能化的生產、 配送、 監測等多領域的運作奠定了基礎.

參考文獻

［1］ BLUM C， ROLI A. Metaheuristics in Combinatorial Optimi

zation： Overview and Conceptual Comparison ［J］. ACM Computing Surveys， 2003， 35（3）： 268-308.

［2］ ARORA S. Polynomial Time Approximation Schemes f

or Euclidean TSP and Other Geometric Problems ［C］//Proceedings of 37th Conference on Foundations of Computer Science. Piscataway， NJ： IEEE， 2002： 2-11.

［3］ KRUSKAL J B. On the Shortest Spanning Subtree of a G

raph and the Traveling Salesman Problem ［J］. Proceedings of the American Mathematical Society， 1956， 7（1）： 48-50.

［4］ LIN S， KERNIGHAN B W. An Effective Heuristic Algorithm for the Traveling-Salesman Problem ［J］. Operations Research， 1973， 21（2）： 498-516.

［5］ DORIGO M， GAMBARDELLA L M. Ant Colony System： A Cooperative Learning Approach

to the Traveling Salesman Problem ［J］. IEEE Transactions on Evolutionary Computation， 1997， 1（1）： 53-66.

［6］ SCHOLZ J. Genetic Algorithms and the Traveling Salesman P

roblem a Historical Review ［EB/OL］. （2019-01-17）［2024-11-20］. https：//arxiv.org/abs/1901.05737.

［7］ GULCZYNSKI D J， HEATH J W， PRICE C C. The Close Enough Traveling Salesman Prob

lem： A Discussion of Several Heuristics ［C］//Perspectives in Operations Research. Berlin： Springer， 2006： 271-283.

［8］ NEDJATIA A， VIZVáRIB B. Robot Path Planning by Traveling Salesman Problem w

ith Circle Neighborhood： Modeling， Algorithm， and Applications ［EB/OL］. （2020-03-14）［2024-11-10］. https：//arxiv.org/abs/2003.06712.

［9］ CARIOU C， MOIROUX-ARVIS L， PINET F， et al. Evolutionary Algorithm with Geomet

rical Heuristics for Solving the Close Enough Traveling Salesman Problem： Applic

ation to the Trajectory Planning of an Unmanned Aerial Vehicle ［J］. Algorithms， 2023， 16（1）： 44-1-44-16.

［10］ MENNELL W K. Heuristics for Solving Three Routing Problems： Close-Enough Tra

veling Salesman Problem， Close-Enough Vehicle Routing Problem， and Sequence-Depen

dent Team Orienteering Problem ［D］. Maryland： University of Maryland，" 2009.

［11］ ALIZADEH F， GOLDFARB D. Second-Order Cone Programming ［J］. Mathematical Programming， 2003， 95（1）： 3-51.

［12］ BEHDANI B， SMITH J C. An Integer-Programming-Based Approach to the Close-En

ough Traveling Salesman Problem ［J］. INFORMS Journal on Computing， 2014， 26（3）： 415-432.

［13］ DECKEROVá J， KUCˇEROVá K， FAIGL J. On Improvement Heuristic to Solutions o

f the Close Enough Traveling Salesman Problem in Environments with Obstacles ［C］//2023 European Conference on Mobile Robots （ECMR）. Piscataway， NJ： IEEE， 2023： 1-6.

［14］ LAWLER E L， WOOD D E. Branch-and-Bound Methods： A Survey ［J］. Operations Research， 1966， 14（4）： 699-719.

［15］ HA M H， BOSTEL N， LANGEVIN A， et al. An Exact Algorithm for the Close Enough

Traveling Salesman Problem with Arc Covering Constraints ［C］//ICORES. ［S.l.］： DBLP， 2012： 233-238.

［16］ CARRABS F， CERRONE C， CERULLI R， et al. A Novel Discretization Scheme for th

e Close Enough Traveling Salesman Problem ［J］. Computers amp; Operations Research， 2017， 78： 163-171.

［17］ YANG Z， XIAO M Q， GE Y W， et al. A Double-Loop Hybrid Algorithm for the Trav

eling Salesman Problem with Arbitrary Neighbourhoods ［J］. European Journal of Operational Research， 2018， 265（1）： 65-80.

［18］ WANG X Y， GOLDEN B， WASIL E. A Steiner Zone Variable Neighborhood Search Heuri

stic for the Close-Enough Traveling Salesman Problem ［J］. Computers amp; Operations Research， 2019， 101： 200-219.

［19］ CARRABS F， CERRONE C， CERULLI R， et al. An Adaptive Heuristic Approach to Co

mpute Upper and Lower Bounds for the Close-Enough Traveling Salesman Problem ［J］. INFORMS Journal on Computing， 2020， 32（4）： 1030-1048.

［20］ DI PLACIDO A， ARCHETTI C， CERRONE C. A Genetic Algorithm for the Close-Enough

Traveling Salesman Problem with Application to Solar Panels Diagnostic Reconnaissance ［J］. Computers amp; Operations Research， 2022， 145： 105831-1-105831-23.

［21］ CARRABS F， CERRONE C， CERULLI R， et al. Improved Upper and Lower Bounds for

the Close Enough Traveling Salesman Problem ［C］//Green， Pervasive， and Cloud Computing. Berlin： Springer， 2017： 165-177.

［22］ MENNELL W， GOLDEN B， WASIL E. Asteiner-Zone Heuristic for Solving the Close-

Enough Traveling Salesman Problem ［C］//2th INFORMS Computing Society Conferenc

e： Operations Research， Computing， and Homeland Defense. ［S.l.］： Informs， 2011： 1-23.

［23］ SINHA ROY D， GOLDEN B， WANG X Y， et al. Estimating the Tour Length for the Clo

se Enough Traveling Salesman Problem ［J］. Algorithms， 2021， 14（4）： 123-1-123-9.

［24］ DI PLACIDO A， ARCHETTI C， CERRONE C， et al. The Generalized Close Enough Trav

eling Salesman Problem ［J］. European Journal of Operational Research， 2023， 310（3）： 974-991.

［25］ LEI Z Y， HAO J K. An Effective Memetic Algorithm for the Close-Enough Traveli

ng Salesman Problem ［J］. Applied Soft Computing， 2024， 153： 111266-1-111266-50.

［26］ DENG Y， LIU Y， ZHOU D Y. An Improved Genetic Algorithm with Initial Population

Strategy for Symmetric TSP ［J］. Mathematical Problems in Engineering， 2015， 2015（1）： 212794-1-212794-6.

［27］ MOSCATO P， COTTA C. A Modern Introduction to Memetic Algorithms ［C］//Handbook of Metaheuristics. Berlin： Springer， 2010： 141-183.

［28］ NERI F， COTTA C. Memetic Algorithms and Memetic Computing Optimization： A Literature Review ［J］. Swarm and Evolutionary Computation， 2012， 2： 1-14.

［29］ REN J， HAO J K， WU F， et al. An Effective Hybrid Search Algorithm for the Mu

ltiple Traveling Repairman Problem with Profits ［J］. European Journal of Operational Research， 2023， 304（2）： 381-394.

［30］ CERRONE C， CERULLI R， GOLDEN B. Carousel Greedy： A Generalized Greedy Algori

thm with Applications in Optimization ［J］. Computers amp; Operations Research， 2017， 85： 97-112.

［31］ ZHANG W D， SAUPPE J J， JACOBSON S H. Results for the Close-Enough Traveling S

alesman Problem with a Branch-and-Bound Algorithm ［J］. Computational Optimization and Applications， 2023， 85（2）： 369-407.

［32］ COUTINHO W P， NASCIMENTO R Q， PESSOA A A， et al. A Branch-and-Bound Algorithm

for the Close-Enough Traveling Salesman Problem ［J］. INFORMS Journal on Computing， 2016， 28（4）： 752-765.

［33］ DECKEROVá J， KUEROVá K， FAIGL J. On Improvement Heuristic to Solutions o

f the Close Enough Traveling Salesman Problem in Environments with Obstacles ［C］//2023 European Conference on Mobile Robots （ECMR）. Piscataway， NJ： IEEE， 2023： 1-6.

［34］ FAIGL J. GSOA： Growing Self-organizing Array-Unsupervised Learning for the C

lose-Enough Traveling Salesman Problem and Other Routing Problems ［J］. Neurocomputing， 2018， 312： 120-134.

（責任編輯：" 韓 嘯）