交巡警服務平臺的設置與調(diào)度B題

1、全國大學生數(shù)學建模競賽承諾書我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的,如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C/D 中選擇一項填寫）： B我們的參賽報名號為（如果賽區(qū)設置報名號的話）：所屬學校

2、（請?zhí)顚懲暾娜何鞅贝髮W參賽隊員 (打印并簽名 )：1.張舒岱2.劉羽3.張成悟指導教師或指導教師組負責人(打印并簽名 )：日期：2014年 8月 10日全國大學生數(shù)學建模競賽編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：交巡警服務平臺的設置與調(diào)度摘要交巡警服務平臺位置的選取以及劃分交巡警服務平臺的管轄范圍對于處理突發(fā)事件有非常大的影響?，F(xiàn)階段，一般依據(jù)經(jīng)驗選取服務平臺位置及劃分管轄區(qū)域。所以如何科學合理處理的交巡警服務平臺的設置與調(diào)度問題具有

3、十分重要的現(xiàn)實意義。本文研究了交巡警服務平臺的設置與調(diào)度問題。具體討論了在給定的區(qū)域A 內(nèi)，如何合理的設置交巡警服務平臺的管轄區(qū)域；發(fā)生特殊事件時應如何調(diào)動服務平臺警力以快速封鎖區(qū)域A；應該增加多少數(shù)量交巡警服務平臺以及在哪個位置增加。本文建立最短路模型、 0-1 整數(shù)規(guī)劃模型，利用MATLAB 軟件解決了分配各平臺管轄范圍、調(diào)度警務資源以及合理設置交巡警服務平臺這三個方面的問題。在解決分配各平臺管轄范圍問題時，本文建立了最短路模型。通過求解各個路口到交巡警平臺的距離是否滿足最低時間限制，解決交巡警服務平臺分配管轄范圍的問題。本文在MATLAB 軟件上運用 Dijkstra 算法進行求解，給出

4、了中心城區(qū) A 的 20 個服務平臺的管轄范圍，并求得到達最近的交巡警服務平臺的時間超過 3 分鐘的 6 個路口。在解決調(diào)度警務資源快速封鎖城區(qū)的問題時，本文建立了0-1整數(shù)規(guī)劃模型。以封鎖城區(qū)所用時間最少為限制條件，利用lingo軟件編程求解，給出了該區(qū)交巡警服務平臺警力合理的調(diào)度方案，并求得對13 個交通要道實現(xiàn)全封鎖最短需要 8.01 分鐘。在解決交巡警服務平臺的選址問題時，本文建立了雙目標0-1整數(shù)規(guī)劃模型。考慮到建設新的服務平臺需要投入更多的成本和警務資源，還需平衡各個服務平臺的工作量。因此，以增加服務平臺數(shù)最小和服務平臺工作量方差最小為目標，建立了雙目標 0-1 整數(shù)規(guī)劃模型。解出

5、增加的服務平臺數(shù)為4 個，新增的服務平臺具體位置為 A29,A39,A48,A88 。本文所提供的模型考慮到均衡各個交巡警服務平臺的工作量和新建服務臺的成本，使結(jié)果更加合理符合需求，可以推廣到任何一個市區(qū)甚至更廣范圍內(nèi)的交巡警服務平臺的設置與調(diào)度問題的解決中。也可以廣泛應用于社區(qū)衛(wèi)生室、公共衛(wèi)生間、消防救火中心等社會服務部門的選址問題，對實際有指導意義。關鍵詞： Dijkstra 算法雙目標 0-1 整數(shù)規(guī)劃模型 Lingo編程一、問題重述“有困難找警察”，是家喻戶曉的一句流行語。警察肩負著刑事執(zhí)法、治安管理、交通管理、服務群眾四大職能。為了更有效地貫徹實施這些職能，需要在市區(qū)的一些交通要道和

6、重要部位設置交巡警服務平臺。每個交巡警服務平臺的職能和警力配備基本相同。由于警務資源是有限的，如何根據(jù)城市的實際情況與需求合理地設置交巡警服務平臺、分配各平臺的管轄范圍、調(diào)度警務資源是警務部門面臨的一個實際課題。試就某市設置交巡警服務平臺的相關情況，建立數(shù)學模型分析研究下面的問題：附件 1 中的附圖 1 給出了該市中心城區(qū)A 的交通網(wǎng)絡和現(xiàn)有的20 個交巡警服務平臺的設置情況示意圖，相關的數(shù)據(jù)信息見附件2。請為各交巡警服務平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3 分鐘內(nèi)有交巡警（警車的時速為60km/h）到達事發(fā)地。對于重大突發(fā)事件，需要調(diào)度全區(qū)20 個交巡警服務平臺的

7、警力資源，對進出該區(qū)的 13 條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警服務平臺警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警服務平臺的工作量不均衡和有些地方出警時間過長的實際情況，擬在該區(qū)內(nèi)再增加2 至 5 個平臺，請確定需要增加平臺的具體個數(shù)和位置。二、模型假設（ 1）每個交巡警服務平臺的職能和警力配備基本相同；（ 2）警車的行駛速度恒定，不考慮實際交通狀況的影響；（ 3）交巡警服務平臺接到報警后能立即出警，中間沒有延誤；（ 4）每個節(jié)點只能被一個服務平臺管轄；（ 5）一個平臺的警力最多封鎖一個路口。三、符號說明賦權(quán)連通圖頂點 i 到頂點 j 的距離頂點 i 到頂

8、點 j 的距離0-1 整型變量第 i 個交巡警服務平臺調(diào)度到第j 個交通路口的情況；封鎖要道所需時間最長的服務平臺的出警時間中心城區(qū) A 的第 j 個交叉路口節(jié)點的發(fā)案率；第 i 個交巡警服務平臺到第 j 個交通路口的最短距離距離的偏差限四、問題分析交巡警服務平臺位置的選取以及劃分交巡警服務平臺的管轄范圍是一件非常重要的事情。由于種種原因，現(xiàn)在交巡警服務平臺的選址及管轄區(qū)域劃分大多根據(jù)經(jīng)驗進行。缺乏科學系統(tǒng)的位置選取與管轄區(qū)劃分，造成了警務資源浪費、突發(fā)事件處理不及時等多種問題。另外，警務資源是有限的，設置交巡警服務平臺也要耗費大量的資源。所以如何科學的規(guī)劃管轄區(qū)，合理的設立新的交巡警服務平臺

9、具有重大的意義。本文意在根據(jù)現(xiàn)有的城區(qū)道路圖與交巡警服務平臺位置，根據(jù)到達突發(fā)事件地點使用時間最少原則進行交巡警服務平臺管轄范圍劃分，根據(jù)使用資金盡量少及各交巡警服務平臺的工作量盡量一致的原則設立新的交巡警服務平臺。在問題一中有三個子問題需要解決。（1）要對 20 個交巡警服務平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3 分鐘內(nèi)有交巡警（警車的時速為60km/h ）到達事發(fā)地。即計算各交巡警服務平臺與各個地點的距離。將巡警在3 分鐘內(nèi)到達事發(fā)地轉(zhuǎn)化為交巡警服務平臺距離事發(fā)地距離不超過3km。這是典型的最短路模型。對于這個問題，我們采用Dijkstra 算法。（2）當重大突發(fā)

10、事件發(fā)生后，要對中心城區(qū)A 的 20 個交巡警服務平臺的警力資源進行調(diào)度，對進出該區(qū)的13 條交通要道實現(xiàn)快速全封鎖，其關鍵在于合理調(diào)度警務資源使得封鎖全部要道所需的總時間達到最小，也就是使得出警時間最長的服務平臺所需的時間盡可能的小。實際中一個平臺的警力最多封鎖一個路口，給出該區(qū)交巡警服務平臺警力合理的調(diào)度方案，我們采用0-1 模型進行求解，給出該區(qū)交巡警服務平臺警力合理的調(diào)度方案。（3）針對現(xiàn)有的中心城區(qū)A 的 20 個交巡警服務平臺進行分析后，需要新增加 25 個服務平臺以解決工作量不平衡和部分路口節(jié)點出警時間過長的問題。這屬于交巡警服務平臺選址問題。一方面考慮采用集合覆蓋模型，目的是在

11、滿足所有節(jié)點3 分鐘內(nèi)都有警方到達的條件下，使新增設的服務平臺數(shù)目盡可能得小，從而降低了建設成本。另一方面也要考慮新增設服務平臺后，能夠解決服務平臺工作量不平衡的問題，所以把盡可能均衡各個服務平臺工作量作為第二個目標。因此考慮需要建立一個兩目標的0-1 整數(shù)規(guī)劃模型。五、模型的建立和求解問題 1.1 A 區(qū)交巡警服務平臺管轄范圍的分配為各交巡警服務平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在 3 分鐘內(nèi)有交巡警（警車的時速為60km/h ）到達事發(fā)地。即計算各交巡警服務平臺與各個地點的距離。將巡警在3 分鐘內(nèi)到達事發(fā)地轉(zhuǎn)化為交巡警服務平臺距離事發(fā)地距離不超過3km。我們建立最

12、短路模型：t3min ， sv t ， v60km / h即求出離每個地點距離最短的交巡警服務平臺，將這個地點分配給距離最短的交巡警平臺管轄。如何求每個地點之間的距離，我們運用了MATLAB 軟件中的最短路函數(shù)“ graphallshortestpaths （） ”函數(shù)。將題目附件中各節(jié)點坐標轉(zhuǎn)化為矩陣，進而建立稀疏矩陣，然后利用最短路函數(shù)提取出符合3分鐘路程要求的矩陣，最后進行整理，即可得所求。模型的求解：先用 Dijkstra 算法求解出各交巡警服務平臺到各個路口節(jié)點的最短距離，利用 MATLAB 軟件進行運算（運算程序見附件一），代入數(shù)據(jù), 求得管轄范圍如下：表一 A 區(qū)各服務平臺的管轄

13、范圍服務平臺節(jié)點編號管轄的節(jié)點11、 42、44、 79、8022、66、74、75、76、 7833、43、54、55、68、 7044、57、58、60、62、 6355、49、 5366、48、 50、51、 52、56、5977、30、 3488、35、36、37、 47、99、3210101111、25、26、2712121313、21、22、23、 2414141515、311616、33、45、461717、40、411818、71、72、 77、84、85、87、88、 89、911919、64、 65、67、69、73、82、 832020、81、86（原始表格見附件二）把出

14、警時間不超過3 分鐘，轉(zhuǎn)化為服務平臺距離所管轄的路口距離不超過3 千米。由此檢驗得六個路口（28，29， 38，39，61， 92）不滿足出警時間要求。到達最近的交巡警服務平臺的時間超過3分鐘的 6個路口如下表：路口標號282938396192歸屬標號1515162720距離47.58150.00534.05936.82241.90236.013問題 1.2 A 區(qū)交巡警服務平臺警力調(diào)度方案對于重大突發(fā)事件，需要調(diào)度全區(qū)20 個交巡警服務平臺的警力資源，對進出該區(qū)的 13 條交通要道實現(xiàn)快速全封鎖。要求得該如何分配警力資源封鎖路口我們使用 0-1 整數(shù)規(guī)劃模型。設 xij 表示第 i 個交巡警

15、服務平臺調(diào)度到第j 個交通路口的情況，即：其中根據(jù)對問題的分析，要實現(xiàn)對要道的快速全封鎖，所以模型的目標是使封鎖所有要道的總時間最短，其關鍵在于控制封鎖要道所需時間最長的服務平臺的出警時間，使之達到最小值。設表示封鎖要道所需時間最長的服務平臺的出警時間Aij 表示 20 個交警平臺到 13 個交通路口的距離封鎖要道所需時間最長的服務平臺的出警時間最短：min；在 13 個交通路口上，每個路口都必須有一個交巡警：20xij1j1.13 ；i 1每個交巡警服務平臺至多只能去一個路口：13xij1i1.20；j1每個交巡警到達路口的距離均小于最后一個到達路口的交警平臺與該路口的距離：xijAiji

16、1.20j 1.13 。建立模型如下：目標函數(shù)： min;20xij1j1.13i 113st. ：xij1i1.20j1xijAiji 1.20j1.13模型的求解：我們利用 lingo軟件進行目標函數(shù)的求解。主程序如下：（具體程序見附件三）由程序結(jié)果可得如下表格：封鎖方案表格距離節(jié)點走向時間距離節(jié)點走向時間（ km（m）（ km（ m）2.476482.472.608162.603.105303.105.409105.408.01.7298.017.7010227.704.7015 284.703.8011243.803.982383.986.7416146.740.354620.353.

17、2614213.26012120下圖是所求得各巡邏點到個路口的時間表：取其中的最大值為8.01546. 故控制封鎖要道所需時間最短約為8.01 分鐘。問題 1.3 擬增 A 區(qū)交巡警服務平臺對于擬增 A 區(qū)交巡警服務平臺，首先分析現(xiàn)有的交巡警服務平臺的分布，發(fā)現(xiàn)存在交巡警服務平臺工作量不均衡和部分交通路口出警時間過長的問題。這就要求新增加幾個服務平臺后，使得各個交巡警服務平臺的工作量盡可能相同以及使各個交通路口出警時間都被控制在 3 分鐘內(nèi)。新建服務平臺需要成本，所以需要合理確定服務平臺的選址，使需要建立的服務平臺的數(shù)目最小。由此，我們參考集合覆蓋模型（在一定的區(qū)域內(nèi)，設置最小數(shù)量的設施來覆蓋

18、其中所有的點），建立了一個兩目標0-1 整數(shù)規(guī)劃模型。（見附件四）目標函數(shù)：約束條件：(i=1,2,92 j =1,2,92)92且 x jj 122j 1x jj25每個交通路口都有一個平臺管轄：所有平臺到其所管轄的交通路口最短距離中的最大值不超過距離偏差a ,即各個交通路口出警時間都被控制在3 分鐘內(nèi)：max(dij * xij )a(i=1,2,92j=1,2,92)模型的求解：第三個子問題所建立的是雙目標的0-1 整數(shù)規(guī)劃模型，第一目標為增加的服務平臺最少，第二目標為各個服務平臺每天的服務強度方差最小。為了求解模型，先只考慮第一目標，然后再在第一目標最優(yōu)的情況下給出第二目標最優(yōu)的解。在

19、 lingo 軟件中運行程序，從 24 至 30 范圍內(nèi)取出若干個偏差限與所對應的目標函數(shù)值。由結(jié)果，增加 5 個平臺，標號與坐標分別為：29（246,337 ）;39 （ 371,333 ） ;48 （ 315,374 ） ;51 （348.5,380.5 ）;88（444.5,383 ）由于該模型發(fā)案率的均衡性不是很好，增加的5 個平臺不一定是劃分A 區(qū)的最優(yōu)解。因此要進行進一步的分析處理。將25 個平臺代入 1.1 的模型中，與原 A 區(qū)的劃分結(jié)果相比較（以 dij >30 的節(jié)點個數(shù)的多少為標準），逐個去掉平臺個數(shù)，再重復以上操作，最終得出結(jié)果。使用和求 A 區(qū)偏差限相同的方法分

20、別確定增加5 個平臺、 4 個平臺、 3 個平臺時的偏差限，即最好均衡性分別為1.9 、1.85 、 1.85 ，并設計表格進行對比，表格如下：增加的點數(shù)均衡性最優(yōu)解時間超過 3 分鐘的路口數(shù)增加的平臺51.9886.25545293948518841.85954.690942939488831.851170.1714293948權(quán)衡均衡性、最優(yōu)解及增加點個數(shù)所需花費的資源，增加四個點數(shù)是最節(jié)省資源且效果最好的。故：交巡警服務平臺增加四個，它們分別為：A29A39A48A88六、模型的評價6.1 模型的優(yōu)點：（ 1）對于問題一的第一個子問題：題目規(guī)定以最短時間為目標，可轉(zhuǎn)化為最短距離不超過 3

21、km?？墒菍τ谟幸恍┕?jié)點，無論怎樣安排都不能達到警方到達事故現(xiàn)場為 3 分鐘之內(nèi)。我們對于這些節(jié)點單獨處理，并根據(jù)已知條件計算出這幾個節(jié)點應該屬于哪個交巡警服務平臺。（ 2）對于問題一的第三個子問題：該問題要求確定增加2-5 個交巡警服務平臺的方案。一方面，根據(jù)限制條件，巡警到達其管轄節(jié)點應在3 分鐘之內(nèi)。另一方面，應平均合理安排各個交巡警服務平臺的工作量，不至于出現(xiàn)某個服務平臺工作量過大而某個平臺工作量過小的情況。6.2 模型的缺點：對于問題一的第一個子問題，建立的模型目標單一，并沒有考慮到各個服務平臺交巡警工作梁的不均衡性。在分配結(jié)果中可以看到，部分交巡警的工作量很小而部分交巡警的工作量很

22、大。這顯然是不合理的。事實上，可以建立一個多目標規(guī)劃問題，以交巡警到達事故現(xiàn)場和工作量的方差為目標，使得分配管轄范圍的方案更加合理。七、模型的推廣本文所提供的模型可以推廣到任何一個市區(qū)甚至更廣范圍內(nèi)的交巡警服務平臺的設置與調(diào)度問題的解決中。也可以廣泛應用于社區(qū)衛(wèi)生室、公共衛(wèi)生間、消防救火中心等社會服務部門的選址問題。在實際運用中有很高的實用性及通用性。八、參考文獻1 殷代君，廣義最大覆蓋模型在應急設施選址中的應用研究，中外企業(yè)家，2010 年第 3 期： 169-170,2010 。2 卓金武， MATLAB在數(shù)學建模中的應用，北京：北京航空航天大學出版社，2011。3 韓中庚，數(shù)學建模方法及

23、其應用，北京：高等教育出版社，2009。4 謝金星，薛毅，優(yōu)化建模與lingo軟件，北京：清華大學出版社，2005。附件一：functionlist,AdjMatrix,distance=getList()edge=csvread('edge.csv');range=size(edge);%刪除非 A區(qū)的邊f(xié)ori=range:-1:1if(edge(i,1)>92)|(edge(i,2)>92)edge(i,:)=;endendnode=csvread('node.csv');S=edge(:,1);%起點向量E=edge(:,2);%終點向量ra

24、nge=size(S);W=zeros(range,1);%權(quán)向量fori=1:1:rangea=node(S(i,1),1),node(S(i,1),2);b=node(E(i,1),1),node(E(i,1),2);distance=norm(a-b);W(i,1)=distance;end%建立稀疏矩陣AdjMatrix=sparse(S;E,E;S,W;W,92,92);%求最短路徑矩陣distance=graphallshortestpaths(AdjMatrix,'directed',false);%提取出符合 3 分鐘路程要求的矩陣A=distance(1:20

25、,21:92);rangeI,rangeJ=size(A);fori=1:1:rangeIforj=1:1:rangeJifA(i,j)>30A(i,j)=NaN;endendend%整理list=zeros(72,1);fori=1:1:72Max=0;R=NaN;forj=1:1:20ifA(j,i)>MaxMax=A(j,i);R=j;endendlist(i,1)=R;endT=linspace(1,20,20)'list=T;list;end附件三：title0-1;sets:p/1.13/:a;l/1.20/:b;link(l,p):c,d;endsetsdat

26、a:d=222.36,160.28,92.87,192.93,210.96,225.02,228.93,190.01,195.16,120.83,58.81,118.50,48.85,204.64,141.30,73.88,173.95,191.97,206.03,211.21,172.29,177.44,103.11,39.82,103.10,60.35,183.52,127.67,60.26,160.32,178.35,192.41,190.09,151.17,156.32,82.00,60.94,81.98,43.93,219.97,150.09,82.67,182.73,200.76,

27、214.82,226.54,162.27,155.35,81.03,48.61,73.96,3.50,176.28,129.70,62.28,162.35,177.50,191.55,182.85,113.07,106.15,31.83,94.21,24.76,52.55,176.59,130.00,62.59,162.65,177.80,191.86,183.16,113.37,106.46,32.14,94.52,25.06,53.37,149.15,109.01,41.60,141.66,150.36,164.42,155.72,85.70,80.15,5.83,73.53,12.90,

28、79.92,140.93,94.34,26.92,126.99,142.14,156.19,147.50,102.28,104.93,30.61,58.85,30.99,86.77,130.11,82.74,15.33,115.39,131.32,145.38,136.68,97.76,107.24,34.92,47.26,41.99,93.37,75.87,127.76,69.57,95.11,77.08,91.13,82.44,141.95,151.44,79.11,101.50 ,86.19,147.61,37.91,83.37,113.95,50.72,32.70,46.75,38.0

29、5,186.33,195.82,123.50,145.88,130.57,191.99,0.00,119.50,145.43,86.85,68.83,64.77,35.92,217.81,227.30,154.98,177.36,162.05,223.47,59.77,59.73,127.15,27.08,9.06,5.00,23.85,228.08,237.57,165.25,161.21,172.32,213.32,119.50,0.00,67.42,32.65,50.68,64.73,83.59,180.50,189.17,114.84,101.48 ,121.91,153.59,170.30,132.98,65.56,165.63,171.51,185.56,176.87,47.52,57.01,44.01,97.50,51.09,118.10,145.43,67.42,0.00,100.07,118.09,