2011全國數(shù)學建模大賽B題答案

1、交巡警服務平臺的設置與調度的規(guī)劃模型摘要 本文通過對問題具體分析，可以把問題一分為三個小問題，針對問題一的第一個小問題可建立最短路模型，通過尋求各個路口到交巡警平臺的滿足時間限制的最短距離，解決交巡警服務平臺分配管轄范圍的問題；對于問題一的第二個小問題由已知的交巡警服務平臺快速封鎖13個主干路口，我們嘗試建立了最小費用流和0-1整數(shù)規(guī)劃兩種模型，以尋求交巡警到達所封鎖路口最遠距離中的最短距離來解決調度問題；問題一的第三個小問題，增加新的交巡警服務平臺以工作量盡量均勻，出警時間盡量短為約束條件，建立0-1整數(shù)規(guī)劃模型，求解需要增加的平臺數(shù)和位置。 問題二可分為兩個小問題，對于問題二的第一個小問題

2、，建立0-1整數(shù)規(guī)劃模型，在此以B區(qū)為例，以不滿足時間限制的路口與B區(qū)總路口個數(shù)之比來衡量B區(qū)交巡警服務平臺設置的合理性；對于問題二的第二個小問題，可建立圖論模型和二分法模型，來聯(lián)合解決問題。文中主要運用MATLAB和AMPL等程序進行求解，得到了比較合理的結果。結果如下：結果1：到達最近的交巡警服務平臺的時間超過3分鐘的6個路口如下表：路口標號282938396192歸屬標號1515162720距離47.58150.00534.05936.82241.90236.013結果2：利用指派算法找出的交巡警服務平臺到交通要道的調度平臺12149161013111587254要道1214162122

3、2324282930384862其中路程最遠的交巡警服務平臺到交通要道的距離為104.93百米利用0-1整數(shù)規(guī)劃找出的交巡警服務平臺到交通要道的調度平臺171615141312111097654要道38142823241221224829163062其中路程最遠的交巡警服務平臺到交通要道的距離為80.15百米故利用0-1整數(shù)規(guī)劃算法找出的交巡警服務平臺到交通要道的調度優(yōu)于指派算法找出的調度方案。結果3：假如不考慮工作強度的前提下，利用0-1整數(shù)規(guī)劃算法求出需新增加4個平臺，標號分別為29,39,61,92；加上工作量均衡的考慮，利用0-1整數(shù)規(guī)劃算法求出需新增加5個平臺，標號分別為23,29,

4、40,61,89。結果4：對于全市平臺設置方案的合理性，若出警時間過長的路口超過總路口的5%則設置方案不合理，以 B區(qū)為例，運用最短路算法找出距離交警平臺超過3分鐘路程的路口個數(shù)為6，B區(qū)的路口總數(shù)為72，故B區(qū)的設置方案不合理。結果5：調度全市交巡警服務平臺警力的最佳圍堵方案為:1->1,2->41,3->71,4->62,6->234,7->239,10->27,11->11,14->14,15->28,17->17,18->72,19->19,20->78,169->240,170->227,

5、171->216,172->172,173->29,182->241,475->561,476->549,482->488。花費時間為7.92分鐘。本文計算分析所采用的基本理論和計算方法參考了圖論的相關理論知識，經過詳細推導得到了相關數(shù)學模型，涉及的全部數(shù)據計算均采用MATLAB和AMPL等編程實現(xiàn)，計算結果準確、可信，所提出的模型和結論具有一定的適用性，對于合理分配交巡警服務平臺位置和調度交巡警來封鎖道路有一定的意義。關鍵詞 最短路 平均工作強度 最小費用流 0-1整數(shù)規(guī)劃 二分法1 問題的提出1.1 問題重述“有困難找警察”，是家喻戶曉的一句流行語

6、。警察肩負著刑事執(zhí)法、治安管理、交通管理、服務群眾四大職能。為了更有效地貫徹實施這些職能，需要在市區(qū)的一些交通要道和重要部位設置交巡警服務平臺。每個交巡警服務平臺的職能和警力配備基本相同。由于警務資源是有限的，如何根據城市的實際情況與需求合理地設置交巡警服務平臺、分配各平臺的管轄范圍、調度警務資源是警務部門面臨的一個實際課題。試就某市設置交巡警服務平臺的相關情況，建立數(shù)學模型分析研究下面的問題：一、附件1中的附圖1給出了該市中心城區(qū)A的交通網絡和現(xiàn)有的20個交巡警服務平臺的設置情況示意圖，相關的數(shù)據信息見附件2。請為各交巡警服務平臺分配管轄范圍，使其在所管轄的范圍內出現(xiàn)突發(fā)事件時，盡量能在3分

7、鐘內有交巡警（警車的時速為60km/h）到達事發(fā)地。對于重大突發(fā)事件，需要調度全區(qū)20個交巡警服務平臺的警力資源，對進出該區(qū)的13條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警服務平臺警力合理的調度方案。根據現(xiàn)有交巡警服務平臺的工作量不均衡和有些地方出警時間過長的實際情況，擬在該區(qū)內再增加2至5個平臺，請確定需要增加平臺的具體個數(shù)和位置。二、針對全市（主城六區(qū)A，B，C，D，E，F(xiàn)）的具體情況，按照設置交巡警服務平臺的原則和任務，分析研究該市現(xiàn)有交巡警服務平臺設置方案（參見附件）的合理性。如果有明顯不合理，請給出解決方案。如果該市地點P（第32個節(jié)點）處發(fā)生了

8、重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調度全市交巡警服務平臺警力資源的最佳圍堵方案。1.2 問題分析 一、（1）這個問題是一個交訓警服務平臺管轄范圍的優(yōu)化設計問題，目的是滿足在其管轄范圍內發(fā)生突發(fā)事件，盡量能在3分鐘之內到達事發(fā)地點，影響交巡警到達事發(fā)地點的因素為該交巡警服務平臺到事發(fā)地點的距離，警車的時速為一定的，由于有時間的限制，每個路口盡可能的歸離它近的交巡警平臺管轄，也就是說每個路口應歸屬于里它最近的交巡警服務平臺，首先利用matlab算出每條路線的長度，即根據兩點坐標，按距離公式求出距離，然后利用最短路算法中的Dijkstra算法找出每

9、個路口到最近的交巡警服務平臺的距離和對應的服務平臺的位置編號。 一、（2）對于重大事件需要調度全市20個交巡警服務平臺的警力資源，對13條交通要道實施快速全封鎖，并且一個平臺的警力最多只能封鎖一條交通要道。即要求13條交通要道在要求封鎖時必須有有交巡警，而且速度要盡可能的快，該問題可以有兩個方法，一是利用AMPL給出最優(yōu)的指派，要求距離最遠的也是最短的，即路程最遠的交巡警到達的時間最短，二是利用線性指派算法，求出總路程最短的，即消耗的總時間最短，從節(jié)省能源角度來說方法二比較合適，從到達時間來說，方法一更快。一、（3）本題想在原有的交巡警平臺上再增加2至5個平臺，以達到工作量的均衡和時間在三分鐘

10、內的要求。為此大膽假設92個節(jié)點全為0-1整數(shù)變量，建立0-1整數(shù)模型并額外引入0-1整數(shù)變量（j=1.92），以每條交通要道只能被一個交巡警平臺管轄、每個交巡警平臺至多管轄一個交通要道、交巡警服務平臺自身可以管轄自身及一個恰當?shù)墓ぷ髁繛樯洗_界作為約束條件，尋求min為目標函數(shù)的可行解。即可求出新增加的平臺數(shù)及位置信息。二、（1）對已知現(xiàn)有全市的交通巡警平臺的位置的具體情況的設置方案進行驗證檢驗其位置是否合理，可將全市劃分為具體的六個市區(qū)，判斷每個市區(qū)的交巡警服務平臺到各節(jié)點的最短路程，判斷交巡警能否在三分鐘之內到達該事件所發(fā)生路口。若在三分鐘之內交巡警能到達出事地點則設計合理，反之不合理。因

11、此可利用第一問的類似算法進行判斷。二、（2）對于P點處的犯罪嫌疑人，因其逃跑路線方向不確定，在時間t分鐘后可根據犯罪嫌疑人所處的圓形區(qū)域確定其所包含的頂點集合，再根據頂點集求得邊界節(jié)點，為了達到對p的成功圍堵，就需要最后一個交巡警到指定地點的時間T小于等于t-3，可構造時間函數(shù)f（t）=t-3-T，分析其單調性，利用二分法求得合理的圍堵方法。2 基本假設在本文模型的建立過程中，為了簡化計算模型，同時采用以下幾個假定:（1） 假如事故發(fā)生在交通路口，并且不考慮發(fā)生在兩個路口之間路上的情況。（2） 假設事故發(fā)生后交巡警能立即前往事故地點。（3） 假設交巡警在路途中不會出現(xiàn)拋錨，堵車的現(xiàn)象，并且能嚴

12、格服從領導要求。（4） 對于不能在3分鐘之內有交巡警到達的路口，歸屬于距離該路口最近的交巡警平臺。（5） 假設一個交巡警平臺正好能封鎖一個路口。(6) 假設罪犯逃跑時的速度為60km/h。(7) 假設每區(qū)的的出警時間過長的路口超過該區(qū)總路口的5%，則該區(qū)的交巡警服務平臺設置不合理。3 符號說明 為了便于描述問題，我們用一些符號來代替問題中涉及的一些基本變量。如下表所示。其他一些變量將在文中陸續(xù)說明。符號意義G（V，E）賦權連通圖 D(i , j)頂點i到頂點j的距離D所有頂點的距離矩陣案發(fā)率0-1整型變量S（t）犯罪嫌疑人逃跑t分鐘后生成的頂點集L（S（t）由S（t）生成的邊界點集T最后一個達

13、到指定路口的交巡警需要的時間 f(t)關于時間t的線性函數(shù)4 有關公式及概念的說明4.1最短路問題的一般提法如下：設G=(V,E)為連通圖，圖中各邊（vi，vj）有權wij（wij=表示vi，vj間無邊），vs，vt為圖中任意兩點，求一條道路，使它是從vs到vt的所有路中總權值最小的路。即：min L()=.Dijkstra算法是典型最短路算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解。Dijkstra算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路

14、徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點都加入到S中，算法就結束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。步驟：（1）給vs以P1標號，P1(vs)=0，其余各點均給T標號，T(vi)=+。（2）若vi點為剛得

15、到P1標號的點，考慮這樣的點vj：（vi，vj）屬于E,且vj為T標號。對vj的T標號進行如下的更改：T(vj)=minT(vj),P1(vi)+lij(3) 比較所有具有T標號的點，把最小者改為P1標號，即：P1()=minT(vi)存在兩個以上最小者時，可同時改為P1標號。若全部點均為P1標號則停止。否則用代vi轉回（2）。4.2 指派算法是用來求解線性指派問題（可以是費用最小，也可以是路程最短）因此可轉化為最小費用流問題。最小費用流定義：網絡G=（V，A，C，W）中，對于每一流值為V（f）的可行流f來說，都存在一個流的費用W（f），使W（f）為最小的可行流，則稱為最小費用流?；舅枷耄簭?/p>

16、某個初始的最小費用可行流f（0）（一般為零流）開始，尋求從源點Vs到收點Vt的關于f（0）的最小費用增廣鏈。在中按最大流的標號法的調整方法進行調整，只是在調整量上，要比較增廣鏈0上可調整的量與V-V(f(0)的量值，若> V-V (f（0）),則上調整的量為V-V(f(0)，算法結束。若在鏈0上按流量進行調整，得到流值為V (f（1）)的最小費用可行流f（1），在f（1）上尋找從vs到vt 的費用最小的增廣鏈1，再在1按上述方法進行流量調整，如此反復，直到最小費用可行流的流值達到V為止。所得出的流值之和即為最小的費用，返回的兩列矩陣前者表示是13個交通要道，后者表示所對應的交巡警平臺。（

17、代碼見附錄1）。4.3 0-1整數(shù)規(guī)劃 定義：在整數(shù)規(guī)劃問題中，若變量xi取值為0或者1，則稱該規(guī)劃為0-1規(guī)劃問題；并稱xi為0-1變量，或稱布爾變量。5 模型的建立與求解問題1.1的模型最短路模型 計算并選出與每個路口距離最近的交巡警服務平臺，我們認為該路口就歸屬這個最近的交巡警服務平臺管轄，并檢驗是否滿足3分鐘出警時間要求。模型1的求解：利用matlab軟件進行運算，代入數(shù)據：(1)D,P=all_shortest_paths(sparse(t,h,h,t,w,w,92,92),struct('algname','floyd_warshall')；/D輸出

18、各節(jié)點之間的最短路徑。(2）A=D(1:20,21:92)；/前20個點為交巡警平臺所在的點，為求出其他點到這20個交巡警平臺的最短路，故取前20行，21到92列的最短路數(shù)據進行分析。(3)Y,U=min(A)；/Y表示輸出非交巡警平臺點到交巡警平臺的最短路程，U表示輸出非交巡警平臺路口到所對應交巡警的標號。（Y,U數(shù)據見附錄2）模型1.1結果：顯然每個交巡警服務平臺負責本身路口的管理，其余信息見下表交巡警服務平臺管轄的非交巡警路口所對應的編號1666768707374757724243697135354646545659626354849505152555758673032464760833

19、459313435441011262712251321222324141516363717404118727980818219767820838485868788899091把出警時間不超過3分鐘，轉化為服務平臺距離所管轄的路口距離不超過3千米。由此檢驗得六個路口（28，29，38，39，61，92）不滿足出警時間要求。問題1.2模型最小費用流模型容量網絡G=(V,E,)中，V是路口標號集，E是13個要道到20個服務平臺的最短距離集合，C每條邊(vi,vj)除了已給出容量cij外，還給出了單位流量的費用dij(0)，記G=(V,E,C,d)。求G的已給可行流f=fij，使得流量W(f)=v，且

20、總費用d(f)=min 問題1.2模型的求解：在本問題中dij=1；用matlab編程輸入數(shù)據得出(代碼見附錄1)A=D(1:20,12,14,16,21,22,23,24,28,29,30,38,48,62)/20個交巡警平臺到13個交通要道的距離矩陣A的數(shù)據見附錄5利用matlab軟件，調用已有程序 assign,mc = assignmentproblem(A')/ assign路程最小的指派方案，兩列矩陣，整理結果assign所得數(shù)據如下表：交通要道編號12141621222324282930384862交警服務平臺12149161013111587254交巡警到所要封鎖的路口

21、最遠距離為104.93百米。問題1.2改進模型0-1整數(shù)規(guī)劃模型在上種模型中考慮的是總路程最短，即調度時的總費用最小，未考慮在封鎖路口時調度的最遠交巡警到所封鎖路口所用的時間，因此建立0-1整數(shù)規(guī)劃模型進行求解。設表示xij第i個交巡警服務平臺調度到第j個交通路口的情況。其中x的取值為設最后一個交巡警到達指定的主干道路口所用時間最短：min ；在13個交通路口上，每個路口都必須有一個交巡警： ；每個交巡警服務平臺至多只能去一個路口：；每個交巡警到達路口的距離均小于最后一個到達路口的交警平臺與該路口的距離： 。建立模型如下：目標函數(shù)： min ;s.t： 利用AMPL進行編程(見附錄3) 代入數(shù)

22、據,結果如下：交通要道編號38142823241221224829163062交警服務平臺171615141312111097654由數(shù)據可以看出改進的模型中交巡警到所要封鎖的路口最遠距離為80.1545686百米，顯然優(yōu)于之前的模型的104.93百米。問題1.3模型0-1整數(shù)規(guī)劃模型y表示交通路口j歸屬于交巡警平臺i的情況本問題要求20個交巡警平臺的基礎上再增加2到5個平臺；設i表示增加的平臺個數(shù)，則有；要求再增加平臺后，每個交巡警平臺到所屬路口的時間不超過3分鐘，即： i,j=192；每個交巡警平臺都可以管理自己所在的路口：；每一個節(jié)點都有一個交巡警對其進行管理：；在設置交巡警平臺的個數(shù)上

23、要盡量少的去滿足條件，因此目標函數(shù)為：min i=2192建立模型如下：min i=2192s.t：由于上個模型在現(xiàn)有軟件下無法計算，現(xiàn)考慮各交巡警工作量平衡問題，引入工作強度指標u，其值由交巡警平臺的對所管轄區(qū)的節(jié)點的犯罪率之和來進行衡量。因此對于交巡警的工作強度有：引入工作強度指標后，將約束條件和目標函數(shù)轉換一下，得到改進的模型如下： min S.t：利用AMPL進行編程，代入數(shù)據，結果見附錄9新增加的交巡警平臺個數(shù)：5新增的交巡警平臺位置：23 29 40 61 89問題2.1模型 首先對于全市平臺設置方案的合理性給出判定。我們規(guī)定若出警時間過長的路口超過總路口的5%則設置方案不合理,將

24、全市的交巡警平臺按6個區(qū)分別計算每個區(qū)的合理性。接著用類同問題1.1的模型，計算出每個區(qū)的出警時間超過3分鐘的路口總數(shù)，再與該去的路口總數(shù)比較，若超過總路口5%，即該區(qū)的交巡警平臺設置方案不合理，反之則合理。最后對如果不合理的則利用0-1整數(shù)規(guī)劃為該區(qū)重新分配，找出滿足出警時間不超過3分鐘，工作量盡量均衡的交巡警服務平臺個數(shù)最少的設置方案。利用matlab所編寫的代碼執(zhí)行得到：A，B,C,D,E,F六區(qū)重新分配交巡警平臺位置及其所管轄范圍見附錄10問題2.2模型二分法模型P點圍堵問題圖示：PABCDabcdegfh其中S（t）表示犯罪嫌疑人逃跑t分鐘所能過得頂點集：S（t）=j=b,d,e ,

25、gL（S（t）表示S（t）的邊界點集，且L（S（t）=a,c,f,h。A,B,C,D為交巡警服務平臺假近設p附近點有四個交巡警服務平臺A、B、C、D，在隨著時間t的增長，即令=t-3：為增函數(shù)。再令=T， p點得范圍圈也在擴大，也就意味著交巡警服務平臺到所堵路口的時間在減小，因此函數(shù)為減函數(shù)。為達到堵住犯罪嫌疑人的所有逃跑路線，就需要時間最長的交巡警到達地點的時間T犯罪嫌疑人所需要的時間（t-3）。構造時間函數(shù)f（t），令f（t）=t-3-T ，f（t）為連續(xù)型增函數(shù)，且在t=3時f（3）0。f我們利用二分法求得調度全市交巡警服務平臺警力的最佳圍堵方案如下：1->1,2->41,3

26、->71,4->62,6->234,7->239,10->27,11->11,14->14,15->28,17->17,18->72,19->19,20->78,169->240,170->227,171->216,172->172,173->29,182->241,475->561,476->549,482->488。圍堵任務完成所花費時間為7.92分鐘。6 評價與分析本文通過對該市所提供的交巡警服務平臺的坐標及其標號等數(shù)據的分析處理的前提下，運用Dijkstra算法

27、、01整型規(guī)劃、最小費用流算法等原理建立模型。1.1的模型直接利用Dijkstra算法的基本原理進行編程，通過計算機的運算較快的得出交巡警服務平臺到各節(jié)點的最短距離，進而選擇出交巡警平臺在滿足題目要求的管轄范圍。1.2的初始模型考慮的是最小的費用問題，將所用的最短時間轉化為最短路徑問題，這樣得出的結果是總的時間最小。題目中所說的盡快封鎖出口應以交巡警平臺到最遠距離的最小為封鎖的最后時間長度，因此將模型改進為線性規(guī)劃模型。求出最遠距離的最小值與前模型相比較，雖然前模型總的路程較短，但由于有的交巡警所花費的時間不能在較短時間內封鎖路口，而改進的模型可在較短的時間內封鎖，因此改進的模型比前模型合理。

28、問題1.3的增加交巡警服務平臺數(shù)目為典型的01規(guī)劃模型，因此利用01規(guī)劃模型的原理進行編寫AMPL程序，選擇出最優(yōu)的添加位置進行添加，這樣既可平衡各交巡警的工作量又可滿足交巡警在三分鐘之內到達出事路口進行處理。問題2.1的模型與問題1.1的模型基本相似故可利用問題1.1的模型進行快速求解。對于問題2.2模型利用了二分法的原理，通過建立規(guī)劃模型便可求出最優(yōu)的圍堵方案。文中的模型均是將各問題看做各分區(qū)域問題進行求解，對問題的影響不大，因此本文較合理地解決了所有問題。參考文獻1 劉衛(wèi)國.MATLAB程序設計教程（第二版）.北京：水利水電出版社，2010.2.2 姜啟源、謝金星、葉俊.數(shù)學模型（第四版

29、）.北京：高等教育出版社，2011.1.3 胡運權、郭耀煌.運籌學教程.北京：清華大學出版社，1998.4 王中鮮.MATLAB建模與仿真應用。機械工業(yè)出版社，2010.10.5 Robert Fourer, David M. Gay, Brian W. Kernighan. A Modeling Language for Mathematical ProgrammingM. boyd &fraser publishing company, 1993.附錄1：最小費用流的代碼function assign,mc=assignmentproblem(costmat)% ASSIGNMEN

30、TPROBLEM 求解線性指派問題（費用最?。? assign, mc = assignmentproblem( costmat )% 輸入參數(shù)：% costmat - 費用矩陣，即可以采用全矩陣，其元素值即為費用；% 也可以采用稀疏矩陣，其非0元素值表示費用，其0元素表示無窮大% 輸出參數(shù)：% assign - 費用最小的指派方案，兩列矩陣，表示前者（編號）獲得后者（編號）表示的任務% mc - 最小費用% 示例：% costmat=6 2 6 7 4 2 9 5% 4 9 5 3 8 5 8 2% 5 2 1 9 7 4 3 3% 7 6 7 3 9 2 7 1% 2 3 9 5 7 2

31、6 5% 5 5 2 2 8 1 4 3;% assign,mc = assignmentproblem(costmat)% See also munkres graphmincostflow % % 這里把指派問題化歸到最小費用流問題。% $Author: wanbaocheng$ $Date: 08/01/2008$% m,n=size(costmat);s=m+n+1;t=s+1;excess=min(m,n);if issparse(costmat) num=m*n;else num=nnz(costmat);endtail=zeros(num+m+n,1);head=tail;cap

32、=ones(num+m+n,1);cost=tail;if issparse(costmat) cost(1:m*n)=costmat; loop=0; for j=m+1:m+n for i=1:m loop=loop+1; tail(loop)=i; head(loop)=j; end endelse i j vv=find(costmat); tail(1:num)=i; head(1:num)=j+m; cost(1:num)=vv;endloop=num;for i=1:m loop=loop+1; tail(loop)=s; head(loop)=i;endfor j=m+1:m+

33、n loop=loop+1; tail(loop)=j; head(loop)=t;endmc,exitflag,solu=graphmincostflow(tail,head,cap,cost,s,t,excess);assign=solu(solu(:,1)<=m & solu(:,3)=1,1:2);if exitflag=0 assign(:,2)=assign(assign(:,1),2)-m; assign(:,1)=1:m;else assign(:,2)=assign(:,2)-m;end附錄2：Y = 1.0e+003 * Columns 1 through 8

34、 2.7083 0.9055 0.5000 2.3854 1.7889 0.9000 0.6103 4.7518 Columns 9 through 16 5.7005 0.5831 2.0557 1.1402 0.8276 0.5025 0.4243 0.9243 Columns 17 through 24 0.6083 3.4059 3.6822 1.9144 0.8500 0.9849 0.8000 0.9487 Columns 25 through 32 1.0951 0.9301 1.2806 1.2902 0.5000 0.8485 1.2293 1.6594 Columns 33

35、 through 40 1.1708 2.2709 1.2659 2.0837 1.8682 2.2296 1.4485 1.7392 Columns 41 through 48 4.1902 0.3500 1.0308 1.9363 1.5240 1.8402 1.6194 1.2071 Columns 49 through 56 0.5000 0.8602 1.1403 1.6062 1.9723 0.6265 0.9301 1.2836 Columns 57 through 64 0.9849 0.6403 0.4472 0.8062 0.6708 1.0793 0.5385 1.175

36、2 Columns 65 through 72 0.4472 0.3606 1.4651 1.2946 0.9487 1.3022 1.5988 3.6013U = Columns 1 through 13 13 13 13 13 12 11 11 15 15 7 9 7 8 Columns 14 through 26 9 9 9 16 16 2 2 17 17 2 2 9 8 Columns 27 through 39 7 7 5 5 5 5 5 3 3 5 4 5 5 Columns 40 through 52 4 7 4 4 4 3 3 1 1 1 2 1 2 Columns 53 th

37、rough 65 18 1 1 1 19 1 19 18 18 18 18 20 20 Columns 66 through 72 20 20 20 20 20 20 20附錄3：解決封鎖交通要道的AMPL代碼param num_platform;param num_io_section;param D_s1 . num_platform, 1 . num_io_section >=0;param node_of_io_A1 . num_io_section;var x1 . num_platform, 1 . num_io_section >=0 binary;var dis_m

38、ax;minimize obj: dis_max;C1i in 1 . num_platform: sumj in 1 . num_io_section xi,j <=1;C2j in 1 . num_io_section: sumi in 1 . num_platform xi,j =1;C3i in 1 . num_platform, j in 1 . num_io_section: xi,j*D_si,j<=dis_max;data;param num_platform:=20;param num_io_section:=13;param D_s := : 1 2 3 4 5

39、 6 7 8 9 10 11 12 13 :=;param node_of_io_A := 1 12 2 14 3 16 4 21 5 22 6 23 7 24 8 28 9 29 10 30 11 38 12 48 13 62 ;option solver gurobi;solve;for (i1,j1) in i in 1 . num_platform, j in 1 . num_io_section: xi,j=1 printf "%d -> %d n",i1,node_of_io_Aj1 ;附錄420個交巡警服務平臺到13個交通要道的距離12141621222

40、32428293038486212.22361.60280.92871.92932.10962.25022.28931.90011.95161.20830.58811.18500.488522.04641.41300.73881.73951.91972.06032.11211.72291.77441.03110.39821.03100.603531.83521.27670.60261.60321.78351.92411.90091.51171.56320.82000.60940.81980.439342.18881.50090.82671.82732.00762.14822.25451.615

41、51.54630.80310.48610.73240.035051.76281.29700.62281.62351.77501.91551.82851.13071.06150.31830.94210.24760.518361.76591.30000.62591.62651.77801.91861.83161.13371.06460.32140.94520.25060.533971.49151.08780.41361.41431.50361.64421.55720.85700.80150.05830.75260.12900.791981.40930.94340.26921.26991.42141

42、.56191.47501.02281.04930.30610.58850.30990.867791.30110.82740.15331.15391.31321.45381.36680.97761.07240.34920.47260.41990.9337100.75871.27760.66510.95110.77080.91130.82441.41951.51440.79111.00410.86191.4652110.37910.83371.10900.50720.32700.46750.38051.86331.95821.23501.44791.30571.90901201.19501.423

43、80.86850.68830.64772.17812.27301.54981.76271.62052.2238130.59770.59731.27150.27080.09060.05000.23852.28082.37571.65251.61211.72322.1332141.195000.67420.32650.50680.64730.83591.77451.86931.14611.01481.21681.5359151.70301.29930.62511.62581.71511.85561.76870.47520.57010.44010.96400.51091.1738161.42380.

44、674201.00071.18091.32151.48951.10031.19520.47200.34060.54270.8617172.17831.49030.81621.81681.99712.13772.24401.85481.94971.22650.47561.29010.7821182.42471.85141.17732.17792.35822.49882.49042.10122.15271.40940.83671.36990.6734192.25471.69611.02202.02262.20292.34352.32041.93121.98261.23940.76391.19990.5034202.69462.12131.44712.44782.62812.76862.76032.29382.22471.48151.10661.41070.6449附錄5A區(qū)調整后的交巡警服務平臺管轄范圍1174