基于Floyd算法的道路优化设计问题

-数学建模基于Floyd算法的公园道路优化设计问题 小组编号： 02 小组成员：队员1 聪-建模队员2 汪 涛-建模队员3胡 娜-建模队员4 薛向龙-建模 队员5蔡诗聂-编程 队员6 志诚-编程 2012年 7月 21日 基于Floyd算法的公园道路优化设计问题摘要本文主要研究了以公园部道路修建为背景的路径优化问题。对于问题一，四个穿插点的情况下，考虑到边缘道路不计入修建道路总长的题目要求和最短道路长不大于两点连线1.4倍前提要求，首选边缘路径，将那些无需借助穿插点即可满足1.4倍前提要求的点从考虑围剔除。然后对剩余不满足条件的路径运用Kruskal算法，生成最小生成树的路径，再在此根底上，利用Floyd算法，找出其中不符合1.4倍约束的路径的边，综合对其路径进展调整并将满足条件的所有路径的边用穷举法进展筛选，最终选取最优路径，其总路程为393。对于问题二，我们在第一问结果上进展改良，运用两点之间线段最短原理将第一问最短路径进展优化，然后引入费马点定义，通过数理计算分析，划分三角形区域，建立非线性规划模型进展局部优化。递增穿插点的个数，并在前一个穿插点的最优路径的根底上对后一个穿插点的取点围进展考量，用lingo对不同数目穿插点的情况下的最短路径目标函数进展规划，并以1.4倍的数学关系作为约束条件，进展局部最优解逼近全局最优解，最终确定最优穿插点个数为3个，坐标分别为、，计算出最短路径。对于问题三，我们在比照道路穿过湖的情况下，考虑到湖边的修路计算到总路程的情况，分析得到在以湖的顶点R2、R4为道路穿插点时比以湖边其他点作为穿插点时的路径要短，所以分别以湖的顶点R2、R4为道路穿插点时进展讨论，在问题二的最短路径的根底上建立非线性规划模型，然后利用费马点逐步进展优化，比拟两种不同穿插点的优化模型情况，最终确定出最优方案下的四个穿插点的坐标分别,，计算出该情况下最优路程长为。关于模型的优化，对于问题二，我们考虑到可以通过蒙特卡洛的方法对公园矩形区域围进展撒点，并借用椭圆法来约束1.4倍的条件关系，此方法可以求出选择不同数目穿插点时的最优路径，结果更准确，但是计算量大、程序运行缓慢。关键词： Kruskal算法 Floyd算法局部优化 费马点 非线性规划 一、问题重述为了美化校园环境，同时为学生提供更好的生活条件，*大学方案建一个形状为矩形或其他不规则图形的公园。该公园方案有假设干个入口，让任意两个入口相连且任意的两个入口之间的最短道路长不大于两点连线的1.4倍。路线的选择可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长。矩形公园相关数据为：长200米，宽100米，1至8各入口的坐标分别为：P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),P8(0,25)。图1 公园及入口示意图我们的任务就是结合该公园已有的方案，对其进展合理的道路安排，建立相应的数学模型，解决以下问题：1、在公园假定要使用A(50,75)，B(40,40)，C(120,40)，D(115,70这4个点作为道路穿插点时，如何设计出新的道路在满足1.4倍要求的前提下使公园道路总路程最短。2、在公园可以任意修建道路的情况下，如何确定穿插点的个数及坐标设计道路使其在满足1.4倍条件下使总路程最少。3、在公园有一条矩形的湖的，新修的道路不能通过，但可以到达湖四周的边的前提下，如何设计穿插点的个数及坐标设计道路使其在满足1.4倍条件下使总路程最少。注：以上问题中都要求公园新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。图2 有湖的示意图二、问题分析此题是一个道路设计的最优化的问题，即是如何设计路径使公园部新修路总长最小，但要满足以下两个控制条件：1、任意两个入口连通；2、任意两个入口的最短路径不超过其直线距离的1.4倍。对于问题一，题中已给出A(50,75)，B(40,40)，C(120,40)，D(115,70这4个点作为道路穿插点，由于题设中说明公园四周存在修好的道路且允许通行，所以我们先利用四周道路，找出，这些沿边道路不能满足1.4倍关系的路径。然后对剩余不满足第2个控制条件的路径运用Kruskal算法，生成最小生成树，再在此根底上，利用Floyd算法，找出其中不符合条件2的路径用穷举法进展优化。对于问题二，我们在第一问结果上进展改良，考虑到两点之间线段最短原理我们将与、与直接相连。引入费马点定义，通过分析划分三角形区域，建立非线性规划模型进展局部优化。假设公园有m个穿插点，从m=0开场，我们继续讨论m=1、m=2和m=3这三种情况，进展局部最优解逼近全局最优解，最终确定穿插点数及坐标并求解出最短路径。对于问题三，首先考虑问题二中设计的道路是否不通过矩形湖，假设不通过，则问题二的结果即为问题三的结果；否则，对问题二方案中穿过湖的道路进展调整将其调整为穿过湖的顶点。利用费马点到三个顶点的距离最短，建立出相应的非线性规划模型，求出相应的穿插点，然后再利用费马点来进展优化，直到不能再优化为止，最终可得到最优方案。三、模型假设1、假设所有点间道路均修建为直线，且都在同一水平面；2、假设入口形状与路宽忽略不计，即将入口抽象为点，道路抽象为线；3、假设穿插点位置的选取不受地理位置的限制，且穿插点的修建不会影响道路的总长4、假设湖的四周没有修建好的道路，假设要沿湖则同样需修建道路并计入道路总长。四、符号说明符号说明点的坐标点、间的距离点与点间的距离、道路穿插点最优路线长度道路穿插点的个数五、模型的建立与求解5.1问题一的模型建立与求解由题所给出的条件可以看出，这与最短路问题联系密切，于是考虑用Kruskal算法和Floyd算法来建立问题的模型。图3、模型一流程图Kruskal算法描述：kruskal算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小消耗的边参加已选择的边的集合中。注意到所选取的边假设产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按消耗递增的顺序来考虑这e 条边，每次考虑一条边。当考虑*条边时，假设将其参加到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。算法步骤:1在公园的矩形区域的12个点中, 利用勾股定理算出任意两点所构成的各边的权值。2逐步比拟各边的权值，依次选出构成权值最小的边的两个点构成连线，与此同时，利用边与边之间不能构成连线的条件，对权值尽可能小的边逐步筛选。3根据选出的边逐步构成连线，生成无圈的最小树。 Floyd算法描述：1从任意节点A到任意节点B的最短路径有2种可能，1是直接从A到B，2是从A经过假设干个节点*到B。2假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点*，检查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%给各点标号赋初值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中边数for i=2:k if b=n-1 %如果树中边数到达n-1 break %算法终止 endif l(*(2,i)=l(*(3,i) %如果两顶点标号不同 b=b+1; %将这条边参加E E(1,b)=*(1,i); E(2,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)=30;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为充分大的正实数 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)+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=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.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-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)=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+(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-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+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+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)+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)2)+143.582;sqrt(*13-61.69650)2+(y13-71.75212)2)+sqrt(*13-120)2+(y13-100)2)+72.699=1.4*122.0656;sqrt(*13-61.69650)2+(y13-71.75212)2)+sqrt(*13-120)2+(y13-100)2)+102.699=1.4*141.4214;sqrt(*12-160)2+(y12)2)+sqrt(*12-140)2+(y12-45)2)+sqrt(*13-120)2+(y13-100)2)+sqrt(*13-140)2+(y13-45)2)=1.4*107.7033;sqrt(*12-160)2+(y12)2)+sqrt(*12-140)2+(y12-45)2)+sqrt(*13-120)2+(y13-100)2)+sqrt(*13-140)2+(y13-45)2)+85=1.4*160.0781;sqrt(*12-160)2+(y12)2)+sqrt(*12-140)2+(y12-45)2)+sqrt(*13-120)2+(y13-100)2)+sqrt(*13-140)2+(y13-45)2)+110=0;*12=0;y12=0;*13=0;y13=100;附录9：MATLAB绘制道路设计图程序*=50 40 120 115 20 50 160 200 120 35 10 0;y=75 40 40 70 0 0 0 50 100 100 100 25;t=ABCD12345678;a*is(0,200,0,100);p=polyfit(*,y,1);plot(*,y,*)hold on;bo* on;for i=1:1:12gte*t(t(i);end注：道路连线用MATLAB的Figure窗口编辑. z.