分享MATLAB杯論文01規(guī)劃的交巡警平臺(tái)設(shè)置與調(diào)度模型(1)

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

2、報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚?xiě)完整的全名）： 參賽隊(duì)員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 2011 年 9 月 12日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2011高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編 號(hào) 專(zhuān) 用 頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：用0-1規(guī)劃的交巡警平臺(tái)設(shè)置與調(diào)度模型摘 要本文研究的是交巡警平臺(tái)的設(shè)置、管轄區(qū)域的劃分以及發(fā)生重大突發(fā)事件時(shí)警務(wù)資源的調(diào)度問(wèn)題。問(wèn)題一中，我

3、們對(duì)城區(qū)A的交通網(wǎng)絡(luò)和交巡警平臺(tái)的設(shè)置進(jìn)行了分析。首先，通過(guò)Floyd算法，計(jì)算出20個(gè)平臺(tái)與各節(jié)點(diǎn)間的最短路徑，并以此劃分管轄區(qū)域，使各節(jié)點(diǎn)被距離它最近的平臺(tái)管轄。盡管如此，仍有6個(gè)節(jié)點(diǎn)（28、29、38、39、61、92）距離平臺(tái)超過(guò)3km,導(dǎo)致這些節(jié)點(diǎn)發(fā)生案件時(shí)相應(yīng)平臺(tái)的出警時(shí)間過(guò)長(zhǎng)。接下來(lái)，我們利用0-1規(guī)劃模型，制定出了發(fā)生重大突發(fā)事件時(shí)交巡警平臺(tái)警力的調(diào)度方案，并得出了最快完成全封鎖的時(shí)間為8min。最后，為使A區(qū)交巡警平臺(tái)的設(shè)置更為合理，我們以各平臺(tái)工作量的變異系數(shù)最小和最長(zhǎng)出警時(shí)間最短為目標(biāo)，再次建立0-1規(guī)劃模型，設(shè)計(jì)出了新增平臺(tái)的方案，即：新增4個(gè)平臺(tái)，分別位于節(jié)點(diǎn)28（或

4、29）、61、39、91，此時(shí)，最長(zhǎng)出警時(shí)間為2.71min，工作量變異系數(shù)為0.2004，是能在3min內(nèi)快速出警且新增平臺(tái)數(shù)最少的方案； 新增5個(gè)平臺(tái)，分別位于節(jié)點(diǎn)28（或29）、61、39、91、67，此時(shí)，最長(zhǎng)出警時(shí)間仍為2.71min，工作量變異系數(shù)下降為0.1526，是能在3min內(nèi)快速出警且各平臺(tái)工作量最均衡的方案。問(wèn)題二中，我們首先結(jié)合問(wèn)題一中的Floyd算法和0-1規(guī)劃模型，在不增加交巡警平臺(tái)的前提下，對(duì)全市各區(qū)平臺(tái)的管轄范圍進(jìn)行了劃分，得到了最優(yōu)的分配方案，并對(duì)其合理性進(jìn)行了分析，發(fā)現(xiàn)： 主城各區(qū)交巡警平臺(tái)工作量的變異系數(shù)都較小，即各平臺(tái)的工作量較均衡，比較合理； 主城各區(qū)

5、的最長(zhǎng)出警時(shí)間都較大，尤其是D區(qū)和E區(qū)，遠(yuǎn)遠(yuǎn)超過(guò)了規(guī)定的3min出警時(shí)間，因此不合理。針對(duì)這一問(wèn)題，以縮短最長(zhǎng)出警時(shí)間為目標(biāo)，繼續(xù)采用0-1規(guī)劃模型，設(shè)計(jì)出了能夠在3min內(nèi)快速出警且新增平臺(tái)數(shù)最少的改進(jìn)方案。最后，在點(diǎn)P（第32個(gè)節(jié)點(diǎn)）發(fā)生了重大刑事案件且犯罪嫌疑人已駕車(chē)逃跑3min的情況下，我們以嫌疑犯落網(wǎng)時(shí)間（從開(kāi)始逃跑到最后被捕的時(shí)間）最短為目標(biāo)，以交巡警成功封鎖節(jié)點(diǎn)和嫌疑犯被完全圍堵為約束條件，建立了0-1規(guī)劃模型。求解出了A區(qū)的圍堵方案，并發(fā)現(xiàn)在圍堵的區(qū)域內(nèi)有逃離A區(qū)的4個(gè)出口（節(jié)點(diǎn)28，30，38，48），因此再將圍堵范圍拓展到C、D、F區(qū)。最終的調(diào)度方案為：調(diào)度18個(gè)平臺(tái)的警力

6、封鎖18個(gè)節(jié)點(diǎn)，可使嫌疑犯在20.25分鐘內(nèi)落網(wǎng)。本文建立的0-1規(guī)劃模型能與實(shí)際緊密聯(lián)系，結(jié)合實(shí)際情況對(duì)問(wèn)題進(jìn)行求解，使得模型具有很好的通用性和推廣性。關(guān)鍵詞：最短路徑 0-1規(guī)劃 交巡警平臺(tái) 1 問(wèn)題重述交巡警平臺(tái)是將行政執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能有機(jī)融合的新型防控體系。由于警務(wù)資源有限，如何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門(mén)需要面臨的一個(gè)實(shí)際課題。試就某市設(shè)置交巡警服務(wù)平臺(tái)的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問(wèn)題：（1）根據(jù)該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服務(wù)平臺(tái)的設(shè)置情況示意圖及相關(guān)的數(shù)據(jù)信息，請(qǐng)

7、為各交巡警服務(wù)平臺(tái)分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3分鐘內(nèi)有交巡警（警車(chē)的時(shí)速為60km/h）到達(dá)事發(fā)地。對(duì)于重大突發(fā)事件，需要調(diào)度全區(qū)20個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個(gè)平臺(tái)的警力最多封鎖一個(gè)路口，請(qǐng)給出該區(qū)交巡警服務(wù)平臺(tái)警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過(guò)長(zhǎng)的實(shí)際情況，擬在該區(qū)內(nèi)再增加2至5個(gè)平臺(tái)，請(qǐng)確定需要增加平臺(tái)的具體個(gè)數(shù)和位置。（2）針對(duì)全市（主城六區(qū)A，B，C，D，E，F(xiàn)）的具體情況，按照設(shè)置交巡警服務(wù)平臺(tái)的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺(tái)設(shè)置方案的合理性。如

8、果有明顯不合理，請(qǐng)給出解決方案。如果該市地點(diǎn)P（第32個(gè)節(jié)點(diǎn)）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報(bào)警，犯罪嫌疑人已駕車(chē)逃跑。為了快速搜捕嫌疑犯，請(qǐng)給出調(diào)度全市交巡警服務(wù)平臺(tái)警力資源的最佳圍堵方案。2 模型假設(shè)（1）交巡警出警時(shí)間是指從交巡警平臺(tái)到達(dá)事發(fā)地路口節(jié)點(diǎn)所用的時(shí)間；（2）交巡警平臺(tái)管轄區(qū)域的劃分對(duì)象為路口節(jié)點(diǎn)；（3）一般情況下，各個(gè)交巡警平臺(tái)的管轄范圍相互獨(dú)立；（4）警車(chē)的平均時(shí)速為60km/h；（5）全封鎖是以最后一個(gè)路口節(jié)點(diǎn)完成封鎖為標(biāo)志；（6）常規(guī)情形下，全市各區(qū)的交巡警平臺(tái)不跨區(qū)管理；（7）每個(gè)節(jié)點(diǎn)僅由一個(gè)平臺(tái)管轄，每個(gè)平臺(tái)可管轄多個(gè)節(jié)點(diǎn)；（8）嫌疑犯的平均逃跑速度與警車(chē)

9、的平均速度相同。3 符號(hào)說(shuō)明(1) ：研究范圍內(nèi)節(jié)點(diǎn)的個(gè)數(shù)；(2) ：研究范圍內(nèi)交巡警平臺(tái)的個(gè)數(shù)； (3) ：研究范圍內(nèi)進(jìn)出口個(gè)數(shù)；(4) ：交巡警平臺(tái)到節(jié)點(diǎn)的距離； (5) ：警車(chē)時(shí)速；(6) ：節(jié)點(diǎn)的案發(fā)率； (7) ：交巡警平臺(tái)的工作量，即平臺(tái)管轄范圍內(nèi)各節(jié)點(diǎn)案發(fā)率的總和； (8) ：第個(gè)平臺(tái)的最長(zhǎng)出警時(shí)間；4 問(wèn)題分析問(wèn)題一：對(duì)于交巡警平臺(tái)管轄區(qū)域的分配問(wèn)題，為了盡量使交巡警在3分鐘內(nèi)（警車(chē)的時(shí)速為60km/h）到達(dá)事發(fā)地。我們將節(jié)點(diǎn)歸為距離其最短的平臺(tái)來(lái)管轄。該問(wèn)題即轉(zhuǎn)化為對(duì)平臺(tái)與節(jié)點(diǎn)間最短路徑的求解1。發(fā)生重大突發(fā)事件后，調(diào)度20個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的13條交通要

10、道實(shí)現(xiàn)快速全封鎖。根據(jù)假設(shè)5，完成全封鎖的時(shí)間取決于調(diào)度中距離最遠(yuǎn)的交巡警平臺(tái)的警力到達(dá)出口的時(shí)間。因此，我們提出以下兩個(gè)調(diào)度原則：（1）以最大調(diào)度距離最短為優(yōu)；（2）以總調(diào)度距離最小為優(yōu)。對(duì)于各平臺(tái)，只有調(diào)度和不調(diào)度兩種情況，因此，可用0-1規(guī)劃的思想建立模型2。為了改善現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過(guò)長(zhǎng)的實(shí)際情況，我們提出以下交巡警平臺(tái)設(shè)置原則：（1）平臺(tái)的最長(zhǎng)出警時(shí)間最短為優(yōu)；（2）平臺(tái)工作量的變異系數(shù)最小為優(yōu)。依據(jù)以上兩個(gè)原則，利用0-1規(guī)劃模型，對(duì)管轄范圍重新劃分，并確定新增平臺(tái)的個(gè)數(shù)及位置。問(wèn)題二：要分析研究全市的交巡警服務(wù)平臺(tái)設(shè)置是否合理，首先應(yīng)根據(jù)問(wèn)題一中交

11、巡警平臺(tái)的設(shè)置原則，對(duì)各區(qū)各平臺(tái)的管轄范圍進(jìn)行劃分，然后，根據(jù)平臺(tái)的最長(zhǎng)出警時(shí)間和工作量的均衡性，對(duì)其合理性進(jìn)行分析。若不合理，則可通過(guò)增加平臺(tái)數(shù)，來(lái)解決這一問(wèn)題。 該市地點(diǎn)P（第32個(gè)節(jié)點(diǎn)）發(fā)生了重大刑事案件，犯罪嫌疑人已駕車(chē)逃跑3min。為了快速?lài)孪右煞?，以其落網(wǎng)時(shí)間（從逃跑到最后被捕的時(shí)間）最短為目標(biāo)，可以通過(guò)0-1規(guī)劃模型設(shè)計(jì)平臺(tái)警力的調(diào)度方案。成功封鎖節(jié)點(diǎn)是指交巡警先于嫌疑犯到達(dá)該節(jié)點(diǎn)；成功圍堵是指嫌疑犯被限制于一定的區(qū)域內(nèi)，該區(qū)域與外界相通的道路節(jié)點(diǎn)全部被成功封鎖。計(jì)算時(shí)可以先求出A區(qū)的圍堵方案，在圍堵的區(qū)域內(nèi)若存在逃離A區(qū)的出口節(jié)點(diǎn)，則再將圍堵范圍拓展到其他區(qū)，直至嫌疑犯被完全

12、圍堵。5 模型的建立與求解5.1 問(wèn)題一：A區(qū)交巡警平臺(tái)的設(shè)置與調(diào)度分析 5.1.1 A區(qū)交巡警平臺(tái)的管轄范圍分配當(dāng)出現(xiàn)突發(fā)事件時(shí)，顯然為使交巡警警力盡量能在3分鐘內(nèi)（警車(chē)的時(shí)速為60km/h）到達(dá)事發(fā)地點(diǎn)，需要各節(jié)點(diǎn)由距離其最近的交巡警平臺(tái)來(lái)管轄。該問(wèn)題的核心是對(duì)平臺(tái)與節(jié)點(diǎn)間路徑之和最小值的求解，常用Floyd算法。5.1.1.1 Floyd算法步驟3（A區(qū)的計(jì)算結(jié)果見(jiàn)附錄1）第1步：將各頂點(diǎn)編為確定矩陣，其中元素等于從頂點(diǎn)到頂點(diǎn)最短弧的長(zhǎng)度(如果有最短弧的話)。如果沒(méi)有這樣的弧，則令 。對(duì)于，令。第2步：對(duì)，依次由的元素確定的元素，應(yīng)用下列遞歸公式 （1）每當(dāng)確定一個(gè)元素時(shí)，就記下它所表示

13、的路。在算法終止時(shí)，矩陣的元素就表示從頂點(diǎn)到頂點(diǎn)最短路的長(zhǎng)度。根據(jù)附件中各點(diǎn)的坐標(biāo)，作A區(qū)的交通網(wǎng)絡(luò)圖，見(jiàn)圖1（畫(huà)圖程序見(jiàn)附錄2）。注：圖中節(jié)點(diǎn)處加上圈的是平臺(tái)。圖1 A區(qū)的交通網(wǎng)絡(luò)與平臺(tái)設(shè)置的示意圖5.1.1.2 根據(jù)Floyd算法結(jié)果，和圖2中的流程圖，利用MATLAB編程4，可找出距離各節(jié)點(diǎn)最近的平臺(tái)及其距離（程序見(jiàn)附錄3），見(jiàn)表1。圖2 A區(qū)尋找距離節(jié)點(diǎn)最近的交巡警平臺(tái)的流程圖表1 距離各節(jié)點(diǎn)最近的平臺(tái)編號(hào)及距離節(jié)點(diǎn)編號(hào)平臺(tái)編號(hào)距離（百米）節(jié)點(diǎn)編號(hào)平臺(tái)編號(hào)距離（百米）節(jié)點(diǎn)編號(hào)平臺(tái)編號(hào)距離（百米）21A1327.083145A910.950869A1522A139.055446A89.3

14、00570A28.602323A13547A712.806271A111.403124A1323.853748A712.90272A216.062325A1217.888549A5573A110.296126A11950A58.485374A16.26527A1116.43351A512.293275A19.3005*28A1547.518452A516.594376A112.8361*29A1557.005353A511.708277A199.848930A75.83154A322.708978A16.403131A920.557255A312.65979A194.472132A711.40

15、1856A520.83780A188.062333A88.276557A418.681581A186.708234A95.024958A523.018982A1810.793535A94.242659A515.208683A185.385236A166.082860A417.392484A2011.752237A1611.1818*61A741.90285A204.4721*38A1634.058862A43.586A203.6056*39A236.821963A410.307887A2014.650940A219.144264A419.363188A2012.946341A178.565A3

16、15.239889A209.486842A179.848966A318.40290A2013.022443A2867A116.194291A2015.987744A29.486868A112.0711*92A2036.0127注：表中加“*”表示該節(jié)點(diǎn)距離相應(yīng)平臺(tái)的最短距離超過(guò)3km.由此可得各平臺(tái)的管轄范圍，見(jiàn)表2。表2 各平臺(tái)的管轄范圍交巡警平臺(tái)節(jié)點(diǎn)A167 68 69 71 73 74 75 76 78A239 40 43 44 70 72A354 55 65 66A457 60 62 63 64A549 50 51 52 53 56 58 59A6無(wú)A730 32 47 48 61A8

17、33 46A931 34 35 45A10無(wú)A1126 27A1225A1321 22 23 24A14無(wú)A1528 29A1636 37 38A1741 42A1880 81 82 83A1977 79A2084 85 86 87 88 89 90 91 92表2中，平臺(tái)6，10，14由于距離周?chē)墓?jié)點(diǎn)較遠(yuǎn)，因此主要負(fù)責(zé)解決自身的突發(fā)事件。根據(jù)表2，我們?cè)趫D中對(duì)各個(gè)平臺(tái)的管轄范圍進(jìn)行劃分，見(jiàn)圖3。一二三四五六七八九十十一十二十三十四十五十六十七十八十九二十252421272628293048613237363847414260576364222362 圖3 A區(qū)各平臺(tái)管轄范圍示意圖5.1.2

18、 A區(qū)13條交通要道的快速封鎖調(diào)度方案根據(jù)Floyd算法得出的最短路徑矩陣，我們可以求出A區(qū)20個(gè)平臺(tái)分別到達(dá)A區(qū)13個(gè)出口的最短路程，見(jiàn)表3（程序見(jiàn)附錄4）。表3 A區(qū)各平臺(tái)到出口的最短路程（單位：百米） 出口A1A2A3A4A5A6A7A8A9A101222.36 204.64 183.52 219.97 176.28 176.59 149.15 140.93 130.11 75.87 2160.28 141.30 127.67 150.09 129.70 130.00 109.01 94.34 82.74 127.76 392.87 73.88 60.26 82.67 62.28 62.

19、59 41.60 26.92 15.33 69.57 4192.93 173.95 160.32 182.73 162.35 162.65 141.66 126.99 115.39 95.11 5210.96 191.97 178.35 200.76 177.50 177.80 150.36 142.14 131.32 77.08 6225.02 206.03 192.41 214.82 191.55 191.86 164.42 156.19 145.38 91.13 7228.93 211.21 190.09 226.54 182.85 183.16 155.72 147.50 136.68

20、 82.44 8190.01 172.29 151.17 162.27 113.07 113.37 85.70 102.28 97.76 141.95 9195.16 177.44 156.32 155.35 106.15 106.46 80.15 104.93 107.24 151.44 10120.83 103.11 82.00 81.03 31.83 32.14 5.83 30.61 34.92 79.11 1158.81 39.82 60.94 48.61 94.21 94.52 73.53 58.85 47.26 101.50 12118.50 103.10 81.98 73.96

21、24.76 25.06 12.90 30.99 41.99 86.19 1348.85 60.35 43.93 3.50 52.55 53.37 79.92 86.77 93.37 147.61 續(xù)表：出口A11A12A13A14A15A16A17A18A19A20137.91 0.00 59.77 119.50 170.30 145.43 218.92 242.47 225.47 269.46 283.37 119.50 59.73 0.00 132.98 67.42 149.03 185.14 169.61 212.13 3113.95 145.43 127.15 67.42 65.56

22、0.00 81.62 117.73 102.20 144.71 450.72 86.85 27.08 32.65 165.63 100.07 181.68 217.79 202.26 244.78 532.70 68.83 9.06 50.68 171.51 118.09 199.71 235.82 220.29 262.81 646.75 64.77 5.00 64.73 185.56 132.15 213.77 249.88 234.35 276.86 738.05 35.92 23.85 83.59 176.87 151.00 225.49 249.04 232.04 276.03 81

23、86.33 217.81 228.08 180.50 47.52 113.08 186.57 210.12 193.12 230.11 9195.82 227.30 237.57 189.17 57.01 121.75 195.24 215.27 198.26 223.19 10123.50 154.98 165.25 114.84 44.01 47.43 120.92 140.94 123.94 148.87 11145.88 177.36 161.21 101.48 97.50 34.06 47.56 83.67 76.39 110.66 12130.57 162.05 172.32 12

24、1.91 51.09 54.50 127.99 136.99 119.99 141.80 13191.99 223.47 213.32 153.59 118.10 86.17 78.21 67.34 50.34 64.49 出現(xiàn)重大突發(fā)事件時(shí)，需調(diào)度20個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。對(duì)于各平臺(tái)，只有調(diào)度和不調(diào)度兩種情況，因此，可用0-1規(guī)劃的思想建立模型。設(shè)為第個(gè)出口被第個(gè)平臺(tái)的警力封鎖的情況，則有： （2）5.1.2.1 最快實(shí)現(xiàn)完全封鎖的調(diào)度方案題目要求在最短時(shí)間內(nèi)實(shí)現(xiàn)全封鎖，而全封鎖的時(shí)間是由封鎖最后一個(gè)路口所用的時(shí)間決定的。因此，以最快實(shí)現(xiàn)全封鎖

25、為目標(biāo)函數(shù)，可轉(zhuǎn)化為求最遠(yuǎn)調(diào)度距離的最小值，表述為： （3）其中，表示所有調(diào)度中的最遠(yuǎn)距離，表示第個(gè)平臺(tái)到第個(gè)出口的距離。約束條件為：(1)平臺(tái)安排的約束。由于有20個(gè)平臺(tái)，13個(gè)出口，每個(gè)平臺(tái)最多封鎖一個(gè)出口，因此第個(gè)平臺(tái)不一定被調(diào)去封鎖出口，即 （4）(2)出口被唯一一個(gè)平臺(tái)封鎖的約束，則有 （5）綜上，最快實(shí)現(xiàn)全封鎖的模型為5： （6）根據(jù)模型（6），利用MATLAB編程，最后可以得到數(shù)個(gè)最優(yōu)解（程序見(jiàn)附錄5），再結(jié)合表3，可得到其中四個(gè)結(jié)果，見(jiàn)表47。表4 調(diào)度方案1 表5 調(diào)度方案2出口平臺(tái)距離（百米）出口平臺(tái)距離（百米）1A120.001A1202A1667.422A1667.42

26、3A562.283A273.884A1327.084A1432.655A1077.085A1077.086A1464.736A135.007A1138.057A1138.058A1547.528A1547.529A780.159A780.1510A830.6110A934.9211A947.2611A858.8512A473.9612A524.7613A260.3513A43.50表6 調(diào)度方案3 表7 調(diào)度方案4出口平臺(tái)距離（百米）出口平臺(tái)距離（百米）1A120.001A120.002A1667.422A1667.423A915.333A826.924A1432.654A1327.085A1

27、077.085A1077.086A1146.756A1464.737A1323.857A1138.058A1547.528A1547.529A780.159A780.1510A830.6110A934.9211A448.6111A239.8212A524.7612A473.9613A260.3513A552.55觀察上述四個(gè)調(diào)度方案可以發(fā)現(xiàn)，這些調(diào)度方案中，距離最遠(yuǎn)的都是平臺(tái)7至出口9，為80.15百米，所以完成A區(qū)完全封鎖的時(shí)間即由此決定，需要8分鐘。在此基礎(chǔ)上，以總調(diào)度距離最短為目標(biāo)函數(shù)，對(duì)除平臺(tái)7和出口9以外的出口和交巡警平臺(tái)進(jìn)一步作0-1規(guī)劃的模型為： （7）其中，表示總調(diào)度距離。表示

28、除平臺(tái)7 以外的平臺(tái)總數(shù)，表示除出口9以外的出口總數(shù)。利用lingo軟件對(duì)其求解6（程序見(jiàn)附錄6），最終結(jié)果見(jiàn)表8。表8 最快實(shí)現(xiàn)完全封鎖且總距離相對(duì)最短的調(diào)度方案出口平臺(tái)距離（百米）1A1202A1667.423A826.924A1432.655A1077.086A1357A1138.058A1547.529A780.1510A934.9211A239.8212A524.7613A43.5綜上，最快實(shí)現(xiàn)完全封鎖的時(shí)間為8分鐘，調(diào)度的總距離為477.79百米。5.1.2.2 總距離最短的調(diào)度方案若以總距離最小為目標(biāo)函數(shù)（不考慮是否能最快完成全封鎖），可表述為： （8）約束條件為： （9）利用L

29、INGO軟件對(duì)其求解（程序見(jiàn)附錄7），最終結(jié)果見(jiàn)表9。表9 總距離最短的調(diào)度方案出口平臺(tái)距離（百米）1A1202A1403A1604A9115.395A1077.086A1357A1138.058A1547.519A8104.9310A75.8311A239.8212A524.7513A43.5總距離為461.88百米，最遠(yuǎn)距離為115.39百米，在11分32秒時(shí)完成全部封鎖。通過(guò)對(duì)比上述兩種目標(biāo)不同的規(guī)劃，可以發(fā)現(xiàn)總距離最短時(shí)，完成全封鎖所需的時(shí)間更長(zhǎng)，是由于其最遠(yuǎn)距離并非最短，不符合題目要求。因此我們采用最快實(shí)現(xiàn)完全封鎖且總距離相對(duì)最短的調(diào)度方案（見(jiàn)表8）。5.1.3 增加交巡警平臺(tái)的分配

30、方案由于各平臺(tái)管轄范圍內(nèi)的節(jié)點(diǎn)數(shù)差異很大，以及各節(jié)點(diǎn)的案發(fā)率不同，造成現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡，部分地方的出警時(shí)間過(guò)長(zhǎng)。因此，可以通過(guò)增加交巡警服務(wù)平臺(tái)及重新分配管轄范圍，來(lái)解決這一問(wèn)題。根據(jù)Floyd算法，平臺(tái)與節(jié)點(diǎn)間的最短路程不超過(guò)3km的對(duì)應(yīng)關(guān)系見(jiàn)表10及表11（程序見(jiàn)附錄8）。表10 各交巡警平臺(tái)周?chē)?km以內(nèi)的所有節(jié)點(diǎn)交巡警平臺(tái)節(jié)點(diǎn)A11、42、43、44、64、65、66、67、68、69、70、71、72、73、74、75、76、77、78、79、80A22、39、40、42、43、44、66、67、68、69、70、71、72、73、74、75、76、78A33、43、

31、44、54、55、64、65、66、67、68、70、76A44、57、58、60、62、63、64、65、66A55、47、48、49、50、51、52、53、56、58、59A66、47、48、50、51、52、56、58、59A77、30、31、32、33、34、47、48、61A88、31、32、33、34、35、36、37、45、46、47A99、31、32、33、34、35、36、37、45、46A1010A1111、25、26、27A1212、25A1313、21、22、23、24A1414A1515、28、29、31A1616、33、34、35、36、37、38、45、46A1

32、717、40、41、42、43、70、72A1818、71、72、73、74、77、78、79、80、81、82、83、84、85、87、88、89、90、91A1919、64、65、66、67、68、69、70、71、73、74、75、76、77、78、79、80、81、82、83A2020、81、82、83、84、85、86、87、88、89、90、91、92注：由表1可知，有6個(gè)節(jié)點(diǎn)（28、29、38、39、61、92）與距其最近的交巡警平臺(tái)的距離超過(guò)3km，但仍將其劃歸為距離最近的平臺(tái)。表11 各節(jié)點(diǎn)周?chē)?km以內(nèi)的所有平臺(tái)節(jié)點(diǎn)平臺(tái)編號(hào)節(jié)點(diǎn)平臺(tái)編號(hào) 節(jié)點(diǎn)平臺(tái)編號(hào)節(jié)點(diǎn)平臺(tái)編號(hào)1A124A

33、1347A5、A6、A7、A870A1、A2、A3、A17、A192A225A11、A1248A5、A6、A7、A2371A1、A2、A17、A183A326A1149A572A1、A2、A17、A184A427A1150A5、A673A1、A2、A18、A195A528A1551A5、A674A1、A2、A18、A196A629A1552A5、A675A1、A2、A197A730A753A576A1、A2、A3、A198A831A7、A8、A9、A1554A377A1、A18、A199A932A7、A8、A955A378A1、A2、A18、A1910A1033A7、A8、A9、A1656A5

34、、A679A1、A18、A1911A1134A7、A8、A9、A1657A480A1、A18、A1912A1235A8、A9、A1658A4、A5、A681A18、A19、A2013A1336A8、A9、A1659A5、A682A18、A19、A2014A1437A8、A9、A1660A483A18、A19、A20、15A1538A1661A784A18、A2016A1639A262A485A18、A2017A1740A2、A17、A2263A486A2018A1841A1764A1、A3、A4、A1987A18、A2019A1942A1、A2、A1765A1、A3、A4、A1988A18、A

35、2020A2043A1、A2、A3、A1766A1、A2、A3、A4、A1989A18、A2021A1344A1、A2、A367A1、A2、A3、A1990A18、A2022A1345A8、A9、A1668A1、A2、A3、A1991A18、A2023A1346A8、A9、A1669A1、A2、A1992A20由表11可知，部分節(jié)點(diǎn)周?chē)?km以內(nèi)有多個(gè)平臺(tái)，因此根據(jù)工作量和出警時(shí)間對(duì)其進(jìn)行規(guī)劃，使得每個(gè)節(jié)點(diǎn)只被一個(gè)平臺(tái)管轄。對(duì)于節(jié)點(diǎn)，只有被平臺(tái)管轄和不被平臺(tái)管轄兩種情況，因此，可設(shè)計(jì)0-1變量。令： （10）交巡警平臺(tái)的工作量可表示為該平臺(tái)管轄范圍內(nèi)各節(jié)點(diǎn)案發(fā)率的總和，即： （11）其中，指交

36、巡警平臺(tái)的工作量，表示節(jié)點(diǎn)的日案發(fā)率。根據(jù)假設(shè)1，交巡警的出警時(shí)間是指從接警到到達(dá)事發(fā)地路口節(jié)點(diǎn)的時(shí)間，即： （12）其中，表示第個(gè)平臺(tái)的最長(zhǎng)出警時(shí)間，表示第個(gè)平臺(tái)到達(dá)第個(gè)節(jié)點(diǎn)的最短距離。 （1）確定目標(biāo)函數(shù)目標(biāo)函數(shù)1：要使各平臺(tái)的工作量更加均衡，可使各交巡警平臺(tái)工作量的變異系數(shù)最小，其值越小，表示各平臺(tái)工作量越均衡，即： （13）目標(biāo)函數(shù)2：最長(zhǎng)出警時(shí)間達(dá)到最少，則有： （14）（2）約束條件1）平臺(tái)不閑的約束。為使每個(gè)平臺(tái)不至于無(wú)管轄范圍，可約束為它至少管轄自己所在的節(jié)點(diǎn)。當(dāng)時(shí)，即： （15）2）每個(gè)節(jié)點(diǎn)都被平臺(tái)管轄的約束。當(dāng)時(shí)，由假設(shè)7，第個(gè)節(jié)點(diǎn)必定被中的唯一一個(gè)平臺(tái)管轄，即： （16）

37、3）出警時(shí)間不超過(guò)3min。綜上，考慮平臺(tái)的工作量呈均衡性及合理出警時(shí)間的模型7為： 在不增加交巡警平臺(tái)的前提下，將表11中的數(shù)據(jù)代入模型（17），利用MATLAB軟件（程序見(jiàn)附錄9）進(jìn)行求解，結(jié)果見(jiàn)表12。表12 最長(zhǎng)出警時(shí)間最短且工作量均衡時(shí)各平臺(tái)的管轄范圍交巡警平臺(tái)管轄的節(jié)點(diǎn)日工作量（案件數(shù)）A11 71 73 74 75 686.5A22 43 44 70 696.9A33 54 55 65 66 67 6.4A44 57 60 62 63 646.6A55 49 52 53 56 586.9A66 50 59 47 51 486.9A77 30 615.1A88 33 46 326.

38、5A99 31 35 456.5A1010 343.7A1111 26 275.6A1212 25 245.1A1313 22 236A1414 214.9A1515 28 294.8A1616 36 37 38 396.4A1717 41 42 40 726.8A1818 81 82 83 84 90 868.4A1919 76 77 78 79 806.1A2020 87 88 89 91 92 858.4在不增加交巡警平臺(tái)的前提下，最長(zhǎng)出警時(shí)間為5.70min，出現(xiàn)在平臺(tái)15前往節(jié)點(diǎn)29處理突發(fā)事件時(shí)。工作量的變異系數(shù)為0.1830。同理可求得增加平臺(tái)15個(gè)時(shí)工作量變異系數(shù)及最長(zhǎng)出警時(shí)間

39、的變化，見(jiàn)表14。表13 增加平臺(tái)后工作量的變異系數(shù)和最長(zhǎng)出警時(shí)間新增平臺(tái)個(gè)數(shù)新增平臺(tái)位置（節(jié)點(diǎn)號(hào)）工作量的標(biāo)準(zhǔn)差工作量的均值變異系數(shù)最長(zhǎng)出警時(shí)間（min）0無(wú)1.146.230.1830 5.70128或291.345.930.2260 4.192611.515.660.2668 3.823391.355.410.2495 3.684911.045.190.2004 2.715670.764.980.1526 2.71由表13可知，增加12個(gè)交巡警平臺(tái)時(shí)，新增的平臺(tái)主要設(shè)置在原來(lái)距離其所屬平臺(tái)較遠(yuǎn)的節(jié)點(diǎn)處，這樣大大縮減了最長(zhǎng)出警時(shí)間，但是該新增平臺(tái)能夠分擔(dān)的工作量相對(duì)較少，因此變異系數(shù)反而增

40、加。而當(dāng)增加45個(gè)交巡警平臺(tái)時(shí)，新增的平臺(tái)主要分布在節(jié)點(diǎn)相對(duì)較密集而平臺(tái)較少的區(qū)域，使工作量更加均衡，因而變異系數(shù)大大減小。出現(xiàn)這種變化趨勢(shì)的原因是：在未增加交巡警平臺(tái)時(shí)，兩個(gè)規(guī)劃目標(biāo)中出警時(shí)間過(guò)長(zhǎng)是主要矛盾；而當(dāng)新增平臺(tái)數(shù)超過(guò)3個(gè)時(shí)，出警時(shí)間已維持在一個(gè)較低的水平，此時(shí)，工作量的變異系數(shù)成為了影響結(jié)果的主導(dǎo)因素。結(jié)論：增加4個(gè)交巡警平臺(tái)，分別位于節(jié)點(diǎn)28（29）、61、39和91，此時(shí)，最長(zhǎng)出警時(shí)間已達(dá)到最小，為2.71min，工作量的變異系數(shù)較小，為0.2004。 增加5個(gè)交巡警平臺(tái)，分別位于節(jié)點(diǎn)28（29）、61、39、91和67，此時(shí)，工作量的變異系數(shù)最小，為0.1526，最長(zhǎng)出警時(shí)間

41、最短，為2.71min。 因此，若只考慮最長(zhǎng)出警時(shí)間，可以只增加4個(gè)交巡警平臺(tái)；若同時(shí)考慮工作量的均衡性，需增加5個(gè)交巡警平臺(tái)。5.2 問(wèn)題二：全市交巡警平臺(tái)的設(shè)置與調(diào)度5.2.1 全市現(xiàn)有交巡警平臺(tái)設(shè)置的合理性分析及調(diào)整方案（1）B區(qū)的情況B區(qū)現(xiàn)有交巡警平臺(tái)8個(gè)，節(jié)點(diǎn)73個(gè)。首先，根據(jù)Floyd算法，得到平臺(tái)與節(jié)點(diǎn)間的最短路程，并與3km作比較，結(jié)果如圖4（程序見(jiàn)附錄10）。注：圖中加有圓圈的節(jié)點(diǎn)表示交巡警平臺(tái)，加有方框的節(jié)點(diǎn)表示被3km以內(nèi)的平臺(tái)管轄的節(jié)點(diǎn)，未加方框的節(jié)點(diǎn)距離周?chē)脚_(tái)超過(guò)3km。(圖5圖8同)圖4 B區(qū)現(xiàn)有交巡警平臺(tái)設(shè)置示意圖 由圖可知，其中距離周?chē)脚_(tái)超過(guò)3km的節(jié)點(diǎn)是造

42、成出警時(shí)間過(guò)長(zhǎng)的原因，將B區(qū)的數(shù)據(jù)代入模型（17）可得到現(xiàn)有交巡警平臺(tái)管轄范圍的劃分方案，見(jiàn)表14。表14 B區(qū)現(xiàn)有交巡警平臺(tái)的管轄范圍及工作量交巡警平臺(tái)管轄的節(jié)點(diǎn)工作量B1101 102 103 120 121 122 1235.4B2104 105 106 107 108 109 110 111 112 117 7.1B3113 114 115 116 126 128 129 131 1367.3B4124 127 130 133 134 138 139 140 1416.2B5135 137 143 144 119 142 145 1626.7B6155 156 157 158 159

43、160 1617.5B7148 149 152 153 163 164 1655.2B8125 132 146 147 150 151 154 1185.5B區(qū)最長(zhǎng)出警時(shí)間為4.47分鐘，平臺(tái)工作量的變異系數(shù)為0.1743。同理可求得其余各區(qū)的管轄范圍及工作量。（2）C區(qū)的情況圖5 C區(qū)現(xiàn)有交巡警平臺(tái)設(shè)置示意圖表15 C區(qū)現(xiàn)有交巡警平臺(tái)的管轄范圍及工作量平臺(tái)管轄的節(jié)點(diǎn)工作量C1262 263 264 265 260 261 243 2447.7C2248 249 250 251 252 255 258 9.3C3189 190 191 192 246 253 315 3167.3C4254 2

44、86 287 289 290 259 2476.8C5222 223 224 225 226 273 276 277 2838.0C6215 216 230 231 240 241 242 2889.6C7217 218 227 228 229 311 3128.1C8232 233 234 235 236 237 238 239 2459.0C9211 212 213 214 219 220 2217.5C10183 193 194 195 196 197 198 1998.8C11184 185 186 187 188 303 304 295 29610.0C12200 201 202 305 306 307 291 2929.7C13203 204 205 206 207 208 209 210 2849.6C14274 275 278 279 280 281 282 2