基于Shiny 與Leaflet 技術的中國郵遞員問題網頁設計與開發

亓玉瀟，張 昆

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

0 引言

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

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

1 相關研究

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

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

2 CPP 建模與求解

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

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

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

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

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

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

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

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

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

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

3 網頁開發

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

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

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

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

（1）設T=?。

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

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

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

Fig.3 Optimal path with loop圖3 帶環路的最優路徑

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

Fig.4 Technical framework圖4 技術框架

4 案例分析

對圖5 所示的目標道路案例進行路徑規劃，將3 號點設定為起始點，需要作業完成加粗路線部分，求解出一條最優路徑。結果路徑如圖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 可知，目標道路構成的原圖中共有12 個奇點，經過模型匹配的結果為2 和3、4 和7、5 和8、9 和13、6 和14、12和15。原圖中共有17 條邊，添加邊生成的歐拉圖中有26條邊，共重復了9 條邊，分別為1 和2、1 和3、4 和7、5 和8、9和10、10 和13、6 和11、11 和14、12 和15 之間的邊。原圖有1 850m，重復邊有958m。

Fig.5 Target roads圖5 目標道路

Fig.6 Route planning results圖6 路線規劃結果

5 結語

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