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

1、2011 題交巡警服務(wù)平臺的設(shè)置與調(diào)度 “有困難找警察,是家喻戶曉的一句流行語。警察肩負著刑事執(zhí)法、治安管理、交 通管理、服務(wù)群眾四大職能。為了更有效地貫徹實施這些職能，需要在市區(qū)的一些交通要 道和重要部位設(shè)置交巡警服務(wù)平臺。每個交巡警服務(wù)平臺的職能和警力配備基本相同。 由于警務(wù)資源是有限的，如何根據(jù)城市的實際情況與需求合理地設(shè)置交巡警服務(wù)平臺、 分配各平臺的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個實際課題。 試就某市設(shè)置交巡警服務(wù)平臺的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問題： （1）附件1 （見原題）中的附圖1 （見原題）給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和 現(xiàn)有的20個交巡警服務(wù)平臺的設(shè)置

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

3、 務(wù)平臺的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案（參見 附件）的合理 性。如果有明顯不合理，請給出解決方案。 如果該市地點P （第32個節(jié)點）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后 接至報 警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調(diào)度全市交巡警服務(wù)平臺警 力資源的最佳圍堵方案。 解答與程序 問題1 對該問題的解決，我們先建立數(shù)學(xué)模型，將需要達至的目標，包括至達事發(fā)地的時間盡量 短，各服務(wù)平臺的工作量盡量均衡，用目標函數(shù)表達出來，同時將需要滿足的 約束也表達出來，構(gòu)成合適的數(shù)學(xué)模型。然后討論求解算法，最后給出具體的計 算結(jié)果。 我們的路口管轄分配方案分為兩步。 第一步：對T

4、j3的路口，分配給到達第j個路口時間最少的平臺。 第二步：對Tj乞3的所有路口，根據(jù)盡量使各平臺分配的任務(wù)量盡量均衡的原則進行 優(yōu)化。 計算得到3分鐘不能到達的路口及所屬平臺信息見表1。 表13分鐘不能到達的路口及所屬平臺信息 序號 路口 任務(wù)量 所屬平臺 最短時間（分鐘） 1 28 1.3 15 4.75 2 29 1.4 15 5.70 3 38 1.2 16 3.41 4 39 1.4 2 3.68 5 61 0.6 7 4.19 6 92 0.8 20 3.60 因此，我們將這6個路口分配給最近的平臺，剩下的 86個路口建立模型，根據(jù)任務(wù)量 盡量均衡的原則進行優(yōu)化。 實現(xiàn)的Matlab

5、程序見附錄1的b2011_1 .m,利用Floyd算法計算92個路口的最短 路矩陣，輸出表1數(shù)據(jù)。輸出20個平臺和剩余86個待分配路口的最短路矩陣文件 dt1.txt, 86個路口的任務(wù)量文件ftl.txto以及20個平臺和13個交通要 道的距離矩陣文件 dis1.txt,該數(shù)據(jù)文件用于第二問計算。 模型建立 設(shè)有20個平臺，路口有86個。 dij表示第i個平臺與第j個路口之間的最短路，由Floyd算法求得。 V為警車行駛速度。這里取 V - 60公里/小時=1000米/分。 、亠一1 第j個路口分配給第i個平臺 建立決策變量x“ 決策變ij0第j個路口不分配給第i個平臺 每個路口只分配給一個

6、平臺，有約束： 20 Xijj =1,2,.,86 i 每個平臺至少管理一個路口，有約束： 86 * Xij -1 i -1,2,., 20 j$ 每個平臺管理自己的路口，則有: 第j個路口到指派的平臺的時間為tj,滿足: 20 tj八 Xj.dij/vj=1,2,.,86 i4 其時間應(yīng)滿足不超過3份鐘，則有: ti-3j = 1,2,. ,8 計算第i個平臺分配的路口數(shù)的任務(wù)量為。設(shè)已知第j個路口的任務(wù)量(平均每天的發(fā) 生報警案件數(shù)量)為 fj, j =1,2,86,則第i個平臺已經(jīng)分配到的任務(wù)量： 86 Sj = w fj .Xij y i =1,2,., 20 Wi為各平臺已分路口數(shù)的

7、任務(wù)量。由表1知為w2=1.4, Wy=0.6, = 1.4 1.3 = 27, W|6 =1.2,W20 = 0.8o 其余為 0o 各平臺分配的任務(wù)量平均值為: 20 20 我們的冃標是各平臺分配的任務(wù)量的標準差盡量小。即: 20 正g minZ=j 丫 20-1 因此我們得到的綜合模型為： 20 z (S -S)2 minZ 二 1 xj _1 j =12 .,86 i4 86 7Xj-1 j4 Xjj 二 1 i 二 i =1,2,.,20 1,2,. .,20 20 tjSt A Xj.dij/vj =1,2,.,86 tj i4 3j“2 ，86 86 S = Wj ，.芻 i =

8、1,2,，20 20 i 4 20 Xjj=0 或 1 i =1,2,., 20; j -1,2,.,86 LINGO程序見附錄2的b2011_1.lg4o 采用Lingo12優(yōu)化很快得到Z=1.76,表示每個平臺的任務(wù)量平均有1.76件的波動 各平臺的分配方案見表2o 表2各平臺管轄的路口分配及任務(wù)量 平臺 管轄的路口 總?cè)蝿?wù)量 取長時間（分鐘） 1 1,64,71,72,77,78,79,80 7.60 2.60 2 2,40,69,74 7.40 2.53 3 3,44,54,55,70,76 7.20 2.97 4 4,57,60,62,63,65,66 7.30 2.84 5 5,4

9、9,53,56,59 6.10 2.08 6 6,50,51,52,58 6.10 2.38 7 7,30,48 6.50 1.29 8 8,32,33,47 6.90 2.08 9 9,35,36,37,45 6.10 1.43 10 10, 1.60 0 11 11,26,27 4.60 1.64 12 12,25 4.00 1.79 13 13,21,22,23,24 8.50 2.71 14 14 2.50 0 15 15,31 6.40 2.97 16 16,34,46 6.70 2.38 17 17,41,42,43 7.00 1.79 18 18,85,87,89,90,91 7

10、.40 2.63 19 19,67,68,73,75,82,83 7.20 2.79 20 20,81,84,86,88 7.40 2.68 問題2 給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個交巡警服務(wù)平臺的設(shè)置情況示意圖, 相關(guān)的數(shù)據(jù)信息見附件2 （見原題）。對于重大突發(fā)事件，需要調(diào)度全區(qū)20個交巡警服務(wù)平 臺的警力資源，對進出該區(qū)的 13條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多 封鎖一個路口，我們的目的是給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。 對該問題，我們先建立最優(yōu)的調(diào)度模型，使各服務(wù)平臺到達交通要道的時間盡量的短。 然后討論求解算法，最后給出具體的計算結(jié)果。 模型建立

11、對于重大突發(fā)事件，需要調(diào)度城市的交巡警服務(wù)平臺的警力資源，對進出該 區(qū)的多條交通要道實現(xiàn)快速全封鎖。采用的模型如下。 設(shè)該市有20個平臺，要封鎖的交通要道有13個。 dj表示第i個平臺與第j個交通要道之間的最短路，由Floyd算法求得。 v為警車行駛速度。這里取v=60公里/小時=1000米/分鐘 設(shè)決策變量人第丿個路口分配給第個平臺圍堵 j0第j個路口不分配給第i個平臺圍堵 對每個交通要道，需要且只需要分配一個平臺的警力，則有： 20 1 ：彳,2, ,. 3 xij - J - I I i 1 每個交巡警服務(wù)平臺的警力最多到一個交通要道去圍堵，因此有： 13 、x 豈 1 i =1,2,2

12、0 j壬 設(shè)Tj表示到第j個路口的時間。則有： 201213 SdjXj/vj =， i =1 我們選取的第一目標是到交通要道的最長時間最小化，這樣可使最長時間盡量小。 則第一目標函數(shù)為： mi n = maxTj 1直V3 當最長時間最小情況下，我們同時對小于最時間的分配方式進行優(yōu)化，使到 達各交通要道的時間平均時間最小。則第二目標函數(shù)為： 13 7 min Z2 二 13 綜合上述，我們建立的的綜合模型為: 13 Tj min Z2 13 20 x ij = i i4 13 EXj1 S.tj 二 20 j =12.,13 i =1,2,.,20 Tj =S dij Xij / V id

13、Xj=0 或 1 LINGO程序見附錄3的b2011_2g4?？上葍?yōu)化第一目標，得到最短時間為8.02分鐘。 然后將Z1乞8.02作為約束優(yōu)化第二目標，得到最小的平均時間為3.55分鐘。圍堵的具 體方案見表3。 表3 LINGO求解的最優(yōu)分配方案 序號 交通要道號 分配的平臺號 到達時間（分鐘） 1 12 12 0 2 14 16 6.74 3 16 9 1.53 4 21 14 3.26 5 22 10 7.71 6 23 13 0.5 7 24 11 3.81 8 28 15 4.75 9 29 7 8.02 10 30 8 3.06 11 38 2 3.98 12 48 5 2.48 1

14、3 62 4 0.35 該模型由于是非線性的，利用LINGO求解較為費時，通常也不能保證最優(yōu)解。為 此。我們也可以另外設(shè)計算法，便于快速求解，同時便于在后面的圍堵問題中快速求解。 3、算法設(shè)計 我們的求解算法采用三步完成。第一步，先利用貪婪法盡量使各平臺到達交通要道 的時間盡量短。第二步，對到各交通要道的時間再進行調(diào)整，進一步優(yōu)化，直到最長時 間不能再減少為止。第三步，在保證最長時間不增大的情況下，對到各交通要道的平均時 間進行調(diào)整，直到不再減小為止。 算法步驟： 1 先將13個交通要道依次分配給最近的路口。 2將時間最長的要道與其余的要道分配的平臺對換，若最長時間可以減少，則對 換。實際中可

15、在對換后，另一要道在剩余平臺中選擇最近的平臺。 3重復(fù)2直到最長時間不再減少為止。 對平均時間的減少采用同樣的方法。直到總時間或平均時間不再減小結(jié)束。輸出各 路口對應(yīng)平臺及時間，平均時間。 采用步驟1中貪婪法求得最長時間為13.67分鐘，平均時間為3.95分鐘。采用步驟 二中減少最長時間的算法，經(jīng)過5次調(diào)整，最長時間達到最小。最長時間為8.02分鐘， 平均時間為3.78分鐘。計算的結(jié)果見表4。遺憾的是沒有達到最小的3.55分鐘。但該方 法的優(yōu)點是計算速度快。不到1秒就可以計算出結(jié)果， 比LINGO計算的2分多鐘快多了。 表4貪婪算法計算出的圍堵方案 序號 交通要道號 分配的平臺號 到達時間（分

16、鐘） 1 12 10 7.59 2 14 16 6.74 3 16 9 1.53 4 21 14 3.26 5 22 11 3.27 6 23 13 0.5 7 24 12 3.59 8 28 15 4.75 9 29 7 8.02 10 30 8 3.06 11 38 2 3.98 12 48 5 2.48 13 62 4 0.35 對全市所有路口的圍堵，我們可建立同樣模型，分別采用LINGO和我們提 出的貪婪算法計算。 全市路口的圍堵計算： 全市有交巡警平臺80個，全市出入口位置有17個。要封鎖的交通要道m(xù)=17個，其集 合為 J =151,153,177,202,203,264,317,

17、325,328,332,362,387,418,483,541,572,578。 可 供分配的平臺 n =80 個,其集合為 P= 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18, 19,20,93,94,95,96,97, 98,99,100,166,167,168,169,170,171,172,173,174,175,176,177, 178,179, 180,181,182,320,321,322,323,324,325,326,327,328, 372,373,374,375,376, 377,378,379,380,381,382,383,

18、384,385,386,475,476,477,478,479,480,481,482,483,484 ,485。 采用步驟一中貪婪法求得最長時間為12.68分鐘，平均時間為5.07分鐘。該 結(jié)果通過調(diào)整并不能減少最長時間，可以驗證，該分配方案中，除202號交通要 道外，其余各交通要道都分配的到達時間最短的平臺。而到達202號交通要道的時間最 少的平臺為177,次之為175, 177號平臺分配177號交通要道最佳，從而分配175號平 臺202號交通要道最佳。總的計算結(jié)果是最長時間最小為1268 分鐘，平均時間最小為5.07分鐘?？沈炞C該結(jié)果即為最優(yōu)結(jié)果。詳細結(jié)果見表5。 表5全市利用貪婪算法計

19、算出的圍堵方案 序號 交通要道號 分配的平臺號 到達時間（分鐘） 1 151 96 3.19 2 153 99 4.47 3 177 177 0 4 202 175 11.62 5 203 178 4.45 6 264 166 6.62 7 317 181 5.48 8 325 325 0 9 328 328 0 10 332 386 7.62 11 362 323 8.11 12 387 100 12.68 13 418 379 7.419 14 483 483 0 15 541 484 7.04 16 572 485 1.66 17 578 479 5.76 對比：利用Lingo12求解，

20、耗時41分鐘，得到局部最優(yōu)解為35.6分鐘因此，當規(guī) 模變大時，采用簡單的貪婪算法有時候更方便快速。 問題3 給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個交巡警服務(wù)平臺的設(shè)置情況示意圖， 相關(guān)的數(shù)據(jù)信息見附件2o根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警時間過 長的實際情況，擬在該區(qū)內(nèi)再增加2至5個平臺，請確定需要增加平臺的具體個數(shù)和位 置。 對該問題，我們先建立最優(yōu)的調(diào)度模型，使各服務(wù)平臺到達交通要道的時間盡量短，各 平臺的任務(wù)量盡量均衡。然后討論求解算法，并最后給出具體的計算結(jié)果。 模型建立 根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警時間過長的實際情況，需要 在一個區(qū)內(nèi)新增

21、加一些平臺。我們需要確定新增加平臺的具體個數(shù)和 位置。 設(shè)該市要巡視的路口有92個，其序號為j=1,2,.,92o交巡警服務(wù)平臺現(xiàn)在 已有20個，其序號為i =1,2,20 dj表示第i個平臺與第j個路口之間的最短路，由Floyd算法求得。 v為警車行駛速度，這里取v = 60公里/小時=1000米/分鐘。 設(shè)增加平臺數(shù)為k個，則總共有平臺20 k個。且所有平臺都在92個路口中選取。 每個路口的日平均案件量為f ri=1,2,.,92o 下面我們建立新增平臺的多目標規(guī)劃模型。 設(shè)變量Yj表示哪些路口選作平臺，設(shè) 丫第j個路口選作平臺少 q jo 第j個路口不選作平臺 建立01決策變量Xj表示平

22、臺處理路口的情況。設(shè) 1第i平臺處理第j個路口 uo第i平臺不處理第j個路口 第j路口需要而且只需要一個平臺處理。則有: 二 Xjj=i,2,9 i4 平臺數(shù)總共為nk個，則有： 92 yj =20 k j4 其中已經(jīng)有20個平臺，且為前20個，因此yj=1 , j =1,2,.,20 只有當?shù)趇個路口選作平臺才能去處理第j路口，因此有： Xijy i,i j 1,2 , .9 考慮各平臺警力到各路口的時間盡量小。我們計算到達各路口的時間。到達 路口 j時間為： 92 Tj 八 Xj.dj/vj =1,2,.,92 我們的目標是讓最長時間最小，因此有： m i nAi m Tx 1恒蘭9 對任

23、務(wù)量，我們考慮將該點的發(fā)案數(shù)作為其度量值，則第i個平臺處理的任 務(wù)量為: 92 W 二，Xjj. fj i =1,2,. , 9 jA 當yuO時，所有Xj-O, j=1,2,.,92o則w=0o即該點沒有選作平臺，其任務(wù)量為 Oo 平均任務(wù)量為： 92 二 Wi W 20 k 下面計算各平臺任務(wù)量的離差平方和。在離差平方和中，其計算式為 92 s = v(Wi-W)2o但這里我們是對任務(wù)量Wi 0的20 k個平臺計算其離差平 i 方和，因此其計算式為: 92 92 S 八 w” -(20 k).W2 樣本標準差為：；-S/(20亠k1) 我們的目標是盡量使各平臺的任務(wù)量均衡，因此有: min

24、 Z2 = min . S/(n k -1) 綜合上述。我們得到的總模型為： min Z2 = min . S/(n k -92 ZXij=1 j=1,2,.,92 i 1 92 Z y. =20 + k i 1 92 Wj/Xj.fji =1,2,.,92 jA 92 送w w = s.t 20+ k 92 s=w： (20+k).W2 i壬 92 Tj二遲 Xj.dj/vj=1,2,.,92 i=1 Xijh i, j =1,2,.,92 %=1, i =1,2,.,20 Xjj=o 或 1i,j =1,2,92 y =0 或 1 i = 21,.,92 該結(jié)果利用LINGO計算十分困難，

25、考慮設(shè)計簡單算法實現(xiàn)。 3、算法設(shè)計 貪婪法 下次再如此進行。 每次從超過3分鐘的路口中選取使最長時間最小的路口作為平臺。 到每個路口到平臺的時間都不超過3分鐘為止。 計算程序為附件4中的b2011_3.mo 對A區(qū)，路口數(shù)92,平臺數(shù)20,超過3分鐘的路口 6個。計算結(jié)果為: Kp= 1 Plat=28 maxT=4.1902 Kp= 2 Plat=61 maxT=3.6822 Kp= 3 Plat=38 maxT=3.6013 Kp= 4 Plat=92 maxT=2.7083 增加4個平臺最佳。 問題4考慮全市6個區(qū)新增平臺情形 對B區(qū)，路口數(shù)73,平臺數(shù)8,超過3分鐘的路口 6 超過3

26、分鐘的路口，平臺，時間 122 94 3.29 123 94 3.37 124 96 3.21 151 96 3.19 152 99 3.37 153 99 4.47 增加平臺數(shù)，最長時間 Kp= 1 Plat=151 maxT=3.3653 Kp= 2 Plat=122 maxT=2.9863對B區(qū)，增加兩個平臺，最長出警時間為2.9863分鐘. 其它區(qū)也可采用該程序計算，之是要讓最大出警時間時候不超過3分鐘，需要增加平臺數(shù)較 多。 全區(qū)同時考慮全區(qū)，路口數(shù)582,平臺數(shù)80,超過3分鐘的路口 138增加平臺數(shù)，最長時間 Kp= 1 Plat=389 maxT=9.1609 Kp= 2 Pl

27、at=329 maxT=8.4671 Kp= 3 Plat=387 maxT=8.1188 Kp= 4 Plat=417 maxT=8.1069 Kp= 5 Plat=362 maxT=7.8085 Kp= 6 Plat=248 maxT=7.0418 Kp= 7 Plat=540 maxT=6.8605 Kp= 8 Plat=199 maxT=6.6223 Kp= 9 Plat=259 maxT=6.6068 Kp=10 Plat=505 maxT=6.5832 Kp=11 Plat=569 maxT=6.5686 Kp=12 Plat=28 maxT=6.4259 Kp=13 Plat=3

28、69 maxT=6.4152 Kp=14 Plat=261 maxT=6.1636 Kp=15 Plat=574 maxT=6.1112 Kp=16 Plat=200 maxT=5.8259 Kp=17 Plat=29 maxT=5.7575 Kp=18 Plat=578 maxT=5.6953 Kp=19 Plat=239 maxT=5.4752 Kp=20 Plat=300 maxT=5.1506 Kp=21 Plat=418maxT=5.0529 從該結(jié)果來看，要讓最大出警時間少于3分鐘，需要增加很多平臺。因此可考慮何時即 可。 問題5.圍堵方案的確定 5.1給定時間t可以包圍罪犯的最小

29、包圍圈的確定 給定時間t,給定罪犯逃跑的速度V,計算出罪犯能逃跑的范圍。這里我們采用點來表 示其逃跑范圍。計算其全市總路口 N =581個中罪犯在t分鐘內(nèi)能到達的點集合，設(shè)為A(t)o計算 公式為: D(i,32) + A(t) -i It,i=12,581 v 其中32點為案發(fā)現(xiàn)場，罪犯的逃跑開始點。D(i,32)為各點到32點的最短距離。 同時計算與A(t)相鄰的點集合，設(shè)為B(t)o |P(i,j) Ji A(t) 其中P(i,j)T表示i與j直接相連；P(i,j)= 0表示i與j不直接相連。該數(shù)據(jù)由附件2 中全市交通路口的路線表單對應(yīng)數(shù)據(jù)得到。 則可以包圍罪犯逃跑區(qū)域 A(t)的最小閉

30、包(用路口節(jié)點表示)為C(t)： C(t)= B(t) -A(t) 這里的減為集合之間的減法。即從點集合B(t)中去掉A(t)中已有的點。 C(t)就是給定時間可以包圍罪犯的最小包圍圈。 二、警察在給定時間t能否到達包圍圈的確定 設(shè)C(t)中節(jié)點個數(shù)為L ,可分配的平臺為 K =80個。我們的目標是采用問題 的模型對平臺的警力進行分配，求出到達各節(jié)點的最長時間值。T(t)o T(t)為模型中(a)的最優(yōu) min Z 二 maxTj 7Xij-1s.t丘人曰 j呂i h,2,.,80 80 j=1,2,，L(a) 80 Tdx/v JIJIJ i =1 Xij=0 或 1 若T(t)乞t -3,

31、則警察可以完成包圍圈C(t)的包圍。否則不能完成包圍。t3是因 為罪犯先逃跑了 3分鐘。 我們的目標就是求出在最短時間完成對罪犯的包圍。因此目標函數(shù)為： mi nZ =t 約束為T(t)乞t-3o 因此總的模型為： mi nZ =t st T(t)蘭 t3 實際計算時，可以采用從 t = 3開始，每隔30秒進行計算，直到滿足約束條件 T(t)空 t_3o 實際計算中平臺數(shù)可以減少。若某平臺的警力在t-3分鐘內(nèi)都不能到達包圍圈G中任意 點，則該平臺刪除。 即可選平臺集合為： Plat -i|Time（i, j）: :t -3,/G,i=1,2,.,80 這樣可大大減少平臺數(shù)，使問題規(guī)模減小，便于

32、求解。 計算程序見附件5中的b2011_5_1.m和附件6中的b2011_5_2.mo計算得到的結(jié)果見圍 堵方案圖2和圍堵方案表6。 600 500 400 300 200 100 50 100150 200250300 350400450 500 圖2圍堵方案圖 其中藍色O為內(nèi)部點紅色為包圍點，藍色為分配的平臺。 表6圍堵方案表 序號 包圍點 平臺號 封鎖時間 份） 罪犯逃跑到該點時 間（分） 1 14 14 3 10.0432 2 17 17 3 10.6504 3 26 11 3.9 9.72654 4 29 15 8.7005 9.15563 5 41 2 6.4411 10.5025

33、 6 43 1 4.8001 9.38794 7 62 4 3.35 9.1319 8 68 19 5.2384 9.15307 9 70 3 5.9719 9.44818 10 76 18 6.1328 9.23845 11 168 168 3 12.4791 12 215 171 6.6274 11.2542 13 217 172 3.9717 9.83724 14 218 170 6.2789 9.44592 15 227 174 6.6998 9.22363 16 240 173 9.6952 10.1541 17 248 167 6.6788 20.5237 18 273 182 5

34、.1024 12.8088 19 371 320 10.361 15.894 20 482 482 3 11.1731 21 487 481 7.565 14.6402 22 549 476 6.0255 10.7206 23 558 475 5.0526 11.0991 24 562 480 4.9416 11.3988 警察在接到報案后，最長完成封鎖時間為10.3613 = 7.361分鐘。 點評： 在完成該題過程中，需要用Matlab編程與LINGQ編程相結(jié)合共同完成問題求解。利 用Matlab可以進行數(shù)據(jù)預(yù)處理，根據(jù)Floyd算法進行最短路計算，對 包圍路線作圖， 以及對自己設(shè)計的算法

35、進行計算。LINGO則可以直接根據(jù)模型進 行優(yōu)化計算，而其中使用的大量數(shù)據(jù)需要通過Matlab計算輸出。這種通過Matlab和 LINGO相互結(jié)合完成計算，是近年來在競賽中經(jīng)常使用的方法。 程序附錄 附件1：數(shù)據(jù)預(yù)處理及輸出數(shù)據(jù)文件的 Matlab程序b2011_1 .m。 %初始數(shù)據(jù)處理，作圖，并得到92個路口之間的最短路A （92,92）, %計算并輸出20個平臺與13個路口之間距離dis1.txt %輸出20個路口到待分配路口 （86個）的距離矩陣（20*86） dt1 .txt %輸出待分配路口的（86） 口的發(fā)案數(shù)ft1.txt %還可對LINGO計算結(jié)果按照規(guī)范形式輸出。 load

36、 DA.txt %所有路口號（582個），x,y,區(qū),發(fā)案率 %街道數(shù)據(jù) load DB.txt; % 連接線,928 條 DA=DA(1:92,:); %取前92個路口信息 ma,na=size(DA); mb,nb=size(DB); pos=12,14,16,21,22,23,24,28,29,30,38,48,62;%A 區(qū)出入口位置 k=20;%1-20 平臺 x=DA(:,2);y=DA(:,3);f=DA(:,5);%分別獲得個路口的x坐標，y坐標,發(fā)案數(shù) plot(x,y,bo,x(1:k),y(1:k),g J; %作圖，藍色為所有路口，綠色為前20個平臺 kp=O; %統(tǒng)計

37、A區(qū)街道數(shù) LineA=zeros(200,2); for i=1:mb if DB(i,1)=92 LineA(kp,1)=DB(i,1); LineA(kp,2)=DB(i,2); end end %將A區(qū)街道的起始點和終點分別放在數(shù)組LineA(kp,1)和LineA(kp,2)中。hold on fprintf(A 區(qū)街道數(shù) %2dn,kp); px=zeros(2,1); py=zeros(2,1); for i=1:kp px(1 )=x(LineA(i,1); py(1 )=y(LineA(i,1)； px(2)=x(LineA(i,2); py(2)=y(LineA(i,2);

38、 plot(px,py); %將A區(qū)所有街道連線 end %利用Floyd算法求任意兩點之間最短路 v=1000;%每分鐘速度 n=92; %A區(qū)路口數(shù)為92 A=zeros(n,n); %存儲任意兩點最短路 for i=1:n forj=1:n if(i=j) A(iJ)=0; else A(i,j)=1000000; end end end for i=1:kp%給每條線路賦予距離 point1=LineA(i,1); point2=LineA(i,2); p1x=x(point1); p1y=y(point1) ; p2x=x(point2); p2y=y(point2); d=sqrt

39、(p1 x-p2x)A2+(p1 y-p2yF2); A(point1 ,point2)=d; A(point2,point1)=d; end U=A; %原始矩陣 %1.1利用Floyd算法計算最短距離矩陣 for k=1 :n for i=1 :n for j=1:n t=A(i,k)+ A(kj); if tA(i,j) A(i,j)=t; end end %end for j end %end for i end %end for k A=100*A;%每毫米代表100米，得到以米為單位的距離. Dis=zeros(20,13);%存儲20個平臺和13個交通要道的距離for i=1:2

40、0 forj=1:13 ip=i； %第ip個平臺 jp=pos(j); % 第 jp 個路口 Dis(i,j)=A(ip,jp); end end%獲得20個平臺和13個交通要道(路口)的距離矩陣 %輸出20個平臺與13個路口之間距離fid=fopen(,d:lingo12datdis1 .txt/w1); %此處目錄可 修改 for i=1:20 forj=1:13 fprintf(fid；%6.2f *,Dis(i,j); end fclose(fid); n=92;% 路口數(shù) m=20; %平臺數(shù) Plat=1:m; % 平臺 T=zeros(1,n); %存儲到各路口的時間 S=ze

41、ros(1 ,n); %存儲到各路口時間最少的平臺號 %求到各路口的最短時間和對應(yīng)的平臺號 forj=1:n jp=j； %路口 mint=1000; for i=1:m ip=Plat(i); % 平臺 t=A(ip,jp)/v; if t3.0 U(j)=O; fprintfC%2d %2d %6.2f %6.2frT,j,S(j),T(j),f(j); end end %輸出超過 3 分鐘 到達的路口 %獲得待分配的路口序號(時間不超過3分鐘的路口) Lu=； for j=1:n if U(j)=1 Lu=Lu,j; end end r=length(Lu); % 剩余路口數(shù) %獲得20

42、個平臺到剩路口(86)的距離矩陣 D=zeros(m,r);%(平臺，路口) fori=1:m %平臺數(shù) m=20 for j=1:r %剩余路口數(shù) r=86 ip=Plat(i); JP=Lu(j); D(iJ)=A(ip,jp); end end fid=fopen(,d:lingo12datdt1.txt,w,); % 輸出 20*86 的距離矩陣 for i=1:m forj=1:r fprintf(fid/%6.2f D(iJ); end fprintf(fid；n,); end fclose(fid); fid=fopen(,d:lingo12datft1 .txt/w); % 輸

43、出剩余 86 個路口的任務(wù)量 for j=1:r k=Lu(j); fprintf(fid,%5.1fn, f(k); end fclose(fid); %此段程序?qū)INGO程序b2011_1 .Ig4計算結(jié)果進行整理，開始時不需要。TEST=1; % 當TEST=1 ,對LINGO計算結(jié)果進行規(guī)范輸出，便于閱讀和寫作。 if TEST=1 %對對Lingo求解結(jié)果進行整合，重新按照規(guī)范格式輸出。x=zeros(m,r); w=0,1.4,0,0,0,0,060,0,0,0,0,0,0,2.7,1.2,0,0,0,0.8; % 初始各平臺的任務(wù)量 %將LINGO計算結(jié)果拷貝在下面 ;x(1,

44、1)=1 ;x(1,59)=1 ;x(1,66)=1 ;x(1,67)=1 ;x(1,72)=1 ;x(1,73)=1 ;x(1,74)=1 ;x(1,75)=1 ; x(2,2)=1 ;x(2,36)=1 ;x(2,64)=1 ;x(2,69)=1 ;x(3,3)=1 ;x(3,40)=1 ;x(3,50)=1 ;x(3,51)=1 ; x(3,65)=1 ;x(3,71)=1 ;x(4,4)=1 ；x(4,53)=1 ;x(4,56)=1 ;x(4,57)=1 ;x(4,58)=1 ;x(4,60)=1 ; x(4,61)=1 ;x(5,5)=1 ;x(5,45)=1 ;x(5,49)=1

45、 ;x(5,52)=1 ;x(5,55)=1 ;x(6,6)=1 ;x(6,46)=1 ; x(6,47)=1 ;x(6,48)=1 ;x(6,54)=1 ;x(7,7)=1 ;x(7,28)=1 ;x(7,44)=1 ；x(8,8)=1 ;x(8,30)=1 ; x(8,31)=1 ;x(8,43)=1 ；x(9,9)=1 ;x(9,33)=1 ;x(9,34)=1 ;x(9,35)=1 ;x(9,41)=1 ;x(10,10)=1 ; x(11,11)=1 ;x(11,26)=1;x(11,27)=1;x(12,12)=1;x(12,25)=1;x(13,13)=1;x(13,21)=1;

46、 x(13,22)=1 ;x(13,23)=1;x(13,24)=1;x(14,14)=1;x(15,15)=1;x(15,29)=1;x(16,16)=1; x(16,32)=1 ;x(16,42)=1;x(17,17)=1;x(17,37)=1;x(17,38)=1;x(17,39)=1;x(18,18)=1; x(18,80)=1 ;x(18,82)=1;x(18,84)=1;x(18,85)=1;x(18,86)=1;x(19,19)=1;x(19,62)=1; x(19,63)=1 ;x(19,68)=1;x(19,70)=1;x(19,77)=1;x(19,78)=1;x(20,2

47、0)=1;x(20,76)=1; x(20,79)=1 ;x(20,81)=1 ;x(20,83)=1; %輸出每個平臺管轄的路口，任務(wù)量，最長時間fprintfCn第一問LINGO求解結(jié)果的輸出An1); fprintfC平臺，管理的路口，任務(wù)量，最長時間:n*); TT=zeros(m,1); W=zeros(m,1); for i=1:m fprintf(%2d:：i); s1=w(i);%初始任務(wù) TT(i)=0; forj=1:r if x(ij)=1 jp=Lu(j); s1=s1+f(jp); t=A(i,jp)/v; if tTT(i) TT(i)=t;end fprintf(

48、%2d,；jp); end W(i)=s1; end fprintfC w=%5.2f t=%5.2fn,s1 ,TT(i); end end 附件2問題1的LING012程序b2011_1 J g4。 該程序?qū)?6個待分配路口進行分派，所使用的數(shù)據(jù)文件dt1.txt和ft1.txt由Matlab 程序b2011 生成。LINGO程序的計算結(jié)果可直接拷貝到b2011 1.m中最后相應(yīng)位置，重 新按照規(guī)范格式輸出。在b2011_1.m中設(shè)置TEST=1控制輸出。 !問題1的LINGC程序； model: sets : Plat/1.20/:s,w; Kou/1.86/:T,f; Assig n(

49、Plat,Kou):dis,x; en dsets dat a: v=1000; n=20; dis=fil efd: lingo12datdt1.txt*); !20個平臺和待分配的86個路口的距離矩陣； f=fil efd: lingo12datft1.txt*);!待分配的 86 個路口的發(fā)案量； text()=wri tefor(Ass ign(ij)|x(ij)#GT#O:,;xC，i；,j,)=,x(i,j)；)； w=0,1.4,0,0,0,0,0.6,0,0,0,0,0,0,0,27,1.2,0,0,0,0.8;!20個平臺的初始發(fā)案量； enddata min=sqt(sum

50、(Pla t(i):(s(i)-sv)A2)/(n-1); !標準差最?。?for(Kou(j):sum (Pla t(i):x(i,j)=1); !每個路口恰好有一個平臺； for(Plat(i): sum(Kou(j):x(i ,j)=1);!每個平臺至少管理一個路口 ； for(Kou(j):T(j)=sum(Plat (i):x (i,j廣dis(i,j )/v); !第個路口的處理時間；for(Kou(j):T( j)=3); !沒 個路口到達時間少于3分鐘； for(Plat(i):x(i,i)=1);!每個平臺管理自己的路口 ； for(Plat (i):s (i)=w(i)+s

51、um(Kou(j):f(j)*x(i,j); !計算各平臺管轄的路口的任務(wù)量； sv=sum(Plat(i ):s( i)/n; !平均路口數(shù); for(Assign(i,j):bin(x(i,j); end 附件3問題2的LINGO12程序b2011_2.lg4o 該程序?qū)?3個交通要道的圍堵問題優(yōu)化求解。 model: sets : Plat/1.2O/; Kou/1.13/:T; Assign(Plat,Kou):dis,x,Time; endsets data : v=1000; dis= file (d:lingo12datdis1.txt*);!20 個平臺和 13 個路口的距離矩

52、陣;text ()= writefor (Assign(i,j)|x(i,j)#GT#O:tx(，,i；j/)=,x(i,j)； *)； en ddata min =aver; ! min=TT; TT=ma(xAssign(i,j):Time(i,j); !最大時間最小化; aver= sum(Kou(j) :T(j)/13; !平均時間； TT8.02; !當優(yōu)化第二目標時將第一目標變?yōu)榧s束； for (Ass ign(i,j):Time(iJ)=x(iJ)*dis(i,j)/v); for(kou (j) :T(j)=sum(PI at(i ):x(i,j)*dis(i,j)/v);!到

53、第 j 個路口 的時間; for(Plat(i): sum(KOu(j):x(i ,j)=1); !第 i 個平臺最多到一個路口； for(Kou(j):sum(Plat(i):x(i,j )=1); ! 第 j 個路口一定有一個平臺到達 ； for(Assi gn(i,j):bin(x(i,j)； end 附件4b2011問題3新增平臺的算法程序b2011_3.m %A （582,582）任意兩點之間的最短距離，先運行b2011_5_1.m獲得最短距離矩陣A （582,582） %采用單選法，每次從超過3分鐘的路口中選取1個降低最長時間最多的路口 %考察B區(qū) Qu=1; %1 （A 區(qū)）;2

54、 （B 區(qū)）,3 （C 區(qū)）,4 （D 區(qū)）,5 （ E 區(qū)）,6 （F 區(qū)丿 %輸出不同區(qū)號可計算不同區(qū)增加平臺情形 load DC.txt; %平臺號（80個），所屬區(qū) K=length （DC）; Plat=; %存儲某區(qū)平臺 n=0; %統(tǒng)計某區(qū)已有平臺數(shù) fori=1:K Belong=DC （i,2） ; %1 （A 區(qū)）;2 （B 區(qū)），3 （C 區(qū)）,4 （D 區(qū)）,5 （ E 區(qū)）,6 （F 區(qū)丿 if Belong=Qu Plat=Plat,DC （i,1） ; n=n+1 ;end end load DA.txt; %路口號（92個丿,x,y,區(qū)，發(fā)案率 Lu=; %存儲

55、某區(qū)路口數(shù) fz=; %存儲發(fā)案率 L=length （DA）; Belong=DA（i,4）; % 路口號（92 個），x,y,區(qū)，發(fā)案率 m=0; %統(tǒng)計某區(qū)已有路口數(shù) fori=1:L if Belong=Qu Lu=Lu,DA(i,1); fz=fz,DA(i,5); m=m+1 ;end end %計算各路口到各平臺的最短時間 %1.初始情形：x=zeros(1,m);%確定每個路口受管轄的平臺T=zeros(1 ,m);%每個路口到所管轄 平臺的時間v=1000;%速度 for i=1:m tmin=100; for j=1:n ip=Lu(i);% 路口號 jp=Plat(j);

56、 % 平臺號 t=A(ip,jp)/v; if t3 P=P+1； S(p,1)=i;S(p,2)=x(i);S(p,3)=T(i); end end fprintfC 區(qū)號2d 路口數(shù) %2d,平臺數(shù)2d 超過 3 分鐘的路口 %2dn,Qu,m,nJp); fprintff 超過 3 分鐘的路口，平臺，時間n)； for i=1:p fprintf(*%2d %2d %5.2fn,Lu(S(i,1),S(i,2),S(i,3); end maxT=max仃）;%最長時間 fprintfC增加平臺數(shù),最長時間n*); %方法，每次從超過3分鐘的路口中選取1個降低最長時間最多的路口 Temp_

57、Plat=zeros(1 ,m); Have_Plat=zeros(1 ,m); Yu=zeros(1 ,m); % 剩余平臺 for i=n+1:m Yu(i)=1; end %獲得當前剩余的平臺for i=1:n Temp_Plat(i)=Plat(i); Have_Plat(i)=Plat(i); % 已經(jīng)選定的平臺 end for Kp=1:22 %增加平臺數(shù)，22為最多增加數(shù)量 flag=0; for k=1:p sel=S(k,1); %選取1個超過3分鐘的平臺序號 Temp_Plat(n+Kp)=Lu(sel); for i=1:m tmin=100; for j=1:n+Kp

58、% 平臺數(shù) ip=Lu(i); jp=Temp_Plat(j); t=A(ip,jp)/v; if ttmin tmin=t; pj=j; end end %end for j x(i)=pj; % 第i個路口受管轄的平臺 T(i)=tmin; % 第i個路口到所管轄平臺的時間 end %end for i maxT1=max(T); if maxT1maxT maxT=maxT1; Add_Plat=sel; flag=1; end end %end for k Temp_Plat(n+Kp)=Lu(Add_Plat); Have_Plat(n+Kp)=Lu(Add_Plat); Yu(Ad

59、d_Plat)=O; flag=O; for i=1:m tmin=100; for j=1:n+Kp ip=Lu(i); jp=Have_Plat(j); t=A(ip,jp)/v; if ttmin tmin=t; pj=j; end end %end for j x(i)=pj; % 第i個路口受管轄的平臺 T(i)=tmin; % 第i個路口到所管轄平臺的時間 end %end for i fprintf(Kp=%2d Plat=%2d maxT=%5.4fn*,Kp丄u(Add_Plat),max(T); end %end if flag=1 end %end for Kp 當對A區(qū)

60、計算，結(jié)果為：增加平臺數(shù) ，最長時間 Kp 1 Plat=28 maxT=4.1902 Kp 2 Plat=61 maxT=3.6822 Kp =3 Plat=38 maxT=3.6013 iP 4 Plat=92 maxT=2.7083 附件5求取最短距離矩陣A(582,582)的程序b2011_5_1 .m clear; load DA.txt; % 路口號(92 個),x,y,區(qū),發(fā)案率 load DB.txt; %連接線 928 條 load DC.txt; % 平臺號，80 個 load DD.txt;%全市出入市區(qū)路口號(17個) x=DA(:,2);y=DA(:,3); b=DA