第一篇：2013全國大學(xué)生數(shù)學(xué)建模B題源程序

運(yùn)行前,請將附件所在的目錄加入到MATLAB的路徑中??！

都是自己編的，還望大神指教！

附件1和2的源程序：

Clear all

I=cell(1,19);%存放二值圖片

A=cell(1,19);%存放原始圖片

for j=1:19

if j-1<10

imageName=strcat('00',num2str(j-1),'.bmp');

else

imageName=strcat('01',num2str(j-11),'.bmp');

end

I{j} = imread(imageName);

end

A=I;

%讀取圖片

for j=1:19

for k=1:1980

for h=1:72

if I{j}(k,h)~=255

I{j}(k,h)=1;

else

I{j}(k,h)=0;

end

end

end

end

%將圖片二值化

b=zeros(1,19);

for i=1:19

sum=0;

for j=1:1980

sum=sum+I{i}(j);

end

b(i)=sum;

end

for i=1:19

if b(i)==0

q=i;

end

%找出原圖最左邊的碎紙片的編號,并存放在變量q中

for i=0:18

I{i+1}(1)=i;

A{i+1}(1)=i;

end

%對每張圖片做標(biāo)記(即在二值化后的矩陣和原始圖片的矩陣的第一個(gè)元素處做標(biāo)記)t=I{q};

I{q}=I{1};

I{1}=t;

%交換二值化后的第q張和第一張圖片

t=A{q};

A{q}=A{1};

A{1}=t;

%交換原始圖片的第q張和第一張

for k=1:18

d=zeros(18,1);

for i=k+1:19

t=0;

for j=1:1980

ifI{k}(j,72)==I{i}(j,1)

t=t+1;

end

end

d(i-1)=t;

end

[w,v]=max(d);

t=I{v+1};

I{v+1}=I{k+1};

I{k+1}=t;

end

%對二值圖片進(jìn)行拼接

for k=1:19

for s=1:19

if I{k}(1)==A{s}(1)

t=A{s};

A{s}=A{k};

A{k}=t;

end

end

end

%根據(jù)拼接好的而二值圖片的標(biāo)記信息交換對應(yīng)的原始圖片以便顯示

r=[A{1:19}];

%對圖片做最后的處理，顯示圖片

for i=1:19

y(i)=A{i}(1);

end

%將碎片序號按復(fù)原后順序填入1×19的矩陣

附件2的源程序：

I=cell(11,19);%存放二值圖片

A=cell(11,19);%存放原始圖片

c=zeros(11,19);

for j=1:209

if j-1<10

imageName=strcat('00',num2str(j-1),'.bmp');

else if j-1<100 && j-1>=10

imageName=strcat('0',num2str(j-1),'.bmp');

else if j-1>=100 && j-1<209

imageName=strcat(num2str(j-1),'.bmp');

end

end

end

I{j} = imread(imageName);

end

A=I;

%讀取圖片

for j=1:209

for k=1:180

for h=1:72

if I{j}(k,h)~=255

I{j}(k,h)=1;

else

I{j}(k,h)=0;

end

end

end

end

%將圖片二值化

for i=0:208

I{i+1}(1)=i;

A{i+1}(1)=i;

end

%對每張圖片做標(biāo)記(即在二值化后的矩陣和原始圖片的矩陣的第一個(gè)元素處做標(biāo)記)a1=zeros(1,209);

a2=zeros(1,209);

a3=zeros(1,209);

for j=1:209

sum1=0;

for i=1:180

sum1=sum1+I{j}(i,1);

end

a1(j)=sum1;

end

for j=1:209

sum2=0;

for i=1:72

sum2=sum2+I{j}(1,i);

end

a2(j)=sum2;

end

for i=1:209

a3(i)=a1(i)+a2(i);

end

q=50;

c(1,1)=q-1;

%找出原圖左上角的碎紙片的編號,并存放在變量q中

%在找的過程中發(fā)現(xiàn)一共有10張碎紙片符合要求，此時(shí)需要涉入人工干預(yù)

%經(jīng)過人工分析比較，發(fā)現(xiàn)，最符合要求的碎紙片的編號為049，因此直接給q賦值為50 %對每張圖片做標(biāo)記(即在二值化后的矩陣和原始圖片的矩陣的第一個(gè)元素處做標(biāo)記)j=1;

for i=1:208

if c(i)==0

C{j}=I{i+1};

j=j+1;

end

end

%找出可能是最左邊邊緣的的碎紙片,并存放在元胞數(shù)組C中,共有16個(gè)符合要求 t=I{q};

I{q}=I{1};

I{1}=t;

%交換二值化后的第q張和第一張圖片

r=cell2mat(A);

for i=1:16

t=0;

for j=1:72

if I{1}(180,j)==C{i}(1,j)

t=t+1;

end

d(i)=t;

end

[w,v]=max(d);

y=C{v}(1);

t=I{2};

I{2}=I{y+1};

I{y+1}=t;

%************************上面的代碼不要修改*************************%

a=[2038 148 2462 1485 770 361 7610 2396 9429 12918 2112 501 230 818 1157 2110 5465 5111 10242

6066 4233 4988 4250 720 10392 2985 1974 9016 3827 409 11833 817 489 1081 3089 90 6100 270

1031 7561 1444 2117 4252 709 6368 428 134 1219 4248 129 1007 406 2994 163 181 3782 10404

2389 1489 4964 5653 299 232 3008 9612 8409 4251 1177 12995 1247 5477 58 1441 1107 5587 160

1104 823 1028 5998 6544 1158 158 3650 2070 5999 5066 7453 4264 3660 2469 8729 11413 3004 1376753 5067 541 81 149 1014 3830 143 7451 4302 3849 6349 1511 1846 2986 11965 2520 2802 4373

2386 2689 348 417 14010 162 2210 492 4372 1092 159 1677 350 2044 233 126 10924 4230 1011

483 69 70 2481 1453 3083 6781 4308 10244 1221 3781 5637 1090 8339 1490 403 4781 1038 1246

1024 4315 10379 1082 164 3954 717 2062 6083 5049 4981 86 712 1801 1667 340 6954 2333 2106

1261 738 1108 1182 1487 161 2329 5046 9587 1 4998 128 3142 2277 4304 4018 1630 5121 6343

10192 2458 2045 300 6942 1688 301 1870 6074 1680 2111 5473 721 2519 11905 6245 1450 1835];

for i=1:209

aa(i)=r(a(i));

end

s1=reshape(aa,11,19);

for k=1:209

for s=1:209

if I{k}(1)==A{s}(1)

t=A{s};

A{s}=A{k};

A{k}=t;

end

end

end

for k=1:19

for i=1:11

for j=1:19

if s1(l,k)==A{i,j}(1)t=A{i,j};A{i,j}=A{l,k};A{l,k}=t;break;end

end

end

end

end

for i=1:11

for j=1:19

I{1}=A{i,j};

end

end

r=cell2mat(A);

imshow(r);

%%對圖片做最后的處理，顯示圖片

第二篇：2016年全國大學(xué)生數(shù)學(xué)建模B題思路

2016 高教社杯全國大學(xué)生數(shù)學(xué)建模競賽題目、注意：這只是看了 3 篇文章，找到的思路，請大家多看文獻(xiàn)，思路會(huì)很多！我們后續(xù)會(huì)整理更多的思路！

關(guān)鍵詞：

1.評價(jià)指標(biāo)體系，評價(jià)開放對周邊道路通行的效果。

2.車輛通行的數(shù)學(xué)模型，研究小區(qū)開放對周邊道路通行的影響。

3.小區(qū)開放產(chǎn)生的效果，可能會(huì)與小區(qū)結(jié)構(gòu)及周邊道路結(jié)構(gòu)、車流量有關(guān)。請選取或構(gòu)建不同類型的小區(qū)，應(yīng)用你們建立的模型，定量比較各類型小區(qū)開放前后對道路通行的影響。

4.根據(jù)你們的研究結(jié)果，從交通通行的角度，向城市規(guī)劃和交通管理部門提出你們關(guān)于小區(qū)開放的合理化建議。

相關(guān)資料整理：

1.評價(jià)指標(biāo)體系，評價(jià)開放對周邊道路通行的效果。B 題分析初稿，旨在交流，有各種做題思路，大家自由發(fā)揮！

參考文獻(xiàn)《居住小區(qū)開發(fā)交通影響分析研究_商仲華》第 48 頁，有 5 個(gè)指標(biāo)，并用層次分析 AHP 進(jìn)行了研究。

我們要做的可能是強(qiáng)調(diào)類似哪些指標(biāo)是針對開放對周邊道路通行的效果，不屬于這類的指標(biāo)可以刪除。

2.車輛通行的數(shù)學(xué)模型，研究小區(qū)開放對周邊道路通行的影響。

參考文獻(xiàn)《城市交通擁堵對策_(dá)封閉型小區(qū)交通開放研究_李向朋》第 11 頁，圖 6 上面，給出一句話，關(guān)于開放小區(qū)的定義。

是不是建模就是選取小區(qū)附件的某些范圍研究，這就是理論依據(jù)。

參考文獻(xiàn)《城市交通擁堵對策_(dá)封閉型小區(qū)交通開放研究_李向朋》第 26 頁，圖 3.2，了解道路系統(tǒng)的簡圖，用簡圖做分析。

簡單的車輛模型，可以化個(gè)節(jié)點(diǎn)，圖，權(quán)重。分析流量。類似文獻(xiàn)《城市應(yīng)急車輛優(yōu)先通行關(guān)鍵問題研究_畢煦東》第 23 頁，用其中的符號定義等，后面的應(yīng)急什么別管，太復(fù)雜。利用這里模型分析第一個(gè)問題中指標(biāo)系統(tǒng)的指標(biāo)。

3.小區(qū)開放產(chǎn)生的效果，可能會(huì)與小區(qū)結(jié)構(gòu)及周邊道路結(jié)構(gòu)、車流量有關(guān)。請選取或構(gòu)建不同類型的小區(qū)，應(yīng)用你們建立的模型，定量比較各類型小區(qū)開放前后對道路通行的影響。

小區(qū)結(jié)構(gòu)：參考文獻(xiàn)《城市交通擁堵對策_(dá)封閉型小區(qū)交通開放研究_李向朋》第 10 頁，還有 26 頁的

我們要定量分析幾類小區(qū)的開放效果，第 4 問寫建議時(shí)候，可能鴨血，那些小區(qū)就不要開放了，那些很有必要，等等。

利用前兩個(gè)模型，對不同小區(qū)進(jìn)行計(jì)算。要考慮小區(qū)結(jié)構(gòu)及周邊道路結(jié)構(gòu)、車流量等的影響。就是調(diào)參數(shù)，算結(jié)果。

4.根據(jù)你們的研究結(jié)果，從交通通行的角度，向城市規(guī)劃和交通管理部門提出你們關(guān)于小區(qū)開放的合理化建議。

參考文獻(xiàn)《居住小區(qū)開發(fā)交通影響分析研究_商仲華》第 69 有一些交通的改善建議，可以類似參考。

寫建議，寫建議時(shí)候注意文章說了兩種觀點(diǎn)，除了開放小區(qū)可能引發(fā)的安保等問題外，議論的焦點(diǎn)之一是：開放小區(qū)能否達(dá)到優(yōu)化路網(wǎng)結(jié)構(gòu)，提高道路通行能力，改善交通狀況的目的，以及改善效果如何。一種觀點(diǎn)認(rèn)為封閉式小區(qū)破壞了城市路網(wǎng)結(jié)構(gòu)，堵塞了城市“毛細(xì)血管”，容易造成交通阻塞。小區(qū)開放后，路網(wǎng)密度提高，道路面積增加，通行能力自然會(huì)有提升。也有人認(rèn)為這與小區(qū)面積、位置、外部及內(nèi)部道路狀況等諸多因素有關(guān)，不能一概而論。還有人認(rèn)為小區(qū)開放后，雖然可通行道路增多了，相應(yīng)地，小區(qū)周邊主路上進(jìn)出小區(qū)的交叉路口的車輛也會(huì)增多，也可能會(huì)影響主路的通行速度。

模型要做的是解答這些觀點(diǎn)，比如哪類小區(qū)結(jié)構(gòu)，哪類周邊道路結(jié)構(gòu)、車流量等適合第一個(gè)觀點(diǎn)，那個(gè)是第二個(gè)，或者有新的觀點(diǎn)，等等。

可參考開放策略《基于城市道路網(wǎng)絡(luò)脆弱性的小區(qū)開放策略研究_詹斌》其他：大神可做更復(fù)雜的流量模型《城市混合交通流微觀仿真建模研究_鄺先驗(yàn)》

可參考，元胞自動(dòng)機(jī)模型。、大神可考慮突發(fā)條件下模型的適用性等等，《冰雪條件下信號交叉口通行能

力研究_劉春曉》，加分點(diǎn)。累死，發(fā)揮點(diǎn)很多。

大神能兩天學(xué)會(huì)交通仿真軟件 VISSIM，也可以一試。

第三篇：2013年全國大學(xué)生數(shù)學(xué)建模大賽B題

2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽題目

（請先閱讀“全國大學(xué)生數(shù)學(xué)建模競賽論文格式規(guī)范”）B題碎紙片的拼接復(fù)原

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。請討論以下問題：

1.對于給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對附件

1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)（見【結(jié)果表達(dá)格式說明】）。

2.對于碎紙機(jī)既縱切又橫切的情形，請?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對附件

3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果表達(dá)要求同上。

3.上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實(shí)情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復(fù)原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果，結(jié)果表達(dá)要求同上。

【數(shù)據(jù)文件說明】

(1)每一附件為同一頁紙的碎片數(shù)據(jù)。

(2)附件

1、附件2為縱切碎片數(shù)據(jù)，每頁紙被切為19條碎片。

(3)附件

3、附件4為縱橫切碎片數(shù)據(jù)，每頁紙被切為11×19個(gè)碎片。

(4)附件5為縱橫切碎片數(shù)據(jù)，每頁紙被切為11×19個(gè)碎片，每個(gè)碎片有正反兩面。該附

件中每一碎片對應(yīng)兩個(gè)文件，共有2×11×19個(gè)文件，例如，第一個(gè)碎片的兩面分別對應(yīng)文件000a、000b。

【結(jié)果表達(dá)格式說明】

復(fù)原圖片放入附錄中，表格表達(dá)格式如下：

(1)附件

1、附件2的結(jié)果：將碎片序號按復(fù)原后順序填入1×19的表格；

(2)附件

3、附件4的結(jié)果：將碎片序號按復(fù)原后順序填入11×19的表格；

(3)附件5的結(jié)果：將碎片序號按復(fù)原后順序填入兩個(gè)11×19的表格；

(4)不能確定復(fù)原位置的碎片，可不填入上述表格，單獨(dú)列表。

第四篇：2011數(shù)學(xué)建模A,B題

2011高教社杯全國大學(xué)生數(shù)學(xué)建模競賽題目

（請先閱讀“全國大學(xué)生數(shù)學(xué)建模競賽論文格式規(guī)范”）

A題

城市表層土壤重金屬污染分析

隨著城市經(jīng)濟(jì)的快速發(fā)展和城市人口的不斷增加，人類活動(dòng)對城市環(huán)境質(zhì)量的影響日顯突出。對城市土壤地質(zhì)環(huán)境異常的查證，以及如何應(yīng)用查證獲得的海量數(shù)據(jù)資料開展城市環(huán)境質(zhì)量評價(jià)，研究人類活動(dòng)影響下城市地質(zhì)環(huán)境的演變模式，日益成為人們關(guān)注的焦點(diǎn)。

按照功能劃分，城區(qū)一般可分為生活區(qū)、工業(yè)區(qū)、山區(qū)、主干道路區(qū)及公園綠地區(qū)等，分別記為1類區(qū)、2類區(qū)、??、5類區(qū)，不同的區(qū)域環(huán)境受人類活動(dòng)影響的程度不同。

現(xiàn)對某城市城區(qū)土壤地質(zhì)環(huán)境進(jìn)行調(diào)查。為此，將所考察的城區(qū)劃分為間距1公里左右的網(wǎng)格子區(qū)域，按照每平方公里1個(gè)采樣點(diǎn)對表層土（0~10 厘米深度）進(jìn)行取樣、編號，并用GPS記錄采樣點(diǎn)的位置。應(yīng)用專門儀器測試分析，獲得了每個(gè)樣本所含的多種化學(xué)元素的濃度數(shù)據(jù)。另一方面，按照2公里的間距在那些遠(yuǎn)離人群及工業(yè)活動(dòng)的自然區(qū)取樣，將其作為該城區(qū)表層土壤中元素的背景值。

附件1列出了采樣點(diǎn)的位置、海拔高度及其所屬功能區(qū)等信息，附件2列出了8種主要重金屬元素在采樣點(diǎn)處的濃度，附件3列出了8種主要重金屬元素的背景值。

現(xiàn)要求你們通過數(shù)學(xué)建模來完成以下任務(wù)：

(1)給出8種主要重金屬元素在該城區(qū)的空間分布，并分析該城區(qū)內(nèi)不同區(qū)域重金屬的污染程度。

(2)通過數(shù)據(jù)分析，說明重金屬污染的主要原因。

(3)分析重金屬污染物的傳播特征，由此建立模型，確定污染源的位置。(4)分析你所建立模型的優(yōu)缺點(diǎn)，為更好地研究城市地質(zhì)環(huán)境的演變模式，還應(yīng)收集什么信息？有了這些信息，如何建立模型解決問題？

B題

交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度

“有困難找警察”，是家喻戶曉的一句流行語。警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實(shí)施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺(tái)。每個(gè)交巡警服務(wù)平臺(tái)的職能和警力配備基本相同。由于警務(wù)資源是有限的，如何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個(gè)實(shí)際課題。

試就某市設(shè)置交巡警服務(wù)平臺(tái)的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問題：

（1）附件1中的附圖1給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服務(wù)平臺(tái)的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見附件2。請為各交巡警服務(wù)平臺(tái)分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3分鐘內(nèi)有交巡警（警車的時(shí)速為60km/h）到達(dá)事發(fā)地。

對于重大突發(fā)事件，需要調(diào)度全區(qū)20個(gè)交巡警服務(wù)平臺(tái)的警力資源，對進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個(gè)平臺(tái)的警力最多封鎖一個(gè)路口，請給出該區(qū)交巡警服務(wù)平臺(tái)警力合理的調(diào)度方案。

根據(jù)現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過長的實(shí)際情況，擬在該區(qū)內(nèi)再增加2至5個(gè)平臺(tái)，請確定需要增加平臺(tái)的具體個(gè)數(shù)和位置。

（2）針對全市（主城六區(qū)A，B，C，D，E，F(xiàn)）的具體情況，按照設(shè)置交巡警服務(wù)平臺(tái)的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺(tái)設(shè)置方案（參見附件）的合理性。如果有明顯不合理，請給出解決方案。

如果該市地點(diǎn)P（第32個(gè)節(jié)點(diǎn)）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報(bào)警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調(diào)度全市交巡警服務(wù)平臺(tái)警力資源的最佳圍堵方案。

附件1：A區(qū)和全市六區(qū)交通網(wǎng)絡(luò)與平臺(tái)設(shè)置的示意圖。

附件2：全市六區(qū)交通網(wǎng)絡(luò)與平臺(tái)設(shè)置的相關(guān)數(shù)據(jù)表（共5個(gè)工作表）。

第五篇：2011年數(shù)學(xué)建模B題

2011年全國大學(xué)生數(shù)學(xué)建模B題

交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度

題 目 警車配置及巡邏問題的研究

摘 要：

本文研究的是某城區(qū)警車配置及巡邏方案的制定問題，建立了求解警車巡邏方案的模型，并在滿足D1的條件下給出了巡邏效果最好的方案。

在設(shè)計(jì)整個(gè)區(qū)域配置最少巡邏車輛時(shí)，本文設(shè)計(jì)了算法1：先將道路離散化成近似均勻分布的節(jié)點(diǎn)，相鄰兩個(gè)節(jié)點(diǎn)之間的距離約等于一分鐘巡邏路程。由警車的數(shù)目m,將全區(qū)劃分成m個(gè)均勻的分區(qū)，從每個(gè)分區(qū)的中心點(diǎn)出發(fā)，找到最近的道路節(jié)點(diǎn)，作為警車的初始位置，由Floyd算法算出每輛警車3分鐘或2分鐘行駛路程范圍內(nèi)的節(jié)點(diǎn)?？紤]區(qū)域調(diào)整的概率大小和方向不同會(huì)影響調(diào)整結(jié)果，本文利用模擬退火算法構(gòu)造出遷移幾率函數(shù)，用遷移方向函數(shù)決定分區(qū)的調(diào)整方向。計(jì)算能滿足D1的最小車輛數(shù)，即為該區(qū)應(yīng)該配置的最小警車數(shù)目，用MATLAB計(jì)算，得到局部最優(yōu)解為13輛。

在選取巡邏顯著性指標(biāo)時(shí)，本文考慮了兩個(gè)方面的指標(biāo)：一是全面性，即所有警車走過的街道節(jié)點(diǎn)數(shù)占總街道節(jié)點(diǎn)數(shù)的比例，用兩者之比來評價(jià)；二是均勻性，即所有警車經(jīng)過每個(gè)節(jié)點(diǎn)數(shù)的次數(shù)偏離平均經(jīng)過次數(shù)的程度，用方差值來大小評價(jià)。

問題三：為簡化問題，假設(shè)所有警車在同一時(shí)刻，大致向同一方向巡邏，運(yùn)動(dòng)狀態(tài)分為四種：向左，向右，向上，向下，記錄每個(gè)時(shí)刻，警車經(jīng)過的節(jié)點(diǎn)和能夠趕去處理事故的點(diǎn)，最后匯總計(jì)算得相應(yīng)的評價(jià)指標(biāo)。

在考慮巡邏規(guī)律隱蔽性要求時(shí)，文本將巡邏路線進(jìn)行隨機(jī)處理，方向是不確定的，采用算法2進(jìn)行計(jì)算，得出相應(yīng)巡邏顯著指標(biāo)，當(dāng)車輛數(shù)減少到10輛或巡邏速度變大時(shí)，用算法2計(jì)算巡邏方案和對應(yīng)的參數(shù)，結(jié)果見附錄所示。

本文最后還考慮到4個(gè)額外因素，給出每個(gè)影響因素的解決方案。

關(guān)鍵詞：模擬退火算法；Floyd算法；離散化

一 問題的重述

110警車在街道上巡邏，既能夠?qū)`法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的安全感，同時(shí)也加快了接處警時(shí)間，提高了反應(yīng)時(shí)效，為社會(huì)和諧提供了有力的保障。

現(xiàn)給出某城市內(nèi)一區(qū)域，其道路數(shù)據(jù)和地圖數(shù)據(jù)已知，該區(qū)域內(nèi)三個(gè)重點(diǎn)部位的坐標(biāo)分別為：（5112，4806），（9126，4266），（7434，1332）。該區(qū)域內(nèi)共有307個(gè)道路交叉口，為簡化問題，相鄰兩個(gè)交叉路口之間的道路近似認(rèn)為是直線，且所有事發(fā)現(xiàn)場均在下圖的道路上。

該市擬增加一批配備有GPS衛(wèi)星定位系統(tǒng)及先進(jìn)通訊設(shè)備的110警車。設(shè)110警車的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h。警車配置及巡邏方案要盡量滿足以下要求：

D1.警車在接警后三分鐘內(nèi)趕到現(xiàn)場的比例不低于90％；而趕到重點(diǎn)部位的時(shí)間必須在兩分鐘之內(nèi)。

D2.使巡邏效果更顯著；

D3.警車巡邏規(guī)律應(yīng)有一定的隱蔽性?，F(xiàn)在我們需要解決以下幾個(gè)問題：

一.若要求滿足D1,該區(qū)最少需要配置多少輛警車巡邏？ 二.請給出評價(jià)巡邏效果顯著程度的有關(guān)指標(biāo)。

三．請給出滿足D1且盡量滿足D2條件的警車巡邏方案及其評價(jià)指標(biāo)值。

四.在第三問的基礎(chǔ)上，再考慮D3條件，給出你們的警車巡邏方案及其評價(jià)指標(biāo)值。五．如果該區(qū)域僅配置10輛警車，應(yīng)如何制定巡邏方案，使D1、D2盡量得到滿足？ 六.若警車接警后的平均行駛速度提高到50km/h，回答問題三。

七.你們認(rèn)為還有哪些因素、哪些情況需要考慮？給出你們相應(yīng)的解決方案。

二 問題分析

本題為城區(qū)道路網(wǎng)絡(luò)中警車配置及巡邏問題。在進(jìn)行警車配置時(shí)，首先要考慮警車在接警后在規(guī)定時(shí)間內(nèi)趕到現(xiàn)場的比例，在此條件下，以車數(shù)最少為目標(biāo)，建模、求解；在制定巡邏方案時(shí)，要考慮巡邏的效果及隱蔽性問題。

問題一只要求滿足D1，求最少的警車配置數(shù)，可以認(rèn)為警車是不動(dòng)的，在三分鐘或兩分鐘內(nèi)它能到達(dá)的區(qū)域就是它的覆蓋范圍。據(jù)此，在滿足所有街道的覆蓋率不低于90%的條件下，尋找最優(yōu)解。

問題二要評價(jià)巡邏效果，有兩個(gè)方面需要考慮：一是巡邏的全面性，即經(jīng)過一段時(shí)間后警車走過的街道數(shù)占總街道數(shù)的比例；二是巡邏的不均勻性，即經(jīng)過一段時(shí)間后警車經(jīng)過每一條街道的次數(shù)相差不大，用方差來衡量。

問題三是在滿足D1的條件上盡量滿足問題二所給的指標(biāo)，并給出評價(jià)方案的指標(biāo)。首先找到一組滿足D1的各警車位置，然后在和各警車位置相連的點(diǎn)中隨機(jī)尋找一個(gè)點(diǎn)，判斷新的點(diǎn)是否滿足D1，如果滿足則警車行駛到該點(diǎn)，否則重新尋找，直到滿足為止。一段時(shí)間后統(tǒng)計(jì)所有車走過的點(diǎn)數(shù)及每個(gè)點(diǎn)被走過的次數(shù)，用問題二給出的兩個(gè)指標(biāo)進(jìn)行評價(jià)。綜合兩個(gè)指標(biāo)，可判斷此路徑的好壞，重復(fù)這個(gè)過程，直到綜合評價(jià)指標(biāo)達(dá)到一個(gè)滿意的值為止。

問題四增加了隱蔽性要求，首先給出評價(jià)隱蔽性的指標(biāo)，隱蔽性可用路線的隨機(jī)性來評價(jià)，將它加入到問題三的模型中去進(jìn)行求解。

問題五限制警車數(shù)量為10，要綜合考慮D1、D2，先分配這10輛車使道路的覆蓋率最高，然后按照問題三的步驟進(jìn)行求解，其中每一步對D1的判斷只需使道路的覆蓋率盡量高即可。

問題六同問題三，只需將車速改為50km/h即可。

三 模型的假設(shè)

1.警車都在路上巡邏，巡警去處理案件的時(shí)間不考慮；

2.所有事發(fā)現(xiàn)場都在道路上，案件在道路上任一點(diǎn)是等概率發(fā)生的； 3.警車初始?？奎c(diǎn)是隨機(jī)的，但盡量讓它們分散分布，一輛警車管轄一個(gè)分區(qū)； 4.假定各個(gè)劃分區(qū)域內(nèi)，較短時(shí)間內(nèi)，最多會(huì)發(fā)生一個(gè)案件；

5.假設(shè)區(qū)域內(nèi)的每條道路都是雙行線，不考慮轉(zhuǎn)彎對結(jié)果造成的影響； 6.如果重點(diǎn)部位不在道路上的，假設(shè)這些重點(diǎn)部位在離它們最近的道路上； 7.圖中水域?qū)ρ策壏桨笡]有影響。

四 符號說明

m 表示警車數(shù)目

d 表示警車初始?？奎c(diǎn)到各道路的最短距離 L 表示整個(gè)區(qū)域的總道路長度

l 表示不能在3分鐘內(nèi)到達(dá)的區(qū)域的道路的長度

k 表示非重點(diǎn)部位的警車在3分鐘內(nèi)不能到達(dá)現(xiàn)場的比例 r 表示三分鐘內(nèi)能從接警位置趕到事發(fā)現(xiàn)場的最大距離是 n 表示整個(gè)區(qū)域總的離散點(diǎn)個(gè)數(shù) ni 表示第i區(qū)內(nèi)的節(jié)點(diǎn)個(gè)數(shù) f1 表示區(qū)內(nèi)調(diào)整函數(shù)

t 表示模擬退火的時(shí)間，表征溫度值 f2 表示區(qū)間調(diào)整函數(shù)

r 表示全面性指標(biāo) e 表示不均勻性指標(biāo) h 表示綜合評價(jià)指標(biāo)

si 表示第i輛車經(jīng)過每條道路的次數(shù) s 表示整個(gè)區(qū)域每條道路經(jīng)過的平均次數(shù)

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

5.1 滿足D1時(shí)，該區(qū)所需要配置的最少警車數(shù)目和巡邏方案 5.1.1 滿足D1條件時(shí)，區(qū)域最少警車的規(guī)律

題目要求警車的配置和巡邏方案滿足D1要求時(shí)，整個(gè)區(qū)域所需要配置的警車數(shù)目最少。由假設(shè)可知警車都在道路上，且所有事發(fā)現(xiàn)場也都在道路上，但區(qū)域內(nèi)總的道路長度是個(gè)定值的；警車在接警后趕到事發(fā)現(xiàn)場有時(shí)間限制和概率限制：三分鐘內(nèi)趕到普通區(qū)域案發(fā)現(xiàn)場的比例不低于90％，而趕到重點(diǎn)部位的時(shí)間必須控制在兩分鐘之內(nèi)。由此可知每輛警車的管轄范圍不會(huì)很大，于是考慮將整個(gè)區(qū)域分成若干個(gè)分區(qū)，每輛警車管轄一個(gè)分區(qū)域。由上面的分析，求解整個(gè)區(qū)域的警車數(shù)目最少這個(gè)問題可轉(zhuǎn)化為求解每一輛警車所能管轄的街道范圍盡量的大。于是我們尋找出使每輛警車管轄的范圍盡量大的規(guī)律。為了簡化問題，我們不考慮趕到現(xiàn)場的90%的幾率的限制，僅對警車能在三分鐘內(nèi)趕到事發(fā)現(xiàn)場的情況作定性分析，其分析示意圖如圖1所示。警車的初始停靠位置是隨機(jī)的分布在道路上的任一節(jié)點(diǎn)上，我們假設(shè)一輛警車停靠在A點(diǎn)上。

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

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

60如圖1所示，我們設(shè)警車初始?？课恢迷贏點(diǎn)，A點(diǎn)是道路1，2，3，4的道路交叉口。我們僅以警車在道路1巡邏為例來進(jìn)行分析，警車以20km/h的速度在道路1上A到A'點(diǎn)之間巡邏，A'與初始停靠點(diǎn)A的距離為xkm。由于案件有可能在道路上任一點(diǎn)發(fā)生，當(dāng)警車巡邏到A點(diǎn)時(shí)，若案發(fā)現(xiàn)場在道路2，3，4上發(fā)生時(shí)，警車以40km/h的速度向事發(fā)現(xiàn)場行駛，警車能在三分鐘內(nèi)從A'點(diǎn)趕到現(xiàn)場的最大距離為(2?x)km。如果警車在道路1上繼續(xù)向前行駛，則該警車能在三分鐘內(nèi)趕到現(xiàn)場的距離繼續(xù)縮小，當(dāng)警車從初始點(diǎn)向A點(diǎn)行駛但沒有達(dá)到A'點(diǎn)時(shí)，此時(shí)該警車的最大管轄范圍比警車到達(dá)A'點(diǎn)時(shí)的最大管轄范圍大。為了使警車的管轄范圍盡量大，警車的巡邏范圍越小越好，當(dāng)x?0時(shí)，即警車在初始?？奎c(diǎn)靜止不動(dòng)時(shí)，警車的管轄范圍達(dá)到最大值2km。

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

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

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

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

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

5.1.2 將道路離散化

由于事發(fā)現(xiàn)場是等概率地分布在道路上的，由區(qū)域地圖可以發(fā)現(xiàn)，整個(gè)區(qū)域中的道路長度不均，為了使計(jì)算結(jié)果更加精確，可將這些道路離散化。只要選取合適的離散方案，就能使警車在經(jīng)過道路上的離散的點(diǎn)時(shí)就相當(dāng)于經(jīng)過了這條道路。這樣，不論是求解警車初始?？奎c(diǎn)還求解警車趕到事發(fā)現(xiàn)場所經(jīng)過的道路時(shí)，所計(jì)算得的的結(jié)果顯然比僅考慮整條道路的叉路口要精確得多。區(qū)域中共有307個(gè)道路交叉口，458條道路。我們采用線性插值方法對道路進(jìn)行離散化，以20km/h的速度行走一分鐘的距離作為步長，一分鐘時(shí)間的選擇是參照問題三的11?20?km。用線性插值的方法，從道路的一個(gè)方向進(jìn)結(jié)果要求來設(shè)定的，步長b?6031行線性插值，實(shí)現(xiàn)將每條道路離散化的目標(biāo)，考慮到有些道路不是km的整數(shù)倍，我們

311就一般情況進(jìn)行討論，其分析示意圖如圖3所示。道路AB長度為n個(gè)km與x(x?km)33長度的和，為了更精確處理CB段道路，那么就要考慮在CB之間是否要插入一個(gè)新的點(diǎn)，根據(jù)x的長度不同，其對應(yīng)的處理方式也有所不同。

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

引進(jìn)臨界指數(shù)y，選取y大小的準(zhǔn)則是使盡量離散化后警車等效的平均巡邏速度和題目給定的速度（20km/h）的差值盡量小，經(jīng)過計(jì)算得y?0.189km時(shí)，不再插入新的坐

1標(biāo)點(diǎn)時(shí)能使整個(gè)區(qū)域的道路離散效果較好。此時(shí)，將CB段長度設(shè)定為km處理，于是

3離散后的AB道路長度會(huì)比實(shí)際長度短些；當(dāng)x?0.189Km時(shí)，需要在兩個(gè)點(diǎn)之間再插入一點(diǎn)，因?yàn)檫@樣處理能使整個(gè)區(qū)域的整體道路的離散化效果比較理想。如圖3所示，在1C與B間再插入新的坐標(biāo)點(diǎn)，插入的位置在距C點(diǎn)km的D點(diǎn)處,這樣處理后所得的道

31路長度比實(shí)際長度長了(?x)km。采用這樣的方法進(jìn)行線性插值，我們使用MATLAB編3程實(shí)現(xiàn)對整個(gè)區(qū)域道路的離散，所得的離散結(jié)果如圖4所示，離散后共得到762個(gè)節(jié)點(diǎn)，比原始數(shù)據(jù)多了455個(gè)節(jié)點(diǎn)，離散后的節(jié)點(diǎn)數(shù)據(jù)見附件中的“newpoint.txt”。

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

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

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

考慮到警車配置和巡邏方案需要滿足：警車在接警后三分鐘內(nèi)趕到普通部位案發(fā)現(xiàn)場的比例不低于90%，趕到重點(diǎn)部位必須控制在兩分鐘之內(nèi)的要求。設(shè)計(jì)算法的目標(biāo)就是求解出在滿足D1情況下，總的警車數(shù)目最小，即每個(gè)區(qū)域都盡可能多地覆蓋道路節(jié)點(diǎn)。由于警車的初始位置是未知的，我們可設(shè)警車初始停靠點(diǎn)在道路上的任一點(diǎn)，即分布在圖4所示的762個(gè)離散點(diǎn)中的某些點(diǎn)節(jié)點(diǎn)上，總體思路是讓每兩輛車之間盡量分散地分布，一輛警車管轄一個(gè)分區(qū)，用這些分區(qū)覆蓋整個(gè)區(qū)域。于是我們設(shè)計(jì)算法1，步驟如下所示：

Step1：將整個(gè)區(qū)域預(yù)分配為m個(gè)分區(qū)，每個(gè)分區(qū)分配一輛警車，警車的初始?？课恢迷O(shè)在預(yù)分配區(qū)中心的道路節(jié)點(diǎn)上，若區(qū)域的中心不在道路節(jié)點(diǎn)上，則將警車放在離中心最近的道路節(jié)點(diǎn)上；

Step2：統(tǒng)計(jì)分區(qū)不能覆蓋的節(jié)點(diǎn)，調(diào)整警車的初始?？奎c(diǎn)，使分區(qū)覆蓋盡可能多的道路節(jié)點(diǎn)，調(diào)整分為區(qū)內(nèi)調(diào)整和區(qū)間調(diào)整方案：（1）區(qū)內(nèi)調(diào)整按照模擬退火思想構(gòu)造的函數(shù)，在區(qū)間調(diào)整調(diào)整車輛初始點(diǎn)的位置（后文中有詳細(xì)說明），當(dāng)分區(qū)內(nèi)節(jié)點(diǎn)數(shù)較多時(shí)，調(diào)整的概率小些，分區(qū)內(nèi)節(jié)點(diǎn)數(shù)較少時(shí)，調(diào)整的概率大些，（2）當(dāng)區(qū)域中存在未被覆蓋的節(jié)點(diǎn)或節(jié)點(diǎn)群（大于等于三個(gè)節(jié)點(diǎn)集中在一個(gè)范圍內(nèi)）時(shí)，將警車初始位置的調(diào)整方向?yàn)槌@些未被覆蓋的節(jié)點(diǎn)按一定的規(guī)則（在算法說明中有詳細(xì)敘述）移動(dòng)，同時(shí)要保證 3個(gè)重點(diǎn)部位能在2分鐘之內(nèi)100%到達(dá)；

Step3：用Floyd算法計(jì)算出警車初始?？奎c(diǎn)到周邊各道路節(jié)點(diǎn)的最短距離d；

Step4：以m個(gè)劃分區(qū)域未覆蓋的總的道路長度l與整個(gè)區(qū)域的道路總長度L的比值lk??100%來表示警車不能3分鐘內(nèi)到達(dá)現(xiàn)場的概率；

LStep5：模擬足夠多的次數(shù)，若k?10%，將車輛數(shù)m減1，跳轉(zhuǎn)到Step1；

Step6：計(jì)算結(jié)束后，比較當(dāng)k?10%時(shí)所對應(yīng)的m值，當(dāng)m取得最小值時(shí)，記錄此時(shí)的區(qū)域劃分方案，m即為最少的警車數(shù)。

對算法的幾點(diǎn)說明：

（1）該算法所取的車輛數(shù)m是由多到少進(jìn)行計(jì)算的，m初始值設(shè)為20，這個(gè)值的選取是根據(jù)區(qū)域圖估算的。

(2)預(yù)分區(qū)的優(yōu)點(diǎn)在于使警車的初始位置盡可能均勻地分散分布，警車的初始?？奎c(diǎn)在一個(gè)分區(qū)的中心點(diǎn)附近尋找得到，比起在整個(gè)區(qū)域隨機(jī)生成停靠點(diǎn)，計(jì)算效率明顯得到提高。

預(yù)分配之后，需要對整個(gè)區(qū)域不斷地進(jìn)行調(diào)整，調(diào)整時(shí)需要考慮調(diào)整方向和 調(diào)整概率。

警車調(diào)整借鑒的是模擬退火算法的方法，為了使分區(qū)內(nèi)包含道路節(jié)點(diǎn)數(shù)較多的分區(qū)的初始停車點(diǎn)調(diào)整的概率小些，而分區(qū)內(nèi)包含道路節(jié)點(diǎn)數(shù)的少的分區(qū)內(nèi)的初始停車點(diǎn)調(diào) 整的概率大些，我們構(gòu)造了一個(gè)調(diào)整概率函數(shù)f1，f1?aexp(?bmni)（1）t（1）式中，a,b均為常數(shù)，m為整個(gè)區(qū)域車輛數(shù)，ni為第i分區(qū)內(nèi)覆蓋的節(jié)點(diǎn)數(shù)，t為時(shí)間，同時(shí)t也能表征模擬退火的溫度變化情況：初始溫度較高，區(qū)域調(diào)整速度較快，隨著時(shí)間的增加，溫度不斷下降，區(qū)域調(diào)整速度逐漸變慢，這個(gè)調(diào)整速度變化也是比較符合實(shí)際情況的。

由式（1）可以得出調(diào)整概率函數(shù)f1，假設(shè)在相同的溫度t（時(shí)間）的條件下，由于總的車輛數(shù)目m是定值，當(dāng)ni?nj時(shí)，即第i分區(qū)內(nèi)的節(jié)點(diǎn)數(shù)大于第j分區(qū)的節(jié)點(diǎn)數(shù)時(shí)，分區(qū)i調(diào)整的概率大些，分區(qū)j的調(diào)整概率小些。分析其原因：當(dāng)分區(qū)內(nèi)包含了較多的節(jié)點(diǎn)個(gè)數(shù)時(shí)，該分區(qū)的警車初始?？课恢眠x取地比較合適了，而當(dāng)分區(qū)內(nèi)包含的道路節(jié)點(diǎn)數(shù)較少時(shí)，說明警車的初始?？课恢脹]有選好，需要更大概率的調(diào)整，這樣的結(jié)論也是比較客觀的。

對于所有分區(qū)外未被覆蓋的道路節(jié)點(diǎn)和很多節(jié)點(diǎn)（稱之為節(jié)點(diǎn)群），用來調(diào)整警車位置遷移的方向，其分析示意圖如圖5所示。調(diào)整方案目標(biāo)是使未被覆蓋的節(jié)點(diǎn)數(shù)盡量的少。在設(shè)計(jì)調(diào)整方向函數(shù)時(shí)，需要考慮：（1）節(jié)點(diǎn)群內(nèi)節(jié)點(diǎn)的數(shù)目；（2）警車距離節(jié)點(diǎn)群的位置。優(yōu)先考慮距離，所以在公式（2）中，用距離的平方來描述調(diào)整方向函數(shù)。由于某一個(gè)區(qū)域范圍內(nèi)的未被覆蓋節(jié)點(diǎn)數(shù)，整個(gè)區(qū)域未被覆蓋的節(jié)點(diǎn)總數(shù)，分區(qū)域與未被覆蓋的節(jié)點(diǎn)或節(jié)點(diǎn)群的距離等幾個(gè)因素會(huì)影響到調(diào)整的方案，所以要綜合考慮這些因素。于是設(shè)計(jì)了區(qū)間調(diào)整函數(shù)f2，f2?nili2??li?1pi?1p2i（2）

i?n式中，ni表示第i個(gè)分區(qū)內(nèi)未被覆蓋的節(jié)點(diǎn)數(shù)，li表示第i分區(qū)域與未被覆蓋的節(jié)點(diǎn)或節(jié)點(diǎn)群的距離，p表示未被覆蓋的節(jié)點(diǎn)和節(jié)點(diǎn)群個(gè)數(shù)。

現(xiàn)在簡要分析第i分區(qū)按區(qū)間調(diào)整函數(shù)的調(diào)整方案，當(dāng)某兩節(jié)點(diǎn)群i,j的節(jié)點(diǎn)數(shù)目相等，但是距離不等時(shí)，如li?lj，由區(qū)間調(diào)整公式可知，該區(qū)間向節(jié)點(diǎn)群j方向調(diào)整。當(dāng)某個(gè)分區(qū)與兩個(gè)節(jié)點(diǎn)群的距離相等，但節(jié)點(diǎn)群的內(nèi)節(jié)點(diǎn)個(gè)數(shù)不相等，如ni?nj時(shí)，由（4）可知，該分區(qū)域會(huì)想節(jié)點(diǎn)群j方向調(diào)整。

注意在整個(gè)調(diào)整過程中，調(diào)整幾率控制是否調(diào)整，調(diào)整方向函數(shù)控制調(diào)整的方向，尋找在這種調(diào)整方案下的最優(yōu)結(jié)果。

圖5 調(diào)整分區(qū)域示意圖

（3）在step3中，使用Floyd算法計(jì)算出警車初始?？奎c(diǎn)到周邊各節(jié)點(diǎn)的最短距離d,目的是當(dāng)區(qū)域內(nèi)有情況發(fā)生時(shí)，警車能在要求的時(shí)間限制內(nèi)到達(dá)現(xiàn)場。

（4）為求出較優(yōu)的警車?？奎c(diǎn)，采用模擬退火算法，算出局部最優(yōu)的方案。5.1.4 警車的配置和巡邏方案

使用MATLAB編程實(shí)現(xiàn)算法1得到，整個(gè)區(qū)域配備13輛警車，這些警車靜止在初始?？奎c(diǎn)時(shí)，能滿足D1要求。警車的初始停靠位置分別為道路交叉節(jié)點(diǎn)6，25，30，37，82，84，110，111，126，214，253，258，278處。每個(gè)警車所管轄的交叉點(diǎn)（原始的交叉節(jié)點(diǎn)）如圖6所示，求解的分區(qū)結(jié)果見附錄所示。9

圖6 滿足D1條件下的區(qū)分劃分圖

13個(gè)分區(qū)共覆蓋了252個(gè)交叉點(diǎn)，另外的55個(gè)原始交叉點(diǎn)沒有被這些分區(qū)域覆蓋：137，138，151，159，167，168，170，174，175，186，188，189，211，215，226，242，255，260，261，262，263，267，270，271，272，275，282，283，284，287，288，289，292，296，297，299，304，305，307。在這種分區(qū)方案下，這些點(diǎn)中，每兩個(gè)相連的點(diǎn)間的道路離散值長度占整個(gè)區(qū)域總的長度的比值為lk??100%?90.18%。因此，在整個(gè)區(qū)域配置13輛警車，每個(gè)警車在初始?？奎c(diǎn)靜L止不動(dòng)，當(dāng)有案件發(fā)生時(shí)，離案發(fā)現(xiàn)場最近的警車從初始?？奎c(diǎn)趕到現(xiàn)場。

5.2 評價(jià)巡邏效果顯著的指標(biāo)

110警車在街道上巡邏是目的是為了對違法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的安全感，同時(shí)還加快了接處警（接受報(bào)警并趕往現(xiàn)場處理事件）時(shí)間，提高了反應(yīng)時(shí)效，為社會(huì)和諧提供了有力的保障。巡警在城市繁華街道、公共場所執(zhí)行巡邏任務(wù), 維護(hù)治安, 服務(wù)群眾, 可以得良好的社會(huì)效應(yīng)[1]。

在整個(gè)區(qū)域中，由于案發(fā)現(xiàn)場都在道路上，道路上的每一點(diǎn)都是等概率發(fā)生的，因此警車巡邏的面越廣，所巡邏的街道數(shù)目越多，警車的巡邏效果就越好，對違法犯罪分子就越有威懾力，警車也能更及時(shí)地處理案件。

我們采用全面性r來衡量巡邏的效果顯著性，即用警車巡邏所經(jīng)過的街道節(jié)點(diǎn)數(shù)占區(qū)域總節(jié)點(diǎn)數(shù)的比值。當(dāng)警車重復(fù)經(jīng)過同一條街道同一個(gè)離散點(diǎn)時(shí)，c僅記錄一次。

c

（3）n式中，c表示警車經(jīng)過的離散點(diǎn)數(shù)，n代表整個(gè)區(qū)域總的離散點(diǎn)數(shù)。r值越大，表明警車所經(jīng)過的街道數(shù)目越多，所取得的效果越顯著。

同時(shí)考慮到在巡邏過程中可能會(huì)出現(xiàn)這樣的情況：在相同的時(shí)段內(nèi)，警車會(huì)多次巡邏部分街道，而一些街道卻很少巡邏甚至沒有警車到達(dá)，這樣會(huì)造成一些巡邏盲區(qū)。分布很不均衡。這樣就可能出現(xiàn)巡邏密度大的街道上的違法犯罪分子不敢在街道上作案，而流竄到巡邏密度稀疏的街道上作案，因此在相同的警車數(shù)目條件下，密度不均衡的巡邏方式的巡邏效果的效果較差，而密度較均衡的巡邏方式所取得的巡邏效果會(huì)更好些。我們引入一個(gè)巡邏的不均勻度e來衡量巡邏效果的顯著性，考慮到方差能表示不均衡度，于是我們用方差的大小來表征不均衡，方差越大，巡邏密度越不均衡，所取得的巡邏效果越差。r?e??(si?1mi?s)2p（4）

式中，p表示警車經(jīng)過的點(diǎn)數(shù)，當(dāng)警車重復(fù)經(jīng)過某一節(jié)點(diǎn)時(shí)，警車經(jīng)過該點(diǎn)多少次就計(jì)多少次。，si表示第i輛車經(jīng)過每條道路的次數(shù)，s表示整個(gè)區(qū)域每條道路經(jīng)過的平均次數(shù)。

我們分析這兩個(gè)指標(biāo)時(shí)，發(fā)現(xiàn)它們是緊密聯(lián)系的，在相同的時(shí)間段內(nèi)，一輛警車在一個(gè)分區(qū)巡邏時(shí)，警車經(jīng)過的街道節(jié)點(diǎn)數(shù)越多，巡邏的全面性指標(biāo)越大，巡邏效果越顯著，而巡邏經(jīng)過了越多的街道節(jié)點(diǎn)數(shù)，對應(yīng)的不均勻度越小，巡邏效果也越好，所以我們將這兩個(gè)指標(biāo)統(tǒng)一來求解，設(shè)定為綜合評價(jià)指標(biāo)h：

rh?（5）

e當(dāng)h越大時(shí)，警車巡邏的顯著性效果越好，而當(dāng)h越小時(shí)，警車巡邏的效果越差。

5.3 滿足D1且盡量滿足D2條件的警車巡邏方案和評價(jià)指標(biāo)值

問題1所給出的滿足D1條件下的警車數(shù)目為13輛，這時(shí)每輛警車在初始停靠點(diǎn)靜止不動(dòng)，只有該管轄區(qū)域內(nèi)發(fā)生了案件時(shí)，警車才從初始?？奎c(diǎn)趕到案發(fā)現(xiàn)場處理案件。當(dāng)警車在巡邏狀態(tài)時(shí)，所需要考慮的問題就更復(fù)雜一些，如當(dāng)節(jié)點(diǎn)運(yùn)動(dòng)時(shí)，警車還能否達(dá)到D1的要求，警車的運(yùn)動(dòng)方向如何等問題，但基本算法思想與問題1類似，所得的算法2的框圖如圖7所示，為了簡化問題，我們假設(shè)各分區(qū)警車的巡邏時(shí)候，盡量保證所有的警車的行駛方向相一致，且警車都走雙行道，即當(dāng)警車走到某個(gè)節(jié)點(diǎn)后，它們又同時(shí)返回初始?？奎c(diǎn)，警車的行駛方向有四種方式，如6所示。

在圖6中，數(shù)字1代表走巡邏走的第一步，2表示朝1的巡邏方向相反的方向巡邏。在具體程序?qū)崿F(xiàn)時(shí)，四種巡邏方向任意選擇，但是盡量保證所有的警車向同一個(gè)方向巡邏。

圖6 各警車巡邏方向圖

我們用MATLAB編程對這種巡邏方式進(jìn)行計(jì)算，所得的車輛數(shù)目為18輛，綜合評價(jià)指標(biāo)為h?0.612，其結(jié)果巡邏方案見附件中的“1193402-Result3.txt”所示。

5.4 在滿足問題三的基礎(chǔ)上討論D3條件，警車的巡邏方案和評價(jià)指標(biāo)

巡邏的隱蔽性體現(xiàn)在警車的巡邏路線和時(shí)間沒有明顯的規(guī)律，主要目的是讓違法犯罪分子無可乘之機(jī)，防止他們在非巡邏時(shí)間實(shí)施違法犯罪活動(dòng)，危害人民的生命和財(cái)產(chǎn)安全。

為了使巡邏的規(guī)律具有隱蔽性，這就需要警車在巡邏時(shí)至少具有兩條不同的路線，時(shí)間最好也是不相同的。因此，考慮到隱蔽性時(shí)，只需要在問題2的基礎(chǔ)上加上一個(gè)隨機(jī)過程即可。對于其評價(jià)指標(biāo)，由于警車有幾條可選的巡邏路線，當(dāng)相同的路線在同一時(shí)間內(nèi)重復(fù)出現(xiàn)時(shí)，重新將所設(shè)定的方案再執(zhí)行一遍，我們用這個(gè)時(shí)間間隔來衡量隱蔽性的程度，當(dāng)循環(huán)周期T越大，表明可選的巡邏方案越多，其規(guī)律就越具有隱蔽性，而循環(huán)周期T越小時(shí)，表明巡邏方案比較少，其隱蔽性較差。在巡邏狀態(tài)時(shí)，最差的隱蔽性巡邏方案是巡邏方案只有一個(gè)，并且時(shí)間固定，這樣的巡邏方案沒有任何隱蔽性可言。

5.5 整個(gè)區(qū)域?yàn)?0輛車時(shí)的巡邏方案

由第三問的結(jié)果可知，10輛車的數(shù)量是不能把整個(gè)區(qū)域完全覆蓋的，其算法與算法2類似，不同的是此時(shí)車的數(shù)目已經(jīng)固定了，要求使D1,D2盡量大的滿足，我們求得的評價(jià)指標(biāo)值為h?0.524，所得的巡邏方案見附件中的“1193402-Result5.txt”所示。

5.6平均行駛速度提高到50km/h時(shí)的巡邏方式和評價(jià)指標(biāo)值

問題六的分析方法與具體實(shí)現(xiàn)與問題三一致，但是警車的接警后的平均速度由原來的40km/h提高到50km/h，于是各分區(qū)的覆蓋范圍也增大了，將數(shù)值帶入問題3的算法中求解，計(jì)算得的指標(biāo)值為h?0.703，其巡邏方案見附件中的“1193402-Result6.txt”所示。

圖7 算法2框圖 5.7 需要另外考慮的因素和對應(yīng)的解決方案

考慮到具體巡邏情況的復(fù)雜性，我們還需考慮以下幾個(gè)因素：

1．該城市的巡邏方式僅有110警車，雖然能將巡邏范圍大大擴(kuò)大，但是警員坐在汽車?yán)镞h(yuǎn)離市民，對社區(qū)情況和案件的了解情況不如徒步巡邏的效果好，同時(shí)警車巡邏時(shí)，只能在道路上行駛，對應(yīng)圖中的非道路區(qū)域沒有進(jìn)行巡邏，使非街道區(qū)域成為巡邏盲區(qū)；

2.對于突發(fā)事件的處理問題；

3.各巡邏警員之間在一些未被覆蓋的區(qū)域如何合作才能使整體的巡邏效果取得比較好的成效；

4.巡邏頻率的選取問題。

針對以上問題，我們提出以下幾個(gè)解決方案： 1.為了了解社區(qū)情況和將巡邏范圍擴(kuò)大到非街道區(qū)，可以采用警車加徒步巡邏或摩托車方式進(jìn)行巡邏，這樣做會(huì)使整個(gè)巡邏范圍擴(kuò)大，必會(huì)大大增加巡警人數(shù)，在制定巡邏方案時(shí)，需要綜合考慮，選取最合適的巡邏方案；

2.當(dāng)有突發(fā)事件發(fā)生時(shí)，要突破分區(qū)限制，各分區(qū)需要通力合作，還要求巡警及時(shí)掌握準(zhǔn)確信息，向上級部門匯報(bào)，隨機(jī)應(yīng)變地解決所遇到的問題；

3.在警員人數(shù)有限的情況下，需要各分區(qū)巡警明確巡邏目的，踏實(shí)工作，明確責(zé)任制，做好本職工作，使人民生命財(cái)產(chǎn)安全得到最大限度的保障；

4.巡邏頻率太高，會(huì)影響到人民的正常工作和生活（報(bào)紙刊登有相關(guān)消息），如果巡邏頻率太低，將降低市民的安全感，同時(shí)給一些違法犯罪分子予可乘之機(jī)，所以要合理安排巡邏方案，將巡邏頻率控制在一個(gè)適當(dāng)?shù)姆秶鷥?nèi)。

六 模型的分析和評價(jià)

在求解滿足D1的條件下，整個(gè)區(qū)域需要配備多少輛警車問題中，采用分區(qū)巡邏的思想，先分析能使各區(qū)管轄范圍達(dá)到最大值時(shí)的規(guī)律，由特殊到一般層層進(jìn)行分析，邏輯嚴(yán)密，結(jié)果合理。

在求解區(qū)域和警車數(shù)目時(shí)，在初步設(shè)定警車?？奎c(diǎn)位置的基礎(chǔ)上，用模擬退火算法思路構(gòu)造函數(shù)f1來確定調(diào)整的概率大小，綜合考慮了影響區(qū)間調(diào)整的因素后構(gòu)造了f2函數(shù)來確定分區(qū)的調(diào)整方向，當(dāng)分區(qū)按照這兩個(gè)調(diào)整函數(shù)進(jìn)行調(diào)整時(shí)，各分區(qū)能管轄盡可能多的道路節(jié)點(diǎn)，所取得效果也比較理想。

參 考 文 獻(xiàn)

[1]中小城市警察巡邏勤務(wù)方式的探討，俞詳，江蘇公安?？茖W(xué)校學(xué)報(bào)，1998年第1期 [2]Matlab7.0從入門到精通，求是科技，人民郵電出版社； [3]不確定車數(shù)的隨機(jī)車輛路徑問題模型及算法，運(yùn)懷立等，工業(yè)工程，第10卷第3期，2005年5月；

[4]隨機(jī)交通分配中的有效路徑的確定方法，李志純等，交通運(yùn)輸系統(tǒng)工程與信息，第3卷第1期，2003年2月。

附 錄

圖 問題三巡邏路徑

圖 問題五巡邏路徑

圖 問題六巡邏路徑