交巡警服務(wù)平臺的設(shè)置及調(diào)度 11年B題

-.z.全國大學(xué)生數(shù)學(xué)建模競賽承諾書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開場后參賽隊(duì)員不能以任何方式〔包括、電子、網(wǎng)上咨詢等〕與隊(duì)外的任何人〔包括指導(dǎo)教師〕研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的,如果引用別人的成果或其他公開的資料〔包括網(wǎng)上查到的資料〕，必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是〔從A/B/C/D中選擇一項(xiàng)填寫〕：B 我們的參賽報(bào)名號為〔如果賽區(qū)設(shè)置報(bào)名號的話〕：所屬學(xué)校〔請?zhí)顚懲暾娜常何鞅贝髮W(xué)參賽隊(duì)員(打印并簽名)：1.舒岱2.羽3.成悟指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人(打印并簽名)：日期：2014年8月10日全國大學(xué)生數(shù)學(xué)建模競賽編號專用頁賽區(qū)評閱編號〔由賽區(qū)組委會評閱前進(jìn)展編號〕：賽區(qū)評閱記錄〔可供賽區(qū)評閱時使用〕：評閱人評分備注全國統(tǒng)一編號〔由賽區(qū)組委會送交全國前編號〕：全國評閱編號〔由全國組委會評閱前進(jìn)展編號〕：-.z.交巡警效勞平臺的設(shè)置與調(diào)度摘要交巡警效勞平臺位置的選取以及劃分交巡警效勞平臺的管轄圍對于處理突發(fā)事件有非常大的影響?，F(xiàn)階段，一般依據(jù)經(jīng)歷選取效勞平臺位置及劃分管轄區(qū)域。所以如何科學(xué)合理處理的交巡警效勞平臺的設(shè)置與調(diào)度問題具有十分重要的現(xiàn)實(shí)意義。本文研究了交巡警效勞平臺的設(shè)置與調(diào)度問題。具體討論了在給定的區(qū)域A，如何合理的設(shè)置交巡警效勞平臺的管轄區(qū)域；發(fā)生特殊事件時應(yīng)如何調(diào)動效勞平臺警力以快速封鎖區(qū)域A；應(yīng)該增加多少數(shù)量交巡警效勞平臺以及在哪個位置增加。本文建立最短路模型、0-1整數(shù)規(guī)劃模型，利用軟件解決了分配各平臺管轄圍、調(diào)度警務(wù)資源以及合理設(shè)置交巡警效勞平臺這三個方面的問題。在解決分配各平臺管轄圍問題時，本文建立了最短路模型。通過求解各個路口到交巡警平臺的距離是否滿足最低時間限制，解決交巡警效勞平臺分配管轄圍的問題。本文在軟件上運(yùn)用算法進(jìn)展求解，給出了中心城區(qū)A的20個效勞平臺的管轄圍，并求得到達(dá)最近的交巡警效勞平臺的時間超過3分鐘的6個路口。在解決調(diào)度警務(wù)資源快速封鎖城區(qū)的問題時，本文建立了0-1整數(shù)規(guī)劃模型。以封鎖城區(qū)所用時間最少為限制條件，利用lingo軟件編程求解，給出了該區(qū)交巡警效勞平臺警力合理的調(diào)度方案，并求得對13個交通要道實(shí)現(xiàn)全封鎖最短需要8.01分鐘。在解決交巡警效勞平臺的選址問題時，本文建立了雙目標(biāo)0-1整數(shù)規(guī)劃模型?？紤]到建立新的效勞平臺需要投入更多的本錢和警務(wù)資源，還需平衡各個效勞平臺的工作量。因此，以增加效勞平臺數(shù)最小和效勞平臺工作量方差最小為目標(biāo)，建立了雙目標(biāo)0-1整數(shù)規(guī)劃模型。解出增加的效勞平臺數(shù)為4個，新增的效勞平臺具體位置為A29,A39,A48,A88。本文所提供的模型考慮到均衡各個交巡警效勞平臺的工作量和新建效勞臺的本錢，使結(jié)果更加合理符合需求，可以推廣到任何一個市區(qū)甚至更廣圍的交巡警效勞平臺的設(shè)置與調(diào)度問題的解決中。也可以廣泛應(yīng)用于社區(qū)衛(wèi)生室、公共衛(wèi)生間、消防救火中心等社會效勞部門的選址問題，對實(shí)際有指導(dǎo)意義。關(guān)鍵詞：Dijkstra算法雙目標(biāo)0-1整數(shù)規(guī)劃模型Lingo編程

一、問題重述“有困難找警察〞，是家喻戶曉的一句流行語。警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、效勞群眾四大職能。為了更有效地貫徹實(shí)施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警效勞平臺。每個交巡警效勞平臺的職能和警力配備根本一樣。由于警務(wù)資源是有限的，如何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警效勞平臺、分配各平臺的管轄圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個實(shí)際課題。試就*市設(shè)置交巡警效勞平臺的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問題：1中的附圖1給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個交巡警效勞平臺的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見2。請為各交巡警效勞平臺分配管轄圍，使其在所管轄的圍出現(xiàn)突發(fā)事件時，盡量能在3分鐘有交巡警〔警車的時速為60km/h〕到達(dá)事發(fā)地。對于重大突發(fā)事件，需要調(diào)度全區(qū)20個交巡警效勞平臺的警力資源，對進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警效勞平臺警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警效勞平臺的工作量不均衡和有些地方出警時間過長的實(shí)際情況，擬在該區(qū)再增加2至5個平臺，請確定需要增加平臺的具體個數(shù)和位置。模型假設(shè)〔1〕每個交巡警效勞平臺的職能和警力配備根本一樣；〔2〕警車的行駛速度恒定，不考慮實(shí)際交通狀況的影響；〔3〕交巡警效勞平臺接到報(bào)警后能立即出警，中間沒有延誤；〔4〕每個節(jié)點(diǎn)只能被一個效勞平臺管轄；〔5〕一個平臺的警力最多封鎖一個路口。三、符號說明賦權(quán)連通圖頂點(diǎn)i到頂點(diǎn)j的距離頂點(diǎn)i到頂點(diǎn)j的距離0-1整型變量第i個交巡警效勞平臺調(diào)度到第j個交通路口的情況；封鎖要道所需時間最長的效勞平臺的出警時間中心城區(qū)A的第個穿插路口節(jié)點(diǎn)的發(fā)案率；第i個交巡警效勞平臺到第j個交通路口的最短距離距離的偏差限四、問題分析交巡警效勞平臺位置的選取以及劃分交巡警效勞平臺的管轄圍是一件非常重要的事情。由于種種原因，現(xiàn)在交巡警效勞平臺的選址及管轄區(qū)域劃分大多根據(jù)經(jīng)歷進(jìn)展。缺乏科學(xué)系統(tǒng)的位置選取與管轄區(qū)劃分，造成了警務(wù)資源浪費(fèi)、突發(fā)事件處理不及時等多種問題。另外，警務(wù)資源是有限的，設(shè)置交巡警效勞平臺也要消耗大量的資源。所以如何科學(xué)的規(guī)劃管轄區(qū)，合理的設(shè)立新的交巡警效勞平臺具有重大的意義。本文意在根據(jù)現(xiàn)有的城區(qū)道路圖與交巡警效勞平臺位置，根據(jù)到達(dá)突發(fā)事件地點(diǎn)使用時間最少原則進(jìn)展交巡警效勞平臺管轄圍劃分，根據(jù)使用資金盡量少及各交巡警效勞平臺的工作量盡量一致的原則設(shè)立新的交巡警效勞平臺。在問題一中有三個子問題需要解決。要對20個交巡警效勞平臺分配管轄圍，使其在所管轄的圍出現(xiàn)突發(fā)事件時，盡量能在3分鐘有交巡警〔警車的時速為60km/h〕到達(dá)事發(fā)地。即計(jì)算各交巡警效勞平臺與各個地點(diǎn)的距離。將巡警在3分鐘到達(dá)事發(fā)地轉(zhuǎn)化為交巡警效勞平臺距離事發(fā)地距離不超過3km。這是典型的最短路模型。對于這個問題，我們采用算法。當(dāng)重大突發(fā)事件發(fā)生后，要對中心城區(qū)A的20個交巡警效勞平臺的警力資源進(jìn)展調(diào)度，對進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖，其關(guān)鍵在于合理調(diào)度警務(wù)資源使得封鎖全部要道所需的總時間到達(dá)最小，也就是使得出警時間最長的效勞平臺所需的時間盡可能的小。實(shí)際中一個平臺的警力最多封鎖一個路口，給出該區(qū)交巡警效勞平臺警力合理的調(diào)度方案，我們采用0-1模型進(jìn)展求解，給出該區(qū)交巡警效勞平臺警力合理的調(diào)度方案。針對現(xiàn)有的中心城區(qū)A的20個交巡警效勞平臺進(jìn)展分析后，需要新增加2~5個效勞平臺以解決工作量不平衡和局部路口節(jié)點(diǎn)出警時間過長的問題。這屬于交巡警效勞平臺選址問題。一方面考慮采用集合覆蓋模型，目的是在滿足所有節(jié)點(diǎn)3分鐘都有警方到達(dá)的條件下，使新增設(shè)的效勞平臺數(shù)目盡可能得小，從而降低了建立本錢。另一方面也要考慮新增設(shè)效勞平臺后，能夠解決效勞平臺工作量不平衡的問題，所以把盡可能均衡各個效勞平臺工作量作為第二個目標(biāo)。因此考慮需要建立一個兩目標(biāo)的0-1整數(shù)規(guī)劃模型。五、模型的建立和求解問題1.1——A區(qū)交巡警效勞平臺管轄圍的分配為各交巡警效勞平臺分配管轄圍，使其在所管轄的圍出現(xiàn)突發(fā)事件時，盡量能在3分鐘有交巡警〔警車的時速為60km/h〕到達(dá)事發(fā)地。即計(jì)算各交巡警效勞平臺與各個地點(diǎn)的距離。將巡警在3分鐘到達(dá)事發(fā)地轉(zhuǎn)化為交巡警效勞平臺距離事發(fā)地距離不超過3km。我們建立最短路模型：，，即求出離每個地點(diǎn)距離最短的交巡警效勞平臺，將這個地點(diǎn)分配給距離最短的交巡警平臺管轄。如何求每個地點(diǎn)之間的距離，我們運(yùn)用了軟件中的最短路函數(shù)——“〔〕〞函數(shù)。將題目中各節(jié)點(diǎn)坐標(biāo)轉(zhuǎn)化為矩陣，進(jìn)而建立稀疏矩陣，然后利用最短路函數(shù)提取出符合3分鐘路程要求的矩陣，最后進(jìn)展整理，即可得所求。模型的求解：先用算法求解出各交巡警效勞平臺到各個路口節(jié)點(diǎn)的最短距離，利用軟件進(jìn)展運(yùn)算〔運(yùn)算程序見一〕，代入數(shù)據(jù),求得管轄圍如下：表一A區(qū)各效勞平臺的管轄圍效勞平臺節(jié)點(diǎn)編號管轄的節(jié)點(diǎn)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〔原始表格見二〕把出警時間不超過3分鐘，轉(zhuǎn)化為效勞平臺距離所管轄的路口距離不超過3千米。由此檢驗(yàn)得六個路口〔28，29，38，39，61，92〕不滿足出警時間要求。到達(dá)最近的交巡警效勞平臺的時間超過3分鐘的6個路口如下表：路口標(biāo)號282938396192歸屬標(biāo)號1515162720距離47.58150.00534.05936.82241.90236.013問題1.2——A區(qū)交巡警效勞平臺警力調(diào)度方案對于重大突發(fā)事件，需要調(diào)度全區(qū)20個交巡警效勞平臺的警力資源，對進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。要求得該如何分配警力資源封鎖路口我們使用0-1整數(shù)規(guī)劃模型。設(shè)表示第個交巡警效勞平臺調(diào)度到第j個交通路口的情況，即：其中根據(jù)對問題的分析，要實(shí)現(xiàn)對要道的快速全封鎖，所以模型的目標(biāo)是使封鎖所有要道的總時間最短，其關(guān)鍵在于控制封鎖要道所需時間最長的效勞平臺的出警時間，使之到達(dá)最小值。設(shè)表示封鎖要道所需時間最長的效勞平臺的出警時間Aij表示20個交警平臺到13個交通路口的距離封鎖要道所需時間最長的效勞平臺的出警時間最短：min；在13個交通路口上，每個路口都必須有一個交巡警：；每個交巡警效勞平臺至多只能去一個路口：；每個交巡警到達(dá)路口的距離均小于最后一個到達(dá)路口的交警平臺與該路口的距離：。建立模型如下：目標(biāo)函數(shù)：min;：模型的求解：我們利用lingo軟件進(jìn)展目標(biāo)函數(shù)的求解。主程序如下：〔具體程序見三〕由程序結(jié)果可得如下表格：封鎖方案表格距離〔km〕節(jié)點(diǎn)走向時間〔m〕距離〔km〕節(jié)點(diǎn)走向時間〔m〕①2.476→482.47⑦2.608→162.60②3.105→303.10⑧5.409→105.40③8.01.7→298.01⑨7.7010→227.70④4.7015→284.70⑩3.8011→243.80⑤3.982→383.98⑾6.7416→146.74⑥0.354→620.35⑿3.2614→213.26=13\*GB2⒀012→120下列圖是所求得各巡邏點(diǎn)到個路口的時間表：取其中的最大值為8.01546.故控制封鎖要道所需時間最短約為8.01分鐘。問題1.3——擬增A區(qū)交巡警效勞平臺對于擬增A區(qū)交巡警效勞平臺，首先分析現(xiàn)有的交巡警效勞平臺的分布，發(fā)現(xiàn)存在交巡警效勞平臺工作量不均衡和局部交通路口出警時間過長的問題。這就要求新增加幾個效勞平臺后，使得各個交巡警效勞平臺的工作量盡可能一樣以及使各個交通路口出警時間都被控制在3分鐘。新建效勞平臺需要本錢，所以需要合理確定效勞平臺的選址，使需要建立的效勞平臺的數(shù)目最小。由此，我們參考集合覆蓋模型〔在一定的區(qū)域，設(shè)置最小數(shù)量的設(shè)施來覆蓋其中所有的點(diǎn)〕，建立了一個兩目標(biāo)0-1整數(shù)規(guī)劃模型?！惨娝摹衬繕?biāo)函數(shù)：約束條件：(i=1,2,…,92=1,2,…,92)且每個交通路口都有一個平臺管轄：所有平臺到其所管轄的交通路口最短距離中的最大值不超過距離偏差,即各個交通路口出警時間都被控制在3分鐘：(i=1,2,…,92j=1,2,…,92)模型的求解：第三個子問題所建立的是雙目標(biāo)的0-1整數(shù)規(guī)劃模型，第一目標(biāo)為增加的效勞平臺最少，第二目標(biāo)為各個效勞平臺每天的效勞強(qiáng)度方差最小。為了求解模型，先只考慮第一目標(biāo)，然后再在第一目標(biāo)最優(yōu)的情況下給出第二目標(biāo)最優(yōu)的解。在lingo軟件中運(yùn)行程序，從24至30圍取出假設(shè)干個偏差限與所對應(yīng)的目標(biāo)函數(shù)值。由結(jié)果，增加5個平臺，標(biāo)號與坐標(biāo)分別為：29〔246,337〕;39〔371,333〕;48〔315,374〕;51〔348.5,380.5〕;88〔444.5,383〕由于該模型發(fā)案率的均衡性不是很好，增加的5個平臺不一定是劃分A區(qū)的最優(yōu)解。因此要進(jìn)展進(jìn)一步的分析處理。將25個平臺代入1.1的模型中，與原A區(qū)的劃分結(jié)果相比擬〔以dij>30的節(jié)點(diǎn)個數(shù)的多少為標(biāo)準(zhǔn)〕，逐個去掉平臺個數(shù)，再重復(fù)以上操作，最終得出結(jié)果。使用和求A區(qū)偏差限一樣的方法分別確定增加5個平臺、4個平臺、3個平臺時的偏差限，即最好均衡性分別為1.9、1.85、1.85，并設(shè)計(jì)表格進(jìn)展比照，表格如下：增加的點(diǎn)數(shù)均衡性最優(yōu)解時間超過3分鐘的路口數(shù)增加的平臺51.9886.25545293948518841.85954.690942939488831.851170.1714293948權(quán)衡均衡性、最優(yōu)解及增加點(diǎn)個數(shù)所需花費(fèi)的資源，增加四個點(diǎn)數(shù)是最節(jié)省資源且效果最好的。故：交巡警效勞平臺增加四個，它們分別為：A29A39A48A88六、模型的評價6.1模型的優(yōu)點(diǎn)：對于問題一的第一個子問題：題目規(guī)定以最短時間為目標(biāo)，可轉(zhuǎn)化為最短距離不超過3km?？墒菍τ谟幸恍┕?jié)點(diǎn)，無論怎樣安排都不能到達(dá)警方到達(dá)事故現(xiàn)場為3分鐘之。我們對于這些節(jié)點(diǎn)單獨(dú)處理，并根據(jù)條件計(jì)算出這幾個節(jié)點(diǎn)應(yīng)該屬于哪個交巡警效勞平臺。對于問題一的第三個子問題：該問題要求確定增加2-5個交巡警效勞平臺的方案。一方面，根據(jù)限制條件，巡警到達(dá)其管轄節(jié)點(diǎn)應(yīng)在3分鐘之。另一方面，應(yīng)平均合理安排各個交巡警效勞平臺的工作量，不至于出現(xiàn)*個效勞平臺工作量過大而*個平臺工作量過小的情況。6.2模型的缺點(diǎn)：對于問題一的第一個子問題，建立的模型目標(biāo)單一，并沒有考慮到各個效勞平臺交巡警工作梁的不均衡性。在分配結(jié)果中可以看到，局部交巡警的工作量很小而局部交巡警的工作量很大。這顯然是不合理的。事實(shí)上，可以建立一個多目標(biāo)規(guī)劃問題，以交巡警到達(dá)事故現(xiàn)場和工作量的方差為目標(biāo)，使得分配管轄圍的方案更加合理。七、模型的推廣本文所提供的模型可以推廣到任何一個市區(qū)甚至更廣圍的交巡警效勞平臺的設(shè)置與調(diào)度問題的解決中。也可以廣泛應(yīng)用于社區(qū)衛(wèi)生室、公共衛(wèi)生間、消防救火中心等社會效勞部門的選址問題。在實(shí)際運(yùn)用中有很高的實(shí)用性及通用性。八、參考文獻(xiàn)[1]殷代君，廣義最大覆蓋模型在應(yīng)急設(shè)施選址中的應(yīng)用研究，中外企業(yè)家，2010年第3期：169-170,2010。[2]卓金武，MATLAB在數(shù)學(xué)建模中的應(yīng)用，：航空航天大學(xué)，2011。[3]中庚，數(shù)學(xué)建模方法及其應(yīng)用，：高等教育，2009。[4]金星，薛毅，優(yōu)化建模與lingo軟件，：清華大學(xué)，2005。一：function[list,AdjMatri*,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);%起點(diǎn)向量E=edge(:,2);%終點(diǎn)向量range=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%建立稀疏矩陣AdjMatri*=sparse([S;E],[E;S],[W;W],92,92);%求最短路徑矩陣distance=graphallshortestpaths(AdjMatri*,'directed',false);%提取出符合3分鐘路程要求的矩陣A=distance(1:20,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:72Ma*=0;R=NaN;forj=1:1:20ifA(j,i)>Ma*Ma*=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;endsetsdata: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,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,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.05,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