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

宿愛靜

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

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

0.引言

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

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

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

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

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

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

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

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

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

2.結論

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

【參考文獻】

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

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

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

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

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