【正文】 2020 高教社杯全國(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è)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚?xiě)完整的全名）： 黑龍江八一農(nóng)墾大學(xué) 參賽隊(duì)員 (打印并簽名 ) ： 1. 謝浩 2. 李朝輝 3. 王英龍 指導(dǎo)教師 或 指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名 )： 日期： 2020 年 09 月 日 賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）： 2020 高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽 編 號(hào) 專 用 頁(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)）： 1 B 題 交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度 摘要 本文建立了交巡警服務(wù)平臺(tái)調(diào)度方案的優(yōu)化模型，合理分配全市區(qū)交巡警服務(wù)平臺(tái)的管轄范圍，使其能在規(guī)定時(shí)間內(nèi)到達(dá)事發(fā)地，并在快速到達(dá)事發(fā)地的前提下提供了一系列合理的調(diào)度方 案。 問(wèn)題一建立了以交巡警服務(wù)平臺(tái)的反應(yīng)時(shí)間最短、調(diào)度封鎖總路程最短兼顧工作強(qiáng)度的均衡性的優(yōu)化模型。應(yīng)用 floyd 算法得到各節(jié)點(diǎn)到平臺(tái)的最短距離矩陣，并建 立了以反應(yīng)時(shí)間最短為目標(biāo)的優(yōu)化模型，得到每個(gè)平臺(tái)所要管轄的節(jié)點(diǎn)。 同時(shí)對(duì)于 20 個(gè)平臺(tái)封鎖 13 個(gè)交通要道的問(wèn)題，我們通過(guò)兩個(gè)約束條件實(shí)現(xiàn)每個(gè)平臺(tái)最多服務(wù)一個(gè)節(jié)點(diǎn)和每個(gè)節(jié)點(diǎn)有且只有一個(gè)平臺(tái)管轄，建立以反應(yīng)時(shí)間最短為目標(biāo)的優(yōu)化模型，通過(guò) Lingo軟件得到對(duì) 13 條交通要道實(shí)現(xiàn)快速全封鎖的合理方案。 我們通過(guò)工作強(qiáng)度的方差定義 各平臺(tái)工作的均衡性，找出原有 20 個(gè)平臺(tái)各自 工作強(qiáng)度的不均衡性和各自出警時(shí)間的差異找出需要增加的平臺(tái)的可能位置 為（ 2 2 36 92） ，通過(guò)比較找出最合適的位置增加平臺(tái) ，它們分別為 （ 28， 40， 48， 91）， 同時(shí)我們給出最優(yōu)的平臺(tái)增加個(gè)數(shù) 為 4。 問(wèn)題二 定義了兩個(gè)評(píng)價(jià)原則，原則一：巡警能在 3min 之內(nèi)到達(dá)案發(fā)路口；原則二：巡警服務(wù)臺(tái)的工作量均衡度盡量小。根據(jù)以上兩個(gè)原則對(duì)該市現(xiàn)有巡警服務(wù)臺(tái)的設(shè)置方案的合理性進(jìn)行評(píng)價(jià)，評(píng)價(jià)結(jié)果顯示： ① 全市有 138 個(gè)路口，在案發(fā)時(shí)巡警不能在 3min 之內(nèi)到達(dá)； ② 此時(shí)的不均衡度已達(dá) ?；谏鲜鰞牲c(diǎn)，現(xiàn)有的 巡警服務(wù)臺(tái)設(shè)置不合理。 針對(duì)現(xiàn)有巡警服務(wù)臺(tái)設(shè)置不合理的情況下，本文提出 一 種方案對(duì)設(shè)置進(jìn)行優(yōu)化調(diào)整。方案 是 保持現(xiàn)有巡警服務(wù)臺(tái)的個(gè)數(shù)和位置，再在 其他路口增設(shè)巡警服務(wù)臺(tái) 。其結(jié)果是 標(biāo)號(hào)為 170 的巡警服務(wù)臺(tái)工作量最大，為 ， 541 巡警服務(wù)臺(tái)工作量最小，為 ，此方案不均衡度降為 。 可以看出此方案的 巡警服務(wù)臺(tái)設(shè)置 是比較合理的。 問(wèn)題 二的第二問(wèn) 實(shí)質(zhì)是單目標(biāo)規(guī)劃問(wèn)題，我們建立 01 規(guī)劃模型，以巡警圍堵時(shí)間最短為目標(biāo)，以成功圍堵為條件。對(duì)于巡警的成功圍堵，可以轉(zhuǎn)化為二 部圖的完全匹配，利用匈牙利算法，求得最佳 圍堵方案 。 關(guān)鍵詞： floyd 算法 ； Lingo 軟件 ； 二部圖 ； 匈牙利算法 2 一、問(wèn)題重述 “有困難找警察”，是家喻戶曉的一句流行語(yǔ)。警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實(shí)施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺(tái)。每個(gè)交巡警服務(wù)平臺(tái)的職能和警力配備基本相同。由于警務(wù)資源是有限的，如何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個(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ù)，為各交巡警服務(wù)平臺(tái)分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在 3 分鐘內(nèi)有交巡警（警車的時(shí)速為 60km/h） 3千米到達(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）的具體情況，按照設(shè)置交巡警服務(wù)平臺(tái)的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺(tái)設(shè)置方案（參見(jiàn)附件）的合理性。如果有明顯不合理，請(qǐng)給出解決方案。 如果該市地點(diǎn) P（第 32 個(gè)節(jié)點(diǎn)）處發(fā)生了重大刑事案件，在案發(fā) 3 分鐘后接到報(bào)警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請(qǐng)給出調(diào)度全市交巡警服務(wù)平臺(tái)警力資源的最佳圍堵方案。 二、問(wèn)題分析 為了更能夠有效的貫徹實(shí)施警察肩負(fù)的刑事執(zhí) 法、治安管理、交通管理、服務(wù)群眾四大職能，在市區(qū)的一些交通要道和重要部位合理的設(shè)置交巡警服務(wù)平臺(tái)，分配各平臺(tái)的管轄范圍、調(diào)度警務(wù)資源十分長(zhǎng)必要的。 問(wèn)題一的分析 對(duì)于問(wèn)題一，我們分成三個(gè)小問(wèn)題進(jìn)行依次解決： （ 1） 管轄區(qū)域的確定； （ 2） 警力的合理調(diào)度方案； （ 3） 確定增加平臺(tái)的個(gè)數(shù)與位置； 首先對(duì)于交巡警服務(wù)平臺(tái)管轄范圍的分配，本問(wèn)題可以屬于優(yōu)化方面的問(wèn)題，為了滿足盡快到達(dá)案發(fā)現(xiàn)場(chǎng)的要求，可利用 Floyd 算法求得最短時(shí)間路徑，同時(shí)，根據(jù)就近原則建立了一個(gè)整數(shù)規(guī)劃模型，然后利用 LINGO 編程求解 出管轄范圍，將交叉路口分配給距離最近的交巡警平臺(tái)管轄即可最大限度滿足分配要求； 然后對(duì)于警力的合理調(diào)度方案問(wèn)題，即從 20 個(gè)交巡警服務(wù)平臺(tái)選擇 13 個(gè)實(shí)行道路全封鎖，要實(shí)現(xiàn)快速封鎖，須使所取封鎖方案中最后一個(gè)到達(dá)交通要道口的交巡警服務(wù) 3 平臺(tái)所用時(shí)間是所有可行方案中最少的一個(gè)，即將最大路徑最小化。進(jìn)一步考慮到方案最優(yōu)化，我們可以將該問(wèn)題看成是一個(gè)多目標(biāo)規(guī)劃的問(wèn)題，因此我們建立了一個(gè)雙目標(biāo)整數(shù)規(guī)劃模型，再按照附件 2 中 20 個(gè)巡警服務(wù)臺(tái)和 13條交通要道的順序進(jìn)行編號(hào)，引入決策變量，根據(jù)已經(jīng)建立的模型中的約束條件和目標(biāo)函數(shù) ，利用 Lingo 求得全局最優(yōu)解。 最后對(duì)于增加平臺(tái)的個(gè)數(shù)的問(wèn)題，我們首先要考慮的因素是出警速度和工作量均衡度，對(duì)這兩個(gè)因素進(jìn)行優(yōu)化，在優(yōu)化前我們利用第一小題 中的方法可得到：距離 C 類各個(gè)路口小于 3km 的路口集合 ；再采用寬容分層序列法，來(lái)分析這兩個(gè)指標(biāo)?？s短出警時(shí)間是警務(wù)部門增設(shè)服務(wù)平臺(tái)的首要目標(biāo)，當(dāng)出警時(shí)間被縮短到一定范圍內(nèi)時(shí)，我們可以近似地將落在這個(gè)范圍內(nèi)的出警時(shí)間看作是無(wú)差異的。若假設(shè)范圍上限為 T，則 [0， T]內(nèi)的出警速度都是可以接受的。采用第一小問(wèn)中的要求，取 T=量后，枚舉所有可能 的位置，求出 tmax 的下界。再采用模擬退火算法求近似最優(yōu)解． 問(wèn)題二的分析 對(duì)于問(wèn)題二我們也將其分成三個(gè)小的問(wèn)題，分別分析從而分別建立模型來(lái)求解。 2 （ 1） 分析全市現(xiàn)有平臺(tái)的合理性； （ 2） 如何里給出理由，不合理給出的解決方案； （ 3） P 點(diǎn)突發(fā)事件的最佳圍堵方案。 首先我們來(lái)分析現(xiàn)有憑他是否合理，為此定義了兩個(gè)評(píng)價(jià)原則： 原則一：巡警能在 3min 之內(nèi)到達(dá)案發(fā)路口 ； 原則二：巡警服務(wù)臺(tái)的工作量均衡度盡量小。 依據(jù)問(wèn)題分析中的兩個(gè)評(píng)價(jià)原則，分別對(duì)現(xiàn)有巡警服務(wù)臺(tái)的設(shè)置方案進(jìn)行評(píng)價(jià)。 然后我們假設(shè)所給的巡 警服務(wù)平臺(tái)設(shè)置的不合理，現(xiàn)在進(jìn)行優(yōu)化： 在不改變現(xiàn)有巡警服務(wù)臺(tái)的位置的情況下，適當(dāng)增加巡警服務(wù)臺(tái)的數(shù)目，從而使城區(qū) A 中無(wú) C類路口且每個(gè)巡警服務(wù)臺(tái)的工作量盡量均衡 ， 將其組成需求點(diǎn)的集合，同樣利用求解問(wèn)題 中的方法與步驟，得到新增加的最小巡警服務(wù)臺(tái)數(shù)目與位置 和 此種方案下巡警服務(wù)臺(tái)的工作量和工作量的不均衡度 ，最后得到相對(duì)合理的平臺(tái)分布。 最后對(duì)于 當(dāng)該市某路口發(fā)生重大刑事案件時(shí)，犯罪嫌疑人已逃跑，由于在案發(fā) 3min后巡警才能接到報(bào)警，為了快速搜捕嫌疑犯，將調(diào)度全市交巡警服務(wù)平臺(tái)警力圍堵嫌疑犯。因?yàn)榫囅鄬?duì)于嫌 疑犯車延遲三分鐘行駛，而且巡警不知道嫌疑犯逃跑方向，所以此問(wèn)題可轉(zhuǎn)化為以下模型：對(duì)于任意時(shí)間 t，嫌疑犯駕車逃跑的最大范圍為：在 t+3 時(shí)間內(nèi)嫌疑犯所有可能行駛路線所包含路口節(jié)點(diǎn)的并集，記為 Q，將的邊界點(diǎn)集記為 3??tQ所謂最快圍堵方案，即尋找一個(gè)最短時(shí)間 t，適當(dāng)?shù)恼{(diào)配巡警警力，使其在時(shí)間內(nèi)能夠到達(dá)邊界點(diǎn)，這樣嫌疑犯就被控制在區(qū)域 Q中，此時(shí)嫌疑犯將無(wú)法逃脫 。 三、模型假設(shè) (1) 假設(shè)題中所給數(shù)據(jù)均真實(shí)可靠。 (2) 相鄰兩個(gè)交叉路口之間的道路近似認(rèn)為是直線。 (3) 假設(shè)發(fā)案 率只在節(jié)點(diǎn)上發(fā)生，不用考慮在本區(qū)之外的情況。 (4) 在出入城區(qū)路口所設(shè)的交巡警服務(wù)平臺(tái)堵住該路口的時(shí)間為零。 (5) 所有道路都是雙向且暢通無(wú)阻的，警車由最短路徑到達(dá)事發(fā)地點(diǎn)。 (6) 警車以 60km/h 的速度勻速行駛，不考慮車輛的調(diào)頭、啟動(dòng)、停止時(shí)的加減速過(guò)程。 4 (7) 一條道路只能歸一個(gè)交巡警平臺(tái)所管轄，而不存在兩個(gè)或多個(gè)交巡警平臺(tái)共同管理一條道路的情況。 (8) 假定各個(gè)劃分區(qū)域在較短時(shí)間內(nèi)最多發(fā)生一個(gè)案件，且警察接到報(bào)警后立刻出警，忽略其反應(yīng)時(shí)間。 四、定義與符號(hào)說(shuō)明 Ao 存放各個(gè)節(jié)點(diǎn)之間的距離的鄰接矩陣； μ A 區(qū)所有平臺(tái)案發(fā)率的平均值； α