cumcm2011B-吳孟達-110警車的配置及巡邏方案-數(shù)模講座26

研究生數(shù)模競賽09年D題

“110警車的配置及巡邏方案”

解題思路解析及論文點評

國防科技大學(xué)吳孟達青島中科院研究生院

2010年7月22日1目錄題目命題思路解題思路論文點評綜合評述2目錄題目110警車配置及巡邏方案

110警車在街道上巡弋，既能夠?qū)`法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的安全感，同時也加快了接處警（接受報警并趕往現(xiàn)場處理事件）時間，提高了反應(yīng)時效，為社會和諧提供了有力的保障?？紤]某城市內(nèi)一區(qū)域，為簡化問題，假定所有事發(fā)現(xiàn)場均在下圖的道路上。該區(qū)域內(nèi)三個重點部位的坐標分別為：（5112，4806），（9126，4266），（7434，1332）（見下圖紅點部位，藍色部分為水域，道路數(shù)據(jù)見附件,相鄰兩個交叉路口之間的道路近似認為是直線）。

3題目4題目某城市擬增加一批配備有GPS衛(wèi)星定位系統(tǒng)及先進通訊設(shè)備的110警車。設(shè)110警車的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h。警車配置及巡邏方案要盡量滿足以下要求：

D1.

警車在接警后三分鐘內(nèi)趕到現(xiàn)場的比例不低于90％；而趕到重點部位的時間必須在兩分鐘之內(nèi)。

D2.

使巡邏效果更顯著；

D3.

警車巡邏規(guī)律應(yīng)有一定的隱蔽性。5題目

請回答以下問題：一.若要求滿足D1,該區(qū)最少需要配置多少輛警車巡邏？二.請給出評價巡邏效果顯著程度的有關(guān)指標。三．請給出滿足D1且盡量滿足D2條件的警車巡邏方案及其評價指標值。四.在第三問的基礎(chǔ)上，再考慮D3條件，給出你們的警車巡邏方案及其評價指標值。五．如果該區(qū)域僅配置10輛警車，應(yīng)如何制定巡邏方案，使D1、D2盡量得到滿足？六.若警車接警后的平均行駛速度提高到50km/h，回答問題三。七.你們認為還有哪些因素、哪些情況需要考慮？給出你們相應(yīng)的解決方案。6題目命題思路“110警車配置及巡邏方案”，是一個根據(jù)現(xiàn)實問題簡化改造而成的數(shù)學(xué)建模問題，其背景知識較單純，容易理解，初看起來比較容易上手，但是隨著對問題分析的逐步深入，會發(fā)現(xiàn)這實際上是一個很難找到最優(yōu)解的問題。如果只考慮警車的靜態(tài)分布，要使之分布盡量均勻，是一件很容易做到的事情，但要考慮十幾輛或者二十幾輛警車在巡邏中的動態(tài)分布的“均勻性”，由于道路的限制，車輛不能隨意行駛，則問題的難點就顯現(xiàn)出來了。本題目希望同學(xué)們解決的問題就是警車巡邏時如何保持“動態(tài)均勻性”的問題，也就是說，要給出一個優(yōu)化算法，使得由此算法計算得出的所有警車的巡邏路線分布越“均勻”越好。7命題思路在命題時，我們針對前些年競賽中發(fā)現(xiàn)的有部分參賽隊“湊結(jié)果”的現(xiàn)象，設(shè)置了結(jié)果驗證環(huán)節(jié)，并在題目中明確告知結(jié)果需要驗證，對結(jié)果輸出格式也有嚴格要求。我們認為，作為將要從事科學(xué)研究的科技工作者，實事求是的工作態(tài)度，嚴謹不茍的工作作風(fēng)，是十分重要的素質(zhì)，也應(yīng)該納入本項競賽活動所要達到的目標之一。8命題思路解題思路題意理解（1）關(guān)于“警車在接警后三分鐘內(nèi)趕到現(xiàn)場的比例不低于90％”，可以有兩種不同理解。一種我們稱之為“空間覆蓋”，即一天內(nèi)警車巡邏覆蓋（三分鐘內(nèi)能到達）過的道路占所有道路的比例要不低于90％。另一種稱之為“時間覆蓋”，即一天內(nèi)任意時刻警車覆蓋的道路占所有道路的比例要不低于90％。

（2）關(guān)于“警車巡邏規(guī)律應(yīng)有一定的隱蔽性”。9解題思路－題意理解解題方法第一問

著重看如何理解“警車在接警后三分鐘內(nèi)趕到現(xiàn)場的比例不低于90％”，以及如何實現(xiàn)這一目標。通常可以考慮區(qū)域劃分的方法解決此問，例如采用聚類方法、集合覆蓋算法、啟發(fā)式搜索算法、遺傳算法等算法作區(qū)域劃分。靜態(tài)處理也可以接受。嚴格說來，最少車輛數(shù)不少于17輛。10解題思路－第一問第二問

題目第二問要求給出“評價巡邏效果顯著程度的有關(guān)指標”，我們認為，至少有以下四個指標（或類似指標）需要加以考慮：（a）平均覆蓋率；（b）瞬時覆蓋率達標比例；（c）到達率（或見警率）；（d）覆蓋次數(shù)方差（或警力分配均勻度）。對此四個指標的含義解釋如下。11解題思路－第二問（a）平均覆蓋率：警車巡邏覆蓋（三分鐘內(nèi)能到達）過的道路占所有道路的比例。按照題目要求，這一比例應(yīng)不低于90％，這是一個硬指標，必須要達到。（b）瞬時覆蓋率達標比例：覆蓋率達到90％的時刻占所有時間的比例。這是針對“時間覆蓋”情形提出的指標，大部分參賽隊未考慮，評閱時是作為一個軟指標來評價模型優(yōu)劣的。12解題思路－第二問

（c）到達率（或見警率）：警車巡邏到達過的道路占所有道路的比例。由于警車巡邏的目的不止是為了能夠及時處警，增加對企圖作案者的震懾作用也是目的之一，所以僅有覆蓋率還不足以度量巡邏效果的顯著性，見警率也是度量巡邏效果的顯著性的一個必不可少的指標，這一指標越大越好。（d）覆蓋次數(shù)方差：道路上各點被覆蓋次數(shù)的方差，用以度量警力分配的均勻度。此指標與平均覆蓋率聯(lián)合使用，方能較全面地反映覆蓋率的真實效果。評閱時主要考察關(guān)于度量巡邏效果顯著性的指標的考慮是否全面，對每一指標的理解與解釋是否準確到位。以上考察反映建模者分析問題的能力，以及其對問題是否有全面且深刻的理解。13解題思路－第二問第三問

本問的主要技術(shù)難點在于要求二十幾輛車在“動態(tài)巡邏”條件下保持“分布均勻性”，求最優(yōu)解的計算復(fù)雜度太高，因此，尋找可接受的計算復(fù)雜度與結(jié)果的優(yōu)化之間的平衡點，是本問的關(guān)鍵所在。本問的求解充分體現(xiàn)了建模方法的多樣性，為參賽者充分發(fā)揮創(chuàng)造性提供了很好的機會。主要解題方法概述如下：14解題思路－第三問

1）單車分區(qū)法：按照覆蓋率要求作區(qū)域劃分，每個區(qū)域固定一輛警車巡邏。此方法主要特點是計算簡單，但是其代價是需要車輛數(shù)較多。例如靜態(tài)時17輛車即能滿足覆蓋率要求，如果分成17個區(qū)域，每個區(qū)域1輛車，則在動態(tài)時要保持滿足覆蓋率要求就非常困難了，所以不得不增加劃分區(qū)域。此種方法通常要求配置3５輛車以上，才能達到覆蓋率要求。15解題思路－第三問

2）多車分區(qū)法：為了改進以上單車分區(qū)法的缺點，可以考慮每個區(qū)域設(shè)置若干輛警車共同巡邏的方法，這樣可以減少一些車輛，但代價是計算難度的增加，且每一區(qū)域配置的車輛越多，計算難度就越大。16解題思路－第三問

3）動靜結(jié)合法：有的參賽隊單純從滿足車輛數(shù)最少的目標出發(fā)，讓有的車靜止不動，這樣即能滿足覆蓋率要求，車輛數(shù)又少。但這樣做，見警率指標就很差了，于是就再安排一些車跑見警率。從覆蓋率與見警率效果來看，此方法很不錯，車輛數(shù)還不多（大約２２或２３輛），計算也相對簡單，似乎是一種好方法。但是這樣做，違背了問題本身的實際意義，所以未能得到評委們的認可。數(shù)學(xué)建模不是解數(shù)學(xué)題，一定要考慮問題的實際意義是什么，不能為了追求指標的好看而罔顧其實際背景。17解題思路-第三問

4）軟分區(qū)法：此方法由方法１）延伸而來。與方法１）一樣，本方法先劃分區(qū)域，每個區(qū)域配置一輛警車，與方法１）不同的是，每個區(qū)域配置的警車并不是一定不能跨區(qū)域巡邏，而是設(shè)置了一個跨區(qū)域因子，此因子隨著周圍區(qū)域警車的位置以及其本身的位置關(guān)系而變化。再設(shè)置一個區(qū)域中心引力因子，以保證該車不會離開自己的區(qū)域中心太遠。此方法的思想有創(chuàng)意，但在實現(xiàn)時由于各個因子之間較難平衡，所以效果改進不大。18解題思路－第三問

5）蟻群算法：此方法屬于啟發(fā)式搜索算法，在此次競賽中成為主流解法，其思想是：在道路上設(shè)置一個“氣味因子”，某段道路上跑過的車越多，則該段道路的“氣味”變大，并且“氣味”隨時間變長而衰減。巡邏車每到一個路口，根據(jù)路口其它各段道路的“氣味”大小，朝“氣味”最小的方向前進。想法蠻有創(chuàng)意，在具體實現(xiàn)時還要處理好多輛車的協(xié)同問題等細節(jié)。如果細節(jié)處理得好，此方法所需要的車輛數(shù)大約為２５輛左右，不失為一種比較理想的方案。19解題思路－第三問

6）引力場方法：此方法與上一方法有類似之處，即每段道路依據(jù)走過的警車多少有一個“引力因子”，走過的車輛越多，則“引力”越??；同時，任兩輛車之間依據(jù)距離遠近有一個“斥力因子”，距離越近，則斥力越大。對每一輛警車而言，道路對它的“引力”與其它車輛對它的的“斥力”共同構(gòu)成了一個“引力場”，它將向著“合成引力”最大的方向前進。這也是一種挺有創(chuàng)意的想法，難處在于細節(jié)的處理（例如引力與斥力的合成）及計算上的復(fù)雜性，對計算能力有較高的要求。20解題思路－第三問

7）切片疊加法：由于靜態(tài)時車輛數(shù)較少，并且車輛可以達到“均勻分布”狀態(tài)，因此一種想法是對時間進行“切片”處理：每一時刻為一個切片，在一個切片上給出所有車輛的一個“均勻分布”，構(gòu)造出充分多（例如：１０００張）的不同切片，并且通過篩選使這些切片上的車輛分布點盡量分散，這是出于提高切片“疊加”后的車輛到達率指標的考慮。然后對這些切片按照“擇近”原則進行排序，再對排序后的切片依次疊加，便得到一個班次（４小時或８小時）的巡邏方案。21解題思路－第三問這個方案的特點是車輛在巡邏時的速度可以不同，但每輛車的平均速度仍為２０公里/小時，其難點在于對切片的“擇近”排序的計算量很大。這是一種很有創(chuàng)意的方法，效果也不錯。大約需要２４輛車，可以使覆蓋率及到達率指標都比較令人滿意?？上Т朔N解法在本次競賽論文中未發(fā)現(xiàn)使用。22解題思路－第三問

有的參賽隊試圖用整數(shù)規(guī)劃方法解決此問，以車數(shù)最少為優(yōu)化目標，但一則覆蓋率及到達率約束條件不易表達，模型不好建立；二則無法求動態(tài)解，所以在此問題中這不是一種現(xiàn)實的方法。其它幾問的解法較簡單，從略。23解題思路－第三問論文點評24解題思路綜合評述解題方法的多樣性在參賽論文中體現(xiàn)得較充分，這是競賽命題所追求的目標之一，這樣，參賽者的創(chuàng)造性才可以有較大的發(fā)揮空間。25綜合評述有過半的參賽隊評價指標（第二問）部分完成的不理想，主要體現(xiàn)在指標考慮不全面及討論不深入，反映出分析問題的能力有不足，對理解題意的重要性的認識也不夠充分。事實上，對問題有深入透徹的理解，往往是好的創(chuàng)意的出發(fā)點，應(yīng)有足夠的重視。26綜合評述計算能力不足成為制約許多參賽隊成績的主要因素。從參賽論文可以看出，有些參賽隊不是沒有想法，而是無法實現(xiàn)這些想法。據(jù)我們所知，有的研究生過于依賴現(xiàn)成軟件，導(dǎo)致編程實踐缺乏，編程能力下降，這是否當前研究生的一種較普遍的狀態(tài)，值得所有關(guān)心研究生教育改革的人們的關(guān)注。27綜合評述驗證結(jié)果之差，超出了我們事先的預(yù)料。針對前些年競賽中發(fā)現(xiàn)的有部分參賽隊“湊結(jié)果”的現(xiàn)象，我們刻意設(shè)置了結(jié)果驗證環(huán)節(jié)，并在題目中明確告知結(jié)果需要驗證，對結(jié)果輸出格式也有嚴格要求。有近半數(shù)的參賽隊沒有按要求提供巡邏方案數(shù)據(jù)或甚至沒有數(shù)據(jù)，在按題目要求提供了結(jié)果數(shù)據(jù)的參賽隊中，又有相當部分的驗證結(jié)果與其論文中給出的結(jié)果有較大差異。這些現(xiàn)象至少說明了在嚴謹求實的作風(fēng)方面，是存在問題的。28綜合評述如何求得本問題的最優(yōu)解，是一個可以繼續(xù)研究的