【正文】 10 , 3 m in 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 21 0 ( 3 ) , 3 m inmjmj i m j m jtf m jtt???? ? ?????? 其中，1mjt表示 A 區(qū) m 號(hào)平臺(tái)到 j 號(hào)節(jié)點(diǎn)的最短時(shí)間， 1,2,...,92j ? 如果損失時(shí)間大于 0，則以 10 倍的損失時(shí)間 10( 3)imjt ? 作為“懲罰”項(xiàng)對(duì)“到達(dá)時(shí)間超出 3 分鐘”的點(diǎn)進(jìn)行“懲罰”；如果損失時(shí)間為 0，則說(shuō)明到達(dá)時(shí)間不超出 3 分鐘，不予懲罰。 增廣目標(biāo)函數(shù)由兩個(gè)部分構(gòu)成，一部分是原目標(biāo)函數(shù)，另一部分是由損失時(shí)間約束函數(shù)構(gòu)造出的“懲罰”項(xiàng)，“懲罰”項(xiàng)的作用是 對(duì)“到達(dá)時(shí)間超出 3 分鐘”的點(diǎn)進(jìn)行“懲罰”。首先，我們將其作為緊約束建立以 所有平臺(tái)到各個(gè)管轄節(jié)點(diǎn)總時(shí)間最小為目標(biāo)函數(shù)的優(yōu)化模型，經(jīng)過(guò)檢驗(yàn)發(fā)現(xiàn)約束過(guò)強(qiáng)導(dǎo)致模型無(wú)解，從圖1中分析原因可知，交通網(wǎng)絡(luò)中部分路段（如 1416,1528,1529）過(guò)長(zhǎng)，無(wú)論如何分配，必存在個(gè)別節(jié)點(diǎn)到周圍的任意平臺(tái)的路段長(zhǎng)超過(guò) 3000m,如節(jié)點(diǎn) 28只與節(jié)點(diǎn) 29（未設(shè)置平臺(tái)）、 15（設(shè)置平臺(tái)）連通，節(jié)點(diǎn) 28只能 歸平臺(tái) 15 管轄，但路段 2815 長(zhǎng)度為 4750m(3000m),故無(wú)論如何分配，管轄節(jié)點(diǎn) 28的平臺(tái)到達(dá)該節(jié)點(diǎn)的時(shí)間都大于 3 分鐘，不滿足要求。 基于以上考慮，我們 只要給出 A 區(qū) 20 個(gè)平臺(tái)管轄路口節(jié)點(diǎn)的方案，即完成了平臺(tái)的管轄范圍分配。這樣即把事故的發(fā)生地統(tǒng)一于路口節(jié)點(diǎn)。我們定義路段 (, )Qi j （ ij? ）是由節(jié)點(diǎn) i 和節(jié)點(diǎn) j 連通而成的路段，路段中間不存在節(jié)點(diǎn) 。 （ 2） 損失時(shí)間：當(dāng)?shù)竭_(dá)時(shí)間不大于 3 分鐘時(shí)，損失時(shí)間為 0；當(dāng)?shù)竭_(dá)時(shí)間大于 3分鐘時(shí)，損失時(shí)間 =到達(dá)時(shí)間 3。 9 模型準(zhǔn)備 交巡警服務(wù)平臺(tái)在接到報(bào)案電話后，應(yīng)盡量在 3 分鐘 內(nèi)派出警力趕赴事故發(fā)生現(xiàn)場(chǎng)，在滿足該條件的情況下，如何合理分配 A 區(qū)每個(gè)平臺(tái)的管轄范圍是我們考慮的主要問(wèn)題。若在算法運(yùn)行過(guò)程中，將每一頂點(diǎn)獲得 P 標(biāo)號(hào)所由來(lái)的邊在圖上標(biāo)明，則算法結(jié)束時(shí)， 0? 至各項(xiàng)點(diǎn)的最短路也在圖上標(biāo)示出來(lái)了。在 v 進(jìn)入 iS 之前的標(biāo)號(hào) ()lv 叫 T 標(biāo)號(hào)， v 進(jìn)入 iS 時(shí)的標(biāo)號(hào) ()lv 叫 P 標(biāo)號(hào)。 Step 3 若 1iv??， 則停止；若 1iv??， 則用 1i? 代替 i ，轉(zhuǎn) Step 2。 Step 1 令 0( ) 0,l ? ? 對(duì) 0v ?? ，令 ( ) ,lv?? ??00,S ?? 0i? Step 2 對(duì)每個(gè) ( \ ),i i iv S S V S?? 用 ??m in ( ), ( ) ( )l v l v? ? ??代替 ()lv 。為避免重復(fù)并保留每一步的計(jì)算信息，采用了標(biāo)號(hào)算法。 8 圖 1 A 區(qū)的交通網(wǎng)絡(luò)與平臺(tái)設(shè)置示意圖（部分截圖） ? Dijkstra 算法計(jì)算兩點(diǎn)最短路徑長(zhǎng)度 Dijkstra 算法 [1] 用來(lái)求兩點(diǎn)之間的最短距離，并給出最短路徑的算法。 本題利用圓圈搜索法進(jìn)行模型求解，即隨著時(shí)刻的變化動(dòng)態(tài)地畫圓覆蓋嫌疑犯可能到達(dá)的區(qū)域范圍，令時(shí)刻按照較短的步長(zhǎng)增長(zhǎng)，不斷計(jì)算相應(yīng)的警方圍堵成功率，在搜索較多的點(diǎn)后，可找到最大的警方圍堵成功率，也可得到最佳圍堵嫌疑犯的方 案。將該區(qū)域內(nèi)的所有節(jié)點(diǎn)統(tǒng)計(jì)出來(lái)，個(gè)數(shù)記為 ()mt ，認(rèn)為這些節(jié)點(diǎn)為嫌疑犯 t 時(shí)刻可能到達(dá)的節(jié)點(diǎn)。 最優(yōu)圍堵模型 本題討論的問(wèn)題是在嫌疑犯逃逸 3 分鐘后，如何合理調(diào)度安排交巡警服務(wù)平臺(tái)的警力資源進(jìn)行圍堵，給出圍堵方案，在緝捕嫌疑犯的成功率達(dá)到最大。我們針對(duì)方案一（增減部分服務(wù)平臺(tái)數(shù)量）建立平臺(tái)設(shè)置優(yōu)化模型，主要基于快速出警原則及平臺(tái)工作均衡原則 使得全市系統(tǒng)的平臺(tái)設(shè)置合理性提高。 平臺(tái)設(shè)置的評(píng)價(jià)模型及其優(yōu)化方案 我們需要考慮的問(wèn)題是綜合考慮全市 6個(gè)區(qū)（ 主城六區(qū) , , , , ,A B C D E F）的服務(wù)平臺(tái)設(shè)置情況， 根據(jù)設(shè)置交巡警服務(wù)平臺(tái)的原則和任務(wù)，對(duì)設(shè)置交巡警平臺(tái)合理性進(jìn)行定量評(píng)價(jià) ，改進(jìn)現(xiàn)有分配方案。最終通過(guò)對(duì)每個(gè)小系統(tǒng)的優(yōu)化逼近整個(gè) A 區(qū)所有平臺(tái)工作量均衡的優(yōu)化。 該算法的實(shí)現(xiàn)思想是通過(guò)求解小系統(tǒng)的最優(yōu)近似逼近總體系統(tǒng)的最優(yōu)。 平臺(tái)工作的均衡優(yōu)化模型 在現(xiàn)有的交巡警服務(wù)平臺(tái)的設(shè)置中，平臺(tái)工作量（平均每天出警次數(shù)）不均衡及部分平臺(tái)出警時(shí)間過(guò)長(zhǎng)的問(wèn)題顯著。 基于以上分析建立交通要道封鎖警力調(diào)度模型，以 13 條交通要道出入口的全部封鎖完成時(shí)間最小為目標(biāo)函數(shù)， i 節(jié)點(diǎn)是否屬于需要封鎖的交通要道出入口 6 的 01 變量為決策變量，以需要封鎖的路口數(shù)、每個(gè)出入口只能由一個(gè)平臺(tái)的警力封鎖、每個(gè)平臺(tái)的警力只能封鎖一個(gè)出入口等要求為約束條件。 交通要道封鎖警力調(diào)度模型 重大突發(fā)事件發(fā)生時(shí)，需要調(diào)度全區(qū) 20 個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的 13 條交通要道出入口實(shí)現(xiàn)快速全封 鎖。 基于以上分析建立平臺(tái)管轄范圍分配模型，以全區(qū)各平臺(tái)到達(dá)所管轄節(jié)點(diǎn)最短時(shí)間之和最小為目標(biāo)函數(shù)，以 j 節(jié)點(diǎn)是否為 1m 平 臺(tái)管轄的 01變量為決策變量，考慮損失時(shí)間判罰、到達(dá)時(shí)間限制、平臺(tái)管轄限制等約束條件，利用 dijkstra 算法計(jì)算圖中任意兩個(gè)節(jié)點(diǎn)的最短距離，進(jìn)行模型求解。因此，我們只需討論各個(gè)路口節(jié)點(diǎn)歸哪個(gè)服務(wù)平臺(tái)管轄即 可將整個(gè)區(qū)進(jìn)行管轄范圍劃分。 對(duì)于路段及路口節(jié)點(diǎn)的歸屬問(wèn)題，我們給出合理假設(shè)，路段 (, )Qi j （ ij? ）的管轄權(quán)歸于管轄節(jié)點(diǎn) i 的服務(wù)平臺(tái)。 平臺(tái)管轄范圍分配模型 交巡警服務(wù)平臺(tái)負(fù)責(zé)其管轄區(qū)域內(nèi)的日常治安管理， 要隨時(shí)接受 “110” 報(bào)警 電話 ，快速反應(yīng)，及時(shí) 出 警 盡量于 3分鐘內(nèi)趕赴事故發(fā)生現(xiàn)場(chǎng)進(jìn)行處理，這是服務(wù)平臺(tái)的基本職能。 犯罪嫌疑人駕車逃逸速度與警車速度相同，為 60km/h。 計(jì)算出警時(shí)間時(shí)僅考慮到達(dá)時(shí)間（從平臺(tái)接到報(bào)案時(shí)間算起，巡警趕到事故現(xiàn)場(chǎng)終止），認(rèn)為平臺(tái)進(jìn)行日常巡查的警力和時(shí)間為常數(shù)，不予考慮。 主城六區(qū) A， B， C， D， E， F 分別用序號(hào) 1~6 表示。 警車的時(shí)速為常值 60km/h。為了快速搜捕嫌疑犯，給出調(diào)度全市交巡警服務(wù)平臺(tái)警力資源的最佳圍堵方案。對(duì)于明顯不合理之處給出解決方案。 （ 3） A 區(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)，要求確定需要增加平臺(tái)的具體個(gè)數(shù)和位置。 （ 2） 給出 A區(qū)突發(fā)情況下封鎖道路的交巡警服務(wù)平臺(tái)警力調(diào)度方案： 考慮應(yīng)對(duì) 重大突發(fā)事件的情況，需要調(diào)度全區(qū) 20 個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的 13 條交通要道實(shí)現(xiàn)快速全封鎖。 需要解決的問(wèn)題 就某市設(shè)置交巡警服務(wù)平臺(tái)的相關(guān)情況，建立數(shù)學(xué)模型進(jìn)行合理設(shè)置交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍、調(diào)度警務(wù)資源等實(shí)際問(wèn)題的分析。為了更有效地貫徹實(shí)施這些職能，既保證警務(wù)資源的合理利用，又能及時(shí)有效解決人民群眾的危機(jī)困難，許多 城市都在城區(qū)的 交通要道和重要部位設(shè)置交巡警服務(wù)平臺(tái)。 最后，我們對(duì)上述模型進(jìn)行了優(yōu)缺點(diǎn)分析，并提出了改進(jìn)方向。 針對(duì)問(wèn)題二的第二問(wèn)，我們建立了最佳圍堵模型，給出了圍堵成功率最大 時(shí)的警力調(diào)度方案。 針對(duì)問(wèn)題二的第一問(wèn)，我們基于城區(qū)系統(tǒng)間比較指標(biāo)建立了平臺(tái)設(shè)置的評(píng)價(jià)模型，并對(duì)現(xiàn)有平臺(tái)設(shè)置不合理之處給出了解決方案。 針對(duì)問(wèn)題一的第三問(wèn)， 我們建立平臺(tái)工作的均衡優(yōu)化模型，對(duì)平臺(tái)出警次數(shù)、出警時(shí)間等指標(biāo)進(jìn)行定量分析，給出了增設(shè)平臺(tái)個(gè)數(shù)及其位置的方案。 針對(duì)問(wèn)題一的第二問(wèn)，我們建立了交通要道封鎖警力調(diào)度模型，給出了封鎖13 個(gè)交通要道的警力調(diào)度方案?？紤]到“盡量到達(dá)時(shí)間不超過(guò) 3分鐘”的快速出警原則以及硬約束下無(wú)可行解的情況，我們利用基于損失時(shí)間的罰函數(shù)法對(duì)“到達(dá)時(shí)間超出 3 分鐘”的點(diǎn)進(jìn)行“懲罰”。 我們參賽選擇的題號(hào)是（從 A/B/C/D 中選擇一項(xiàng)填寫）： 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜? 參賽隊(duì)員 (打印并簽名 ) ： 1. 2. 3. 指導(dǎo)教師 或 指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名 )： 日期： 2020 年 9 月 12 日 賽 區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）： 2020 高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽 編 號(hào) 專