全國(guó)賽題最佳災(zāi)情巡視路線

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

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

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

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

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

6、相鄰的干枝上的點(diǎn)分在同一組；準(zhǔn)則三：盡量將長(zhǎng)的干枝與短的干枝分在同一組.由上述分組準(zhǔn)則，我們找到兩種分組形式如下：分組一：（，），（，），（，）分組二：（，），（，），（，）顯然分組一的方法極不均衡，故考慮分組二.對(duì)分組二中每組頂點(diǎn)的生成子圖，用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線.使用算法一時(shí)，在每個(gè)子圖所構(gòu)造的完備圖中，取一個(gè)盡量包含圖11-10中樹(shù)上的邊的H圈作為其第2步輸入的初始圈.分組二的近似解見(jiàn)表1. 表1（單位：公里）小組名稱路 線總路線長(zhǎng)度路線的總長(zhǎng)度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因?yàn)樵摲纸M的均衡度=54.2%所以此分法的均衡性很差.為改善均衡性，將第組中的頂點(diǎn)C，2，3，D，4分給第組（頂點(diǎn)2為這兩組的公共點(diǎn)），重新分組后的近似最優(yōu)解見(jiàn)表2. 表2（單位：公里）編號(hào)路 線 路線 長(zhǎng)度路線總長(zhǎng)度IOP282726N2423221716I15I18K212025MO191.1599.8IIO2567E8E9F10F12H1413G11J19L652O216.4III

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

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