一種大規(guī)模稀疏中國(guó)郵遞員問題快速求解方法

唐繼州　何麗莉　白洪濤

摘要： 針對(duì)現(xiàn)有中國(guó)郵遞員問題求解方法在大規(guī)模稀疏路網(wǎng)圖上求解效率的瓶頸， 提出一種在可接受時(shí)間范圍內(nèi)求得可行解的基于蟻群優(yōu)化的快速求解方法. 該方法針對(duì)Euler回路求解的奇偶點(diǎn)圖上作業(yè)法的第二階段， 采用蟻群算法進(jìn)行求解， 同時(shí)根據(jù)大規(guī)模稀疏路網(wǎng)圖的特性基于密度峰值聚類算法對(duì)方法進(jìn)行改進(jìn)： 首先在蟻群算法求解前對(duì)大規(guī)模稀疏路網(wǎng)圖進(jìn)行聚類分割； 其次根據(jù)鄰近節(jié)點(diǎn)覆蓋率對(duì)分割后的節(jié)點(diǎn)群進(jìn)行合并; 最后通過改變部分節(jié)點(diǎn)所屬聚類使各節(jié)點(diǎn)群內(nèi)部節(jié)點(diǎn)個(gè)數(shù)均為偶數(shù). 實(shí)驗(yàn)結(jié)果表明： 在奇偶點(diǎn)圖上作業(yè)法所能支持的節(jié)點(diǎn)規(guī)模下， 該方法可求得與確定性算法相同的最優(yōu)解， 并在運(yùn)算時(shí)間上達(dá)到約10倍的效率優(yōu)化； 且該方法在大規(guī)模稀疏路網(wǎng)圖下可有效提高計(jì)算效率， 并在可控時(shí)間范圍內(nèi)得到優(yōu)化的可行解， 針對(duì)5 000個(gè)節(jié)點(diǎn)規(guī)模的路網(wǎng)圖最快可在60 s內(nèi)完成求解.

關(guān)鍵詞： 中國(guó)郵遞員問題； 蟻群優(yōu)化； 密度峰值聚類； Euler圖

中圖分類號(hào)： TP391文獻(xiàn)標(biāo)志碼： A文章編號(hào)： 1671-5489（2024）02-0311-09

A Fast Solution Method for Large-ScaleSparse Chinese Postman Problem

TANG Jizhou， HE Lili， BAI Hongtao

（College of Computer Science and Technology， Jilin University， Changchun 130012， China）3）.

Abstract： Aiming at the bottleneck of solving efficiency of existing Chinese postman problem solving methods on large-scale sparse road network graph， we proposed a fast solution method based on ant colony optimization to obtain feasible solutions in an acceptable time range. This method used ant colony algorithms to solve the second stage of the odd even point graph operation method for Eulers loop solution. At the same time， we improved the method based on density peak clustering algorithm according to the characteristics of large-scale sparse road network graph. Firstly， we clustered and segmented the large-scale sparse road network graph before using the ant colony algorithm to solve the problem. Secondly， we merged the segmented node groups according to the coverage of adjacent nodes. Finally， by changing the clustering of some nodes， the number of internal nodes in each node group was even. The experimental results show that： under the node size supported by the homework method on the odd even point graph， the proposed method can obtain the same optimal solution as the deterministic algorithm and achieve the efficiency optimization of about 10 times in the operation time. The proposed method can effectively improve computational efficiency in large-scale sparse road network graphs and obtain optimized feasible solutions within a controllable time range. When facing road network graphs with a scale of 5 000 nodes， the fastest solution can be completed within 60 s.

Keywords： Chinese postmen problem; ant colony optimization; density peak clustering; Euler diagram

中國(guó)郵遞員問題（Chinese postman problem， CPP）也稱為弧路由問題（arc routing problem， ARP）， 是一個(gè)經(jīng)典的組合優(yōu)化問題， 可描述為尋找一條從給定起點(diǎn)出發(fā)， 遍歷路網(wǎng)圖上的所有邊， 然后回到起點(diǎn)， 使總開銷最小的路徑. 該問題應(yīng)用廣泛， 如郵遞員送信、 道路勘探、 警察巡邏［1］、 垃圾車收集垃圾、 掃雪車清掃街道［2］、 街景圖攝制等［3］. 這類問題從目的和效率方面均需一條從某一起點(diǎn)出發(fā)， 遍歷區(qū)域中所有邊， 最后回到起點(diǎn)的最短路徑.

CPP問題求解的傳統(tǒng)方法以管梅谷［4］提出的奇偶點(diǎn)圖上作業(yè)法為代表， 其核心思想為在原圖上添加重復(fù)邊消除奇數(shù)度節(jié)點(diǎn). 針對(duì)該方法第二步中最優(yōu)重復(fù)邊添加方案的尋找， Edmonds等［5］進(jìn)一步提出了一般圖上的最大權(quán)匹配算法， 通過不斷尋找增廣路徑找出一個(gè)確定的最大匹配， 得到最優(yōu)解. 近年來(lái)已提出了多種采用啟發(fā)式方法求解CPP問題的方案： 文獻(xiàn)［6］利用Shin等［7］的編碼方案對(duì)實(shí)數(shù)進(jìn)行編碼， 采用分子規(guī)劃的算法以及遺傳算法進(jìn)行求解； Ralphs［8］針對(duì)遺傳算法求解中國(guó)郵遞員問題的局限性， 提出了一種邊權(quán)動(dòng)態(tài)混合的求解方案; 于紅斌等［9］引入螞蟻算法， 通過隨機(jī)概率選擇出行方向和最短路線激勵(lì)策略， 改善了常規(guī)情況下先進(jìn)行奇點(diǎn)匹配再求回路的兩步求解法， 使得在設(shè)定目標(biāo)的約束下可直接求出最優(yōu)解. 目前的工作大多數(shù)在節(jié)點(diǎn)數(shù)量最多只有幾百的規(guī)模下進(jìn)行. 傳統(tǒng)方法在路網(wǎng)圖規(guī)模較小的情況下可得到最優(yōu)路徑. 隨著路網(wǎng)規(guī)模的擴(kuò)大， 節(jié)點(diǎn)數(shù)量快速增長(zhǎng)， 求解時(shí)間呈指數(shù)級(jí)增長(zhǎng)， 通常需要數(shù)小時(shí)， 甚至數(shù)天， 難以滿足工作的時(shí)效性需求. 啟發(fā)式方法可有效縮短求解時(shí)長(zhǎng)， 得到滿足要求的可行解， 但隨著路網(wǎng)規(guī)模的增大， 可行解與最優(yōu)解的偏差也隨之增加.

針對(duì)現(xiàn)有工作在大規(guī)模路網(wǎng)下求解問題的瓶頸， 本文基于奇偶點(diǎn)圖上作業(yè)法提出一種結(jié)合分治與啟發(fā)式思想的中國(guó)郵遞員問題快速求解方法（fast solution method for large scale sparse Chinese postal problem method， FS-LSSCPP）. 對(duì)于大規(guī)模路網(wǎng)存在的稀疏特性， 該方法采用分治思想， 將大規(guī)模節(jié)點(diǎn)群分割為多個(gè)小規(guī)模節(jié)點(diǎn)群［10］， 以降低每個(gè)節(jié)點(diǎn)群內(nèi)部的計(jì)算規(guī)模， 減少搜索空間， 降低偏差； 并采用啟發(fā)式算法降低每個(gè)小規(guī)模節(jié)點(diǎn)群內(nèi)部的求解時(shí)長(zhǎng)， 從而降低有效可行解的求解時(shí)間.

2 FS-LSSCPP方法框架

2.1 基本思想

針對(duì)給定路網(wǎng)圖G上由奇數(shù)度節(jié)點(diǎn)形成的無(wú)向完全圖Gc， FS-LSSCPP求解最短匹配邊集的基本方法如下， 流程如圖2所示.

1） 采用密度峰值聚類方法對(duì)奇數(shù)度節(jié)點(diǎn)群進(jìn)行聚類分割， 形成多個(gè)子節(jié)點(diǎn)群Vc.

2） 通過計(jì)算Vc中各子節(jié)點(diǎn)群自身鄰近節(jié)點(diǎn)覆蓋率， 以覆蓋率閾值為標(biāo)準(zhǔn)， 合并相關(guān)節(jié)點(diǎn)群， 形成多個(gè)合并后的子節(jié)點(diǎn)群Vm.

3） 計(jì)算Vm中節(jié)點(diǎn)個(gè)數(shù)為奇數(shù)的節(jié)點(diǎn)群之間的最小權(quán)完美匹配， 并修改邊界節(jié)點(diǎn)所屬的類歸屬， 形成節(jié)點(diǎn)個(gè)數(shù)均為偶數(shù)的多個(gè)子節(jié)點(diǎn)群Vp.

4） 在Vp中各節(jié)點(diǎn)群中分別使用蟻群算法求得各節(jié)點(diǎn)群的最短匹配邊集E′.

后續(xù)根據(jù)各節(jié)點(diǎn)群的最短匹配邊集E′在原路圖上添加重復(fù)邊， 形成Euler圖G*， 可使用Fleury算法在G*中得到從任意起點(diǎn)開始的Euler回路.

2.2 奇數(shù)度節(jié)點(diǎn)群密度峰值聚類

為有效且合理地縮小每個(gè)節(jié)點(diǎn)群的規(guī)模， 本文采用密度峰值聚類算法對(duì)節(jié)點(diǎn)群進(jìn)行分割. 密度峰值聚類的流程如圖3所示.

為直觀地根據(jù)局部密度ρi和相對(duì)距離δi判斷聚類中心， 使用決策值γi對(duì)兩者進(jìn)行結(jié)合， 定義為γi=ρi-ρmin/ρmax-ρmin×δi-δmin/δmax-δmin，（3）其中ρmax，ρmin分別為所有節(jié)點(diǎn)局部密度的最大值和最小值， δmax，δmin分別為所有節(jié)點(diǎn)相對(duì)距離的最大值和最小值.

決策值γi可直觀地看到每個(gè)節(jié)點(diǎn)作為聚類中心的特征情況， 但原始密度峰值聚類算法并未給出自動(dòng)選擇相關(guān)聚類中心的方法， 而是根據(jù)決策圖人工選擇， 引入了一定的主觀性和不確定性. 基于此， FS-LSSCPP方法將同時(shí)使用決策值閾值γthreshold和最大決策值鄰近差γdmax自動(dòng)選擇聚類中心， 以提高算法的可用性. 對(duì)決策值γi由大到小排序后， 自動(dòng)選擇聚類中心的流程如下：

1） 使用決策值閾值確定聚類中心集合CP1={V1，V2，…，Vi}， 根據(jù)排序后的決策值γ序列， 由前向后選擇決策值γ超過決策值閾值γthreshold的節(jié)點(diǎn)作為聚類中心集合CP1， 一般閾值為0.5；

2） 使用最大決策值鄰近差確定聚類中心集合CP2={V1，V2，…，Vj}， 根據(jù)排序后的決策值γ序列， 由前向后選擇具有最大決策值鄰近差γdmax的節(jié)點(diǎn)與其之前的所有節(jié)點(diǎn)作為聚類中心集合CP2， 最大決策值鄰近差γdmax定義為γdmax=max{i≥1}∩{i≤N-1}（γi+1-γi-1），（4）其表示節(jié)點(diǎn)處的決策值變化趨勢(shì).

兩種選擇聚類中心的方法均對(duì)同一有序中心點(diǎn)序列進(jìn)行順序操作， 因此CP1和CP2具有包含關(guān)系. 選擇CP1和CP2中節(jié)點(diǎn)數(shù)量較多的集合作為選定的聚類中心集合， 其余節(jié)點(diǎn)按相對(duì)聚類中心點(diǎn)的距離進(jìn)行聚類， 形成Num個(gè)子節(jié)點(diǎn)群Vc={C1，C2，…，CNum}.

2.3 子節(jié)點(diǎn)群合并

最短匹配邊集的有效性與子節(jié)點(diǎn)群包含的鄰近節(jié)點(diǎn)數(shù)量有關(guān). 子節(jié)點(diǎn)群內(nèi)鄰近節(jié)點(diǎn)數(shù)量過少會(huì)導(dǎo)致節(jié)點(diǎn)匹配的選擇范圍減小， 從而大概率增加Euler回路路徑長(zhǎng)度［15］， 為有效提高最短匹配邊集的有效性， 本文采用子節(jié)點(diǎn)群合并提高節(jié)點(diǎn)群中鄰近節(jié)點(diǎn)的個(gè)數(shù).

2.3.1 相關(guān)定義

子節(jié)點(diǎn)群合并的參考標(biāo)準(zhǔn)， 鄰近節(jié)點(diǎn)集合覆蓋率閾值與子節(jié)點(diǎn)群數(shù)量滿足如下關(guān)系時(shí)最短匹配邊集可用性較好：thresholdcov=1/eNum/10，（6）其中thresholdcov為鄰近節(jié)點(diǎn)集合覆蓋率閾值， Num為聚類個(gè)數(shù).

子節(jié)點(diǎn)群合并目標(biāo)是使各子節(jié)點(diǎn)群自身鄰近節(jié)點(diǎn)集合覆蓋率均超過鄰近節(jié)點(diǎn)集合覆蓋率閾值. 子節(jié)點(diǎn)群內(nèi)鄰近節(jié)點(diǎn)數(shù)量m的選取與路網(wǎng)圖中總奇數(shù)度節(jié)點(diǎn)的數(shù)量有關(guān)， 一般為總奇數(shù)度節(jié)點(diǎn)數(shù)量的1%［16］； 不同的子節(jié)點(diǎn)群個(gè)數(shù)會(huì)影響覆蓋率閾值的大小， 較少的子節(jié)點(diǎn)群數(shù)量， 節(jié)點(diǎn)分布相對(duì)集中， 需要較高的鄰近節(jié)點(diǎn)覆蓋率閾值才可保證最短匹配邊集的可用性； 若子節(jié)點(diǎn)群個(gè)數(shù)很多， 則節(jié)點(diǎn)分布相對(duì)分散， 每個(gè)子節(jié)點(diǎn)群內(nèi)部節(jié)點(diǎn)較少， 鄰近節(jié)點(diǎn)覆蓋率閾值要求應(yīng)適當(dāng)降低.

2.3.2 子節(jié)點(diǎn)群合并

子節(jié)點(diǎn)群合并流程如下：

1） 計(jì)算Vc中各子節(jié)點(diǎn)群鄰近節(jié)點(diǎn)集合和鄰近節(jié)點(diǎn)覆蓋率；

2） 合并Vc中相關(guān)子節(jié)點(diǎn)群， 直到各子節(jié)點(diǎn)群鄰近節(jié)點(diǎn)覆蓋率均滿足鄰近節(jié)點(diǎn)覆蓋率閾值.

設(shè)合并后的子節(jié)點(diǎn)群數(shù)量為n個(gè)， 合并后的子節(jié)點(diǎn)群記為Vm， 合并流程如下：

2.4 子節(jié)點(diǎn)群節(jié)點(diǎn)數(shù)量偶數(shù)化

Vm中各子節(jié)點(diǎn)群內(nèi)部節(jié)點(diǎn)個(gè)數(shù)可能為奇數(shù)， 而最短匹配邊集E′的尋找要求集合的節(jié)點(diǎn)個(gè)數(shù)為偶數(shù)， 故需對(duì)節(jié)點(diǎn)個(gè)數(shù)為奇數(shù)的節(jié)點(diǎn)群進(jìn)行偶數(shù)化處理才可進(jìn)行后續(xù)的匹配操作.

群節(jié)點(diǎn)數(shù)量偶數(shù)化的過程如下： 首先確定所有節(jié)點(diǎn)數(shù)量為奇數(shù)的子節(jié)點(diǎn)群的中心節(jié)點(diǎn); 然后確定群中心點(diǎn)之間的最小權(quán)完美匹配集合； 最后在具有匹配關(guān)系的兩個(gè)節(jié)點(diǎn)群之間， 選擇一個(gè)邊界節(jié)點(diǎn)進(jìn)行群間移動(dòng). 邊界節(jié)點(diǎn)是指具有匹配關(guān)系的兩個(gè)節(jié)點(diǎn)群中， 與兩個(gè)群中心點(diǎn)的距離差值最小的節(jié)點(diǎn). 由于奇數(shù)度節(jié)點(diǎn)群的數(shù)量為偶數(shù)， 所以調(diào)整后的子節(jié)點(diǎn)群節(jié)點(diǎn)數(shù)量均為偶數(shù). 子節(jié)點(diǎn)群節(jié)點(diǎn)數(shù)量偶數(shù)化流程如下.

程序2

子節(jié)點(diǎn)群節(jié)點(diǎn)數(shù)量偶數(shù)化流程.

輸入： 子節(jié)點(diǎn)群Vm={C1，C2，…，Cn};

輸出： 子節(jié)點(diǎn)群Vp={C1，C2，…，Cn};

1） 使用蟻群算法求Vm各子節(jié)點(diǎn)群中心節(jié)點(diǎn)間最小權(quán)完美匹配Em

2） for i in Em do

3）取出i邊對(duì)應(yīng)的Vm中的子節(jié)點(diǎn)群Ca，Cb

4）for j in Ca or Cb do

5）

計(jì)算Lja和Ljb（j點(diǎn)到Ca，Cb中心的距離）

6）

找出具有min（Lja-Ljb）的節(jié)點(diǎn)j（即邊界節(jié)點(diǎn)）

7）end for

8）if j∈Ca then

9）

修改j所屬→jCa， j∈Cb

10）else if j∈Cb then

11）

修改j所屬→jCb， j∈Ca

12）end if

13） end for

14） 合并后子節(jié)點(diǎn)群為Vp.

確立奇數(shù)度節(jié)點(diǎn)群中心點(diǎn)之間的最小權(quán)完美匹配集合的方法有很多， 如果節(jié)點(diǎn)數(shù)量較多， 可采用類似蟻群算法實(shí)現(xiàn). 群節(jié)點(diǎn)數(shù)量偶數(shù)化的流程如圖4所示.

2.5 基于蟻群算法求解子節(jié)點(diǎn)群內(nèi)最短匹配邊集

2.5.1 蟻群算法整體思路

為保證構(gòu)造出的Euler圖總路徑長(zhǎng)度最短， 同時(shí)提高求解速率， 本文應(yīng)采用相關(guān)啟發(fā)式方法進(jìn)行求解. 最短匹配邊集的求解可視為尋找最短路徑， 為同時(shí)滿足上述需求， 本文采用蟻群算法求解各子節(jié)點(diǎn)群Vp內(nèi)部最短匹配邊集E′. Vp中各子節(jié)點(diǎn)群依次使用蟻群算法進(jìn)行求解時(shí)， 多只螞蟻同時(shí)進(jìn)行下述操作， 具體流程如圖5所示.

1） 隨機(jī)選擇一個(gè)未匹配節(jié)點(diǎn)， 并根據(jù)相關(guān)信息素和節(jié)點(diǎn)間路徑長(zhǎng)度計(jì)算當(dāng)前節(jié)點(diǎn)選擇其余未匹配節(jié)點(diǎn)的概率.

2） 根據(jù)步驟1）中計(jì)算的概率從其余未選擇節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)， 兩者進(jìn)行匹配， 若仍有節(jié)點(diǎn)未進(jìn)行匹配則重復(fù)步驟1）和步驟2）， 直到所有節(jié)點(diǎn)均已匹配完成.

3） 所有螞蟻均完成所有節(jié)點(diǎn)的匹配后， 從多只螞蟻所得的匹配結(jié)果中選擇具有最短添加路徑長(zhǎng)度的匹配結(jié)果， 并根據(jù)此結(jié)果對(duì)相關(guān)匹配路徑上的信息素進(jìn)行修改.

4） 若當(dāng)次迭代的最佳匹配結(jié)果優(yōu)于之前迭代的最佳匹配結(jié)果， 則保存當(dāng)前的最佳匹配結(jié)果作為整體最佳匹配結(jié)果; 若未達(dá)到最大迭代次數(shù)， 則重復(fù)步驟1）～4）， 直到達(dá)到最大迭代次數(shù).

5） 當(dāng)達(dá)到最大迭代次數(shù)后， 用保存的整體最佳匹配結(jié)果作為最終結(jié)果.

結(jié)合Vp中各子節(jié)點(diǎn)群的最短匹配邊集和原路網(wǎng)圖可得到從任意起點(diǎn)開始的最短Euler回路.

2.5.2 信息素更新方案

在一次迭代結(jié)束后， 需根據(jù)當(dāng)次迭代結(jié)果對(duì)信息素進(jìn)行更新. 傳統(tǒng)的信息素更新是每個(gè)螞蟻對(duì)信息素更新的疊加， 同時(shí)信息素的增加量和當(dāng)前尋找的路徑長(zhǎng)度有關(guān)， 該方案中信息素受不同長(zhǎng)度的路徑和固定的信息素總量影響， 但不同長(zhǎng)度的路徑可能會(huì)產(chǎn)生不同量級(jí)的信息素大小， 從而使信息素可能會(huì)異常增大， 導(dǎo)致整體收斂異常， 而且所有螞蟻均會(huì)對(duì)信息素進(jìn)行更新， 可用性較差的結(jié)果對(duì)信息素的更新會(huì)導(dǎo)致整體向錯(cuò)誤的方向收斂， 從而加大尋找可用解的難度. 因此， 改進(jìn)方案中采用精英螞蟻策略， 一次迭代只有路徑最短的螞蟻才更新信息素. 同時(shí)信息素的增加改為每次增加常量Px， 從而避免信息素不同數(shù)量級(jí)的問題：τij=τij+Px，ij∈MA，（7）其中： τij為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的信息素濃度； MA為精英螞蟻的匹配結(jié)果集； ij為匹配結(jié)果集中的具體路徑； Px為信息素常量， 大小在0.05～0.1內(nèi)效果較好.

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

本文在Windows10平臺(tái)和Visual Studio 2019環(huán)境下進(jìn)行實(shí)驗(yàn)， 輸入為奇數(shù)度節(jié)點(diǎn)完全圖， 其中所有節(jié)點(diǎn)均為奇數(shù)度節(jié)點(diǎn)， 且奇數(shù)度節(jié)點(diǎn)完全圖中各節(jié)點(diǎn)間路徑長(zhǎng)度均隨機(jī)生成， 以模擬實(shí)際路網(wǎng)環(huán)境中不同路徑長(zhǎng)度間的隨機(jī)性， 從而排除數(shù)據(jù)的特殊性導(dǎo)致實(shí)驗(yàn)結(jié)果的誤差； 輸出為重復(fù)路徑的添加長(zhǎng)度和運(yùn)行時(shí)間.

3.1 小規(guī)模CPP問題求解結(jié)果比較

為證明FS-LSSCPP算法所得匹配結(jié)果接近于具有最短路徑長(zhǎng)度的匹配結(jié)果， 應(yīng)將同等規(guī)模下FS-LSSCPP算法結(jié)果與確定性算法所得結(jié)果進(jìn)行比較， 但限制于確定性算法所能處理問題規(guī)模較小， 故此處比較確定性算法所能求解范圍內(nèi)的結(jié)果， 并以此推廣到大規(guī)模情況. 確定性算法采用線性規(guī)劃方法， 在170個(gè)節(jié)點(diǎn)以下的路徑長(zhǎng)度比較結(jié)果列于表1（單位： m）， FS-LSSCPP算法采用1 000次迭代5次運(yùn)行平均值. 由表1可見， 在較小規(guī)模下FS-LSSCPP算法可得到與線性規(guī)劃相同的重復(fù)路徑長(zhǎng)度， 即FS-LSSCPP算法可得到小規(guī)模下的最優(yōu)解.

3.2 小規(guī)模CPP問題求解時(shí)間比較

在同等規(guī)模下1 000次迭代FS-LSSCPP算法和線性規(guī)劃方法的計(jì)算時(shí)間比較如圖6所示. 由圖6可見， 在節(jié)點(diǎn)數(shù)量較小時(shí)， 兩種算法求解所需時(shí)長(zhǎng)均較小且差距不大. 隨著節(jié)點(diǎn)個(gè)數(shù)的增加， FS-LSSCPP算法的效率優(yōu)勢(shì)顯著增加. 在170個(gè)節(jié)點(diǎn)時(shí)， FS-LSSCPP算法相比于線性規(guī)劃方法有約8倍的提升效率. 實(shí)驗(yàn)結(jié)果表明， 確定性算法雖然能得到最優(yōu)解， 但整體計(jì)算時(shí)長(zhǎng)隨著節(jié)點(diǎn)規(guī)模的增大而快速增長(zhǎng)， 當(dāng)節(jié)點(diǎn)規(guī)模過大時(shí)， 將無(wú)法在可接受時(shí)間內(nèi)得到所需解； 而FS-LSSCPP算法時(shí)長(zhǎng)主要與迭代次數(shù)和單次蟻群時(shí)長(zhǎng)有關(guān)， 在節(jié)點(diǎn)規(guī)模上， 隨著節(jié)點(diǎn)規(guī)模的增大整體時(shí)長(zhǎng)將會(huì)緩慢線性增加， 即使在大規(guī)模情況下， 也依然可在有限時(shí)間內(nèi)得到可行解.

3.3 大規(guī)模CPP問題求解結(jié)果比較

FS-LSSCPP算法在使用蟻群算法進(jìn)行求解前， 采用聚類算法針對(duì)路網(wǎng)圖中節(jié)點(diǎn)的稀疏特性對(duì)原始奇數(shù)度點(diǎn)群進(jìn)行分割. 下面給出引入聚類后的FS-LSSCPP算法相比于單一蟻群算法在結(jié)果可用性和整體效率上的提升.

FS-LSSCPP算法通過聚類縮小節(jié)點(diǎn)群規(guī)模， 有效提高運(yùn)行效率， 并通過聚類合并提高子節(jié)點(diǎn)群中鄰近節(jié)點(diǎn)的覆蓋率， 從而有利于降低后續(xù)蟻群算法尋找的有效重復(fù)路徑長(zhǎng)度. 圖7為FS-LSSCPP算法和單獨(dú)蟻群算法在不同規(guī)模節(jié)點(diǎn)下運(yùn)行結(jié)果的比較. 由圖7可見， 隨著節(jié)點(diǎn)規(guī)模的增大， FS-LSSCPP算法在重復(fù)路徑長(zhǎng)度的結(jié)果上具有明顯優(yōu)勢(shì).

3.4 大規(guī)模CPP問題求解時(shí)間比較

使用聚類方法后可將大規(guī)模節(jié)點(diǎn)群分割為多個(gè)小規(guī)模節(jié)點(diǎn)群， 從而縮小求解空間， 提高運(yùn)行效率. 圖8為不同規(guī)模的節(jié)點(diǎn)群分別在蟻群算法和FS-LSSCPP算法下的運(yùn)行效率. 由圖8可見，? 隨著節(jié)點(diǎn)規(guī)模的增加， FS-LSSCPP算法的計(jì)算效率優(yōu)勢(shì)逐漸明顯.

由蟻群算法和FS-LSSCPP算法運(yùn)行效率的比較可見， 不同節(jié)點(diǎn)規(guī)模下， FS-LSSCPP算法的求解所需時(shí)間明顯降低， 且隨著節(jié)點(diǎn)規(guī)模的增大， 效率的提升也越來(lái)越明顯.

綜上所述， 針對(duì)現(xiàn)有中國(guó)郵遞員問題求解方法在大規(guī)模稀疏路網(wǎng)圖上求解效率的瓶頸， 本文結(jié)合分治和啟發(fā)的思想提出了一種有效降低所需時(shí)間， 同時(shí)得到迭代次數(shù)內(nèi)最優(yōu)Euler回路的大規(guī)模稀疏中國(guó)郵遞員問題快速求解方法， 通過分析、 計(jì)算及實(shí)驗(yàn)比對(duì)， 得到如下結(jié)論：

1） 在確定性算法可支持的節(jié)點(diǎn)規(guī)模下， 本文方法可以極大概率得到最優(yōu)Euler回路的同時(shí)大幅度降低所需時(shí)間；

2） 在大規(guī)模節(jié)點(diǎn)情況下， 可在保證結(jié)果有效性的前提下有效提高運(yùn)算效率， 降低所需時(shí)間.

該方法主要針對(duì)無(wú)向Euler圖的第二階段構(gòu)造過程進(jìn)行求解， 針對(duì)有向Euler圖的構(gòu)造方法和第一階段奇數(shù)度節(jié)點(diǎn)間最短路徑的快速求解［17］還有待進(jìn)一步研究.

參考文獻(xiàn)

［1］WILLEMSE E J，? JOUBERT J W. Applying Min-Max k Postmen Problems to the Routing of Security Guards [J]. Journal of the Operational Research Society， 2012， 63（2）： 245-260.

［2］SALAZAR-AGUILAR M A， LANGEVIN A，? LAPORTE G. Synchronized Arc Routing for Snow Plowing Operations [J].Computers & Operations Research， 2012， 39（7）： 1432-1440.

［3］管梅谷. 關(guān)于中國(guó)郵遞員問題研究和發(fā)展的歷史回顧 ［J］. 運(yùn)籌學(xué)學(xué)報(bào)， 2015， 19（3）： 1-7. （GUAN M G. A Historical Review of the Research and Development of the Chinese Postman Problem ［J］. Journal of Operational Research， 2015， 19（3）： 1-7.）

［4］管梅谷. 奇偶點(diǎn)圖上作業(yè)法 ［J］. 數(shù)學(xué)學(xué)報(bào)， 1960（3）： 263-266. （GUAN M G. Working Method on Odd and Even Point Graphs ［J］. Journal of Mathematics， 1960（3）： 263-266.）

［5］EDMONDS J， JOHNSON E L. Matching， Euler Tours and the Chinese Postman ［J］. Mathematical Programming， 1973， 5（1）： 88-124.

［6］SUN J H， MENG Y K， TAN G Z. An Integer Programming Approach for the Chinese Postman Problem with Time-Dependent Travel Time ［J］. Journal of Combinatorial Optimization， 2015， 29（3）： 565-588.

［7］SHIN S Y ， LEE I H， KIM D， et al. Multiobjective Evolutionary Optimization of DNA Sequences for Reliable DNA Computing [J].? IEEE Transactions on Evolutionary Computation， 2005，? 9（2）： 143-158.

［8］RALPHS T K. On the Mixed Chinese Postman Problem ［J］. Operations Research Letters， 1993， 14（3）： 123-127.

［9］于紅斌， 薛占熬. 基于螞蟻算法的中國(guó)郵路問題 ［J］. 河南師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2011， 39（5）： 169-171. （YU H B， XUE Z A. Chinas Postal Route Problem Based on Ant Algorithm ［J］. Journal of Henan Normal University （Natural Science Edition）， 2011， 39（5）： 169-171.）

［10］CORBERN A， PLANA I， RODRGUEZ-CHA A M， et al. A Branch and Cut Algorithm for the Maximum Benefit Chinese Postman Problem ［J］. Mathematical Programming， 2013， 141： 21-48.

［11］PEARN W L， CHOU J B. Improved Solutions for the Chinese Postman Problem on Mixed Networks ［J］. Computers and Operations Research， 1999， 26（8）： 819-827.

［12］徐曉， 丁世飛， 丁玲. 密度峰值聚類算法研究進(jìn)展 ［J］. 軟件學(xué)報(bào)， 2022， 33（5）： 1800-1816. （XU X， DING S F， DING L. Research Progress in Density Peak Clustering Algorithms ［J］. Journal of Software Science， 2022， 33（5）： 1800-1816.）

［13］孫林， 秦小營(yíng)， 徐久成， 等. 基于K近鄰和優(yōu)化分配策略的密度峰值聚類算法 [J]. 軟件學(xué)報(bào)， 2022， 33（4）： 1390-1411. （SUN L， QIN X Y， XU J C， et al. Density Peak Clustering Algorithm Based on K-Nearest Neighbor and Optimal Allocation Strategy [J]. Journal of Software， 2022，? 33（4）： 1390-1411.）

［14］吳斌， 盧紅麗， 江惠君.自適應(yīng)密度峰值聚類算法 [J]. 計(jì)算機(jī)應(yīng)用， 2020， 40（6）： 1654-1661. （WU B， LU H L， JIANG H J. Adaptive Density Peak Clustering Algorithm [J]. Computer Applications， 2020， 40（6）： 1654-1661.）

［15］李長(zhǎng)明， 張紅臣， 王超， 等. 一種高效的陰陽(yáng)k-Means聚類算法 ［J］. 吉林大學(xué)學(xué)報(bào)（理學(xué)版）， 2021， 59（6）： 1455-1460. （LI C M， ZHANG H C， WANG C， et al. An Efficient Yin Yang k-Means Clustering Algorithm ［J］. Journal of Jilin University （Science Edition）， 2021， 59（6）： 1455-1460.）

［16］胡雅婷， 陳營(yíng)華， 寶音巴特， 等. 一種增量式MinMax k-Means聚類算法 ［J］. 吉林大學(xué)學(xué)報(bào)（理學(xué)版）， 2021， 59（5）： 1205-1211. （HU Y T， CHEN Y H， BAOYIN B， et al. An Incremental MinMax k-Means Clustering Algorithm ［J］. Journal of Jilin University （Science Edition）， 2021， 59（5）： 1205-1211.）

［17］王玉， 申鉉京， 周昱洲， 等. 一種求解交通網(wǎng)絡(luò)中最短路徑問題的人工蜂群算法 ［J］. 吉林大學(xué)學(xué)報(bào)（理學(xué)版）， 2021， 59（5）： 1144-1150. （WANG Y， SHEN X J， ZHOU Y Z， et al. An Artificial Bee Colony Algorithm for Solving the Shortest Path Problem in Traffic Networks ［J］. Journal of Jilin University （Science Edition）， 2021， 59（5）： 1144-1150.）

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

收稿日期： 2023-05-04.

第一作者簡(jiǎn)介： 唐繼州（1999—） ， 男， 漢族， 碩士研究生， 從事高性能計(jì)算的研究， E-mail： 931515887@qq.com.

通信作者簡(jiǎn)介： 白洪濤（1975—） ， 男， 漢族， 博士， 教授， 從事高性能計(jì)算與機(jī)器學(xué)習(xí)的研究， E-mail： baiht@jlu.edu.cn.

基金項(xiàng)目： 國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（批準(zhǔn)號(hào)： 2022YFF0606900