數(shù)學(xué)建模 最短路程

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

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

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

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

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

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

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

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

9、為終點。每兩個點之間用距離公式求解，路線的總長度為各段距離之和，挑選出那些線路距離小的線路。S= 公式（12） 調(diào)度方案的關(guān)鍵是：調(diào)度的警力離始發(fā)地距離L最短。最短距離用LINGO程序求解。（見附錄：程序三）調(diào)度方案如表三：表三 調(diào)度方案表巡警平臺 經(jīng)歷的路口 要到達(dá)的要道 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區(qū)增加交巡警平臺統(tǒng)計各交巡警平臺管轄的節(jié)點數(shù)可得圖一：圖一 平臺管轄節(jié)點數(shù)平臺A4、 A6、 A17、 A

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

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

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

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

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

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

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

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

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

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

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

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