災情巡視路線選擇

1、災情巡視路線選擇摘要 本文就災情巡視問題進行分析，并建立相應的數(shù)學模型，根據(jù)路程長短以及村鎮(zhèn)的停留時間合理地規(guī)劃路線，并根據(jù)要求調(diào)整優(yōu)化。問題一中要求設計總路程最短且各組盡可能均衡。先找出最短生成樹，然后設計路線，并人工優(yōu)化路線。問題二要求分組最少的前提下設計最佳的巡視路線。將總路程、鄉(xiāng)（鎮(zhèn)）、村的數(shù)目大致均分，能最大程度的節(jié)約時間，同時合理優(yōu)化。問題三的人員足夠多，先計算到達該縣最遠的鄉(xiāng)（鎮(zhèn)）或村所需的時間，此時間為完成巡視的最短時間。其余村鎮(zhèn)可以運用統(tǒng)籌的方式遍歷并最后優(yōu)化。問題四要求盡快完成巡視，先用函數(shù)式表示這個最小的時間，然后分別討論T、t、V的改變對最小時間以及最佳路線的影響。同時

2、根據(jù)實際分組等具體因素的影響確定均衡度的合理范圍，再根據(jù)均衡度對各小組的路線進行優(yōu)化。關鍵字：普林算法 最小生成樹 均衡度 統(tǒng)籌 一、 問題的描述與分析1.1問題的描述 大水無情人有情，為考察災情，縣領導決定派人及早將各鄉(xiāng)（鎮(zhèn)），村巡視一遍，巡視路線為從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)），村，又回到縣政府所在地的路線。1. 若分三組（路）巡視，試設計總路程最短且各組盡可能均衡的巡視路線。 2. 假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2 小時，在各村停留時間 t=1 小時，汽車行駛速度V=35公里/ 小時。要在 24小時內(nèi)完成巡視，至少應分幾組；給出這種分組下你認為最佳的巡視路線。3. 在上述關于T

3、 , t 和V 的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認為最佳的巡視路線。 4. 若巡視組數(shù)已定（比如三組），要求盡快完成巡視，討論 T，t 和V 改變對最佳巡視路線的影響。（圖見附錄）1.2問題的分析對于問題一，我們應該要抓住設計總路程最短且各組盡可能均衡這一要點，即總路程不一定是最短的，不一定是最均衡的，但是二者要統(tǒng)籌兼顧。所以路程的設計很重要。由題意可以看出，在設計路線時，三組人的路線盡量不重復，盡量無交叉。對于問題二，我們不再要求路線均衡，但是值得注意的是分組應盡可能的少，在完成任務，分組最少的前提下設計最佳的巡視路線?？梢詮慕o出

4、的題圖看出該縣的各鄉(xiāng)（鎮(zhèn)），村分布較為均與，要想用盡可能少的組在24小時內(nèi)完成任務，其實各組的路程還是大致均分的，才有可能最大程度的節(jié)約時間，從而完成最佳路線的設計。由此看出問題一得到的總路程對于分組的最小值很有參考價值。對于問題三，因為要盡快的完成巡視，并且巡視的人員足夠多。所以我們可以考慮到達該縣最遠的鄉(xiāng)（鎮(zhèn)）或村所需的時間，此時間為完成巡視的最短時間。其余村鎮(zhèn)可以運用統(tǒng)籌的方式遍歷，而且時間差均不大，基本保證人盡其用。對于問題四，題目要求要盡快完成巡視，并討論T、t、V的改變對最佳巡視路線的影響，這些的前提都是巡視組數(shù)一定。由于都不是定值，我們可以用函數(shù)表達式來進行討論。首先確定最短的巡

5、視時間，然后根據(jù)T、t、V的變化討論對最佳路線的影響。然后再根據(jù)具體的分組及在合理的不確定度的范圍內(nèi)，再對各個小組的路線進行優(yōu)化，以求最佳的巡視路線。1.3問題的假設(1) 巡視過程中無意外情況發(fā)生； (2)非本縣村不限制通過；(3）非本縣村不作停留；(4）汽車一旦行駛，始終保持勻速V；(5) 各鄉(xiāng)（鎮(zhèn)），村只考察一次，多次經(jīng)過時只計算一次停留的時間；二、 模型的假設1.均衡度設為，=最大值-最小值最大值，其中最大值和最小值均為一組內(nèi)的數(shù)據(jù)；2.n表示分的小組數(shù)； 3.Ci表示各小組的巡視時間；4. xi表示第i個小組所要巡視巡視的鄉(xiāng)鎮(zhèn)數(shù)；5.yi表示第i個小組所要巡視的村莊數(shù)；6.Si表示第

6、i個小組巡視路線的長度。三、 模型的建立問題一3.1.1問題分析 對于問題一，因為路程盡量短，所以我們可以通過普林算法畫出最小生成樹，依據(jù)最小生成樹的樹干進行劃分，粗略的劃分為三組。這三組很有可能并不是最均衡合理的，但是距離一定是較短的，所以還要計算均衡度并進行優(yōu)化。在最小生成樹中從O點出發(fā)的樹枝稱為干枝，總共有6個干枝，我們考慮把6個干枝兩兩組合分為3組，構(gòu)成3個回路。并計算其均衡度，根據(jù)其均衡度進行相應的人工優(yōu)化，最終得出均衡度合適且總距離最短的3個巡視路線。3.1.2 問題解答 根據(jù)普林算法，我們可以得到最小生成樹如下：根據(jù)上述的問題分析，先把6個干枝編號-，把分為一組，分為一組，分為一

7、組。分組如下：計算其總距離與均衡度，計算結(jié)果如下： 均衡度=241.9-125.5241.9=48.12% 由上面的計算結(jié)果可以看出，其總距離較短但是均衡度較大，所以這種劃分不合理要進行優(yōu)化。所以要將現(xiàn)有的路線進行手工改進，稍稍改變其路線，調(diào)整均衡度，改進后的結(jié)果如下：均衡度=216.4-191.1216.4=11.69%12%由計算可以看出該方案的巡視總路程相比較原來的巡視總路程并未增加太多，但是均衡度明顯下降到11.69%，我們認為均衡度在12%內(nèi)的均為合理的均衡度。所以我們現(xiàn)在認為改進后的路線不僅總路程較小，而且均衡，即為最佳的巡視路線。問題二3.2.1問題分析對于問題二，我們首先可以用

8、問題一得到的巡視總路程作為問題二的巡視總路程進行估算，然后得到最小的分組數(shù)為4。還有，我們從圖上可以看出，該縣的鄉(xiāng)（鎮(zhèn)），村分布較為均勻，我們可以將鄉(xiāng)（鎮(zhèn)），村較為合理的分為4組，并進行時間及路程的計算，確保在24小時內(nèi)完成巡視。3.2.2 問題解答 我們將599.8近似的看為600參與計算。我們從圖上得到共有17個鄉(xiāng)（鎮(zhèn)），35個村，要遍歷這些地方至少要停留172+35=69(小時)設分為n組600v+69n24解得n3.59通過計算，我們可以得到我們至少要將組數(shù)定為4。根據(jù)我們得到的最小生成樹圖和該縣地圖我們，將4條巡視路線定為如下：圖上每種顏色代表一條巡視路線。由上面的路線圖，可以計算這

9、四條巡視路線各自所需的時間。小組編號路線路線長度（km）所用時間（h）O-2-5-6-7-E-11-G-12-H-F-10-F-9-E-8-E-7-6-5-2-O195.822.59O-M-25-21-K-18-I-15-14-13-J-19-L-20-25-M-O162.422.64O-P-26-N-23-22-17-16-17-22-23-24-27-28-Q-29-R-O156.921.48O-C-3-D-4-D-3-C-B-A-34-35-32-30-32-31-33-A-1-O186.622.33我們可以看出4條路線的巡視都在24小時內(nèi)完成，而且都控制在23小時內(nèi)，路線劃分合理。問題

10、三3.3.1問題分析對于問題三，我們可以從題目得到，巡視的人員足夠多，但是務必要求在最短的時間內(nèi)完成巡視。要求最短的時間，就應該求出離縣委政府O最遠的鄉(xiāng)（鎮(zhèn)）或村所需的時間，且在途經(jīng)的鄉(xiāng)（鎮(zhèn)）或村不作停留，這樣才能求出最短的巡視時間。我們要得到最佳的巡視路線，盡管人員足夠多，我們還是應當避免不必要的人力物力的浪費，每組完成巡視的時間應當盡量差不多。根據(jù)最小生成樹及該縣地圖還有求出的最短的巡視時間，我們將整個巡視路線進行統(tǒng)籌規(guī)劃，合理分組。3.3.2 問題解答我們通過計算可得離縣委政府O最遠的鄉(xiāng)（鎮(zhèn)）為H，到H所需的時間至少是6.43小時。并通過最小生成樹及該縣的地圖進行合理的分組。顯然，其余組

11、的時間要小于第一組O-H-O的時間6.43小時，根據(jù)統(tǒng)籌學，我們進行了合理的劃分和計算。詳細如下表：小組名稱路線所用時間（h）停留地點時間差（h）第一組O-H-O6.43H0第二組O-3-D-4-D-3-2-O5.993、4、D0.44第三組O-2-5-6-M-O6.342、3、5、M0.09第四組O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O5.859、120.58第五組O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O5.767、100.67第六組O-2-5-6-E-11-G-11-E-6-5-2-O5.58G0.85第七組O-2-5-6-7-E-9

12、-F-9-E-7-6-5-3-O6.15F、E0.28第八組O-2-5-6-7-E-11-E-8-E-8-E-11-E-7-6-5-2-O5.658、110.78第九組O-2-5-6-L-20-L-6-5-2-O5.54L、200.89第十組O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O6.1513、140.28第十一組O-2-5-6-L-19-J-19-L-6-5-2-O6.1019、J0.33第十二組O-M-25-21-K-17-16-17-K-21-25-M-O5.4516、170.98第十三組O-M-25-21-K-18-I-15-I-18-K-21-25

13、-M-O5.9915、180.44第十四組O-M-25-21-K-18-I-18-K-21-25-M-O5.49I0.94第十五組O-M-25-21-K-21-25-M-O5.4921、K0.94第十六組O-P-26-N-23-22-23-N-26-27-26-P-O6.2522、23、270.18第十七組O-M-25-N-26-P-O6.0525、26、N0.38第十八組O-P-26-N-24-27-28-Q-29-R-O6.0624、28、290.37第十九組O-P-28-Q-29-R-O5.67P、Q0.76第二十組O-R-29-Q-30-32-31-R-O6.17R、30、320.26

14、第二十一組O-R-31-33-A-34-35-34-A-1-O5.6431、33、350.79第二十二組O-1-A-B-1-O6.261、A、B0.17第二十三組O-1-A-34-A-1-O-C-O5.2534、C1.18問題四3.4.1問題分析巡視組數(shù)一定，要求盡快完成巡視，討論T、t、V的改變對最佳巡視路線的影響。本問要求盡快完成巡視，也就是要求各組巡視時間的最大值盡可能小。用數(shù)學表達式表示出這個最小的時間，然后分別討論T、t、V的改變對最小時間以及最佳路線的影響。同時根據(jù)實際的人員及環(huán)境等具體因素的影響確定均衡度的合理范圍，再根據(jù)確定的均衡度對各小組的路線進行優(yōu)化。3.4.2 問題解答巡

15、視的最小時間的數(shù)學表達式為minmaxCi=minmax1inT*xi+t*yi+SiV這里，Ci表示各小組的巡視時間，n表示分的小組數(shù)，xi表示第i個小組所要巡視巡視的鄉(xiāng)鎮(zhèn)數(shù)，yi表示第i個小組所要巡視的村莊數(shù)，Si表示第i個小組巡視路線的長度。 Ci= T*xi+t*yi+SiV 在上述表達式中，T和t的作用完全相仿，所以在討論時，T和t一起進行討論。1. 若T或t增加而V保持不變。為了使Ci盡可能小，則必須使T*xi+t*yi的最大值盡可能小。然而，當T和t確定之后，i(T*xi+t*yi)的值是確定的，因為總共有17個鄉(xiāng)（鎮(zhèn)）和35個村。這時，在鄉(xiāng)、村停留的時間對總的巡視時間的影響變大

16、。這就要求，每組停留的鄉(xiāng)村數(shù)要基本一致。當然，還要計算均衡度并根據(jù)設定的均衡度以及實際情況對各組進行相應的調(diào)整優(yōu)化。2. 若V增大而T和t保持不變。為了使Ci盡可能小，則必須使SiV的最大值盡可能小。此時，巡視路線對總的巡視時間的影響變大。由于巡視路程的不固定性，我們在使巡視路線相對均衡的前提下，還要考慮T*xi+t*yi的影響，并根據(jù)設定的均衡度以及實際情況對巡視路線進行調(diào)整優(yōu)化。四、模型的評價 1.該問題屬于行遍性問題中的流動推銷員問題，也就是TSP問題。是已經(jīng)被論證的NPC問題，至今仍沒有簡單有效的算法，在圖中尋求最佳回路問題可轉(zhuǎn)化為在一個完備加權圖中尋求最佳哈密爾頓圈的問題，運算量很大，而且還不能保證得到