1、交巡警服務平臺的設置與調度摘要本論文主要是關于圖論中的“最短路徑問題”和“最優搜索問題”。問題所述的模型已經很自然地用圖表示出來，所以我們運用圖的性質和算法來求解問題。圖論中求最短路徑通常采用dijkstra算法，但本題涉及的交巡警平臺數量較多，即求多個源點到其它所有頂點的距離，所以采用floyd算法求解比較簡單，其基本思想是通過程序得到每個節點到其他節點的最優距離。針對問題一，用floyd算法算出每個交巡警平臺3分鐘內所能到達的全部節點，這些節點就是平臺的管轄范圍，但仍有3分鐘內不能到達的節點，這些節點處就應該增設交巡警服務平臺。在快速封鎖13條交通要道時，要遵循封鎖時間最短、每個平臺的警力

2、最多封鎖一個路口的原則，運用LINGO程序解答。最后分析得到出警時間至少大于3分鐘的節點，及工作量最大的平臺，在這些節點處需要增加3個服務平臺。針對問題二，需要對發案率進行降序排列，篩選出發案率較高，但是未設置交巡警服務平臺的節點。根據六個城區的基本數據，得到每個平臺管轄的面積和人口，比較各平臺的工作量，從而找出不合理的理由。在搜捕犯罪嫌疑人時要遵循兩個原則：搜捕時間最短和圍堵區域最小。根據逃犯的位置和逃跑的可能路徑建立關于時間T的目標函數和初始概率密度函數，對交巡警的搜捕區域建立探測函數，模型應該滿足以下約束條件：最后運用拉格朗日乘數法求得圍堵嫌疑人的最佳圍堵方案。模型的建立提高了交巡警服務

3、平臺的工作效率，同時這個模型也可以運用于最優選址、搜索正在執行任務的敵方潛艇等問題，并可將該模型的算法擴展到其他領域。關鍵字：交巡警 最短路徑 最優搜索 動態規劃 floyd算法 1、問題重述交巡警為了更有效地貫徹落實四大職能，需要在市區的交通要道和重要部位設置交巡警服務平臺。在警力、管轄范圍、封鎖能力、搜捕能力等方面有三個基本要求：每個平臺的職能和警力配備基本相同、出現突發事件時能夠及時趕到事發地、一個平臺的警力最多封鎖一個路口。問題1：根據附件中給出的中心城區A的交通網絡圖和現有交巡警服務平臺設置情況，分配各平臺的管轄范圍，使其能在3分鐘內趕到管轄區所在的事發地。問題2：發生重大事件時如何

4、調度A區20個平臺的警力資源，對該區的13條交通要道實現快速封鎖。問題3：根據現有平臺的工作量不均衡和出警時間過長的情況，擬在該區再增加2至5個平臺，確定增加平臺的個數和位置。問題4：分析全市交巡警平臺設置方案的合理性，并改正不合理的地方。問題5：該市P點處發生了重大刑事案件，在案發3分鐘后接到報警，犯罪嫌疑人已經駕車逃跑。調度全市警力，設計最佳的圍堵方案。2、 模型假設1、 警車在出警過程中速度恒為60km/h，不會出現堵車或拋錨等現象。2、 每個路口節點至少有一個交巡警服務平臺管轄。3、 交通網絡圖中兩個節點間的道路視為直線段。4、 每個交巡警服務平臺的職能和警力配備基本相同。3、參數說明

5、：A區節點的橫坐標：A區節點的縱坐標：兩節點間的距離:事發地到交巡警服務平臺的最大距離:交巡警平臺到A區各交通要道的距離：出警時間或者搜捕犯罪嫌疑人的時間 ：犯罪嫌疑人的初始位置：交巡警所在位置 ：初始概率分布函數 ：犯罪嫌疑人逃跑的速度 ：交巡警搜捕到犯罪嫌疑人的概率 ：由搜捕環境所決定的常量 ：拉格朗日乘子:資源（警力，時間）上限：交巡警空間坐標的一個常量pf：最大探測概率4、模型分析及求解通過對題目所給數據的處理，得到中心城區A的每對起點標號和終點標號間的距離。運用這些距離求出每個交巡警服務平臺所管轄的區域，從而為分析交巡警服務平臺設置方案的合理性提供依據。根據逃犯的位置和路徑建立概率密

6、度函數，對交巡警的搜捕區域建立探測函數，最后運用拉格朗日乘數法得到動態規劃的約束條件，用解決動態規劃的方法來制定搜捕犯罪嫌疑人的方案。4.1分配各交巡警服務平臺的管轄范圍中心城區A的每對起點標號和終點標號間的距離在平臺的分配管轄范圍內，出現突發事件，要求交巡警能在3分鐘內到達事發地，且警車時速為60km/h，即平臺到所管轄的每個路口節點的距離不超過3km（地圖上為30mm）。從全市交通路口線路中篩選出中心城區A的所有交通路口，已知每個節點的坐標，由MATLAB程序和兩點間距離公式：S= 公式（11）得到每對起始標號和終點標號間的距離。（見附錄：表一） 建立“覆蓋圓”以交巡警平臺為圓心，以長為3

7、0mm的射線為半徑做一個圓。這個圓面所“覆蓋”的節點即為平臺所管轄的范圍。由matlab程序（見附錄：程序二）和數據統計得到表二：表二 平臺管轄范圍表平臺編號位置標號管轄范圍A11169747576A222434470A3334445666768A444576062636465A5554950515253A666545556575859A7772930323334A8884748A999343537A101010A111111262728A12121225A131313222324A14141421A15151531A16161614363839A171717404142437273A1818

8、18808182838485A1919197779A202020868788899091924.2 警力調度方案本題要求給出該區巡警快速封鎖13條交通要道的方案，由于各平臺到要道的距離不等，故所用的時間也不一樣。由“木桶效應”可知總量取決于最小的一個分量，此題相反：最快封鎖全部要道的時間取決于用時最多的那一組交巡警。因此，總方案應使每一組巡警到交通要道的時間盡量短。根據上一小題我們知道每一組巡警的管轄范圍，故可以首先調度部分交巡警到其所管轄的范圍。由于一個平臺的警力最多封鎖一個路口，但是有的巡警管轄范圍內不止一個要道，所以只能調其附近平臺的警力來封鎖。建立“網格型線路“，以巡警平臺為起點，要道

9、為終點。每兩個點之間用距離公式求解，路線的總長度為各段距離之和，挑選出那些線路距離小的線路。S= 公式（12） 調度方案的關鍵是：調度的警力離始發地距離L最短。最短距離用LINGO程序求解。（見附錄：程序三）調度方案如表三：表三 調度方案表巡警平臺 經歷的路口 要到達的要道 4 16 16 38 8 93536 16 14 14 13 23 12 25 24 11 21 15 28 7 30 29 5 477 30 6 47 48 10 2627 22 9 34102627 124.3在A區增加交巡警平臺統計各交巡警平臺管轄的節點數可得圖一：圖一 平臺管轄節點數平臺A4、 A6、 A17、 A

10、18、 A20管轄的節點都大于7，而平臺A10、 A12 、A14 、A15管轄的節點都小于3，工作量不均衡。節點29、30、60、61、62、90、91、92等的出警時間都超過了3分鐘，出警時間明顯過長。節點30、60、90處出警時間過長并且平臺A4、A6、A20的工作量大，因此可以在節點60、30、90處分別設立一個交巡警平臺，共計增加了3個平臺。4.4 探討現有交巡警服務平臺設置方案的合理性設置交巡警服務平臺的原則和方案具體如下：a.每個交巡警服務平臺的職能和警力配備基本相同；b.管轄范圍內出現突發事件時能夠在3分鐘內有交巡警到達事發地；c.重大突發事件時，全市所有警力要對所有出入市區的

11、交通要道實現快速封鎖；d.每個平臺承擔的工作量應該基本相等。交巡警服務平臺的設置要服從快捷性，該題要求根據設置交巡警服務平臺的原則和任務分析平臺設置的合理性，題中限制條件是：各交巡警服務平臺在所管轄的范圍內出現突發事件時，能在3分鐘內到達事發地。針對此題，可以將全市分為6個區進行分析，具體步驟如下：計算各區交巡警服務平臺在3分鐘內到達事發地的比例： 由于計算距離信息比較容易，所以將時間限制轉化為距離限制，即交巡警服務平臺到事發地的距離在限制的距離內才可能在規定的時間內到達。設事發地到交巡警服務平臺的最大距離為R,該題的速度為60 km/h,則最大距離為：km各區的交巡警服務平臺數和平臺能夠到達

12、的節點已知，可以利用Floyd算法計算3分鐘內交巡警服務平臺能夠到達的各節點的最短距離，將最短距離和3km進行比較，如果最短距離大于3km，則不滿足條件，統計滿足條件的節點，然后將能到達的節點數除以交巡警服務平臺所能到達的所有節點數，得到服務平臺在3分鐘內能到達事發地的比例，根據比例的大小即可以看出交巡警服務平臺設置的合理性（比例越大代表設置得越合理）。 篩選出平臺覆蓋率小于90%的區域： 計算出各區交巡警服務平臺的覆蓋比率，由于不可能都達到100%，所以設置為90%，篩選出比率在90%以下的區域。以及全市交通路口節點數據篩選出發案率大于1.6，但是未設立交巡警平臺的節點（見附錄：表四）統計表

13、四可得各區域發案率大于等于1.6，但是沒有設立交巡警服務平臺的節點個數見圖二：圖二 各區未設平臺節點數由圖二可知：區域A、E某些節點發案率較高但是未設立交巡警服務平臺的節點個數較多，所以在發生突發事件時很難在3分鐘內到達事發地，綜合上述分析可知：交巡警服務平臺設置不合理。 篩選出工作壓力大的區域：根據各個城區的平臺數、面積、人口分析得到平均每個平臺管轄的面積和人口如表五： 表五 平臺工作壓力表全市六個城區平臺個數每個平臺管轄的面積（平方公里）每個平臺管理的人數（萬）A201.103.00B812.882.63C1713.002.89D2614.732.81E1528.805.10F1617.1

14、33.31從表五中可以知道：在全市的六個區中，只有B區設置的平臺個數為一位數，除了A和E區外，其余的四個區域每個平臺管轄的面積都是十幾平方公里，A區每個平臺管轄的面積最少，僅有1.10平方公里，所以A區的交巡警服務平臺的工作強度不大；區域E中每個平臺的管轄面積為28.80平方公里，遠遠大于其他地區，在警力配備基本相同的情況下，倘若發生突發事件，交巡警無法在3分鐘內趕到事發地點。除了區域E外，每個交巡警平臺管理的人數在3萬人左右，只有區域E每個交巡警平臺管理的人數為5.10萬人，相對而言管理的人數就比較多，會導致管理效率降低，發生重大事件時形勢難以控制，這兩個不合理的地方都增加了平臺的工作量 確

15、定需要設置的交巡警服務平臺的個數： 將篩選出的區域分別求解，將交巡警服務平臺在3分鐘內到達事發地的比例限制在90%，然后利用Matlab計算出滿足條件的各區的最少平臺數，用最少平臺數減去各自區域所設置的平臺數得到的值即是各區所需要設置的平臺個數。4.5 追捕犯罪嫌疑人的最佳圍堵方案本問是“最優搜索”問題中的“雙邊搜索”，逃犯企圖逃避被發現，甚至反擊交巡警。最優搜索問題包括三個基本要素：其一、犯罪嫌疑人位置和移動路徑的初始概率分布。其二、探測函數。假定犯罪嫌疑人確實位于某個區域，則將投入這個區域搜索的資源（如時間）與成功搜索到目標的概率之間的函數關系建立成為探測函數。其三，對時間警力的約束條件。

16、搜索不可能無休止的進行下去，搜索的時間、人力資源都是受到限制的。給定探索函數和目標函數的概率分布后，最優搜索理論要解決的核心問題就是在各平臺警力和配備一定的情況下，如何分配警力資源使得成功搜索到犯罪嫌疑人的可能性最大，或搜索代價最小。利用以上搜索理論進行問題優化的關鍵是建立合理的數學模型：概率密度函數已知犯罪嫌疑人位于空間Rn的某個子集A中，它的初始位置用向量X表示，各交巡警平臺的初始位置用向量Z表示： 公式（13） 通常情況下，這個向量不能準確給出，為了描述逃犯位置的不確定性，我們用初始概率分布函數表示，定義如下： 公式（14） 概率密度函數定義如下： 公式（15） 探測函數探索問題的第二個

17、要素是探測函數。探測函數給出將投入到整個城區的時間與給定犯罪嫌疑人位于該區域時成功探測到該逃犯的可能性大小聯系起來的函數關系。探測函數是指逃犯落在某一區域內，交巡警在該區域上進行搜索后發現犯罪嫌疑人的概率，用函數b表示，。這里的假設條件是探測到犯罪嫌疑人的概率僅與分配的警力有關，與分配的方式無關。在離散搜索空間中有： 公式（16）探測函數是搜索問題中的一個基本要素，我們運用視覺探測模型如圖三：OhSab圖三 探測模型示意圖假設犯罪嫌疑人位于平面上的X點，交巡警的位置在空間Z點處，探測函數b與嫌疑人所在平面和交巡警與目標位置所在直線的立體角成正比例。即： 公式（17）其中k是一個由搜索環境所決定

18、的常量。如圖32，當a, b的值相對于h, r, s非常小時，立體視覺可以定義為之積。 公式（18）因為是嫌疑人與交巡警在平面的投影距離，且在一般情況下有，因此有： 公式（19）所以該模型被稱為探測法則。 用拉格朗日乘數法用于解決任意目標函數min(t)在任意實數集上的帶約束的問題，按照前面的定義： 公式（110）得到最大探測概率pf且滿足約束條件： 公式（111）其中K是資源（警力，時間）上限。構造拉格朗日函數l如下： 公式（112）其中叫做拉格朗日乘子，它是一個參數。交巡警要想成功抓獲嫌疑人必須滿足一下約束條件： 公式（113） 利用附件的數據及以上模型分析可得：A區與D、C、F、E區鄰接

19、。固嫌疑犯只能向D、C、E、F四個方向逃去。在A區去往E的道路上設置了多處交巡警服務平臺，且與P點相距很近，固不能逃亡E區。由A區通往E區、F區各有兩條路，均在離P很近的敵方設有平臺。嫌犯唯一能夠逃離A區的路徑只能是C區，由于3分鐘后才接到報警，故嫌疑犯能夠騙過他附近的交巡警平臺進入到C區，最后很可能從237號節點逃走。所以應該盡可能的多調集警力到C區增援。5、模型評價但總的來說，整個模型的思路清晰，遵循了可操作性原則、科學性原則、可比性原則，該模型建立了在較理想狀態下交巡警服務平臺的最優設置，減少了出警時間，提高了出警效率，可以給生活中交巡警平臺的設立一些參考，具有一定的實用價值。另外還設計

20、了一套搜捕犯罪嫌疑人的方案，可使交巡警在接到任務后更好的在較短時間分配救援力量，選擇最佳行進路徑，以爭取更多的時間執行任務，取得更好的執行效果。6、模型應用本模型較好地解決了公交司機排班的最優化問題。隨著南昌市經濟的迅速發展，人口增加人流量增大，公交線路的正常運營時暢通城市的有力保障。該模型也可以運用到其他優化問題中去，比如：酒店、百貨公司工作人員的排班問題，某些人力、物力資源的合理配置問題等。本模型較好的解決了交巡警平臺的最佳選址問題，當事故發生時，交巡警可以在第一時間到達事發地點，有效的改善了交巡警在執行任務中的效率。在經濟迅猛發展的今天，城市加速擴展，人口迅速增長，交巡警平臺的設置是平安

21、城市的最好保障，該模型也可以運用到其他最優選址問題中去，比如：關于消防救援工作最優路徑問題、重大生產安全事故應急救援問題、公共交通的最優路徑問題、工廠假設最優選址問題等。搜捕犯罪嫌疑人的模型也可以用于其他領域。對靜止目標的搜索，如搜索沉落海洋的失事傳播、搜索工廠污染源；對機動目標的搜索，即搜索目標的運動規律對搜索者是可知的，并不是不變的，如搜索在海上迷失方向的船舶；對規避目標的搜索：被搜索目標企圖逃跑避免被發現，甚至反擊搜索者，搜索者與被搜索目標之間是敵意的、非合作的、雙方是搜索與逃避的關系，如搜索正在執行任務的敵方潛艇。7、參考文獻【1】韓中庚，數學建模方法及其應用，北京：高等教育出版社，2010年11月。【2】楊啟帆、何勇、談之奕，數學建模競賽，浙江：浙江大學出版社，2005年7月。【3】趙靜、但琦，數學建模與數學實驗，北京：高等教育出版社，2003年6月。【4】曹吉利、張東生、趙臨龍，數學模型方法及其應用，重慶：重慶大學出版社，2005年3月 【5】肖華勇，基于MATLAB和LINGO的數學實驗，西安：西北工業大學出版社，2009年3月附錄表1：發案率大于1.6但是未設立交巡警服務平臺的