數學建模（第3頁）

ni表示第i區內的節點個數

f1表示區內調整函數

t表示模擬退火的時間，表征溫度值

f2表示區間調整函數

r表示全面性指標

e表示不均勻性指標

h表示綜合評價指標

si表示第i輛車經過每條道路的次數

-s表示整個區域每條道路經過的平均次數

五模型的建立與算法的設計

51滿足d1時，該區所需要配置的最少警車數目和巡邏方案

511滿足d1條件時，區域最少警車的規律

題目要求警車的配置和巡邏方案滿足d1要求時，整個區域所需要配置的警車數目最少。由假設可知警車都在道路上，且所有事發現場也都在道路上，但區域內總的道路長度是個定值的；警車在接警后趕到事發現場有時間限制和概率限制：叁分鐘內趕到普通區域案發現場的比例不低于90％，而趕到重點部位的時間必須控制在兩分鐘之內。由此可知每輛警車的管轄范圍不會很大，于是考慮將整個區域分成假設干個分區，每輛警車管轄一個分區域。

由上面的分析，求解整個區域的警車數目最少這個問題可轉化為求解每一輛警車所能管轄的街道范圍盡量的大。于是我們尋找出使每輛警車管轄的范圍盡量大的規律。為了簡化問題，我們不考慮趕到現場的90的幾率的限制，僅對警車能在叁分鐘內趕到事發現場的情況作定性分析，其分析示意圖如圖1所示。警車的初始停靠位置是隨機的分布在道路上的任一節點上，我們假設一輛警車停靠在a點上。

圖1一輛警車管轄范圍分析示意圖

由于警車的平均巡邏速度為20kh，接警后的平均行駛速度為40kh，由于距離信息比擬容易得到，于是我們將時間限制轉化為距離限制，這樣便于分析和求解。當警車接警后，在叁分鐘內能從接警位置趕到事發現場的最大距離是r，其中。

如圖1所示，我們設警車初始停靠位置在a點，a點是道路1，2，3，4的道路交叉口。我們僅以警車在道路1巡邏為例來進行分析，警車以的速度在道路1上a到點之間巡邏，與初始停靠點a的距離為。由于案件有可能在道路上任一點發生，當警車巡邏到a點時，假設案發現場在道路2，3，4上發生時，警車以40kh的速度向事發現場行駛，警車能在叁分鐘內從點趕到現場的最大距離為。如果警車在道路1上繼續向前行駛，那么該警車能在叁分鐘內趕到現場的距離繼續縮小，當警車從初始點向a點行駛但沒有到達點時，此時該警車的最大管轄范圍比警車到達點時的最大管轄范圍大。為了使警車的管轄范圍盡量大，警車的巡邏范圍越小越好，當時，即警車在初始停靠點靜止不動時，警車的管轄范圍到達最大值。

圖1所分析的是特殊的情況，道路1，2，3，4對稱分布，現在我們來對一般的情況進行分析，如圖2所示。

圖21圖22

圖2一輛警車最大管轄范圍分析示意圖

圖21所示的情況是道路分布不對稱，與圖1相比，圖21所示的道路方向和角度都發生了改變，圖23中的情形更為復雜。參照對圖1的分析方法，我們分析這兩種情形下，警車巡邏時能在叁分鐘內趕到現場的最大距離的規律，我們只分析圖22的情況，道路1，2，3，4，5相交于點c，同時道路1與道路6也有個道路交叉口d，由于警車巡邏時是在道路上行駛的，行走的路線是分段直線，并不影響路徑的長度，所以當警車巡邏到距離初始停靠點c點遠處的d，此時假設有案件發生時，該警車要在叁分鐘內能趕到現場處理案件，最大行駛距離在之內，如果警車在道路1上繼續向前行駛，那么該警車能在叁分鐘內趕到現場的距離繼續縮小，當警車沒有行駛到d點時，此時該警車的最大管轄范圍比大，為了使警車的管轄范圍盡量大，警車的巡邏范圍越小越好。當時，即警車靜止不動時，一輛警車的管轄范圍能到達最大值。

以上分析的僅作定性的分析，對于叁個重點部位也可以同理分析，所得的結論是一致的，以上的分析沒有考慮到90的到達幾率限制，但在設計算法需要充分考慮。

綜上所述，當警車靜止在初始停靠點時，在叁分鐘時間限制內，警車能從初始停靠點趕到事發現場的最大距離為。

512將道路離散化

由于事發現場是等概率地分布在道路上的，由區域地圖可以發現，整個區域中的道路長度不均，為了使計算結果更加精確，可將這些道路離散化。只要選取適宜的離散方案，就能使警車在經過道路上的離散的點時就相當于經過了這條道路。這樣，不管是求解警車初始停靠點還求解警車趕到事發現場所經過的道路時，所計算得的的結果顯然比僅考慮整條道路的叉路口要精確得多。

區域zhonggong有307個道路交叉口，458條道路。我們采用線性插值方法對道路進行離散化，以的速度行走一分鐘的距離作為步長，一分鐘時間的選擇是參照問題叁的結果要求來設定的，步長。用線性插值的方法，從道路的一個方向進行線性插值，實現將每條道路離散化的目標，考慮到有些道路不是的整數倍，我們就一般情況進行討論，其分析示意圖如圖3所示。道路ab長度為個與長度的和，為了更精確處理cb段道路，那么就要考慮在cb之間是否要插入一個新的點，根據的長度不同，其對應的處理方式也有所不同。

圖3道路離散化分析示意圖

引進臨界指數，選取大小的準那么是使盡量離散化后警車等效的平均巡邏速度和題目給定的速度〔〕的差值盡量小，經過計算得時，不再插入新的坐標點時能使整個區域的道路離散效果較好。此時，將cb段長度設定為處理，于是離散后的ab道路長度會比實際長度短些；當時，需要在兩個點之間再插入一點，因為這樣處理能使整個區域的整體道路的離散化效果比擬理想。如圖3所示，在c與b間再插入新的坐標點，插入的位置在距c點的d點處，這樣處理后所得的道路長度比實際長度長了。采用這樣的方法進行線性插值，我們使用atb編程實現對整個區域道路的離散，所得的離散結果如圖4所示，離散后共得到762個節點，比原始數據多了455個節點，離散后的節點數據見附件中的“newpottxt〞。

圖4整個區域離散結果圖

采用這種插值方法道路離散后，將直線上的無窮多個點轉化有限個點，便于分析問題和實現相應的算法，由圖4可知，所取得的整體離散效果還是比擬理想的。

513分區域求解警車數目的算法設計