全國賽題最佳災情巡視路線

1、建模案例：最佳災情巡視路線 這里介紹1998年全國大學生數(shù)學模型競賽B題中的兩個問題.一、問 題今年夏天某縣遭受水災.為考察災情、組織自救，縣領導決定，帶領有關(guān)部門負責人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視.巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線.1 若分三組（路）巡視，試設計總路程最短且各組盡可能均衡的路線.2 假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時.要在24小時內(nèi)完成巡視，至少應分幾組；給出這種分組下最佳的巡視路線.鄉(xiāng)鎮(zhèn)、村的公路網(wǎng)示意圖見圖11-9. 圖11-9二、 假 設1汽車在路上的速度總是一定，不

2、會出現(xiàn)拋錨等現(xiàn)象；2巡視當中，在每個鄉(xiāng)鎮(zhèn)、村的停留時間一定，不會出現(xiàn)特殊情況而延誤時間；3每個小組的汽車行駛速度完全一樣；4分組后，各小組只能走自己區(qū)內(nèi)的路，不能走其他小組的路，除公共路外.三、模 型 的 建 立 與 求 解將公路網(wǎng)圖中，每個鄉(xiāng)（鎮(zhèn)）或村看作圖中的一個節(jié)點，各鄉(xiāng)（鎮(zhèn)）、村之間的公路看作圖中對應節(jié)點間的邊，各條公路的長度（或行駛時間）看作對應邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡圖，問題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡圖中尋找從給定點O出發(fā)，行遍所有頂點至少一次再回到O點，使得總權(quán)（路程或時間）最小，此即最佳推銷員回路問題.在加權(quán)圖G中求最佳推銷員回路問題是NP完全問題，我們采用一種近似算

3、法求出該問題的一個近似最優(yōu)解，來代替最優(yōu)解，算法如下：算法一 求加權(quán)圖G（V，E）的最佳推銷員回路的近似算法：1 用圖論軟件包求出G中任意兩個頂點間的最短路，構(gòu)造出完備圖， ；2 輸入圖的一個初始H圈；3 用對角線完全算法（見23）產(chǎn)生一個初始H圈；4 隨機搜索出中若干個H圈，例如2000個；5 對第2、3、4步所得的每個H圈，用二邊逐次修正法進行優(yōu)化，得到近似最佳H圈；6 在第5步求出的所有H圈中，找出權(quán)最小的一個，此即要找的最佳H圈的近似解.由于二邊逐次修正法的結(jié)果與初始圈有關(guān)，故本算法第2、3、4步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計算結(jié)果.問題一 若分為三組巡視，設計總路程最

4、短且各組盡可能均衡的巡視路線.此問題是多個推銷員的最佳推銷員回路問題.即在加權(quán)圖G中求頂點集V的劃分，將G分成n個生成子圖，使得（1）頂點 i=1，2，3n（2）（3），其中為的導出子圖中的最佳推銷員回路，為的權(quán)，i，j=1，2，3n（4） 定義 稱為該分組的實際均衡度.為最大容許均衡度. 顯然，越小，說明分組的均衡性越好.取定一個后，與滿足條件（3）的分組是一個均衡分組.條件（4）表示總巡視路線最短.此問題包含兩方面：第一、對頂點分組；第二、在每組中求最佳推銷員回路，即為單個推銷員的最佳推銷員問題.由于單個推銷員的最佳推銷員回路問題不存在多項式時間內(nèi)的精確算法，故多個推銷員的問題也不存在多項

5、式時間內(nèi)的精確算法.而圖中節(jié)點數(shù)較多，為53個，我們只能去尋求一種較合理的劃分準則，對圖19進行粗步劃分后，求出各部分的近似最佳推銷員回路的權(quán)，再進一步進行調(diào)整，使得各部分滿足均衡性條件（3）.圖11-10 O點到任意點的最短路圖（單位：公里） 從O點出發(fā)去其它點，要使路程較小應盡量走O點到該點的最短路.故用圖論軟件包求出O點到其余頂點的最短路，這些最短路構(gòu)成一棵O為樹根的樹，將從O點出發(fā)的樹枝稱為干枝，見圖0，從圖中可以看出，從O點出發(fā)到其它點共有6條干枝，它們的名稱分別為，.根據(jù)實際工作的經(jīng)驗及上述分析，在分組時應遵從以下準則：準則一：盡量使同一干枝上及其分枝上的點分在同一組；準則二：應將

6、相鄰的干枝上的點分在同一組；準則三：盡量將長的干枝與短的干枝分在同一組.由上述分組準則，我們找到兩種分組形式如下：分組一：（，），（，），（，）分組二：（，），（，），（，）顯然分組一的方法極不均衡，故考慮分組二.對分組二中每組頂點的生成子圖，用算法一求出近似最優(yōu)解及相應的巡視路線.使用算法一時，在每個子圖所構(gòu)造的完備圖中，取一個盡量包含圖11-10中樹上的邊的H圈作為其第2步輸入的初始圈.分組二的近似解見表1. 表1（單位：公里）小組名稱路 線總路線長度路線的總長度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.

7、5IIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-C241.9IIIO-R-29-Q-30-32-31-33-35-34-A-B-1-O125.5因為該分組的均衡度=54.2%所以此分法的均衡性很差.為改善均衡性，將第組中的頂點C，2，3，D，4分給第組（頂點2為這兩組的公共點），重新分組后的近似最優(yōu)解見表2. 表2（單位：公里）編號路 線 路線 長度路線總長度IOP282726N2423221716I15I18K212025MO191.1599.8IIO2567E8E9F10F12H1413G11J19L652O216.4III

8、OR29Q303231333534A1BC3D4D32O192.3因該分組的均衡度11.69%所以這種分法的均衡性較好.問題二 當巡視人員在各鄉(xiāng)（鎮(zhèn)）、村的停留時間一定，汽車的行駛速度一定，要在24小時內(nèi)完成巡視，至少要分幾組及最佳的巡視路線.由于T=2小時，t=1小時，V=35公里/小時，需訪問的鄉(xiāng)鎮(zhèn)共有17個，村共有35個.計算出在鄉(xiāng)（鎮(zhèn)）及村的總停留時間為172+35=69小時，要在24小時內(nèi)完成巡回，若不考慮行走時間，有: (i為分的組數(shù)).得i最小為4，故至少要分4組. 由于該網(wǎng)絡的鄉(xiāng)（鎮(zhèn)）、村分布較為均勻，故有可能找出停留時間盡量均衡的分組，當分4組時各組停留時間大約為小時，則每組

9、分配在路途上的時間大約為24-17.25=6.75小時.而前面討論過，分三組時有個總路程599.8公里的巡視路線，分4組時的總路程不會比599.8公里大太多，不妨以599.8公里來計算.路上時間約為小時，若平均分配給4個組，每個組約需=4.25小時6.75小時，故分成4組是可能辦到的.現(xiàn)在嘗試將頂點分為4組.分組的原則：除遵從前面準則一、二、三外，還應遵從以下準則：準則四：盡量使各組的停留時間相等.用上述原則在圖11-10上將圖分為4組，同時計算各組的停留時間,然后用算法一算出各組的近似最佳推銷員巡回，得出路線長度及行走時間，從而得出完成巡視的近似最佳時間.用算法一計算時，初始圈的輸入與分三組時同樣處理.這4組的近似最優(yōu)解見表3. 表3（路程單位：公里；時間單位：小時）組名路 線路線總長度停留時間行走時間完成巡視的總時間IO2567E8E11G12H12F10F9E7652O 195.8175.5922.59IIOR29Q30Q282726N242322171617K2223N26PO199.2165.6921.69IIIOM252021K18I151413J19L6