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

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

計算交通要道l從剩余平臺集合r中分配平臺的最短時間七二min{J,/料，作丫 ,j分配的平臺為To若t1<maxT七<maxT，則表示調整成功，最長時間減小。存儲到第k個要道的新時間孔=匕，新平臺氣=氣；到第l個要道的新時間氣=t2;新平臺在該循環(huán)體中若成功，則跳出該循環(huán)；若始終無法成功，則直到循環(huán)完成跳出。Step4:重復Stepl,Step2,Step3。直到最長時間maxT不再減小結束。輸出各路口對應平臺及時間。步驟三、減小平均時間算法該算法與步驟二中算法思想類似。只是將目標函數(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個路口對應的平臺氣,平臺到交通要道的時間計算將交通要道r以前分配的平臺Ur加入剩余平臺后的集合mY—P-U+Uj—1計算交通要道l從剩余平臺集合Y中分配平臺的最短時間t2—min{d〔/v},jeY "分配的平臺為To若t+1<T+T，且t<maxT,t<maxT則表示調整成功，最長時間沒有增12 12 1 2大，總時間減小，從而平均時間減小。存儲到第r個要道的新時間T—t1，新平臺U=氣；到第l個要道的新時間T=七；新平臺在該循環(huán)體中若成功，則跳出該循環(huán)；若始終無法成功，則直到循環(huán)完成跳出。Step4：重復Stepl，Step2，Step3。直到總時間或平均時間不再減小結束。輸出各路口對應平臺及時間，平均時間。4、結果計算示例一對問題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分鐘。詳細結果見表1。該結果需要調整最長時間。表1貪婪法求得各交通要道到達時間與分配的平臺序號交通要道號分配的平臺號到達時間（分鐘）112120214140316160421132.71522113.27623109.11724913.67828154.7592978.02103083.06113823.98124852.48136240.35采用步驟二中減少最長時間的算法，經過5次調整，最長時間達到最小。最長時間為8.02分鐘，平均時間為3.78分鐘。該結果最長時間達到了最小。詳細結果見表2。該方案的平均時間需要調整。表2調整最長時間后各交通要道到達時間與分配的平臺序號交通要道號分配的平臺號到達時間（分鐘）112107.59

214166.7431691.53421143.26522113.27623130.5724123.59828154.7592978.02103083.06113823.98124852.48136240.35采用步驟三中減少平均時間的算法，最長時間仍然為8.02分鐘，有3個交通要道指派的平臺經過了調整。平均時間由3.78分鐘減小到3.55分鐘。該結果最長時間達到了最小，平均時間也達到最小，結果達到了最優(yōu)。詳細結果見表3。表3調整平均時間后各交通要道到達時間與分配的平臺序號交通要道號分配的平臺號到達時間(分鐘)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分鐘。該結果通過調整并不能減少最長時間，可以驗證，該分配方案中，除202號交通要道外，其余各交通要道都分配的到達時間最短的平臺。而到達202號交通要道的時間最少的平臺為177，次之為175，177號平臺分配給177號交通要道最佳，從而分配175號平臺給202號交通要道最佳?？沈炞C該結果即為最優(yōu)結果。即最長時間最小為12.68分鐘，平均時間最小為5.07分鐘。詳細結果見表1。表4各交通要道到達時間與分配的平臺序號交通要道號分配的平臺號