災情巡視的數(shù)學模型 Microsoft W

1、災情巡視的數(shù)學模型摘 要本文解決的是對全縣各鄉(xiāng)鎮(zhèn)和村莊的災情巡視問題，要求到達每一個鄉(xiāng)鎮(zhèn)和村莊，屬于點的遍歷性的旅行推銷員問題。有所不同的是要考慮不同組的均衡。所以我們建立了約束最優(yōu)路線模型，雖然在處理該問題上不能得到精確的值，但是可以通過遺傳算法得出求得較好的近似解。得出相對最優(yōu)的巡視分配和路線選擇方案，結果令人滿意。對于問題一： 對于問題二： 對于問題三： 對于問題四： 【關鍵詞】 約束最優(yōu)路線 遺傳算法1. 問題重述今年夏天某縣遭受水災，為考察災情、組織自救，縣領導決定，帶領有關部門負責人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視，巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線

2、。下圖為某縣的鄉(xiāng)（鎮(zhèn)）、村公路網示意圖，公路邊的數(shù)字為該路段的公里數(shù)。附：圖中節(jié)點間距如下所示：(X 節(jié)點,Y 節(jié)點,x 與y 間距)(16,17,6.8) (16,i,11.8) (15,i,8.8) (i,18,8.2) (17,k,9.8) (17,22,6.7)(22,k,10.1) (22,23,10.0) (21,23,9.1) (21,k,4.1) (21,25,7.8) (23,n,7.9) (23,24,8.9) (24,n,13.2) (25,n,8.8) (25,20,6.5) (21,20,7.9) (18,j,8.2) (18,k,9.2) (14,13,8.6) (

3、14,h,9.9) (h,12,10.2) (12,f,12.2) (12,g,7.8) (13,g,8.6) (g,11,6.8) (j,11,13.2) (j,19,8.1) (19,L,7.2) (19,20,9.3) (11,e,14.2) (f,10,10.8) (f,9,5.6) (9,e,7.8) (e,8,8.0) (e,7,7.2) (L,7,14.5) (L,6,11.8) (7,6,7.3) (7,d,15.2) (d,4,12.7) (5,d,11.3) (6,5,9.7) (6,m,9.5)(25,m,12.0) (n,m,14.2) (n,26,10.5) (27,

4、26,7.8) (27,28,7.9) (26,p,10.5) (28,p,12.1) (28,q,8.3) (q,30,7.7) (30,32,10.3) (q,29,7.2) (p,29,15.2) (m,o,19.8) (m,5,11.4) (5,2,8.3) (d,3,8.2) (3,c,7.9) (2,3,4.8) (2,o,9.2) (o,c,11.5) (o,1,60) (p,o,10.1) (o,r,12.9) (29,r,7.9) (31,r,9.2) (31,32,8.2) (33,32,19.0) (31,33,7.3) (33,a,7.4) (r,a,8.8) (a,3

5、4,11.5) (a,1,10.3) (a,b,12.2) (1,b,5.9) (1,c,11.2) (b,c,11.1) (8,4,20.4) (15,14,15.0) (i,13,16.4) (i,j,15.8) (13,j,9.8) (L,20,5.5) (24,27,18.8) (32,35,14.9) (33,35,20.3) (34,35,8.2) (34,b,17.6) 本文需解決的問題有：問題一：若分三組（路）巡視，試設計總路程最短且各組盡可能均衡的巡視路線。問題二：假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。要在24小

6、時內完成巡視，至少應分幾組；給出這種分組下你認為最佳的巡視路線。問題三：在上述關于T , t和V的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認為最佳的巡視路線。問題四：若巡視組數(shù)已定(如三組），要求盡快完成巡視，討論T，t和V改變對最佳巡視路線的影響。2. 模型的假設與符號說明2.1模型的假設假設1： 在巡視過程中沒有意外（如汽車拋錨等）使巡視中斷。假設2： 巡視途中只考慮巡視鄉(xiāng)（鎮(zhèn)）、村，只與巡視路徑、時間有關。假設3： 不考慮巡視人員除巡視外的休息時間。假設4： 在不同的路段汽車的行駛速度相同。假設5： 各巡視組統(tǒng)一行動。假設6： 屬同一鄉(xiāng)

7、鎮(zhèn)的村不一定要分到同一個巡視小組。2.2符號說明3. 問題分析在該題上給出的道路交通圖，要求的是在不同條件下對災情的巡視最佳分組方案和路線的選擇。每一個鄉(xiāng)（鎮(zhèn)）、村都走到還要回到縣城的點遍歷性問題，點的遍歷性問題在圖論中屬于哈密頓問題和旅行推銷員問題。由于該題中需要的分組巡視的最佳路線與多個旅行推銷員問題相似。但是也有不同，對個組的分配還存在均衡性的要求。該題中有53個點（包括縣城）要進行分組巡視。路線、鄉(xiāng)村停留時間、巡視小組的數(shù)量等不盡相同，所以對問題的處理上考慮分組路線最短外還有考慮各組均衡度來對模型進行改進。針對問題一：在分三組的巡視情況下，由于只考慮了路程和均衡度的平衡，所以在得到的最

8、短路程時可能得到的均衡度不好要重新考慮，該問題類似MTSP問題，在得出的結果路線中如果路線優(yōu)均衡度好的結果是檢驗模型好壞的標準。針對問題二：在添加了停留時間的不同之后，有了鄉(xiāng)鎮(zhèn)與村莊的區(qū)別，還有汽車的行駛速度v=35千米/小時，和總時間不能超過24小時的限制，要得到最佳的巡視路線和由多少組去巡視方案。先考慮一個組的線路最短的巡視路徑所需最小的時間和路徑，在來考慮總時間的限制和所需要的組數(shù)。在分配的路線中路程小、要求的組數(shù)也少，均衡度好的結果就要求的最佳巡視路線。針對問題三：在問題二的條件下，現(xiàn)在給的巡視小組足夠多，但是要求的是在最短的時間內完成巡視任務。巡視人員多，但是還是有偏遠的鄉(xiāng)村不容易到達的，所以要考慮在到偏遠鄉(xiāng)村時經過的其他鄉(xiāng)村是由哪個組來巡視的問題要討論。針對問題四：在巡視小組確定的情況下，要盡快完成巡視任務，改變T,t和V時在考慮最佳路線的選取。4. 模型的準備4.1 4.2 遺傳算法： 第k組通過弧（i,j）時取1,其它的為0。 （1） 第k組巡視i時取1，其它的為0。 （2）目標函數(shù) （3） 其中 k=1、2、3、m （4）約束條件 （5） （6） （7） (8)5 問題一的解答6. 問題二的解答7. 問題三的解答8. 問題四的解答