數(shù)學(xué)建模（第3頁）

ni表示第i區(qū)內(nèi)的節(jié)點個數(shù)

f1表示區(qū)內(nèi)調(diào)整函數(shù)

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

f2表示區(qū)間調(diào)整函數(shù)

r表示全面性指標(biāo)

e表示不均勻性指標(biāo)

h表示綜合評價指標(biāo)

si表示第i輛車經(jīng)過每條道路的次數(shù)

-s表示整個區(qū)域每條道路經(jīng)過的平均次數(shù)

五模型的建立與算法的設(shè)計

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

511滿足d1條件時，區(qū)域最少警車的規(guī)律

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

由上面的分析，求解整個區(qū)域的警車數(shù)目最少這個問題可轉(zhuǎn)化為求解每一輛警車所能管轄的街道范圍盡量的大。于是我們尋找出使每輛警車管轄的范圍盡量大的規(guī)律。為了簡化問題，我們不考慮趕到現(xiàn)場的90的幾率的限制，僅對警車能在叁分鐘內(nèi)趕到事發(fā)現(xiàn)場的情況作定性分析，其分析示意圖如圖1所示。警車的初始?？课恢檬请S機的分布在道路上的任一節(jié)點上，我們假設(shè)一輛警車?？吭赼點上。

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

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

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

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

圖21圖22

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

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

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

綜上所述，當(dāng)警車靜止在初始?？奎c時，在叁分鐘時間限制內(nèi)，警車能從初始?？奎c趕到事發(fā)現(xiàn)場的最大距離為。

512將道路離散化

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

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

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

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

圖4整個區(qū)域離散結(jié)果圖

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

513分區(qū)域求解警車數(shù)目的算法設(shè)計