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

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

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

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

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

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

關(guān)鍵詞： 足夠接近的旅行商問題； 啟發(fā)式算法； 路徑規(guī)劃； 模型應(yīng)用

中圖分類號(hào)： TP301.6" 文獻(xiàn)標(biāo)志碼： A" 文章編號(hào)： 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—）， 女， 滿族， 博士， 教授， 博士生導(dǎo)師， 從事人工智能和基于模型診斷的研究， E-mail： ouyd@jlu.edu.cn.

基金項(xiàng)目： 國家自然科學(xué)基金（批準(zhǔn)號(hào)： 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

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

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

雖然這類問題的應(yīng)用廣泛， 但在求解過程中， 隨著問題的規(guī)模越來越大， 同時(shí)產(chǎn)生了巨大的時(shí)間成本， 而且現(xiàn)有的許多方法對(duì)解決這類問題都沒有很好的綜

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

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

商問題的啟發(fā)式解決方法及其應(yīng)用， 并對(duì)CETSP模型未來的研究方向進(jìn)行了展望.

1 旅行商問題的產(chǎn)生與發(fā)展

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

泛認(rèn)可的數(shù)學(xué)和運(yùn)籌學(xué)問題， 隨著計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)的發(fā)展而備受關(guān)注." TSP問題最初來源于實(shí)際生活中的旅行商行走問題， 即如何規(guī)劃一條最短

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

即沒有已知的多項(xiàng)式時(shí)間算法可解決所有實(shí)例. 經(jīng)過多年的發(fā)展， 目前該問題的求解算法已有很多， 主要分為找出最優(yōu)解的精確算法和基于經(jīng)驗(yàn)或直

觀規(guī)則構(gòu)建解， 不保證找到最優(yōu)解， 但能在合理時(shí)間內(nèi)得到較好的可行解啟發(fā)式算法［5］.

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

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

動(dòng)態(tài)規(guī)劃法［6］將問題分解為多個(gè)子問題， 利用子問題的重疊性， 通過遞歸關(guān)系求解， 在城市數(shù)量相對(duì)較少時(shí)能有效減少計(jì)算量， 但空間復(fù)雜度較高， 需存儲(chǔ)大量中間結(jié)果， 對(duì)大規(guī)模問題可能面臨內(nèi)存限制.

分支定界法基于樹狀搜索結(jié)構(gòu)， 對(duì)解空間進(jìn)行系統(tǒng)性搜索， 通過計(jì)算下界（如使用最小生成樹等方法估計(jì)路徑長度下限）剪枝不必要的分支， 適用于中等規(guī)模問題， 但對(duì)復(fù)雜問題

實(shí)例， 下界估計(jì)可能不夠精確， 導(dǎo)致搜索空間大、 計(jì)算時(shí)間長.

線性規(guī)劃與割平面法將 TSP 問題轉(zhuǎn)化為線性規(guī)劃問題， 通過添加約束條件（割平面）逐步逼近整數(shù)最優(yōu)解， 對(duì)一些特殊結(jié)構(gòu)的TSP問題或結(jié)合其他優(yōu)化技術(shù)時(shí)， 能有效找到最優(yōu)

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

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

無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)采集、 通信網(wǎng)絡(luò)中的信號(hào)覆蓋等. 在這些場景中， 銷售員（如無人機(jī)或信號(hào)設(shè)備）不需要精確到達(dá)每個(gè)點(diǎn)， 只需覆蓋一個(gè)范圍， 因此研究CETSP有助于為

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

2 足夠接近的旅行商問題

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

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

2.1 問題描述

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

1，…，pn，p0}， Hamilton環(huán)在倉庫p0處開始和結(jié)束， pi為通過每個(gè)目標(biāo)vi盤鄰域Ni中的點(diǎn). 定義d（x，y）為點(diǎn)x和點(diǎn)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 問題特點(diǎn)

在傳統(tǒng)TSP中， 推銷員必須精確訪問目標(biāo)， 而在CETSP中， 允許在目標(biāo)城市的鄰域范圍內(nèi)選擇一個(gè)合適位置進(jìn)行訪問. 路徑只需覆蓋目標(biāo)城市所在區(qū)域而不是精確坐標(biāo)， 因此路徑

優(yōu)化考慮的是通過區(qū)域而不是點(diǎn). TSP路徑優(yōu)化的目標(biāo)是最短距離， 而CETSP路徑優(yōu)化的目標(biāo)是足夠接近的最短距離， 路徑不必經(jīng)過精確位置. 這種優(yōu)化目標(biāo)相比于傳統(tǒng)TSP更靈活，

適用性更強(qiáng)， 且能容忍一定誤差， 減少計(jì)算的復(fù)雜度.

標(biāo)準(zhǔn)CETSP模型是圓形的覆蓋區(qū)域， 但其也適應(yīng)不同形狀的覆蓋區(qū)域， 如橢圓形、 多邊形等， 這取決于實(shí)際問題的需求. 在三維空間中， 覆蓋區(qū)域可以是球體或其他三維形狀.

例如， 在無人機(jī)執(zhí)行任務(wù)時(shí)， 其信號(hào)覆蓋范圍可能是一個(gè)不規(guī)則的三維空間區(qū)域， CETSP可以對(duì)這種情況進(jìn)行建模.

CETSP和TSP的特殊性導(dǎo)致其可以獲得較短的路徑， 在許多實(shí)際應(yīng)用中更有效. 圖1為TSP訪問和CETSP訪問示意圖， 其中黑色三角形表示倉庫， 黑色節(jié)點(diǎn)是目標(biāo)及其

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

所有圓盤鄰域的半徑都為0， 則CETSP即簡化為標(biāo)準(zhǔn)TSP. CETSP是一個(gè)NP-難問題， 在計(jì)算上很難求解.

2.3 應(yīng)用場景

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

， 當(dāng)城市數(shù)量龐大時(shí)， 完全精確的路徑優(yōu)化不現(xiàn)實(shí)， 而CETSP模型可提供足夠接近的路徑解決方案; 在無人駕駛和智能交通中， 若處于動(dòng)態(tài)變化的交通環(huán)境中， 則可能不需要絕對(duì)最

優(yōu)的路徑， 而是一個(gè)足夠好的解， 能在合理的時(shí)間內(nèi)快速生成. 相比于TSP的求解必須遵循嚴(yán)格的最優(yōu)標(biāo)準(zhǔn)， 路徑誤差不可容忍， 計(jì)算結(jié)果的靈活性較低， C

ETSP則提供了一定的靈活性， 允許在一些約束條件下進(jìn)行權(quán)衡， 如時(shí)間、 計(jì)算資源、 路徑長度等， 允許在給定的誤差范圍內(nèi)找到一個(gè)接近最優(yōu)的解. 這種容錯(cuò)性使CETSP在一些現(xiàn)實(shí)場景下更具實(shí)用性.

3 CETSP模型的求解算法

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

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

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

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

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

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

Placido等［20］提出了一種有效的遺傳算法， 表明該領(lǐng)域的元啟發(fā)式方法仍有潛力， 并獲得了更多的更優(yōu)解.

由于CETSP的解空間在問題規(guī)模擴(kuò)大的過程中會(huì)呈現(xiàn)指數(shù)式增長， 精確算法難以求解， 啟發(fā)式算法相比于盲目搜索則會(huì)更有效， 因?yàn)閱l(fā)函數(shù)經(jīng)過設(shè)計(jì)修改， 一般可以在較短的時(shí)

間內(nèi)得到一個(gè)搜索問題的最優(yōu)解， 對(duì)于NP-難問題， 使用啟發(fā)式算法也可以在多項(xiàng)式時(shí)間內(nèi)得到一個(gè)當(dāng)前的最優(yōu)解， 所以目前人們更多使用啟發(fā)式算法對(duì) CETSP 進(jìn)行求解. 隨

著問題的發(fā)展， 無論是從原始的優(yōu)化推銷員路徑問題、 機(jī)器人調(diào)度問題， 還是到現(xiàn)在的無人機(jī)協(xié)同任務(wù)分配、 無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)采集、 通信網(wǎng)絡(luò)中的信號(hào)覆蓋等問題中， 雖

然由于問題變體的多樣性導(dǎo)致求解的側(cè)重點(diǎn)不同， 但都可以使用啟發(fā)式算法對(duì)其進(jìn)行求解. 本文主要圍繞啟發(fā)式算法解決CETSP展開綜述.

3.1 基于離散化的啟發(fā)式算法

離散化的啟發(fā)式算法主要是指在解決優(yōu)化問題時(shí)， 特別是在處理連續(xù)變量需要被轉(zhuǎn)化為離散變量的場景中， 采用的一些基于經(jīng)驗(yàn)和直觀構(gòu)造的算法. 這些方法在可接受的計(jì)算時(shí)間和空

間花費(fèi)下， 為組合優(yōu)化問題提供可行解， 雖然這些解可能不是最優(yōu)的， 但在實(shí)際應(yīng)用中通常能在合理的時(shí)間內(nèi)得到較好的方案.

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

型求解. 之后， 他們進(jìn)一步改進(jìn)了內(nèi)部離散化方案， 結(jié)合SOCP進(jìn)一步優(yōu)化解的質(zhì)量.

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

°， 離散化點(diǎn)均勻分布在圓周上. 在最差情況下， 即當(dāng)最優(yōu)路徑T的轉(zhuǎn)向點(diǎn)p1位于圓周上Cv某圓形弧d1，d2的中點(diǎn)時(shí)， 產(chǎn)生最大離散化誤差.

IDS方案核心也是選擇離散化點(diǎn)逼近最優(yōu)解. IDS方案同樣將每個(gè)鄰域N（v）的圓周Cv等分為k份， 但把離散化點(diǎn)放置在每個(gè)弧對(duì)應(yīng)的弦ab的中點(diǎn). 如k=3或k=4時(shí)， 離散化點(diǎn)

的分布位置會(huì)相應(yīng)改變.

這些離散化的啟發(fā)式方法通過不同的離散化策略， 在降低離散化誤差方面逐步改進(jìn)， 為計(jì)算 CETSP 的最優(yōu)解上下界提供了更有效的方法， 有助于在實(shí)際應(yīng)用中更快、 更準(zhǔn)確地找到接

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

3.2 基于Steiner-zone的啟發(fā)式算法

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

雖然找到了接近最優(yōu)的解， 但運(yùn)行時(shí)間較長. Wang等［18］在上述方法的基礎(chǔ)上， 提出了一種快速三階段啟發(fā)式算法（SZVNS）， 可在較短時(shí)間為CETSP提供高質(zhì)量解.

SZVNS通過減少問題規(guī)模、 構(gòu)建初始解并優(yōu)化解的方式高效解決CETSP. 利用Steiner區(qū)域（Steiner-zone）［22-23］化簡問題， 將CETSP轉(zhuǎn)化為標(biāo)準(zhǔn)TSP， 并通過可變鄰域搜索（

VNS）進(jìn)一步優(yōu)化， 按順序分為數(shù)據(jù)清理、 構(gòu)造初始解和解的優(yōu)化三個(gè)階段.

數(shù)據(jù)清理階段的目的是減少問題規(guī)模， 縮短運(yùn)行時(shí)間. 由于并非所有客戶都需要顯式考慮， 例如， 如果一個(gè)客戶的服務(wù)區(qū)域完全被另一個(gè)客戶的服務(wù)區(qū)域覆蓋， 則可以將該客戶

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

構(gòu)造初始解的過程需要用到Steiner-zone， 是指多個(gè)客戶服務(wù)區(qū)域（圓盤）的重疊部分. 如果一個(gè)路徑經(jīng)過某個(gè) Steiner-zone， 則該區(qū)域內(nèi)所有客戶都被服務(wù). Steiner

-zone的“度”定義為其包含的圓盤數(shù)量. 度越高， 路徑經(jīng)過該區(qū)域時(shí)服務(wù)的客戶越多， 但區(qū)域面積通常較小， 限制了選擇 Steiner點(diǎn)的靈活性.

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

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

在識(shí)別所有Steiner區(qū)域后， 通過求解集合覆蓋問題（set covering problem， SCP）， 選擇最少數(shù)量的Steiner區(qū)域覆蓋所有客戶. 從選定的Steiner區(qū)域中選擇Steiner點(diǎn)， 構(gòu)造一條可

行路徑. 使用3種規(guī)則選擇Steiner點(diǎn)， 生成3條可行路徑， 并保留其中最優(yōu)的一條作為初始解. 再在初始解的基礎(chǔ)上， 通過多種鄰域操作進(jìn)一步優(yōu)化路徑長度.

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

計(jì)算過程中復(fù)雜度較高， 尤其是在處理復(fù)雜實(shí)例時(shí)， 由于對(duì)初始解的質(zhì)量依賴較大， 且Steiner區(qū)域最大度數(shù)限制為3， 可能會(huì)錯(cuò)過一些高質(zhì)量解.

3.3 基于粒子群優(yōu)化算法的方法

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

的核心思想是個(gè)體通過局部的信息交流（如通過位置、 速度等方式）協(xié)調(diào)行動(dòng)， 以實(shí)現(xiàn)全局目標(biāo)的最優(yōu)化.

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

， 并結(jié)合K-means聚類［26］初始化種群. GA的核心操作包括選擇、 交叉和變異， 并結(jié)合局部搜索和數(shù)學(xué)優(yōu)化方法進(jìn)一步改進(jìn)解.

與大部分算法相同［27-28］， 為減少問題規(guī)模， GA同樣在正式求解前需進(jìn)行預(yù)處理， 移除在覆蓋其他目標(biāo)時(shí)會(huì)被自動(dòng)覆蓋的目標(biāo)節(jié)點(diǎn). 主要包括以下兩部分： 如果一個(gè)目標(biāo)節(jié)點(diǎn)的鄰域

完全包含在另一個(gè)目標(biāo)節(jié)點(diǎn)的鄰域中， 則可以移除前者； 如果一個(gè)目標(biāo)節(jié)點(diǎn)的鄰域與其他多個(gè)目標(biāo)節(jié)點(diǎn)的鄰域重疊， 并且這些重疊區(qū)域已經(jīng)被覆蓋， 則可以移除該目標(biāo)節(jié)點(diǎn). 通過這些

預(yù)處理步驟， 可顯著減少問題規(guī)模， 提高算法效率.

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

的基因表示目標(biāo)節(jié)點(diǎn)的訪問順序. 適應(yīng)度函數(shù)用于評(píng)估每個(gè)染色體的質(zhì)量， 目標(biāo)是最小化路徑長度. 路徑長度的計(jì)算考慮了目標(biāo)節(jié)點(diǎn)的鄰域覆蓋特性. 使用基于適應(yīng)度的選擇機(jī)制（如

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

的解. 隨機(jī)改變?nèi)旧w中的基因順序， 以增加種群的多樣性， 避免陷入局部最優(yōu). 變異操作可能包括交換兩個(gè)基因的位置或隨機(jī)調(diào)整訪問順序. 每次生成或修改染色體后， 調(diào)用改進(jìn)操

作對(duì)解進(jìn)行局部優(yōu)化. 最后對(duì)解進(jìn)行優(yōu)化， 包括2-opt局部搜索、 SOCP和3Alg算法3種. 2-opt局部搜索是交換兩個(gè)節(jié)點(diǎn)順序以優(yōu)化路徑順序， 減少路徑長度. SOCP是在固定訪問順

序的情況下， 通過數(shù)學(xué)優(yōu)化調(diào)整路徑中的轉(zhuǎn)折點(diǎn)位置， 進(jìn)一步縮短路徑. 3Alg算法是基于貪心策略調(diào)整轉(zhuǎn)折點(diǎn)位置， 作為SOCP的快速替代方法. 由于SOCP求解耗時(shí)較長， 算法僅對(duì)種群中的

隨機(jī)個(gè)體應(yīng)用SOCP， 剩余節(jié)點(diǎn)使用3Alg算法.

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

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

3.4 基于貪心算法的啟發(fā)式方法

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

單直觀， 易于實(shí)現(xiàn)， 計(jì)算速度相對(duì)較快. 在處理小規(guī)模問題或?qū)獾木纫蟛桓叩那闆r下， 能快速得到一個(gè)可行的旅行路線. 但貪心算法并不能總是得到全局最優(yōu)解， 它易陷

入局部最優(yōu)解. 由于它只考慮當(dāng)前的最優(yōu)選擇， 而未考慮后續(xù)步驟的影響， 可能會(huì)錯(cuò)過全局最優(yōu)的路徑. 特別是在復(fù)雜的旅行商問題中， 城市之間的距離關(guān)系復(fù)雜， 貪心算法得到的

解可能與最優(yōu)解相差較大.

在實(shí)際應(yīng)用中， 傳統(tǒng)貪心算法雖然不能保證得到最優(yōu)解， 但仍具有一定的實(shí)用價(jià)值. 例如， 在對(duì)實(shí)時(shí)性要求較高的場景中， 需要快速得到一個(gè)可行的旅行路線， 貪心算

法可作為一種初步的解決方案， 然后在此基礎(chǔ)上進(jìn)一步優(yōu)化或調(diào)整.

CG（carousel greedy）算法［19］結(jié)合離散化方案， 通過貪心策略［30］快速生成可行解， 并在后續(xù)階段優(yōu)化路徑. CG算法的設(shè)計(jì)理念是設(shè)計(jì)一種通用

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

擴(kuò)展解空間， 比傳統(tǒng)貪心算法的準(zhǔn)確性更高， 并具有比元啟發(fā)式算法（如模擬退火、 禁忌搜索等）更簡單的結(jié)構(gòu).

CG算法是一種構(gòu)造性啟發(fā)式算法， 通過引入兩個(gè)參數(shù)（α和β）， 在構(gòu)造解的過程中動(dòng)態(tài)調(diào)整部分解， 從而探索更多可能的解， 并通過多次迭代調(diào)整， CG算法可修正傳統(tǒng)貪心算法

中早期選擇的錯(cuò)誤. 與元啟發(fā)式算法不同， CG算法只生成一個(gè)最終可行解， 而不是在多個(gè)解之間迭代優(yōu)化. 通過多次調(diào)整部分解， CG算法能修正早期選擇中的錯(cuò)誤.

CG算法的執(zhí)行過程可分為3個(gè)階段： 首先， 使用傳統(tǒng)貪心算法生成一個(gè)初始部分解; 其次， 通過多次迭代調(diào)整部分解， 延長解的構(gòu)造過程， 在每次迭代中， 都移除部分解中的某些元素（由參數(shù)

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

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

提升了解的質(zhì)量. 與其他元啟發(fā)式算法（如模擬退火、 禁忌搜索、 蟻群優(yōu)化算法）相比， CG算法的運(yùn)行時(shí)間較少， 尤其適合處理大規(guī)模問題. 文獻(xiàn)［19］還將CG算法應(yīng)用于多個(gè)經(jīng)典的組

合優(yōu)化問題中， 如最小標(biāo)號(hào)生成樹， 最小頂點(diǎn)覆蓋問題等.

實(shí)驗(yàn)結(jié)果表明， CG算法在解的質(zhì)量上優(yōu)于傳統(tǒng)貪心算法， 并在某些情況下接近甚至超過元啟發(fā)式算

法， 且CG算法的運(yùn)行時(shí)間顯著低于元啟發(fā)式算法， 尤其在大規(guī)模問題上表現(xiàn)出色. 但由于貪心策略可能導(dǎo)致局部最優(yōu)， 在復(fù)雜實(shí)例的實(shí)驗(yàn)上可能導(dǎo)致適應(yīng)性較差.

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

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

上界或下界， 以估計(jì)子問題的最優(yōu)解（定界）. 根據(jù)這個(gè)界限判斷是否繼續(xù)深入搜索或剪枝. 如果子問題的界限無法比當(dāng)前最優(yōu)解更好（即該解不可能超過或達(dá)到當(dāng)前的最優(yōu)解），

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

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

賴于問題的規(guī)模和分支界定的設(shè)計(jì)， 在處理大規(guī)模問題時(shí)仍會(huì)面臨時(shí)間和空間復(fù)雜度過高的問題.

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

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

覆蓋所有頂點(diǎn)， 則將當(dāng)前路徑長度作為下界， 并將其加入搜索樹作為根節(jié)點(diǎn).

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

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

序列從搜索樹中移除. 在搜索中使用循環(huán)最佳優(yōu)先搜索（CBFS-CV）策略選擇下一個(gè)要探索的節(jié)點(diǎn)， CBFS-CV策略通過維護(hù)一組有序且標(biāo)記的輪廓， 以指導(dǎo)搜索過程，

每個(gè)輪廓包含一組未探索的搜索樹節(jié)點(diǎn). 由于通過假設(shè)遠(yuǎn)離插入位置的頂點(diǎn)覆蓋狀態(tài)不會(huì)改變， 所以可以減少頂點(diǎn)覆蓋檢查的數(shù)量， 從而減少不必要的計(jì)算. 基于

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

探索節(jié)點(diǎn)的數(shù)量， 通過在短暫的搜索中探索子樹， 并在必要時(shí)將未探索的節(jié)點(diǎn)重新插入搜索樹. 持續(xù)搜索直到到達(dá)預(yù)設(shè)的時(shí)間和空間限制， 得到目前的最優(yōu)解.

4 CETSP應(yīng)用領(lǐng)域

4.1 物流配送

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

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

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

對(duì)電商企業(yè)的倉儲(chǔ)中心到多個(gè)零售點(diǎn)的貨物運(yùn)輸， CETSP模型有助于確定最佳的配送順序和路徑， 使貨物能及時(shí)、 高效地到達(dá)各零售點(diǎn)， 同時(shí)減少車輛的空載里程和能源消耗.

在冷鏈物流網(wǎng)絡(luò)中， 涉及到易腐貨物的運(yùn)輸， 如生鮮食品、 藥品等. CETSP模型可用于構(gòu)建具有無人機(jī)運(yùn)輸功能的新型預(yù)冷站， 解決根據(jù)各產(chǎn)地日產(chǎn)量的運(yùn)輸方式選擇及新型預(yù)冷站當(dāng)

日無人機(jī)和卡車的運(yùn)輸能力分配等問題. 例如， 在水果產(chǎn)地， 根據(jù)果園的分布情況（視為客戶點(diǎn)）， 利用CETSP模型確定無人機(jī)和卡車的最優(yōu)運(yùn)輸路線， 將采摘的水果快速運(yùn)輸?shù)筋A(yù)冷

站， 保證水果的新鮮度， 同時(shí)提高冷鏈物流網(wǎng)絡(luò)的運(yùn)行效率， 減少資源浪費(fèi).

4.2 工業(yè)制造

在電子電路設(shè)計(jì)中， 需要在電路板上布置各種電子元件并連接它們的線路. CETSP模型可以確定線路的最佳布局， 將電子元件視為客戶點(diǎn)， 線路需要經(jīng)過元件周圍的一定區(qū)域（覆

蓋區(qū)域）. 通過優(yōu)化線路路徑， 減少線路長度， 不僅可以降低生產(chǎn)成本（減少材料使用）， 還能減少信號(hào)傳輸延遲和干擾， 提高電路的性能和可靠性. 例如， 在高密度電路板設(shè)計(jì)中，

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

在工廠中， 有大量的生產(chǎn)設(shè)備需要定期巡檢維護(hù). 將每臺(tái)設(shè)備視為一個(gè)客戶點(diǎn)， 設(shè)備周圍的可操作區(qū)域視為覆蓋區(qū)域， CETSP模型可用于規(guī)劃巡檢人員或巡檢機(jī)器人的最優(yōu)巡檢路徑.

從而確保設(shè)備得到及時(shí)檢查， 同時(shí)減少巡檢時(shí)間和人力成本， 提高生產(chǎn)設(shè)備的維護(hù)效率， 保障生產(chǎn)線的正常運(yùn)行.

4.3 交通規(guī)劃

在城市公共交通系統(tǒng)中， 公交車或地鐵的線路規(guī)劃可以借助CETSP模型. 以公交站點(diǎn)為客戶點(diǎn)， 站點(diǎn)周圍一定范圍為覆蓋區(qū)域， 優(yōu)化公交車輛的行駛路線， 使乘客能在站點(diǎn)附近方便

地上下車， 同時(shí)提高公交車輛的運(yùn)行效率， 減少乘客的候車時(shí)間和出行成本. 例如， 在設(shè)計(jì)新的公交線路時(shí)， 考慮如何以最短的路徑連接多個(gè)站點(diǎn)覆蓋區(qū)域， 滿足居民的出行需求.

對(duì)于智能交通系統(tǒng)中的出租車調(diào)度， CETSP模型可以幫助確定出租車在接送乘客時(shí)的最優(yōu)行駛路徑， 提高出租車的運(yùn)營效率， 減少空駛里程， 降低能源消耗， 同時(shí)也為乘客提供更快捷的服務(wù).

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

為覆蓋區(qū)域， 通過優(yōu)化設(shè)備布局， 以最少的設(shè)備數(shù)量實(shí)現(xiàn)對(duì)交通狀況的全面監(jiān)測和有效控制， 提高智能交通系統(tǒng)的性能.

4.4 信息通訊

在無線網(wǎng)絡(luò)建設(shè)中， 基站的布局對(duì)信號(hào)覆蓋和通信質(zhì)量至關(guān)重要. 將需要覆蓋的區(qū)域劃分為多個(gè)客戶點(diǎn)及其覆蓋區(qū)域， CETSP模型可用于確定基站的最佳位置， 使基站能以最少的

數(shù)量實(shí)現(xiàn)對(duì)目標(biāo)區(qū)域的有效覆蓋， 同時(shí)減少信號(hào)干擾， 提高網(wǎng)絡(luò)通信質(zhì)量， 降低建設(shè)成本. 例如， 在城市中規(guī)劃移動(dòng)通信基站的布局， 確保各區(qū)域都能獲得良好的信號(hào)服務(wù).

在無線傳感器網(wǎng)絡(luò)中， 傳感器節(jié)點(diǎn)分布在監(jiān)測區(qū)域內(nèi)［34］， 數(shù)據(jù)采集設(shè)備（如移動(dòng)數(shù)據(jù)采集器或無人機(jī)）需要定期收集傳感器數(shù)據(jù). 將傳感器節(jié)點(diǎn)視為客戶點(diǎn)， 數(shù)據(jù)采集設(shè)備能與傳感器

通信的有效范圍作為覆蓋區(qū)域， CETSP模型可以幫助規(guī)劃數(shù)據(jù)采集設(shè)備的最優(yōu)路徑， 提高數(shù)據(jù)采集效率， 延長傳感器網(wǎng)絡(luò)的使用壽命， 降低數(shù)據(jù)采集成本. 例如， 在環(huán)境監(jiān)測傳感器網(wǎng)

絡(luò)中， 無人機(jī)按CETSP模型規(guī)劃的路徑采集各傳感器節(jié)點(diǎn)的數(shù)據(jù)， 實(shí)現(xiàn)對(duì)環(huán)境參數(shù)的實(shí)時(shí)監(jiān)測.

隨著技術(shù)的不斷進(jìn)步和發(fā)展， CETSP模型的應(yīng)用領(lǐng)域還將不斷拓展， 為解決各種實(shí)際優(yōu)化問題提供更有效的解決方案.

5 未來研究方向

CETSP是TSP的一種變體和推廣， TSP是經(jīng)典的組合優(yōu)化問題， 而CETSP在TSP的基礎(chǔ)上擴(kuò)展了訪問區(qū)域， 將訪問目標(biāo)從精確位置擴(kuò)展到一定的鄰域范圍， 提升了解決問題的靈活性. 這種

拓展豐富了組合優(yōu)化問題的類型， 為理論研究提供了新的方向和思路. 作為NP-難問題， CETSP的研究有助于推動(dòng)NP-難問題的研究與發(fā)展， 其復(fù)雜的解空間結(jié)構(gòu)和較高的求解難度，

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

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

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

. 這種算法主要關(guān)注優(yōu)化路徑長度， 未來研究還可以考慮其他可能的優(yōu)化目標(biāo)， 如路徑平滑性等.

三段式啟發(fā)式算法（如SZVNS）結(jié)合了數(shù)據(jù)清理、 初始解構(gòu)建和解的優(yōu)化等方法， 利用Steiner-zone化簡問題， 這種多階段的算法設(shè)計(jì)理念和對(duì)Steiner-zone的利用， 豐富了啟發(fā)式算

法的設(shè)計(jì)方案. 但該方案仍需進(jìn)行優(yōu)化， 例如， 由于剪枝算法的原理導(dǎo)致當(dāng)客戶半徑均勻的

情況下， 沒有客戶可以被修剪， 此時(shí)數(shù)據(jù)清理的效果較差. 未來研究可以考慮與機(jī)器學(xué)習(xí)技術(shù)相結(jié)合， 使用強(qiáng)化學(xué)習(xí)優(yōu)化耗時(shí)較長的VNS搜索策略， 動(dòng)態(tài)調(diào)整搜索順序或操作參數(shù).

基于粒子群的優(yōu)化算法在CETSP求解中通過結(jié)合局部搜索和數(shù)學(xué)優(yōu)化方法， 展示了如何在復(fù)雜的組合優(yōu)化問題中利用種群進(jìn)化和局部改進(jìn)提高解的質(zhì)量， 推動(dòng)了遺傳

算法等粒子群優(yōu)化算法的進(jìn)一步發(fā)展. 在現(xiàn)有研究中， 雖然GA在大多數(shù)實(shí)例上可以找到高質(zhì)量的解， 但在某些情況下， 其計(jì)算時(shí)間明顯高于其他啟發(fā)式算法， 如在變動(dòng)重疊率實(shí)例中，

GA的計(jì)算時(shí)間長于SZVNS， 未來研究仍應(yīng)在改進(jìn)算法效率方面進(jìn)行探索.

基于貪心算法的啟發(fā)式方法（如CG算法）， 通過引入?yún)?shù)動(dòng)態(tài)調(diào)整部分解， 拓展了解空間， 為貪心算法在復(fù)雜問題中的有效應(yīng)用提供了新的范例， 也啟發(fā)了更多對(duì)傳統(tǒng)簡單算法進(jìn)行

改進(jìn)以適應(yīng)復(fù)雜組合優(yōu)化問題的研究. 然而對(duì)于CG算法中的兩個(gè)關(guān)鍵參數(shù)α和β， 目前雖然有對(duì)其使用的推薦范圍， 但仍需針對(duì)具體問題進(jìn)行調(diào)優(yōu)， 缺乏自動(dòng)化， 且不同問題的

最佳參數(shù)組合差異較大， 增加了算法的使用難度. 未來研究可以考慮引入自動(dòng)化參數(shù)調(diào)優(yōu)技術(shù)， 以減少人工干預(yù)提高適用性. 由于CG算法的設(shè)計(jì)目標(biāo)是生成單一解， 因此會(huì)限制解空間

的探索深度， 尤其是在解空間復(fù)雜和局部最優(yōu)較多的問題中， 可以擴(kuò)展CG的框架， 生成多個(gè)可行解， 如在每次迭代中記錄多個(gè)部分解， 并對(duì)這些部分解進(jìn)行進(jìn)一步優(yōu)化.

目前對(duì)CETSP的研究取得了許多成果， 但不同算法仍在不同方面（如計(jì)算效率、 調(diào)整局部最優(yōu)、 種群多樣性維護(hù)和實(shí)際應(yīng)用普適性等）存在不足. 未來研究仍可針對(duì)

這些問題進(jìn)行改進(jìn)， 通過進(jìn)一步優(yōu)化不同算法的各組件和機(jī)制， 提高其在不同問題實(shí)例上的性能和應(yīng)用廣泛性. 未來研究可以測試不同算法在不同問題規(guī)模、 復(fù)雜度和多樣性

上的性能， 以評(píng)估其魯棒性和適應(yīng)性， 也可以考慮加入一些抗噪聲的機(jī)制， 以應(yīng)對(duì)實(shí)際應(yīng)用中的不確定性.

CETSP研究推動(dòng)了智能化決策與自動(dòng)化操作的發(fā)展， 在面對(duì)大規(guī)模、 復(fù)雜的任務(wù)分配和路徑規(guī)劃時(shí)， CETSP為相關(guān)算法和智能系統(tǒng)提供了有效的模型基礎(chǔ)， 使無人機(jī)、 機(jī)器人等自動(dòng)化

設(shè)備能根據(jù)該模型更智能地規(guī)劃任務(wù)路線， 提高自動(dòng)化作業(yè)的效率和精準(zhǔn)度， 為實(shí)現(xiàn)智能化的生產(chǎn)、 配送、 監(jiān)測等多領(lǐng)域的運(yùn)作奠定了基礎(chǔ).

參考文獻(xiàn)

［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.

（責(zé)任編輯：" 韓 嘯）