交巡警服務(wù)平臺的設(shè)置與調(diào)度.doc

2011高教社杯全國大學生數(shù)學建模競賽承 諾 書我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）： B 我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）： 所屬學校（請?zhí)顚懲暾娜?黔南民族師范學院 參賽隊員 (打印并簽名) ：1 龔 浪 2 劉可馨 3 李文文 指導教師或指導教師組負責人（打印并簽名）： 謝治州 日期： 2011 年 09 月 12 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：2011高教社杯全國大學生數(shù)學建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：交巡警服務(wù)平臺的設(shè)置與調(diào)度摘 要本文研究了城區(qū)交巡警服務(wù)平臺的設(shè)置與調(diào)度問題。我們將全市的交叉路口作為圖的頂點、道路作為圖的邊來構(gòu)建交通網(wǎng)絡(luò)圖G。將圖G的每邊起點和終點的直線距離作為邊權(quán)，根據(jù)已知的數(shù)據(jù)構(gòu)建圖G的權(quán)矩陣W，在此基礎(chǔ)上采用Dijstra算法求出圖G的每個頂點到達其他各點的最短路及路長，并構(gòu)造了最短路長矩陣D，建立了服務(wù)平臺管轄范圍最優(yōu)分配方案的條件模型；依據(jù)最短路長矩陣D構(gòu)造服務(wù)平臺管轄范圍分配的覆蓋算法，用此算法求出A區(qū)服務(wù)平臺較為均衡的管轄范圍，給出了增加服務(wù)平臺的較優(yōu)方案。對于封鎖A區(qū)的問題，我們建立了指派模型，并求出了全局最優(yōu)解，給出了最優(yōu)的調(diào)度方案。另外，我們采用簡單的圓覆蓋原理，分析全市區(qū)現(xiàn)有服務(wù)平臺設(shè)置的不合理性，根據(jù)服務(wù)平臺負載情況來均衡各服務(wù)平臺的工作量以及出警時間的原則和任務(wù)，將服務(wù)平臺管轄范圍內(nèi)的發(fā)案率和到其所轄頂點的最短路作為服務(wù)平臺設(shè)置的評價指標，采用模糊目標函數(shù)均值聚類法中的目標函數(shù)采用極小化類別方法建立了服務(wù)平臺設(shè)置評價模型并得了較好的結(jié)果。最后對圍堵重大刑事案件嫌疑犯的最佳方案問題，轉(zhuǎn)化為在圖G的邊集中求始點在中而終點不在中的邊的終點和終點在中而始點不在中的邊的始點構(gòu)成的集合所包含的元素個數(shù)和具體元素，即集合的元素個數(shù)即為需要封鎖的路口個數(shù)，集合所包含的元素對應(yīng)需要封鎖的路口。本文提出的算法模型解決了服務(wù)平臺的管轄范圍，均衡了服務(wù)平臺的工作量，并且?guī)缀鯖]有“越界”的情況。同時針對任意地區(qū)發(fā)生重大刑事案件，可以得出非常好的圍堵方案。本文提出的服務(wù)平臺選址模型，同樣還適用于物流網(wǎng)點、超市、垃圾轉(zhuǎn)運站的設(shè)立，有較好的推廣價值。關(guān)鍵詞：交巡警；Dijstra算法；最短路長矩陣；均值聚類; 極小化類別法18一、問題重述“有困難找警察”，是家喻戶曉的一句流行語。警察肩負著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺。如果假設(shè)每個交巡警服務(wù)平臺的職能和警力配備基本相同，如何根據(jù)城市的實際情況與需求合理地設(shè)置交巡警服務(wù)平臺、分配各平臺的管轄范圍、調(diào)度有限的警務(wù)資源是警務(wù)部門面臨的一個實際課題。某市的交通網(wǎng)絡(luò)與交巡警服務(wù)平臺的設(shè)置如圖1所示。圖1 全市六區(qū)交通網(wǎng)絡(luò)與交巡警服務(wù)平臺設(shè)置示意圖說明：1) 圖中實線表示市區(qū)道路，紅色線表示連接兩個區(qū)之間的道路；2) 實圓點“”表示交叉路口的節(jié)點，沒有實圓點的交叉線為道路立體相交；3) 星號“*”表示出入城區(qū)的路口節(jié)點；4) 圓圈“”表示現(xiàn)有交巡警服務(wù)平臺的設(shè)置點；5) 圓圈加星號“* ”表示在出入城區(qū)的路口處設(shè)置了交巡警服務(wù)平臺；6) 圖中的不同顏色表示不同的區(qū)。建立數(shù)學模型分析研究下面的問題：問題1 圖2給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個交巡警服務(wù)平臺的設(shè)置情況，為各交巡警服務(wù)平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3分鐘內(nèi)有交巡警（警車的時速為60km/h）到達事發(fā)地。對于重大突發(fā)事件，需要調(diào)度全區(qū)20個交巡警服務(wù)平臺的警力資源，對進出該區(qū)的13條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警時間過長的實際情況，擬在該區(qū)內(nèi)再增加2至5個服務(wù)平臺，確定需要增加平臺的具體個數(shù)和位置。圖2 A區(qū)的交通網(wǎng)絡(luò)與交巡警服務(wù)平臺設(shè)置示意圖問題2 針對全市(主城六區(qū)A，B，C，D，E，F(xiàn))的具體情況，按照設(shè)置交巡警服務(wù)平臺的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案的合理性。如果有明顯不合理，給出解決方案。如果該市地點P(如圖1的P點)處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，給出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案。二、問題分析問題的研究是在將全市的交叉路口作為圖的頂點、道路作為圖的邊所構(gòu)成的圖G上來進行。設(shè)圖G的頂點集為V，共有582個頂點，依次標為1，2，582，圖G的邊集為E，每邊起點和終點的標號已知。在圖G上建立平面直角坐標系，給出了每個頂點對應(yīng)位置的坐標和平均每天發(fā)生報警案件的數(shù)量(即發(fā)案率)。在目前的交巡警服務(wù)平臺設(shè)置方案中，服務(wù)平臺建在圖G的一些頂點上，服務(wù)平臺設(shè)置方案由服務(wù)平臺與頂點標號的對應(yīng)關(guān)系確定。各服務(wù)平臺依據(jù)它所在的城區(qū)依次標為：A1，A2，；B1，B2，；。另外，還明確了出入市區(qū)的路口標號和出入A區(qū)的路口標號(詳見“附件2_全市六區(qū)交通網(wǎng)路和平臺設(shè)置的數(shù)據(jù)表”)。若整個市區(qū)各點的海拔高度相差不大，相鄰兩個交叉路口間的道路近似為直線段，我們可將圖G的每邊起點和終點的直線距離作為它的權(quán)值，根據(jù)已知的數(shù)據(jù)可得圖G的權(quán)矩陣，其中，若標號為的頂點坐標分別為和，則 (2.1)不難看出，圖G是一個連通圖，由圖G的權(quán)矩陣W，采用求最短路的Dijstra算法(詳見文獻1)，按附錄中的程序1可求出圖G的每個頂點到達其他各點的最短路及路長，記為從點到達的最短路長，可構(gòu)造最短路長矩陣(其中，當時，)，最短路長矩陣的數(shù)據(jù)見“附件3_最短路長矩陣數(shù)據(jù)”。2.1 問題1的分析對于問題1，要為A區(qū)的各交巡警服務(wù)平臺Ak(k=1,2,，20)分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3分鐘內(nèi)有交巡警(警車的時速為60km/h)到達事發(fā)地，需制定合理的分配方案，滿足：納入服務(wù)平臺Ak的管轄范圍的頂點，盡量不超過3km；各服務(wù)平臺的工作量相對均衡。對于重大突發(fā)事件，若一個平臺的警力只能封鎖一個路口，調(diào)度全區(qū)20個服務(wù)平臺的警力資源將進出該區(qū)的13條交通要道快速全封鎖?？梢詫⑵淇粗粋€指派問題，求出它的全局最優(yōu)解即可。對于具體的服務(wù)平臺管轄范圍的分配方案，得出的服務(wù)平臺工作量可能不均衡，有些地方出警時間甚至會超過3分鐘。若允許增加2至5個平臺，可根據(jù)操作分配方案中遇到的問題和分配結(jié)果，確定增加平臺的具體個數(shù)和位置。2.2 問題2的分析問題2的規(guī)模較問題1大得多，但可將解決問題1所制定的服務(wù)平臺管轄范圍的分配方案分別應(yīng)用于各個分區(qū)或整個市區(qū)，通過對比所得結(jié)果是否符合服務(wù)平臺的設(shè)置原則和完成任務(wù)的情況來分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案的合理性。如果有明顯的不合理，再給出有效的解決方案。如果該市地點P(如圖1的P點)處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車逃跑。根據(jù)犯罪嫌疑人逃跑速度和調(diào)度全市交巡警服務(wù)平臺警力資源圍堵嫌疑犯所需的時間，得出嫌疑犯在案發(fā)后的分鐘內(nèi)逃跑的路程。在圖G中，對于以P點為始點的所有出逃道路，無論沿哪條道路，嫌疑犯在分鐘內(nèi)到過的頂點應(yīng)滿足，由此建立包含嫌疑犯的最佳區(qū)域(區(qū)域所包含的頂點和進出該區(qū)域的路口盡可能的少)，快速全封鎖該區(qū)域的方案即為最佳圍堵方案。三、問題假設(shè)1整個市區(qū)各點的海拔高度相差不大，相鄰兩個交叉路口間的道路近似為直線段；2圖1所示的交通網(wǎng)絡(luò)對應(yīng)的道路皆為雙向車道；3每個路口節(jié)點，平均每天發(fā)生的報案數(shù)包含它附近發(fā)生的案件；4警員到達出事地塊邊緣即為到達出事地點；5出警時道路恒暢通(無交通事故、交通堵塞等發(fā)生)，警車行駛正常；6出警時總是沿最短路到達出事點。四、符號說明： 圖1所示的交通網(wǎng)絡(luò)圖，其中為頂點集，為邊集；： 圖的頂點標號；：圖的權(quán)矩陣，其中為圖的邊的權(quán)，取值見(2.1)；：最短路長矩陣，其中為從點到達的最短路長；： 頂點的發(fā)案率；： 服務(wù)平臺工作量的度量，為服務(wù)平臺管轄的所有頂點的發(fā)案率之和；： 各服務(wù)平臺工作量數(shù)據(jù)的標準差；: 表示嫌犯逃跑時的平均車速: 表示分鐘內(nèi)嫌犯逃跑的最大半徑: 表示分鐘內(nèi)嫌犯逃跑的最大范圍五、模型建立與求解5.1 服務(wù)平臺管轄范圍的最優(yōu)分配方案的條件模型對于A區(qū)，設(shè)各服務(wù)平臺Ak(k=1,2,，20)的管轄范圍為頂點集，其中為A區(qū)交通網(wǎng)絡(luò)圖的頂點集的子集，并且兩兩不相交，(A區(qū)交通網(wǎng)絡(luò)圖的頂點個數(shù)為92)。用表示頂點的發(fā)案率，用作為服務(wù)平臺Ak(k=1,2,，20)的每天工作量的度量，為各服務(wù)平臺工作量數(shù)據(jù)的標準差，那么，A區(qū)服務(wù)平臺管轄范圍的最優(yōu)分配方案應(yīng)滿足： (5.1)5.2 分配服務(wù)平臺管轄范圍的算法及計算結(jié)果分配服平臺管轄范圍，我們采用覆蓋的方法確定管轄范圍。具體地，對于A區(qū)，一共有20個服務(wù)平臺，對應(yīng)的最短路長矩陣為。為確保出現(xiàn)突發(fā)事件時，盡量能在3分鐘內(nèi)有交巡警(警車的時速為60km/h)到達事發(fā)地，在上構(gòu)造覆蓋矩陣，其中為服務(wù)平臺Ak(k=1,2,，20)對應(yīng)的頂點，且 (5.2)若第行的第個元素的值為，那么頂點可納入服平臺Ak的管轄范圍。由于該區(qū)的服務(wù)平臺分布不均衡，一方面，存在3分鐘內(nèi)不能到達事發(fā)地的頂點；另一方面，在頂點密集區(qū)，存在同屬于兩個以上服務(wù)平臺管轄范圍頂點(稱為重復頂點)。對于在3分鐘內(nèi)不能到達的頂點，則將它納入距它最近的服務(wù)平臺的管轄范圍；對于同屬于兩個以上服務(wù)平臺的頂點(不含服務(wù)平臺所在的頂點)，我們考慮均衡A區(qū)各服務(wù)平臺的工作量以及出警時間的原則綜合考慮采用發(fā)案率與出警時間，將它們均衡分配給其中的某一個服務(wù)平臺，具體算法如下：Step1：將非重復頂點直接分配給各服務(wù)平臺；Step2：將發(fā)案率和出警時間歸一化，分別嘗試給發(fā)案率和出警時間賦權(quán)值，根據(jù)各服務(wù)平臺管轄頂點的總發(fā)案率和出警時間，令 (5.3)算出每個服務(wù)平臺的得分。Step3：定義矩陣用于表示重復頂點和它所屬服務(wù)平臺的情況，具體地，的每行的第一個元素為重復頂點的標號，后面的元素依次為該頂點所屬的服務(wù)平臺對應(yīng)頂點的標號(不只一個)，為了運算上的方便，將矩陣設(shè)置為選擇方案數(shù)最多的維數(shù)，不滿個選擇的頂點，先存儲可選擇服務(wù)平臺標號，余下的元素用21補位）Step4：選擇矩陣的任意一行(原則上，可以從第一行取到最后一行)，得到該行所表示頂點可選擇的服務(wù)平臺，將該路口分配給其中得分最少的服務(wù)平臺，并將該路口與服務(wù)平臺的得分加到該服務(wù)平臺的得分中。Step5：選擇下一行。重復Step4，直到矩陣中每一行元素都有且只有一次被分配。實現(xiàn)上述算法的程序見附錄的文件夾1_3，運行程序算出A區(qū)各頂點在不同權(quán)重下服務(wù)平臺管轄范圍的分配方案和各服務(wù)平臺工作量的標準差見表1。表1權(quán)重（0.4,0.6）(0.3,0.7)(0.2,0.8)標準差2.24992.28512.2718當出警時間和發(fā)案率的權(quán)重為0.4:0.6時，得出各服務(wù)平臺工作量的標準差最小，分配效果最好。但在這一方案下，分布最密集的1號服務(wù)平臺所管轄的范圍，其中頂點80，82，43，67，70出現(xiàn)“越界”情況。也就是說，如果1號服務(wù)平臺要到頂點80，82，43，67，70，必須途經(jīng)18號服務(wù)平臺所轄的78號頂點，2號服務(wù)平臺所轄的69號頂點，19號服務(wù)平臺所轄的68號頂點。這樣和實際生活中大相徑庭。為了盡量避免“越界”情況的發(fā)生，則對上述分配方案進行改進。具體方法如下：先確定每個服務(wù)平臺以內(nèi)的所有不重復的頂點，并將其分配給對應(yīng)的交巡警平臺，保證在每個服務(wù)平臺的內(nèi)不會出現(xiàn)“越界”情況。對于沒被分配的頂點，按照原先的算法得出分配結(jié)果?？紤]到實際管轄的合理性。我們考慮每個服務(wù)平臺被分配的管轄范圍是否有“越界”情況。用改進的算法給出重新分配的方案，我們同樣尋找1號服務(wù)平臺所轄范圍的“越界”情況。在重新分配后，1號服務(wù)平臺只有兩個出現(xiàn)“越界”的頂點。即頂點65，67，必須經(jīng)過19號服務(wù)平臺的68號頂點。由此說明，改進后的分配方案要比為改進的方案更合理。這樣的改進務(wù)必會使服務(wù)平臺發(fā)案率的標準差有所增加(從2.2249增加到2.3702)，但是聯(lián)系實際，本文啟用改進后的分配方案，確定每個服務(wù)服務(wù)平臺的管轄范圍(見表2)。增加服務(wù)平臺保證A區(qū)發(fā)生突發(fā)事故時，都有交巡警在3分鐘內(nèi)到達事發(fā)地，現(xiàn)在A區(qū)服務(wù)平臺工作量的標準差為1.9906，比未增加前減少了0.3796，說明現(xiàn)在設(shè)置的服務(wù)平臺，工作量比未添加服務(wù)平臺前更均衡，更具合理性，但需要更多的警力資源。表2 各服務(wù)平臺的管轄范圍表服務(wù)平臺服務(wù)范圍A11 65 67 69 71 74 75 78A22 39 40 43 44 70 72A33 54 55 64A44 57 60 62 63A55 48 49 50 52 53 56 59A66 47 51 58A77 30 61A88 32 33 45 46A99 31 34 35 37A1010A1111 26 27A1212 25A1313 21 22 23 24A1414A1515 28 29A1616 36 38A1717 41 42A1818 73 80 81 83 88 91A1919 66 68 76 77 79A2020 82 84 85 86 87 89 905.3 快速全封鎖A區(qū)的模型與方案對A區(qū)的交通網(wǎng)絡(luò)圖，用表示服務(wù)平臺集，表示進出A區(qū)的路口集, 調(diào)度全區(qū)20個服務(wù)平臺的警力資源將進出該區(qū)的13個路口快速全封鎖，可將其看著一個指派問題，指派模型如下2： (5.4)式中：是到的最短路長。用lingo軟件進行求解(代碼見附錄代碼3)，得全局最優(yōu)解，最優(yōu)調(diào)度方案如表3。表3：調(diào)度方案表服務(wù)平臺標號進出口標號服務(wù)平臺標號進出口標號A1A1122A238A1212A3A1323A462A1421A548A1528A6A1616A730A17A829A18A914A19A1024A205.4 增加A區(qū)服務(wù)平臺的方案對于A區(qū)現(xiàn)有服務(wù)平臺的設(shè)置，按我們所提出的管轄范圍分配方案，依然存在交巡警服務(wù)平臺的工作量不均衡和有些地方出警時間過長的情況(見表4)。.表4：交巡警工作量（發(fā)案率）一覽表服務(wù)平臺標號發(fā)案率服務(wù)平臺標號發(fā)案率A18.1A114.6A29.7A124.0A34.9A138.5A45.8A142,5A59.2A154.8A66.0A164.9A75.1A175.3A87.9A187.7A96.9A196.2A101.6A2010.8為了均衡各服務(wù)平臺的工作量和縮短出警時間，我們給出以下方案：首先，找出工作量繁重的服務(wù)平臺，服務(wù)平臺A20號的所管轄路口的發(fā)案率總和最大，距A20號服務(wù)平臺最近的A18號服務(wù)平臺的發(fā)案率總和為7.7，高于A區(qū)所有服務(wù)平臺管轄路口發(fā)案率的平均值6.225。所以在A20號和A18號服務(wù)平臺附近增加一個服務(wù)平臺是十分必要的。經(jīng)過對服務(wù)平臺和各街道路口的分布圖的分析，選定在標號為91號的路口添加服務(wù)平臺。其次，A13號服務(wù)平臺的管轄范圍為21，22，23，24號路口，工作量也較大，且處在A區(qū)的出入口；23號路口的發(fā)案率又高達2.4，為了降低23號路口的發(fā)案率，由于13號路口是進入23號路口的必經(jīng)之路，所以考慮在13號路口臨近的22號路口增設(shè)服務(wù)平臺。最后，在3分鐘內(nèi)沒有到達交巡警到達的路口(28，29，38，39，61，92)增加交巡警服務(wù)平臺。其中28，29號路口可以被同一個交巡警服務(wù)平臺管轄，由于29號路口的發(fā)案率為1.3，29號路口的發(fā)案率為1.4，則任取一個路口設(shè)置交巡警服務(wù)平臺即可，這里我們選取28號路口；38，39號路口也可以被同一個交巡警服務(wù)平臺管轄，由于38號路口為 A區(qū)的出口，則選擇在38號路口設(shè)置服務(wù)平臺；61號路口距其他路口距離稍遠，獨立設(shè)置一個交巡警服務(wù)平臺；由于先設(shè)置了91號交巡警服務(wù)平臺，可以在3分鐘內(nèi)到達92號路口，于是不考慮再為92號路口設(shè)置服務(wù)平臺。最終得出A區(qū)增加的服務(wù)平臺為5個，分別位于22，29，38，61，91號路口。采用5.2分配服務(wù)平臺管轄范圍的算法，對A區(qū)增加服務(wù)平臺后的新服務(wù)平臺設(shè)置，再次劃分各服務(wù)平臺的管轄范圍(管轄分配情況見表5)。表5 新服務(wù)平臺設(shè)置下的管轄范圍分配表服務(wù)平臺服務(wù)范圍A11 67 68 71 72 74 75 78A22 40 43 44 70A33 54 55 65 66A44 57 60 62 63 64A55 49 50 52 53 56 59 A66 47 51 58A77 30 31 48A88 33 45 46A99 32 34 35A1010A1111 26 27A1212 25A1313 23 23 24A1414A1515A1616 36 37A1717 41 42A1818 73 81 82 83A1919 76 77 79 80A2020 84 85 86 89A2929 28A2222 21A3838 39A6161A9191 87 88 90表6 新服務(wù)平臺設(shè)置下的服務(wù)工作量表服務(wù)平臺標號發(fā)案率服務(wù)平臺標號發(fā)案率A17.3A142.5A27.4A152.1A34.9A165.1A45.8A175.3A57.8A187.3A66.0A195.3A77.5A206.6A86.5A212.7A95.3A222.8A101.6A234.3A114.6A240.6A124.0A254.6A135.75.5 市區(qū)現(xiàn)有服務(wù)平臺設(shè)置方案的合理性分析圖3 現(xiàn)有服務(wù)平臺服務(wù)范圍覆蓋圖類似5.2節(jié)，對各個分區(qū)應(yīng)用其算法得到一個全市區(qū)各服務(wù)平臺管轄范圍分配方案，對整個市區(qū)我們也求得另一個分配方案，這個方案比分區(qū)處理要好得多，但仍不能否符合服務(wù)平臺的設(shè)置原則和任務(wù)(數(shù)據(jù)詳見附件)，說明該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案很不合理。實事上，運用Matlab畫圖函數(shù)畫出各個路口的散點圖，以每個交巡警服務(wù)平臺為圓心，為半徑畫圓。圓內(nèi)的頂點表示被其所屬的服務(wù)平臺。事實上，圖中的管轄范圍管轄的路口到對應(yīng)的服務(wù)平臺可能大于，因為實際道路是各個道路相連的折線段，而圖中用直線代替服務(wù)半徑，由直線距離小于折線距離可知，沒有被分配管轄范圍的路口到任意交巡警服務(wù)平臺一定大于，即3分鐘內(nèi)一定沒有交巡警到達事發(fā)地，由圖3可知，這樣不合理的路口多達167個，顯然現(xiàn)在全市交巡警服務(wù)平臺的分布是不合理的。5.6 市區(qū)服務(wù)平臺設(shè)置評價模型根據(jù)服務(wù)平臺負載情況來均衡各服務(wù)平臺的工作量以及出警時間的原則和任務(wù)，將服務(wù)平臺管轄范圍內(nèi)的發(fā)案率和到其所轄頂點的最短路作為服務(wù)平臺設(shè)置的評價指標。模糊目標函數(shù)均值聚類法中的目標函數(shù)采用極小化類別方法3，假如可供選擇的服務(wù)平臺有個，則，按照個指標來劃分，即，將其分為個子集()，其對應(yīng)的模型為： (5.5) (5.6)其中：為加權(quán)指數(shù)，一般情況下為大于等于1的定值；為元素屬于類別的隸屬度；為模糊分類矩陣；是類別的聚類中心；。新的服務(wù)平臺對應(yīng)的頂點編號為：156 398 354 36 17 183 449 428 437 135 14 219 432 212 47 471 442 306 450 2 405 394 10 78 208 227 509 568 318 238 334 5 581 463 58 512 106 224 197 460 222 263 408 388 344 144 28 278 54 577 186 142 110 162 528 400 366 331 554 572 82 192 200 25 303 23 520 66 483 514 413 298 89 289 253 269 343 338 545 293 252 448 493 71 564 499 582 124 311 201 379 459 348 502 203 454 300 259 62 482。圖4 重置服務(wù)平臺后服務(wù)范圍詳細數(shù)據(jù)見“附件4_重置方案后的結(jié)果”。5.7 圍堵重大刑事案件嫌疑犯的最佳方案方案如果該市地點P(如圖1的P點)處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車逃跑。設(shè)嫌疑犯逃跑平均車速為，據(jù)此可以算出分鐘內(nèi)嫌疑犯逃跑的最大半徑。以點為圓心，為半徑畫圓，可以得出分鐘內(nèi)嫌犯逃跑的最大范圍，從而可以確定在這段時間內(nèi)嫌犯可能經(jīng)過的路口，設(shè)以這些路口構(gòu)成的集合為，對需要封鎖路口的個數(shù)及具體位置的確定問題，轉(zhuǎn)化為在圖G的邊集中求始點在中而終點不在中的邊的終點和終點在中而始點不在中的邊的始點構(gòu)成的集合所包含的元素個數(shù)和具體元素，即集合的元素個數(shù)即為需要封鎖的路口個數(shù)，集合所包含的元素對應(yīng)需要封鎖的路口。算法步驟為：Step1：輸入嫌犯逃跑速度；Step2：計算3分鐘內(nèi)嫌犯逃跑的最大范圍，并找出屬于這一范圍內(nèi)的頂點，并以這些頂點的編號為元素做成集合；Step3：以全市交通網(wǎng)絡(luò)圖路線表中的數(shù)據(jù)作邊集其中m表示邊集所包含的元素個數(shù)，為整數(shù)，且。Step4： 求在圖G的邊集中求始點在中而終點不在中的邊的終點和終點在中而始點不在中的邊的始點構(gòu)成的集合所包含的元素個數(shù)和具體元素。由于服務(wù)平臺在案發(fā)后3分鐘才接到報警，假設(shè)嫌犯逃跑車速為，服務(wù)平臺接到報警電話后，馬上開始組織搜捕工作，且在3分鐘內(nèi)封鎖所有出口，此時嫌犯已駕車逃跑時間，逃跑的最大半徑，以點(32號路口)為圓心，為半徑畫圓，可以得出6分鐘內(nèi)嫌犯逃跑的最大范圍即為該圓的面積。由最短路長矩陣進行分析可知，此時嫌犯最遠可能在距離點的道路上的具體位置分別是以下37個路口(如表1所示)以外，相鄰的下一個以外的站點之內(nèi)。表7：與之間的最短路小于等于的頂點567891516303132333435363745464748495051525355565961173232233234235236237245247據(jù)此，以這37個路口的編號作為元素構(gòu)成集合用“附件2_全市六區(qū)交通網(wǎng)路和平臺設(shè)置的數(shù)據(jù)表”所給出的全市交通路線的路線表中的數(shù)據(jù)作邊集求在圖G的邊集中求始點在中而終點不在中的邊的終點和終點在中而始點不在中的邊的始點構(gòu)成的集合所包含的元素個數(shù)和具體元素。具體求解過程見附錄的MATLAB程序luokouqueding.m，通過求解可知需要對17個路口進行封鎖，這些路口的編號分別如表8所示：表8：需要封鎖的頂點31014282938395457 860168231238244246560然而結(jié)合下面給出的點到各個頂點路口的有向賦權(quán)圖5進行分析：圖5 點到各個頂點路口的有向賦權(quán)圖發(fā)現(xiàn)存在兩個問題，一是有些服務(wù)平臺位于待封鎖點的前一個位置，同時滿足距離點的距離在以外以內(nèi)，對于滿足此類條件的服務(wù)平臺，考慮直接將該路口進行封鎖，即可節(jié)省部分用于封鎖該點以外路口的警力，比如16號服務(wù)平臺，距離點的距離為，此時考慮將該服務(wù)平臺直接進行封鎖，即可節(jié)省原本需要用于封鎖路口14號、38號以及560號的警力；二是對于無法實現(xiàn)3分鐘到達的路口，將封鎖地點向外移動，直到能夠?qū)崿F(xiàn)最短時間封鎖，比如60號路口，不存在三分鐘內(nèi)可以到達的服務(wù)平臺，此時考慮將待封鎖地點向外移動到62號路口，并用1號服務(wù)平臺對其進行封鎖，即可實現(xiàn)最短時間封鎖。在已確定17個待封鎖路口的基礎(chǔ)上綜合以上兩點，可得具體可行的最短時間封鎖方案如表9所示：表9：最短時間封鎖方案待封鎖點編號用于進行封鎖工作的服務(wù)平臺所對頂點的編號所需封鎖時間(min)322.11101001616040172.695432.275741.876214.8916816802311722.782401714.92441732.252461712.952481673.68由此可知，總共需要封鎖13個路口，計算得封鎖所需時間為4.9分鐘。六、模型的優(yōu)缺點及推廣優(yōu)點：1得出了服務(wù)平臺的管轄范圍，均衡了服務(wù)平臺的工作量，并且?guī)缀鯖]有“越界”的情況。2在任意地區(qū)發(fā)生重大刑事案件，都可以得出最短時間內(nèi)的圍堵方案。缺點：1對于大型數(shù)據(jù)量，確定服務(wù)平臺的管轄范圍比較繁瑣。2沒有考慮在同一個服務(wù)平臺同時發(fā)生兩起案件的情況。推廣：服務(wù)平臺選址的模型，同樣適用于物流網(wǎng)點、超市、垃圾轉(zhuǎn)運站的設(shè)立。參考文獻1 代西武, Dijkstra矩陣算法J, 北京建筑工程學院學報, 第23卷 第2期: 65-66,2007年6月.2 謝金星, 優(yōu)化建模與lindo/lingo軟件, 清華大學出版社.3 張兆民, 模糊C-均值在內(nèi)陸無水港選址中的應(yīng)用J, 上海海事大學學報, 第29卷第4期,3437,2008年12月.附錄：1最短路代碼，D.mn=582;A=ones(n)+inf;for i=1:n A(i,i)=0;endB=xlsread(點位置.xls,B2:C583);C=xlsread(可達點.xls,A2:B929);for i=1:928 A(C(i,1),C(i,2)=sqrt(B(C(i,1),1)-B(C(i,2),1)2+(B(C(i,1),2)-B(C(i,2),2)2);endfor i=1:582 for j=1:582 if A(i,j)=inf&A(i,j)=0 A(j,i)=A(i,j); end endenda=Dijstra(A);a=a/10;Dijstra.mfunction a=Dijstra(a)n=length(a);for i=2:n for j=1:(i-1) a(i,j)=a(j,i); endendfor k=1:(n-1) b=1:(k-1),(k+1):n; kk=length(b); a_id=k; b1=(k+1):n; kk1=length(b1); while kk0 for j=1:kk1 te=a(k,a_id)+a(a_id,b1(j); if tea(k,b1(j) a(k,b1(j)=te; end end miid=1; for j=2:kk if a(k,b(j)k miid1=find(b1=a_id); b1=b1(1:(miid1-1),b1(miid1+1):kk1); kk1=length(b1); end end for j=(k+1):n a(j,k)=a(k,j); endend2lingo代碼：model:!17個警力平臺，10出口;sets: jingli/1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20/; chuko /12 14 16 21 22 23 24 28 29 30 38 48 62/; Assign(jingli,chuko):c,x;endsets! 加權(quán)矩陣;data: c =22.24 16.03 9.29 19.29 21.10 22.50 22.89 19.00 19.52 12.08 5.88 11.85 4.89 20.46 14.13 7.39 17.39 19.20 20.60 21.12 17.23 17.74 10.31 3.98 10.31 6.04 18.35 12.77 6.03 16.03 17.83 19.24 19.01 15.12 15.63 8.20 6.09 8.20 4.39 22.00 15.01 8.27 18.27 20.08 21.48 22.65 16.23 15.54 8.10 4.86 7.40 0.35 17.63 12.97 6.23 16.23 17.75 19.16 18.29 11.31 10.62 3.18 9.42 2.48 5.26 17.66 13.00 6.26 16.27 17.78 19.19 18.32 11.34 10.65 3.21 9.45 2.51 5.4 14.91 10.90 4.16 14.17 15.04 16.44 15.57 8.57 8.02 0.58 7.35 1.29 7.99 14.09 9.43 2.69 12.70 14.21 15.62 14.75 10.23 10.49 3.06 5.89 3.10 8.68 13.01 8.27 1.53 11.54 13.13 14.54 13.67 9.78 10.72 3.49 4.73 4.20 9.34 7.59 1