基于拓撲結構下的交巡警服務平臺的設置與調度

姚克儉

摘 要：交巡警平臺擔負著完善交通環境，處理突發事件的責任。在城市中如何合理的設置交巡警服務平臺的數量，確定管轄范圍，制定服務平臺的調度方案，是本文著重解決的問題。我們利用MATLAB軟件建立交巡警平臺管轄范圍模型，針對突發事件進行合理的警力調配提出應急交巡警服務平臺模型，該模型基于圖論原理構建原始問題的拓撲結構，以滿足在現有條件下，盡可能在指定時間內完成該區域的全封鎖。可以得到優化的交巡警平臺警力的合理調度方案，結合發案率，根據每個節點被服務平臺覆蓋的次數確定完善的交巡警服務平臺的設置方案。將道路離散化處理，利用Floyd算法求解。建立相應的整數規劃模型，利用貪婪算法近似求解，提出利用交巡警服務平臺覆蓋率和服務平臺缺失率兩個評價服務平臺顯著程度的指標。

關鍵詞：遺傳算法 計算幾何 拓撲結構 貪心算法 圖論法

中圖分類號：G6 文獻標識碼：A 文章編號：1673-9795（2014）04（a）-0116-02

1 問題分析

根據某市設置交巡警平臺的相關情況，為各交巡警平臺分配管轄范圍，使其在所管轄的范圍內出現突發事件時，盡量能在3分鐘內有交巡警到達事發地。對于重大突發事件，需要調度全區20個交巡警服務平臺的警力資源，對進出該區的13條交通要道實現快速全封鎖。我們按照設置交巡警服務平臺的原則和任務，設計了該區交巡警服務平臺警力合理的調度方案。

2 交巡警服務平臺覆蓋模型[1]

現有交巡警警車的車速為60 km/h，要求交巡警在3分鐘內到達事發地，經過計算交巡警的車速為1 km/h。

我們利用MATLAB軟件編程：以交巡警服務平臺為中心3 km為半徑的圓，所得的圓為交巡警服務平臺的覆蓋范圍。

設為道路節點集合為區域網絡圖中與每個節點相關聯的到路邊的集合，邊的兩個端點為和（假設）則，有

兩個端點的距離為

，

針對上述模型1和2，采用Lingo、Lindo等軟件按分支定界法求得精確解但過程是十分困難的，原因如下：

（1）分支定界法屬于非多項式算法，當整數變量較多時求解困難。

（2）交巡警在3分鐘內到達事發地點的比例不低于90%和3分鐘以后到達重大事件部位的約束條件，很難用常規的線性與非線性表達式來精確表達。所以，該問題屬于復雜非線性整數規劃問題，難以精確求解，故考慮近似算法。我們選取貪婪算法進行近似求解。

5.2 評價交巡警平臺設置是否合理的指標主要有以下幾點

（1）交巡警服務平臺收走路徑包含的標記點數量占區域標記點總數的百分比。

（2）一直處在交巡警服務平臺的控制區域之外的標記點數量占區域標記點總量的百分比。

我們分別用交巡警服務平臺覆蓋率和交巡警服務平臺的缺失率來表示以上兩個指標，交巡警服務平臺覆蓋率越高，巡警服務平臺的缺失率越低，巡警服務平臺設置就越顯著。我們認為交巡警服務平臺覆蓋率達到90%以上，交巡警服務平臺的缺失率低于10%時，巡警服務平臺設置效果顯著。

分別求解P=20～22時滿足D1條件的交巡警服務平臺設置方案，并給出相應的交巡警服務平臺設置效果顯著指標。

根據評價原則：交巡警平臺覆蓋率達到90%以上，同時交巡警平臺的缺失率低于10%時，巡警平臺設置效果顯著。

結論：在A區增設2個交巡警平臺；B區不用增設平臺；C區增設2個平臺；D區增設8個平臺；E區增設5個平臺；F區增設4個平臺。

6 調度方案模型優缺點分析

該方案對道路數據的離散化處理，給模型建立和求解帶來很大便利，對于D1要求中90%的比例，本文采用統計標記點的方式計算，精確性較高，本模型方法不依賴具體的街道走向以及城市的地理形狀，具有普適性。可以推廣到其他地區的交巡警服務平臺的合理設置，稍加改進可用于其他有類似特點的設置問題如：巡邏問題，移動廣告等，如果考慮到車流量以及道路方向本模型更具有實際意義。

參考文獻

[1] 張志涌.MATLAB教程[M].北京：北京航空航天大學出版社，2004.

[2] 姜啟源，謝金星，葉俊.數學模型[M].3版.北京：高等教育出版社，1997.

[3] 朱茵，江越.城市道路應急警力配置模型研究[J].中國安全科學學報2010，2011：170-176.

[4] 謝金星.優化建模與LINDO/LINGO軟件[M].北京，清華大學出版社，2005.

[5] 林陽斌.110警車配置及巡邏方案[J].數學的實踐與認識，2010，40（15）：186-195.