基于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、模型一流程图5.1.1 Kruskal算法描述：kruskal算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。算法步骤:（1）在公园的矩形区域内的12个点中, 利用勾股定理算出任意两点所构成的各边的权值。（2）逐步比较各边的权值，依次选出构成权值最小的边的两个点构成连线，与此同时，利用边与边之间不能构成连线的条件，对权值尽可能小的边逐步筛选。（3）根据选出的边逐步构成连线，生成无圈的最小树。5.1.2 Floyd算法描述：（1）从任意节点A到任意节点B的最短路径有2种可能，1是直接从A到B，2是从A经过若干个节点X到B。（2）假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，检查Dis(AX) + Dis(XB) x(1,j) a=x(1,i);x(1,i)=x(1,j);x(1,j)=a; a=x(2,i);x(2,i)=x(2,j);x(2,j)=a; a=x(3,i);x(3,i)=x(3,j);x(3,j)=a; endendend%给各点标号赋初值for i=1:nl(i)=i;end%初始时选e1加入集合EE(1,1)=x(1,1); %E矩阵的第一行记录最小生成树的边长E(2,1)=x(2,1); %E矩阵的第二行记录边的起点E(3,1)=x(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(x(2,i)=l(x(3,i) %如果两顶点标号不同 b=b+1; %将这条边加入E E(1,b)=x(1,i); E(2,b)=x(2,i); E(3,b)=x(3,i);for j=1:n %对于所有顶点 if l(j)=max(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=max(max(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; end end end end a, path 附录4:问题二中1个交叉点情况时的lingo程序:min=sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)+sqrt(x9-120)2+(y9-100)2)+16.0078*2+53.85165*2+32.01562*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)=1.4*50.55937*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-120)2+(y9-100)2)=1.4*61.03278*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)+25=1.4*53.85165*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-120)2+(y9-100)2)+30=1.4*70.71068*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)+30=0;-10*x9+7*y9+500=0;y9=0;y9=100;附录5:问题二中2个交叉点情况时的lingo程序:min=sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)+sqrt(x9-120)2+(y9-100)2)+sqrt(x10-160)2+(y10)2)+sqrt(x10-200)2+(y10-50)2)+sqrt(x10-120)2+(y10-100)2)+16.0078*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)=1.4*50.55937*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-120)2+(y9-100)2)=1.4*61.03278*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)+25=1.4*53.85165*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-120)2+(y9-100)2)+30=1.4*70.71068*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)+30=1.4*50.55937*2;sqrt(x10-160)2+(y10)2)+sqrt(x10-120)2+(y10-100)2)=1.4*53.85165*2;sqrt(x10-160)2+(y10)2)+sqrt(x10-200)2+(y10-50)2)=0;-10*x9+7*y9+500=0;5*x10-4*y10-800=0;5*x10+8*y10-1400=0;y9=0;y10=100;附录6:问题二中3个交叉点情况时的lingo程序:min=sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)+sqrt(x10-160)2+(y10)2)+sqrt(x10-200)2+(y10-50)2)+sqrt(x11-x9)2+(y11-y9)2)+sqrt(x11-120)2+(y11-100)2)+sqrt(x11-x10)2+(y11-y10)2)+16.0078*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)=1.4*50.55937*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-120)2+(y9-100)2)=1.4*61.03278*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)+25=1.4*53.85165*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-120)2+(y9-100)2)+30=1.4*70.71068*2;sqrt(x9-50)2+(y9)2)+sqrt(x9-35)2+(y9-100)2)+30=1.4*50.55937*2;sqrt(x10-160)2+(y10)2)+sqrt(x10-120)2+(y10-100)2)=1.4*53.85165*2;sqrt(x10-160)2+(y10)2)+sqrt(x10-200)2+(y10-50)2)=1.4*32.01562*2;sqrt(x9-50)2+(y9)2)+sqrt(x11-x9)2+(y11-y9)2)+sqrt(x11-120)2+(y11-100)2)=1.4*61.03278*2;sqrt(160-x10)2+(0-y10)2)+sqrt(x10-x9)2+(y10-y9)2)+sqrt(35-x9)2+(100-y9)2)=1.4*80.03905*2;30+sqrt(x9-50)2+(y9)2)+sqrt(x11-x9)2+(y11-y9)2)+sqrt(x11-120)2+(y11-100)2)=1.4*70.71068*2;sqrt(x10-160)2+(y10)2)+sqrt(x11-x10)2+(y11-y10)2)+sqrt(x11-120)2+(y11-100)2)+110=1.4*90.13878*2;sqrt(x10-160)2+(y10)2)+sqrt(x11-x10)2+(y11-y10)2)+sqrt(x11-120)2+(y11-100)2)=0;-10*x9+7*y9+500=0;5*x10-4*y10-800=0;5*x10+8*y10-1400=0;y9=0;y10=0;x11=0;y11=100;附录7:问题三对过R4路径的求解程序:min=sqrt(x12-165)2+(y12-70)2)+sqrt(x12-160)2+(y12-0)2)+sqrt(x12-200)2+(y12-50)2);sqrt(x12-160)2+(y12)2)+sqrt(x12-165)2+(y12-70)2)+sqrt(120-165)2+(100-70)2)=1.4*107.7033;sqrt(x12-160)2+(y12)2)+sqrt(x12-165)2+(y12-70)2)+sqrt(120-165)2+(100-70)2)+85=1.4*160.07981;sqrt(x12-160)2+(y12)2)+sqrt(x12-165)2+(y12-70)2)+sqrt(120-165)2+(100-70)2)+110=1.4*180.2776;sqrt(x12-160)2+(y12)2)+sqrt(x12-200)2+(y12-50)2)=0;x12=0;y12=100; 附录8:问题三对过R2路径的求解程序:min=sqrt(x12-160)2+(y12)2)+sqrt(x12-200)2+(y12-50)2)+sqrt(x12-140)2+(y12-45)2)+sqrt(x13-61.69650)2+(y13-71.75212)2)+sqrt(x13-120)2+(y13-100)2)+sqrt(x13-140)2+(y13-45)