交巡警平臺警力調(diào)度方案的優(yōu)化模型與算法設(shè)計

交巡警平臺警力調(diào)度方案的優(yōu)化模型與算法設(shè)計摘要：關(guān)鍵詞：服務(wù)平臺，交巡警，優(yōu)化模型，算法設(shè)計1、問題提出“有困難找警察”，是家喻戶曉的一句流行語。警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實(shí)施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺。每個交巡警服務(wù)平臺的職能和警力配備基本相同。由于警務(wù)資源是有限的，如何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警服務(wù)平臺、分配各平臺的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個實(shí)際課題。給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個交巡警服務(wù)平臺的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見附件2。對于重大突發(fā)事件，需要調(diào)度全區(qū)20個交巡警服務(wù)平臺的警力資源，對進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個平臺的警力最多封鎖一個路口，現(xiàn)在要給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。對該問題的解決，我們先建立最優(yōu)的調(diào)度模型，使各服務(wù)平臺到達(dá)交通要道的時間盡量的短。然后討論求解算法，最后給出具體的計算結(jié)果。2、模型建立對于重大突發(fā)事件，需要調(diào)度城市的交巡警服務(wù)平臺的警力資源，對進(jìn)出該區(qū)的多條交通要道實(shí)現(xiàn)快速全封鎖。采用的模型如下。設(shè)該市有n個平臺，用集合P表示，其序號為i=1,2,...,n。要封鎖的交通要道有m個，用集合J表示，其序號為j=1,2,...,m。%表示第i個平臺與第j個交通要道之間的最短路，由Floyd算法求得。p為警車行駛速度。這里取v=60公里/小時=1000米/分鐘泌n1池笛亦旦 J】第1個平臺指派到第1個路口設(shè)0-1決策變量x=<ij［。第1個平臺不指派到第］個路口每個交巡警服務(wù)平臺的警力最多到一個交通要道去圍堵，因此有：并x<1i=1,2,...,nijj=1對每個交通要道，需要且只需要分配一個平臺的警力，則有：Xx=1j=1,2,...,mi=1設(shè)Tj表示到第j個路口的時間。則有：T=￡d.x./vj=1,2,...,mi=1我們選取的第一目標(biāo)是到交通要道的最長時間最小化，這樣可使最長時間盡量小。則第一目標(biāo)函數(shù)為：minZ=maxT1<j<m當(dāng)最長時間最小情況下，我們同時對小于最時間的分配方式進(jìn)行優(yōu)化，使到達(dá)各交通要道的時間平均時間最小。則第二目標(biāo)函數(shù)為：XtjminZ=j——綜合上述，我們建立的的綜合模型為:minZ=maxT1<j<mXt. jminZ=jJ——i=1,2,...,nj=i=1,2,...,nj=1,2,...,m/v5rl：Xxy.=1s.Ii=1T=Xdxj ijiji=1x=0或1ij該結(jié)果的計算可以采用Lingo先求解第一目標(biāo)，使最長時間最小。當(dāng)求解出第一目標(biāo)后，將到各交通要道的時間不超過最長時間變?yōu)榧s束，然后求最二目標(biāo)，使用平均時間最小。但第一目標(biāo)是非線性，通常Lingo并不能得到最優(yōu)解，且計算很耗時。為此。我們另外設(shè)計算法，便于快速求解，并得到滿意結(jié)果。3、算法設(shè)計我們的求解算法采用三步完成。第一步，先利用貪婪法盡量使各平臺到達(dá)交通要道的時間盡量短。第二步，對到各交通要道的時間再進(jìn)行調(diào)整，進(jìn)一步優(yōu)化，直到最長時間不能再減少為止。第三步，在保證最長時間不增大的情況下，對到各交通要道的平均時間進(jìn)行調(diào)整，直到不再減小為止。步驟一：貪婪法Stepl：對第1個交通要道，在n個平臺中分配到達(dá)時間最短的一個。令最短時間為T，分配的平臺為，，則有：T=d/v=min{d/v}；令剩下1 1 1 z],1 冒i，1的平臺集合為P，則有：P=P-{i}oStep2:對第k個交通要道，在剩下的平臺集合P中，分配到達(dá)時間最短的k-1一個。令最短時間為T，分配的平臺為i，則有：T=d/v=min{d/v}；令剩k k k ik,k aik下的平臺集合為P，則有：P=P-{i},(k=2,3,...,m)。k k k-1kStep3：重復(fù)Step2,直到對所有交通要道都完成平臺分配。通過貪婪法，可使各平臺到達(dá)交通要道的時間盡量短，但不能保證最優(yōu)。下面通過第二步的較少最長時間，可使最長時間達(dá)到最小，從而實(shí)現(xiàn)最優(yōu)。步驟二：減少最長時間算法該算法采用交換平臺的思想，若交換后使最最長時間減小則成功一次，直到不能再減小為止。算法描述如下：Step1：根據(jù)步驟一確定出到第j個交通要道的時間T.(j=1,2,...,m)，第j個J交通要道指派的平臺U(j=1,2,...,m)。剩余未分配的平臺集合Y=P-mUj=1Step2：求出到各交通要道的最長時間maxT=“=min氣，其對應(yīng)交通要道序號為k，分配的平臺序號為UoStep3:循環(huán)執(zhí)行l(wèi)=1,2,....,m(l豐k)計算對交通要道k指派第i個路口對應(yīng)的平臺u,平臺到要道的時間t=d/vo計算將交通要道k以前分配的平臺uk加入剩余平臺后的集合mY=P—U+Uj=1

計算交通要道l從剩余平臺集合r中分配平臺的最短時間七二min{J,/料，作丫 ,j分配的平臺為To若t1<maxT七<maxT，則表示調(diào)整成功，最長時間減小。存儲到第k個要道的新時間孔=匕，新平臺氣=氣；到第l個要道的新時間氣=t2;新平臺在該循環(huán)體中若成功，則跳出該循環(huán)；若始終無法成功，則直到循環(huán)完成跳出。Step4:重復(fù)Stepl,Step2,Step3。直到最長時間maxT不再減小結(jié)束。輸出各路口對應(yīng)平臺及時間。步驟三、減小平均時間算法該算法與步驟二中算法思想類似。只是將目標(biāo)函數(shù)由最長時間變?yōu)槠骄鶗r間。算法描述如下：Stepl：根據(jù)步驟一確定出到第j個交通要道的時間T(j-1,2,...,m)，第j個J交通要道分配的平臺U(j-1,2,...,m)。乘IJ余未分配的平臺集合Y—P-mUjj—1YTStep2YTStep2:求出到各交通要道的平均時間MT—4」mStep3:循環(huán)執(zhí)彳丁l—1,2,....,m；r—1,2,....,m（l豐r）計算對交通要道r指派第l個路口對應(yīng)的平臺氣,平臺到交通要道的時間計算將交通要道r以前分配的平臺Ur加入剩余平臺后的集合mY—P-U+Uj—1計算交通要道l從剩余平臺集合Y中分配平臺的最短時間t2—min{d〔/v},jeY "分配的平臺為To若t+1<T+T，且t<maxT,t<maxT則表示調(diào)整成功，最長時間沒有增12 12 1 2大，總時間減小，從而平均時間減小。存儲到第r個要道的新時間T—t1，新平臺U=氣；到第l個要道的新時間T=七；新平臺在該循環(huán)體中若成功，則跳出該循環(huán)；若始終無法成功，則直到循環(huán)完成跳出。Step4：重復(fù)Stepl，Step2，Step3。直到總時間或平均時間不再減小結(jié)束。輸出各路口對應(yīng)平臺及時間，平均時間。4、結(jié)果計算示例一對問題2中的A區(qū)，要封鎖的交通要道有m=13個，其集合為J={12,14,16,21,22,23,24,28,29,30,38,48,62}。可供指派的平臺有n=20個，其集合為P={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,17,18,19,20}。采用步驟一中貪婪法求得最長時間為13.67分鐘，平均時間為3.95分鐘。詳細(xì)結(jié)果見表1。該結(jié)果需要調(diào)整最長時間。表1貪婪法求得各交通要道到達(dá)時間與分配的平臺序號交通要道號分配的平臺號到達(dá)時間（分鐘）112120214140316160421132.71522113.27623109.11724913.67828154.7592978.02103083.06113823.98124852.48136240.35采用步驟二中減少最長時間的算法，經(jīng)過5次調(diào)整，最長時間達(dá)到最小。最長時間為8.02分鐘，平均時間為3.78分鐘。該結(jié)果最長時間達(dá)到了最小。詳細(xì)結(jié)果見表2。該方案的平均時間需要調(diào)整。表2調(diào)整最長時間后各交通要道到達(dá)時間與分配的平臺序號交通要道號分配的平臺號到達(dá)時間（分鐘）112107.59

214166.7431691.53421143.26522113.27623130.5724123.59828154.7592978.02103083.06113823.98124852.48136240.35采用步驟三中減少平均時間的算法，最長時間仍然為8.02分鐘，有3個交通要道指派的平臺經(jīng)過了調(diào)整。平均時間由3.78分鐘減小到3.55分鐘。該結(jié)果最長時間達(dá)到了最小，平均時間也達(dá)到最小，結(jié)果達(dá)到了最優(yōu)。詳細(xì)結(jié)果見表3。表3調(diào)整平均時間后各交通要道到達(dá)時間與分配的平臺序號交通要道號分配的平臺號到達(dá)時間(分鐘)112120214166.7431691.53421143.26522107.71623130.5724113.81828154.7592978.02103083.06113823.98124852.48136240.35示例二：全市有交巡警平臺80個，全市出入口位置有17個。要封鎖的交通要道m(xù)=17個，其集合為J={151,153,177,202,203,264,317,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,384,385,386,475,476,477,478,479,480,481,482,483,484,485｝。采用步驟一中貪婪法求得最長時間為12.68分鐘，平均時間為5.07分鐘。該結(jié)果通過調(diào)整并不能減少最長時間，可以驗(yàn)證，該分配方案中，除202號交通要道外，其余各交通要道都分配的到達(dá)時間最短的平臺。而到達(dá)202號交通要道的時間最少的平臺為177，次之為175，177號平臺分配給177號交通要道最佳，從而分配175號平臺給202號交通要道最佳?？沈?yàn)證該結(jié)果即為最優(yōu)結(jié)果。即最長時間最小為12.68分鐘，平均時間最小為5.07分鐘。詳細(xì)結(jié)果見表1。表4各交通要道到達(dá)時間與分配的平臺序號交通要道號分配的平臺號