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

唐繼州　何麗莉　白洪濤

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

關鍵詞： 中國郵遞員問題； 蟻群優化； 密度峰值聚類； Euler圖

中圖分類號： TP391文獻標志碼： A文章編號： 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

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

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

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

2 FS-LSSCPP方法框架

2.1 基本思想

針對給定路網圖G上由奇數度節點形成的無向完全圖Gc， FS-LSSCPP求解最短匹配邊集的基本方法如下， 流程如圖2所示.

1） 采用密度峰值聚類方法對奇數度節點群進行聚類分割， 形成多個子節點群Vc.

2） 通過計算Vc中各子節點群自身鄰近節點覆蓋率， 以覆蓋率閾值為標準， 合并相關節點群， 形成多個合并后的子節點群Vm.

3） 計算Vm中節點個數為奇數的節點群之間的最小權完美匹配， 并修改邊界節點所屬的類歸屬， 形成節點個數均為偶數的多個子節點群Vp.

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

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

2.2 奇數度節點群密度峰值聚類

為有效且合理地縮小每個節點群的規模， 本文采用密度峰值聚類算法對節點群進行分割. 密度峰值聚類的流程如圖3所示.

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

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

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

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

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

2.3 子節點群合并

最短匹配邊集的有效性與子節點群包含的鄰近節點數量有關. 子節點群內鄰近節點數量過少會導致節點匹配的選擇范圍減小， 從而大概率增加Euler回路路徑長度［15］， 為有效提高最短匹配邊集的有效性， 本文采用子節點群合并提高節點群中鄰近節點的個數.

2.3.1 相關定義

子節點群合并的參考標準， 鄰近節點集合覆蓋率閾值與子節點群數量滿足如下關系時最短匹配邊集可用性較好：thresholdcov=1/eNum/10，（6）其中thresholdcov為鄰近節點集合覆蓋率閾值， Num為聚類個數.

子節點群合并目標是使各子節點群自身鄰近節點集合覆蓋率均超過鄰近節點集合覆蓋率閾值. 子節點群內鄰近節點數量m的選取與路網圖中總奇數度節點的數量有關， 一般為總奇數度節點數量的1%［16］； 不同的子節點群個數會影響覆蓋率閾值的大小， 較少的子節點群數量， 節點分布相對集中， 需要較高的鄰近節點覆蓋率閾值才可保證最短匹配邊集的可用性； 若子節點群個數很多， 則節點分布相對分散， 每個子節點群內部節點較少， 鄰近節點覆蓋率閾值要求應適當降低.

2.3.2 子節點群合并

子節點群合并流程如下：

1） 計算Vc中各子節點群鄰近節點集合和鄰近節點覆蓋率；

2） 合并Vc中相關子節點群， 直到各子節點群鄰近節點覆蓋率均滿足鄰近節點覆蓋率閾值.

設合并后的子節點群數量為n個， 合并后的子節點群記為Vm， 合并流程如下：

2.4 子節點群節點數量偶數化

Vm中各子節點群內部節點個數可能為奇數， 而最短匹配邊集E′的尋找要求集合的節點個數為偶數， 故需對節點個數為奇數的節點群進行偶數化處理才可進行后續的匹配操作.

群節點數量偶數化的過程如下： 首先確定所有節點數量為奇數的子節點群的中心節點; 然后確定群中心點之間的最小權完美匹配集合； 最后在具有匹配關系的兩個節點群之間， 選擇一個邊界節點進行群間移動. 邊界節點是指具有匹配關系的兩個節點群中， 與兩個群中心點的距離差值最小的節點. 由于奇數度節點群的數量為偶數， 所以調整后的子節點群節點數量均為偶數. 子節點群節點數量偶數化流程如下.

程序2

子節點群節點數量偶數化流程.

輸入： 子節點群Vm={C1，C2，…，Cn};

輸出： 子節點群Vp={C1，C2，…，Cn};

1） 使用蟻群算法求Vm各子節點群中心節點間最小權完美匹配Em

2） for i in Em do

3）取出i邊對應的Vm中的子節點群Ca，Cb

4）for j in Ca or Cb do

5）

計算Lja和Ljb（j點到Ca，Cb中心的距離）

6）

找出具有min（Lja-Ljb）的節點j（即邊界節點）

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） 合并后子節點群為Vp.

確立奇數度節點群中心點之間的最小權完美匹配集合的方法有很多， 如果節點數量較多， 可采用類似蟻群算法實現. 群節點數量偶數化的流程如圖4所示.

2.5 基于蟻群算法求解子節點群內最短匹配邊集

2.5.1 蟻群算法整體思路

為保證構造出的Euler圖總路徑長度最短， 同時提高求解速率， 本文應采用相關啟發式方法進行求解. 最短匹配邊集的求解可視為尋找最短路徑， 為同時滿足上述需求， 本文采用蟻群算法求解各子節點群Vp內部最短匹配邊集E′. Vp中各子節點群依次使用蟻群算法進行求解時， 多只螞蟻同時進行下述操作， 具體流程如圖5所示.

1） 隨機選擇一個未匹配節點， 并根據相關信息素和節點間路徑長度計算當前節點選擇其余未匹配節點的概率.

2） 根據步驟1）中計算的概率從其余未選擇節點中隨機選擇一個節點， 兩者進行匹配， 若仍有節點未進行匹配則重復步驟1）和步驟2）， 直到所有節點均已匹配完成.

3） 所有螞蟻均完成所有節點的匹配后， 從多只螞蟻所得的匹配結果中選擇具有最短添加路徑長度的匹配結果， 并根據此結果對相關匹配路徑上的信息素進行修改.

4） 若當次迭代的最佳匹配結果優于之前迭代的最佳匹配結果， 則保存當前的最佳匹配結果作為整體最佳匹配結果; 若未達到最大迭代次數， 則重復步驟1）～4）， 直到達到最大迭代次數.

5） 當達到最大迭代次數后， 用保存的整體最佳匹配結果作為最終結果.

結合Vp中各子節點群的最短匹配邊集和原路網圖可得到從任意起點開始的最短Euler回路.

2.5.2 信息素更新方案

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

3 實驗結果及分析

本文在Windows10平臺和Visual Studio 2019環境下進行實驗， 輸入為奇數度節點完全圖， 其中所有節點均為奇數度節點， 且奇數度節點完全圖中各節點間路徑長度均隨機生成， 以模擬實際路網環境中不同路徑長度間的隨機性， 從而排除數據的特殊性導致實驗結果的誤差； 輸出為重復路徑的添加長度和運行時間.

3.1 小規模CPP問題求解結果比較

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

3.2 小規模CPP問題求解時間比較

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

3.3 大規模CPP問題求解結果比較

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

FS-LSSCPP算法通過聚類縮小節點群規模， 有效提高運行效率， 并通過聚類合并提高子節點群中鄰近節點的覆蓋率， 從而有利于降低后續蟻群算法尋找的有效重復路徑長度. 圖7為FS-LSSCPP算法和單獨蟻群算法在不同規模節點下運行結果的比較. 由圖7可見， 隨著節點規模的增大， FS-LSSCPP算法在重復路徑長度的結果上具有明顯優勢.

3.4 大規模CPP問題求解時間比較

使用聚類方法后可將大規模節點群分割為多個小規模節點群， 從而縮小求解空間， 提高運行效率. 圖8為不同規模的節點群分別在蟻群算法和FS-LSSCPP算法下的運行效率. 由圖8可見，? 隨著節點規模的增加， FS-LSSCPP算法的計算效率優勢逐漸明顯.

由蟻群算法和FS-LSSCPP算法運行效率的比較可見， 不同節點規模下， FS-LSSCPP算法的求解所需時間明顯降低， 且隨著節點規模的增大， 效率的提升也越來越明顯.

綜上所述， 針對現有中國郵遞員問題求解方法在大規模稀疏路網圖上求解效率的瓶頸， 本文結合分治和啟發的思想提出了一種有效降低所需時間， 同時得到迭代次數內最優Euler回路的大規模稀疏中國郵遞員問題快速求解方法， 通過分析、 計算及實驗比對， 得到如下結論：

1） 在確定性算法可支持的節點規模下， 本文方法可以極大概率得到最優Euler回路的同時大幅度降低所需時間；

2） 在大規模節點情況下， 可在保證結果有效性的前提下有效提高運算效率， 降低所需時間.

該方法主要針對無向Euler圖的第二階段構造過程進行求解， 針對有向Euler圖的構造方法和第一階段奇數度節點間最短路徑的快速求解［17］還有待進一步研究.

參考文獻

［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］管梅谷. 關于中國郵遞員問題研究和發展的歷史回顧 ［J］. 運籌學學報， 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］管梅谷. 奇偶點圖上作業法 ［J］. 數學學報， 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］于紅斌， 薛占熬. 基于螞蟻算法的中國郵路問題 ［J］. 河南師范大學學報（自然科學版）， 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］. 軟件學報， 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］孫林， 秦小營， 徐久成， 等. 基于K近鄰和優化分配策略的密度峰值聚類算法 [J]. 軟件學報， 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］吳斌， 盧紅麗， 江惠君.自適應密度峰值聚類算法 [J]. 計算機應用， 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］李長明， 張紅臣， 王超， 等. 一種高效的陰陽k-Means聚類算法 ［J］. 吉林大學學報（理學版）， 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］胡雅婷， 陳營華， 寶音巴特， 等. 一種增量式MinMax k-Means聚類算法 ［J］. 吉林大學學報（理學版）， 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］王玉， 申鉉京， 周昱洲， 等. 一種求解交通網絡中最短路徑問題的人工蜂群算法 ［J］. 吉林大學學報（理學版）， 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.）

（責任編輯： 韓 嘯）

收稿日期： 2023-05-04.

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

通信作者簡介： 白洪濤（1975—） ， 男， 漢族， 博士， 教授， 從事高性能計算與機器學習的研究， E-mail： baiht@jlu.edu.cn.

基金項目： 國家重點研發計劃項目（批準號： 2022YFF0606900