交巡警服務平臺的設置與調度模型與算法求解

宿愛靜

【摘 要】本文根據城市的實際情況與需求，合理地設置交巡警服務平臺、分配各平臺的管轄范圍、調度警務資源。針對交巡警服務平臺管轄范圍的分配與警力調度問題，利用Floyd算法確定交通網絡中任意兩節點間的最短路徑，根據其路徑值建立優化模型對問題進行求解。

【關鍵詞】交巡警服務平臺的設置調度；最短路徑；Floyd算法

0.引言

為了更有效地貫徹實施警察刑事執法、治安管理、交通管理、服務群眾四大職能，在市區的一些交通要道和重要部位設置交巡警服務平臺，使得案件發生后，巡警能夠盡快抵達出事現場。本文考慮了具有完善交通路網城區各交巡警服務平臺分配管轄范圍的情景，使其在所管轄的范圍內出現突發事件時，盡量能在規定時間內有交巡警到達事發地。當有突發事件發生時，需調度全區交巡警服務平臺的警力資源，對進出該區交通要道實現快速全封鎖。

為解決這一問題，我們首先用Floyd算法求出城區平臺到路口的最短路徑及其距離，然后進行分配。對于每一個路口，找出距離它最近的平臺，并將路口歸這個平臺管轄，按此方法即可得到交巡警服務平臺的分配方法，使事故發生時，交巡警能以最快的速度趕到。當事故發生時，需要從全部平臺中選一定數量的平臺分配。所以我們用Floyd算法求出該城區所有平臺到所有路口的最短路徑及其距離，然后以最晚到達封鎖路口的警力所需要的時間最短為優化目標進行優化，得到最佳方案。

1.案例說明與模型的建立

為了方便建立模型并使得模型更符合實際需求，本文首先對模型做了以下假設：（1）出警過程中，警車行駛的總是最短路徑；（2）所有道路均為雙行道；（3）在較短的時間內，服務平臺管轄范圍里不會出現兩個以上的突發事件；（4）假設出現突發事件后立即有人報警，交巡警服務平臺接警后，準備時間忽略不計，視為立刻出發，即出警時間僅包含警方從服務平臺驅車到達事發地的時間.（5）假設一個平臺的警力最多封鎖一個路口。（6）假設每個交巡警服務平臺的職能和警力配備基本相同。（7）假設嫌犯逃竄的速度與警車平均時速相同。

本文規定rij為任意兩節點i與j間的最短路徑；xij表示節點i是否屬于平臺j管轄，若等于1則i屬于j管轄，等于0則i不屬于j管轄；dij表示節點i和j的最短距離；S為警力封鎖最后一個路口所用的時間；ri表示路口i的案發率。

本文參考了2011年“高教杯”全國數學建模比賽B題的數據。要為城區A各交巡警服務平臺分配管轄范圍，我們先用Floyd算法求出該區20個平臺到92個路口的最短路徑及其距離，然后對于每一個路口，找出距離它最近的平臺，并使此路口歸這個平臺管轄，即可得到分配結果。根據圖論，以城區各路口節點為圖G的頂點，以交通網中任意兩路口節點之間路線為圖G相應兩頂點的邊，得圖G。對G的每一邊e，賦以一個實數w（e）表示連接兩路口節點路線的長度，稱為該邊的權，得到賦權圖G。利用matlab編程求出圖G中有邊的任意兩節點i與j間的路徑rij及其長度dij，若節點i與j間不連通則dij，（1≤i≤92，1 ≤j≤20），得到鄰接矩陣。用matlab編出Floyd算法，代入鄰接矩陣，從而求出A區20個平臺到92個路口的最短路徑及其距離。

根據上面的結果，對于每一個路口，找到距離它最近的平臺，將此路口歸這個平臺管轄，按此方法即可得到交巡警服務平臺最終的分配方法，如下表1所示：

本文考慮了為調度全區20個交巡警服務平臺的警力資源，對進出該區的13條交通要道實現快速全封鎖，所以我們要在20個平臺中選13個進行優化分配，使最晚到達路口的警力所需時間最短。首先以城區各路口節點為圖G的頂點，城區交通網中連接兩路口節點路線為圖G相應兩頂點的邊，得圖G。對G的每一邊e，賦以一個實數w（e）表示連接兩路口節點路線的長度，稱為該邊的權，得到賦權圖G。

利用matlab編程得到距離矩陣，代入到Floyd算法，求出20個平臺到13個節點的最短距離dij（1<=i<=20，1<=j<=13）。引用0-1規劃模型，用xij表示路口是否歸平臺管轄（等于1為i歸j管轄，等于0為i不歸j管），S為警力封鎖最后一個路口所用的時間。以最晚到封鎖路口的警力所走距離S最短為優化目標，以每個平臺到所管轄路口距離小于S、每一個路口有且僅有一個平臺管轄、一個平臺至少管一個路口為約束條件進行優化，所建立的優化模型如下：

2.結論

本文以交巡警平臺的設置和調度問題的情境下，考慮了如何對交巡警平臺的警力分配問題，建立模型并用Matlab軟件求解，在處理數據過程中，利用Excel 軟件對數據進行處理并作出各種圖表，簡便、直觀并運用多種數學軟件（如Matlab、LINGO），取長補短，使計算結果更加準確；同時也對一些數據進行了必要的近似處理，會帶來一定的誤差，另外模型中為使計算簡便，使所得結果更理想化，忽略了一些次要的影響因素。 [科]

【參考文獻】

[1]陳華友.運籌學[M].合肥：中國科技大學出版社，2008.

[2]韓中庚.實用運籌學[M].北京：清華大學出版社，2007.

[3]韓中庚.數學建模方法及其應用[M].北京：高等教育出版社，2005.

[4]楊桂元，黃己立.數學建模[M].合肥：中國科技大學出版社，2008.

[5]謝金星，薛毅.優化模型與LINDO/LINGO 軟件[M].北京：清華大學出版社，2005.