亓玉瀟，張 昆

（華東師范大學(xué) 地理科學(xué)學(xué)院，上海 200241）

0 引言

街道噴灑消毒液是新冠肺炎疫情期間的重要防疫措施。假設(shè)有若干條道路需要消毒，消毒車輛走怎樣的路線既能夠完成作業(yè)，又可使總路程最短，這便是一個路徑優(yōu)化問題。除此之外，警察巡邏、垃圾車收集垃圾、掃雪車清掃街道、街景圖攝制等均涉及路徑優(yōu)化問題，可統(tǒng)稱為中國郵遞員問題（Chinese Postman Problem，CPP）［1］。CPP 最早由管梅谷［2］提出，即一個郵遞員從郵局出發(fā)，經(jīng)過需要投遞信件的每條街道然后返回郵局，應(yīng)該走怎樣的路線以使總里程最短。CPP 是歐拉環(huán)游的擴展，歐拉環(huán)游是尋找經(jīng)過每條邊一次，最后回到起點的路線；CPP 則是尋找經(jīng)過每條邊至少一次，最后回到起點，且總里程最短的路線。相比之下，CPP 具有更廣的應(yīng)用領(lǐng)域。

Shiny 是一個R 語言包，可以應(yīng)用R 語言構(gòu)建交互式Web 應(yīng)用程序［3］。開發(fā)者無需了解開發(fā)網(wǎng)頁的HTML、CSS或JavaScript 等傳統(tǒng)技術(shù)，直接使用R 語言便可以完成服務(wù)器端和前端網(wǎng)頁開發(fā)，應(yīng)用程序可免費托管在Shinyapps.io云端并獲得一個網(wǎng)址，用戶訪問該網(wǎng)址即可使用應(yīng)用程序。Leaflet 是用于交互式地圖開發(fā)的JavaScript 庫，Leaflet R 包用R 語言封裝了JavaScript 命令［4］。將CPP 應(yīng)用于解決實際問題的軟件和程序并不多見，若能以CPP 為基礎(chǔ)借助以上開源軟件開發(fā)一個供道路作業(yè)人員使用的應(yīng)用程序，可為其工作開展提供便利。

1 相關(guān)研究

目前對于CPP 的研究主要集中在算法改進和模型擴展（如帶風(fēng)向的郵遞員問題、鄉(xiāng)村郵遞員問題等）方面。CPP為非確定性多項式（Nondeterministic Polynomially，NP）類問題，關(guān)于求解算法，管梅谷［2］提出了奇偶點圖上作業(yè)法，該方法適用于規(guī)模較小的CPP 問題；Edmonds 等［5］提出了更為有效的最優(yōu)匹配算法；也有一些研究采用啟發(fā)式算法求解該類問題［6-8］。

國內(nèi)外均有借助Shiny 進行網(wǎng)頁開發(fā)的案例。例如，李玲玉等［9］應(yīng)用Shiny 技術(shù)開發(fā)了用于快遞員配送路徑規(guī)劃的網(wǎng)頁應(yīng)用Delivery Helper；陸瑤等［10］以降水監(jiān)測數(shù)據(jù)作為輸入，借助Shiny 技術(shù)開發(fā)了山洪預(yù)警系統(tǒng)；白秀顯［11］借助Shiny 技術(shù)實現(xiàn)了高校招生數(shù)據(jù)的挖掘與可視化；Zhou等［12］基于用戶創(chuàng)造內(nèi)容（User-Generated Contents，UGC）開發(fā)了旅行規(guī)劃工具，在利用地理空間數(shù)據(jù)挖掘方法獲取酒店信息、路線費用等內(nèi)容后開發(fā)了網(wǎng)頁界面，為用戶提供景點酒店、旅游路線等綜合建議。Shiny 技術(shù)與Leaflet 結(jié)合可以實現(xiàn)網(wǎng)頁地圖數(shù)據(jù)的可視化與交互性，例如Edward等［13］基于Shing 與Leaflet 技術(shù)開發(fā)了全球新冠疫情地圖COVID-19 tracker，在一張世界地圖上展示了每個國家的疫情分布情況，數(shù)據(jù)每日更新。本文基于Shiny 與Leaflet 技術(shù)，開發(fā)了一個求解CPP 類問題的網(wǎng)頁應(yīng)用程序Chinese Postman Problem Solver（CPP Solver，https：//qiyuxiao.shin?yapps.io/myapp1/），為道路作業(yè)人員規(guī)劃最優(yōu)路線。

2 CPP 建模與求解

含有歐拉環(huán)游的圖稱為歐拉圖，一個連通圖是歐拉圖的充分必要條件是圖中每個頂點的度數(shù)均為偶數(shù)。CPP 與歐拉圖密切相關(guān)，如果CPP 對應(yīng)的連通圖是歐拉圖，則可采用Fluery 算法找出歐拉環(huán)游（回路），該環(huán)游即為CPP 的最優(yōu)解；如果CPP 對應(yīng)的連通圖不是歐拉圖，則圖中必定存在度數(shù)為奇數(shù)的頂點（奇點）。一個圖中奇點的個數(shù)必定為偶數(shù)，因此可將奇點兩兩匹配，找出任意兩個匹配奇點之間的最短路徑，在該路徑上添加重復(fù)邊，將奇點的度數(shù)變?yōu)榕紨?shù)，即可構(gòu)造出歐拉圖。CPP 的關(guān)鍵是找出重復(fù)邊長度最短的奇點匹配方式。只有2 個奇點的連通圖是最簡單的情況，因為只有1 種匹配方式；若有4 個奇點，則有3 種兩兩匹配的方式；若有6 個奇點，第一個奇點便可與另外5 個奇點中的任意一個匹配，一旦匹配，便只能剩下4 個奇點進行匹配（3 種），因此共有5×3=15 種匹配方式。以此類推，n個奇點的匹配方式數(shù)為：

根據(jù)式（1），10 個奇點的匹配方式有945 種，20 個奇點則有654 729 075 種之多，顯然不能采用枚舉算法。計算機一般只能枚舉十幾個奇點，不能滿足實際應(yīng)用需求。本文采用整數(shù)規(guī)劃模型找出最佳匹配方式，以圖1 為例，假設(shè)有4 個奇點，所有可能的兩兩匹配構(gòu)成了一個完全圖，每條邊上的數(shù)字代表權(quán)重，即兩個奇點之間最短路徑的長度，圖1右側(cè)則是對應(yīng)的距離矩陣。

Fig.1 Complete graph and distance matrix of four singularities圖1 四奇點完全圖與距離矩陣

定義決策變量xij表示奇點i與j是否匹配，xij等于1 表示匹配，等于0 表示不匹配。ωij表示奇點i與j匹配的權(quán)重，即i、j之間最短路徑的長度。對于每個奇點而言，其必須與另一個奇點匹配，且只能匹配一次。以奇點1 為例，約束條件為：

該約束對應(yīng)距離矩陣的第一列。為避免自身匹配的情況，將距離矩陣的對角線元素設(shè)置為很大的值（9 999）。規(guī)定若xij等于1，則xji也等于1，因此得到以下整數(shù)規(guī)劃模型：

式（3）為目標(biāo)函數(shù)；式（4）為約束條件，其中第一項對應(yīng)距離矩陣的每一列。采用R 語言的Rglpk 包求解整數(shù)規(guī)劃，求解100 個奇點的匹配用時不超過5s。圖1 的最優(yōu)匹配為奇點1 與3 匹配，奇點2 與4 匹配，即x13=x31=x24=x42=1，其他xij=0，目標(biāo)函數(shù)的值為16，其值的一半（8）即為重復(fù)邊的長度。

確定了奇點匹配的方式后，便可在CPP 對應(yīng)的圖上添加重復(fù)邊，構(gòu)造出歐拉圖G，然后采用Fleury 算法求出歐拉回路。Fluery 算法的主要思想為從一個頂點出發(fā)，能不走橋就不走橋［14］，算法步驟為：

（1）任取一頂點v0，令W0=v0。

（2）設(shè)已經(jīng)選定的跡Wi=v0e1v1e2…eivi，按以下原則從E（G）-｛e1，e2，…，ei｝中選取邊ei+1：①ei+1與vi相關(guān)聯(lián)；②除非沒有別的邊可供選擇，否則ei+1不是G-｛e1，e2，…，ei｝的橋（割邊）。

（3）重復(fù)步驟（2），直至E（G）-｛e1，e2，…，ei｝為空。

3 網(wǎng)頁開發(fā)

Shiny 應(yīng)用程序由用戶界面對象（UI）和服務(wù)器函數(shù)（server）組成，UI 負責(zé)應(yīng)用程序的布局，server 負責(zé)程序的功能實現(xiàn)并控制輸出。采用grid layout 布局整個頁面，以便控制模塊列寬，使用到的主要控件包括：leafletOutput 用于顯示地圖；textOutput 控件用于輸出文字；actionButton 創(chuàng)建按鈕“Finish Clicking”“Clear”和“Generate Route”；selectIn?put 控件允許用戶從列表中選擇起點。Shiny 也提供了構(gòu)建HTML 文檔的簡單函數(shù)，如hr（添加橫線）、h3（添加標(biāo)題）等。

Fig.2 User interface（Website：https：//qiyuxiao.shinyapps.io/myapp1/）圖2 用戶界面（網(wǎng)址：https：//qiyuxiao.shinyapps.io/myapp1/）

如圖2 所示，程序的使用包括兩個步驟：首先采用鼠標(biāo)在地圖上選擇一個連通的道路網(wǎng)，這些連通的道路即為需要至少經(jīng)過一次的服務(wù)邊，點擊按鈕“Finish Clicking”后，程序會對選中道路的路口進行編號；然后選擇一個路口作為起點，或用缺省的1 號作為起點，點擊按鈕“Generate Route”求解路線規(guī)劃。

CPP 的解是一條經(jīng)過服務(wù)邊至少一次，且回到起點的最短路徑。由于經(jīng)常會有重復(fù)邊（經(jīng)過兩次的道路），最佳路徑的行走次序往往難以清晰表達。為了便于用戶查看，本文提出郵遞員路徑分解算法，步驟為：

（1）設(shè)T=?。

（2）歐拉回路記為C=｛v1，v2，…，vn｝，遍歷C 中的頂點，記當(dāng)前頂點為vi。

（3）T=T∪C，算法結(jié)束，T 中保存的即為分解后的路徑。

該算法的思路為依次判斷最終路徑中是否有重復(fù)經(jīng)過的路口，如果有，則將路徑分解為兩部分，一部分路徑?jīng)]有重疊部分，然后對另一部分的路徑重復(fù)前面的判斷。算法中對v2=v1的情況進行了判斷，是考慮到了環(huán)路的情形。如圖3 所示，加粗的路線是需要經(jīng)過的服務(wù)邊，起點為頂點3，最優(yōu)路徑的頂點序列為｛3，2，1，2，2，3｝。頂點序列對于用戶而言是不直觀的，而圖形顯示可能有二義性，例如從頂點3 走到頂點2 后，是經(jīng)過環(huán)路回到頂點2，還是直接走到頂點1。采用分解算法對該條路徑進行分解，得到4 段路徑：｛3，2，1｝，｛1，2｝，｛2，2｝，｛2，3｝，在圖形窗口中依次顯示這4 段路徑，既直觀又不會造成誤解，因為沒有重疊部分。

Fig.3 Optimal path with loop圖3 帶環(huán)路的最優(yōu)路徑

道路網(wǎng)數(shù)據(jù)是解決CPP 必不可少的組成部分。本文道路網(wǎng)數(shù)據(jù)來自O(shè)penStreetMap 官網(wǎng)（https：//www.openstreet?map.org），在地圖中定位到研究區(qū)域后，點擊頁面上方的“導(dǎo)出”按鈕，可將矢量數(shù)據(jù)導(dǎo)出為osm 文件。在QGIS 軟件中對道路圖層（map lines）進行必要的編輯，如將斷開的道路合并、兩條道路在交叉點打斷等。采用R 語言的rgdal 包將處理好的道路網(wǎng)讀取并加載到leaflet 中，具體技術(shù)框架如圖4 所示。

Fig.4 Technical framework圖4 技術(shù)框架

4 案例分析

對圖5 所示的目標(biāo)道路案例進行路徑規(guī)劃，將3 號點設(shè)定為起始點，需要作業(yè)完成加粗路線部分，求解出一條最優(yōu)路徑。結(jié)果路徑如圖6 所示，總路徑（route_undecom?posed）為3-1-2-1-4-7-4-5-8-5-11-6-10-9-10-13-10-12-15-12-16-11-14-11-6-1-3，分解后為route1：3-1-2；route2：2-1-4-7；route3：7-4-5-8；route4：8-5-11-6-10-9；route5：9-10-13；route6：13-10-12-15；route7：15-12-16-11-14；route8：14-11-6-1-3，總路線長度 為2 808m。由圖5 可知，目標(biāo)道路構(gòu)成的原圖中共有12 個奇點，經(jīng)過模型匹配的結(jié)果為2 和3、4 和7、5 和8、9 和13、6 和14、12和15。原圖中共有17 條邊，添加邊生成的歐拉圖中有26條邊，共重復(fù)了9 條邊，分別為1 和2、1 和3、4 和7、5 和8、9和10、10 和13、6 和11、11 和14、12 和15 之間的邊。原圖有1 850m，重復(fù)邊有958m。

Fig.5 Target roads圖5 目標(biāo)道路

Fig.6 Route planning results圖6 路線規(guī)劃結(jié)果

5 結(jié)語

CPP 是為數(shù)不多的由中國學(xué)者提出的路徑優(yōu)化問題。如果道路網(wǎng)中沒有奇點，CPP 的求解就等同于尋找一個歐拉回路；如果存在奇點，則尋找奇點的最優(yōu)匹配方式是解決CPP 的關(guān)鍵。本文建立了一個整數(shù)規(guī)劃模型，可以快速求解上百個奇點的匹配。在此基礎(chǔ)上，借助開源Web 工具Shiny 建立了一個求解CPP 的網(wǎng)頁應(yīng)用程序CPP Solver，為國內(nèi)推廣應(yīng)用Shiny 進行網(wǎng)頁開發(fā)提供了案例，其中還用到了leaflet 技術(shù)顯示地圖并加載道路圖層。如果存在需重復(fù)經(jīng)過的道路或路口，CPP Solver 能采用路徑分解算法對最優(yōu)路徑進行分段，消除了路徑導(dǎo)航可能產(chǎn)生的二義性，進一步優(yōu)化了結(jié)果的可視化程度。然而，CPP Solver 也存在一些不足：①只能處理道路網(wǎng)連通的情況，即經(jīng)典CPP，下一步可考慮對不連通情況下的鄉(xiāng)村郵遞員問題建模并進行網(wǎng)頁開發(fā)；②研究區(qū)域的道路網(wǎng)是CPP Solver 的基礎(chǔ)，而道路網(wǎng)的編輯與處理需要一定的GIS 專業(yè)知識和技術(shù)，當(dāng)研究區(qū)域較大時，道路網(wǎng)編輯的工作量會大大增加，這在一定程度上制約了CPP Solver 的推廣；③CPP Solver 沒有考慮復(fù)雜的交通規(guī)則，例如單行道、車輛拐彎的限制等，以后可針對混合圖中的CPP 建模求解。