基于Floyd算法的道路優(yōu)化設計問題

1、-. z.- - - z -數(shù)學建?；贔loyd算法的公園道路優(yōu)化設計問題 小組編號： 02 小組成員：隊員1 聰-建模隊員2 汪 濤-建模隊員3胡 娜-建模隊員4 薛向龍-建模 隊員5蔡詩聶-編程 隊員6 志誠-編程 2012年 7月 21日 基于Floyd算法的公園道路優(yōu)化設計問題摘要本文主要研究了以公園部道路修建為背景的路徑優(yōu)化問題。對于問題一，四個穿插點的情況下，考慮到邊緣道路不計入修建道路總長的題目要求和最短道路長不大于兩點連線1.4倍前提要求，首選邊緣路徑，將那些無需借助穿插點即可滿足1.4倍前提要求的點從考慮圍剔除。然后對剩余不滿足條件的路徑運用Kruskal算法，生成最小生成

2、樹的路徑，再在此根底上，利用Floyd算法，找出其中不符合1.4倍約束的路徑的邊，綜合對其路徑進展調(diào)整并將滿足條件的所有路徑的邊用窮舉法進展篩選，最終選取最優(yōu)路徑，其總路程為393。對于問題二，我們在第一問結(jié)果上進展改良，運用兩點之間線段最短原理將第一問最短路徑進展優(yōu)化，然后引入費馬點定義，通過數(shù)理計算分析，劃分三角形區(qū)域，建立非線性規(guī)劃模型進展局部優(yōu)化。遞增穿插點的個數(shù)，并在前一個穿插點的最優(yōu)路徑的根底上對后一個穿插點的取點圍進展考量，用lingo對不同數(shù)目穿插點的情況下的最短路徑目標函數(shù)進展規(guī)劃，并以1.4倍的數(shù)學關系作為約束條件，進展局部最優(yōu)解逼近全局最優(yōu)解，最終確定最優(yōu)穿插點個數(shù)為3個

3、，坐標分別為、，計算出最短路徑。對于問題三，我們在比照道路穿過湖的情況下，考慮到湖邊的修路計算到總路程的情況，分析得到在以湖的頂點R2、R4為道路穿插點時比以湖邊其他點作為穿插點時的路徑要短，所以分別以湖的頂點R2、R4為道路穿插點時進展討論，在問題二的最短路徑的根底上建立非線性規(guī)劃模型，然后利用費馬點逐步進展優(yōu)化，比擬兩種不同穿插點的優(yōu)化模型情況，最終確定出最優(yōu)方案下的四個穿插點的坐標分別,，計算出該情況下最優(yōu)路程長為。關于模型的優(yōu)化，對于問題二，我們考慮到可以通過蒙特卡洛的方法對公園矩形區(qū)域圍進展撒點，并借用橢圓法來約束1.4倍的條件關系，此方法可以求出選擇不同數(shù)目穿插點時的最優(yōu)路徑，結(jié)果

4、更準確，但是計算量大、程序運行緩慢。關鍵詞： Kruskal算法 Floyd算法局部優(yōu)化 費馬點 非線性規(guī)劃 一、問題重述為了美化校園環(huán)境，同時為學生提供更好的生活條件，*大學方案建一個形狀為矩形或其他不規(guī)則圖形的公園。該公園方案有假設干個入口，讓任意兩個入口相連且任意的兩個入口之間的最短道路長不大于兩點連線的1.4倍。路線的選擇可以利用公園四周的邊，即默認矩形的四條邊上存在已經(jīng)建好的道路，此道路不計入道路總長。矩形公園相關數(shù)據(jù)為：長200米，寬100米，1至8各入口的坐標分別為：P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,

5、100),P7(10,100),P8(0,25)。圖1 公園及入口示意圖我們的任務就是結(jié)合該公園已有的方案，對其進展合理的道路安排，建立相應的數(shù)學模型，解決以下問題：1、在公園假定要使用A(50,75)，B(40,40)，C(120,40)，D(115,70這4個點作為道路穿插點時，如何設計出新的道路在滿足1.4倍要求的前提下使公園道路總路程最短。2、在公園可以任意修建道路的情況下，如何確定穿插點的個數(shù)及坐標設計道路使其在滿足1.4倍條件下使總路程最少。3、在公園有一條矩形的湖的，新修的道路不能通過，但可以到達湖四周的邊的前提下，如何設計穿插點的個數(shù)及坐標設計道路使其在滿足1.4倍條件下使總路

6、程最少。注：以上問題中都要求公園新修的道路與四周的連接只能與8個路口相通，而不能連到四周的其它點。圖2 有湖的示意圖二、問題分析此題是一個道路設計的最優(yōu)化的問題，即是如何設計路徑使公園部新修路總長最小，但要滿足以下兩個控制條件：1、任意兩個入口連通；2、任意兩個入口的最短路徑不超過其直線距離的1.4倍。對于問題一，題中已給出A(50,75)，B(40,40)，C(120,40)，D(115,70這4個點作為道路穿插點，由于題設中說明公園四周存在修好的道路且允許通行，所以我們先利用四周道路，找出，這些沿邊道路不能滿足1.4倍關系的路徑。然后對剩余不滿足第2個控制條件的路徑運用Kruskal算法，

7、生成最小生成樹，再在此根底上，利用Floyd算法，找出其中不符合條件2的路徑用窮舉法進展優(yōu)化。對于問題二，我們在第一問結(jié)果上進展改良，考慮到兩點之間線段最短原理我們將與、與直接相連。引入費馬點定義，通過分析劃分三角形區(qū)域，建立非線性規(guī)劃模型進展局部優(yōu)化。假設公園有m個穿插點，從m=0開場，我們繼續(xù)討論m=1、m=2和m=3這三種情況，進展局部最優(yōu)解逼近全局最優(yōu)解，最終確定穿插點數(shù)及坐標并求解出最短路徑。對于問題三，首先考慮問題二中設計的道路是否不通過矩形湖，假設不通過，則問題二的結(jié)果即為問題三的結(jié)果；否則，對問題二方案中穿過湖的道路進展調(diào)整將其調(diào)整為穿過湖的頂點。利用費馬點到三個頂點的距離最短

8、，建立出相應的非線性規(guī)劃模型，求出相應的穿插點，然后再利用費馬點來進展優(yōu)化，直到不能再優(yōu)化為止，最終可得到最優(yōu)方案。三、模型假設1、假設所有點間道路均修建為直線，且都在同一水平面；2、假設入口形狀與路寬忽略不計，即將入口抽象為點，道路抽象為線；3、假設穿插點位置的選取不受地理位置的限制，且穿插點的修建不會影響道路的總長4、假設湖的四周沒有修建好的道路，假設要沿湖則同樣需修建道路并計入道路總長。四、符號說明符號說明點的坐標點、間的距離點與點間的距離、道路穿插點最優(yōu)路線長度道路穿插點的個數(shù)五、模型的建立與求解5.1問題一的模型建立與求解由題所給出的條件可以看出，這與最短路問題聯(lián)系密切，于是考慮用K

9、ruskal算法和Floyd算法來建立問題的模型。圖3、模型一流程圖Kruskal算法描述：kruskal算法每次選擇n- 1條邊，所使用的貪婪準則是：從剩下的邊中選擇一條不會產(chǎn)生環(huán)路的具有最小消耗的邊參加已選擇的邊的集合中。注意到所選取的邊假設產(chǎn)生環(huán)路則不可能形成一棵生成樹。kruskal算法分e 步，其中e 是網(wǎng)絡中邊的數(shù)目。按消耗遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮*條邊時，假設將其參加到已選邊的集合中會出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。算法步驟:1在公園的矩形區(qū)域的12個點中, 利用勾股定理算出任意兩點所構成的各邊的權值。2逐步比擬各邊的權值，依次選出構成權值最小的邊

10、的兩個點構成連線，與此同時，利用邊與邊之間不能構成連線的條件，對權值盡可能小的邊逐步篩選。3根據(jù)選出的邊逐步構成連線，生成無圈的最小樹。 Floyd算法描述：1從任意節(jié)點A到任意節(jié)點B的最短路徑有2種可能，1是直接從A到B，2是從A經(jīng)過假設干個節(jié)點*到B。2假設Dis(AB)為節(jié)點A到節(jié)點B的最短路徑的距離，對于每一個節(jié)點*，檢查Dis(A*) + Dis(*B) *(1,j) a=*(1,i);*(1,i)=*(1,j);*(1,j)=a; a=*(2,i);*(2,i)=*(2,j);*(2,j)=a; a=*(3,i);*(3,i)=*(3,j);*(3,j)=a; endendend%

11、給各點標號賦初值for i=1:nl(i)=i;end%初始時選e1參加集合EE(1,1)=*(1,1); %E矩陣的第一行記錄最小生成樹的邊長E(2,1)=*(2,1); %E矩陣的第二行記錄邊的起點E(3,1)=*(3,1); %E矩陣的第三行記錄邊的終點a=min(l(E(2,1),l(E(3,1);l(E(2,1)=a;l(E(3,1)=a;b=1;%記錄E中邊數(shù)for i=2:k if b=n-1 %如果樹中邊數(shù)到達n-1 break %算法終止 endif l(*(2,i)=l(*(3,i) %如果兩頂點標號不同 b=b+1; %將這條邊參加E E(1,b)=*(1,i); E(2

12、,b)=*(2,i); E(3,b)=*(3,i);for j=1:n %對于所有頂點 if l(j)=ma*(l(E(2,b),l(E(3,b)%如果該頂點的標號,等于=,新參加邊中的頂點標號較大的值 l(j)=min(l(E(2,b),l(E(3,b);%將其改為較小的那一個以避圈 endendendend附錄3：問題一中Floyd算法程序：clc; n=12; a=zeros(n); a(1,2)=30;a(1,8)=32;a(1,2)=30;a(1,3)=140;a(2,10)=41;a(2,3)=100;a(3,4)=64;a(3,11)=57;a(5,6)=85;a(5,12)=3

13、0;a(6,7)=25;a(6,9)=29;a(9,10)=36;a(9,12)=65;a(11,12)=30;a(1,4)=230;a(1,5)=240;a(1,6)=155;a(1,7)=130;a(2,4)=200;a(2,5)=270;a(2,6)=185;a(2,7)=160;a(2,8)=70;a(3,5)=120;a(3,6)=295;a(3,7)=270;a(3,8)=180;a(4,5)=130;a(4,6)=215;a(4,7)=240;a(4,8)=270;a(5,8)=200;a(6,8)=115;a(7,8)=90;a=a+a; M=ma*(ma*(a)*n2; %M

14、為充分大的正實數(shù) a=a+(a=0)-eye(n)*M; path=zeros(n); for k=1:n for i=1:n for j=1:n if a(i,j)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; endendendenda, path 附錄4:問題二中1個穿插點情況時的lingo程序:min=sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+sqrt(*9-120)2+(y9-100)2)+16.0078*2+53.85165*2+32.01562*2;sqrt(*9-50)2+(y9)2

15、)+sqrt(*9-35)2+(y9-100)2)=1.4*50.55937*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)=1.4*61.03278*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+25=1.4*53.85165*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)+30=1.4*70.71068*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+30=0;-10*9+7*y9+500=0;y9=0;y9=

16、100;附錄5:問題二中2個穿插點情況時的lingo程序:min=sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+sqrt(*9-120)2+(y9-100)2)+sqrt(*10-160)2+(y10)2)+sqrt(*10-200)2+(y10-50)2)+sqrt(*10-120)2+(y10-100)2)+16.0078*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)=1.4*50.55937*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)=1.4*61.0

17、3278*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+25=1.4*53.85165*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)+30=1.4*70.71068*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+30=1.4*50.55937*2;sqrt(*10-160)2+(y10)2)+sqrt(*10-120)2+(y10-100)2)=1.4*53.85165*2;sqrt(*10-160)2+(y10)2)+sqrt(*10-200)2+(y1

18、0-50)2)=0;-10*9+7*y9+500=0;5*10-4*y10-800=0;5*10+8*y10-1400=0;y9=0;y10=100;附錄6:問題二中3個穿插點情況時的lingo程序:min=sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+sqrt(*10-160)2+(y10)2)+sqrt(*10-200)2+(y10-50)2)+sqrt(*11-*9)2+(y11-y9)2)+sqrt(*11-120)2+(y11-100)2)+sqrt(*11-*10)2+(y11-y10)2)+16.0078*2;sqrt(*9-50)2+(

19、y9)2)+sqrt(*9-35)2+(y9-100)2)=1.4*50.55937*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)=1.4*61.03278*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+25=1.4*53.85165*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)+30=1.4*70.71068*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+30=1.4*50.55937*2;sqrt(*10

20、-160)2+(y10)2)+sqrt(*10-120)2+(y10-100)2)=1.4*53.85165*2;sqrt(*10-160)2+(y10)2)+sqrt(*10-200)2+(y10-50)2)=1.4*32.01562*2;sqrt(*9-50)2+(y9)2)+sqrt(*11-*9)2+(y11-y9)2)+sqrt(*11-120)2+(y11-100)2)=1.4*61.03278*2;sqrt(160-*10)2+(0-y10)2)+sqrt(*10-*9)2+(y10-y9)2)+sqrt(35-*9)2+(100-y9)2)=1.4*80.03905*2;30+

21、sqrt(*9-50)2+(y9)2)+sqrt(*11-*9)2+(y11-y9)2)+sqrt(*11-120)2+(y11-100)2)=1.4*70.71068*2;sqrt(*10-160)2+(y10)2)+sqrt(*11-*10)2+(y11-y10)2)+sqrt(*11-120)2+(y11-100)2)+110=1.4*90.13878*2;sqrt(*10-160)2+(y10)2)+sqrt(*11-*10)2+(y11-y10)2)+sqrt(*11-120)2+(y11-100)2)=0;-10*9+7*y9+500=0;5*10-4*y10-800=0;5*10

22、+8*y10-1400=0;y9=0;y10=0;*11=0;y11=100;附錄7:問題三對過R4路徑的求解程序:min=sqrt(*12-165)2+(y12-70)2)+sqrt(*12-160)2+(y12-0)2)+sqrt(*12-200)2+(y12-50)2);sqrt(*12-160)2+(y12)2)+sqrt(*12-165)2+(y12-70)2)+sqrt(120-165)2+(100-70)2)=1.4*107.7033;sqrt(*12-160)2+(y12)2)+sqrt(*12-165)2+(y12-70)2)+sqrt(120-165)2+(100-70)2

23、)+85=1.4*160.07981;sqrt(*12-160)2+(y12)2)+sqrt(*12-165)2+(y12-70)2)+sqrt(120-165)2+(100-70)2)+110=1.4*180.2776;sqrt(*12-160)2+(y12)2)+sqrt(*12-200)2+(y12-50)2)=0;*12=0;y12=100; 附錄8:問題三對過R2路徑的求解程序:min=sqrt(*12-160)2+(y12)2)+sqrt(*12-200)2+(y12-50)2)+sqrt(*12-140)2+(y12-45)2)+sqrt(*13-61.69650)2+(y13-71.75212)2)+sqrt(*13-120)2+(y13-100)2)+sqrt(*13-140)2+(y13-45