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

数学建模基于Floyd算法的公园道路优化设计问题小组编号：02小组成员：队员1张聪-建模队员2汪涛-建模队员3胡娜-建模队员4薛向龙-建模队员5蔡诗聂-编程队员6杨志诚-编程 2023年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.1Kruskal算法描述： kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小花费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不也许形成一棵生成树。kruskal算法分e步，其中e是网络中边的数目。按花费递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。算法环节:（1）在公园的矩形区域内的12个点中,运用勾股定理算出任意两点所构成的各边的权值。（2）逐步比较各边的权值，依次选出构成权值最小的边的两个点构成连线，与此同时，运用边与边之间不能构成连线的条件，对权值尽也许小的边逐步筛选。（3）根据选出的边逐步构成连线，生成无圈的最小树。5.1.2Floyd算法描述：（1）从任意节点A到任意节点B的最短途径有2种也许，1是直接从A到B，2是从A通过若干个节点X到B。（2）假设Dis(AB)为节点A到节点B的最短途径的距离，对于每一个节点X，检查Dis(AX)+Dis(XB)<1.4*Dis(AB)是否成立。（3）假如成立，证明从A到X再到B的途径比A直接到B的途径短，便设立Dis(AB)=Dis(AX)+Dis(XB)，这样一来，当遍历完所有节点X，Dis(AB)中记录的便是A到B的最短途径的距离。基本环节：（1）运用kruskal算法得到的最短途径计算出两点间的通过途径的长度和两点间的径直线段长度；（2）判断两点间的径直线段长度是否满足不大于两点间的通过途径的长度1.4倍的关系；（3）若满足此条件则拟定为最小生成树；若不满足此条件则显示那条边不符合。5.1.3算法求解结果通过数据分析发现部分入口间最短途径不满足1.4倍的关系条件，如表1中突出显示数据（由于这是一个无向图，因此下三角数据不予列出）：表1：入口间最短途径（粗体表达不满足条件的入口）0301402302401551305501102002701851607509022029527018501302151402750851101950251100850（1）运用Kruskal算法生成最小生成树的matlab程序，我们通过程序运营结果可以得到图4的最短途径：图4、Kruskal算法生成的最小生成树途径（2）但是通过Floyd算法对所求得的最短途径经行1.4倍关系约束条件的检查时得到之间最短途径不满足1.4倍关系。由图4分析，运用穷举法对之间的所有途径进行计算，最后求得最优途径如图5所示。图5、Folyd筛选后运用穷举法得到的最优途径经计算，在满足题目1.4倍规定且使用A(50,75)，B(40,40)，C(120,40)，D(115,70）这4个点作为道路交叉点时，公园内道路总路程最短距离为393。5.2问题二的模型建立与求解由于问题二中在公园内可以任意修路，交叉点个数无限制，结合问题一的分析及求解结果知，两条道路必须修建，且在满足题目规定下使修路的总路程最短的基础上对交叉点的个数以及坐标位置进行优化。5.2.1一个交叉点的情况问题一中已经验证在无交叉点的前提下不能满足题目的规定，下面我们讨论一个交叉点的情况。在问题一的基础上根据两点之间线段最短原理将和直接连接，所得结果如图6所示：图6、无道路交叉点的优化图对图中路线进行1.4倍验证得到不满足题目规定，所以我们考虑到在点将、、三点所构成三角形中寻找一个局部最优点来满足的1.4倍关系。此处为了找到这个最优点，由于其它点间距离固定，只需考虑、、之间的距离关系，因此我们引入费马点定义。定义：在几何学中，费马点是位于三角形内的一点，给定一个三角形△ABC的话，从费马点P到三角形的三顶点A、B、C的距离之和比其它点都要小。假如三角形的内角所有小于120度则费马点存在，在、、所构成三角形（如图7）内部必存在费马点。图7、第一个道路交叉点的三角分割区域由于点在、、三点所构成三角形内部，且满足费马点定义。设交叉点坐标为，建立非线性优化模型：目的函数：约束条件：运用LINGO软件求出最优解（程序见附录4）一个交叉点的坐标为。计算得到局部最优途径，总的道路长道路设计图如图8所示图8、一个交叉点的道路分布5.2.2两个交叉点的情况一个交叉点我们在满足1.4倍的前提下求得了局部途径最短，但是忽略了、、三点之间的最优化问题。图9、第二个道路交叉点的三角分割区域考虑两个交叉点的情况，设第二个交叉点坐标为，由于点在、、三点所构成三角形内部，且满足费马点定义，由此建立非线性约束模型：目的函数：约束条件：运用LINGO软件求出最优解（程序见附录5）两个交叉点坐标分别为和。道路设计如图10所示图10、两个交叉点的道路分布计算得到局部最优途径,总的道路长。5.2.3三个交叉点的情况结合一个交叉点和两个交叉点的局部优化情况，由图。。。知在E、F、P5三点所构成三角形内部存在一个费马点，根据对区域的分割我们进行总的优化，建立如下非线性规划模型：目的函数：约束条件：运用LINGO软件求出最优解（程序见附录6）三个交叉点坐标分别为、、。道路设计图如图11所示图11、三个交叉点的道路分布计算得到全局最优途径。对于更多交叉点的情况，我们将两个交叉点和三个交叉点优化后的最短途径相比较得出三个交叉点的最短途径和两个交叉点的最短途径相差不大，以此推测出四个甚至更多交叉点的设立并不能大幅度的优化路线。考虑到增长交叉点对施工带来的麻烦，以及给交通带来不便利，所以于人性化角度设立3个交叉点比较合理。5.3问题三的模型建立与求解一方面，判断问题二最终所修道路是否不通过湖泊，运用MATLAB作出道路设计图（见附录9），如图12所示：图12判断问题二的方案是否满足新修道路不通过湖泊由图12知，在问题二的新修道路方案中G-F穿过了湖泊，从而G-F需重新设计。若借助湖边的道路来使G到达F，由假设若沿湖建路，则所修道路的长度要计入路程总长，故需四条直线才使G到达F，不符合两点之间直线最短，故考虑借助湖的顶点R4、R2来使G到达F，同时G、F的位置也需调整。有两种情况，G-R4-F，G-R2-F，现分别考虑这两种情况。5.对于图12，当调整连接G-R4-F时，我们考虑到在到到R4之间，有费马点定义可知既为费马点，所以我们将点移动到，所得道路如图13所示。图13以R4为交叉点的改善图对调整后的路线用非线性规划进行优化，优化模型如下：目的函数：约束条件：运用LINGO（程序见附录7）可求出交叉点经验证，所连之后的任意两入口之间的最短道路长全满足不大于两连线点之间的1.4倍。最短路长为。道路设计图如图14所示。图14以R4为交叉点的改善图5.对于以R2为交叉点的途径，我们对点和点继续用费马点来进行优化，建立非线性规划模型：目的函数：约束条件：运用LINGO程序（见附录8）可计算出调整后的交叉点G和交叉点F。经验证，所连之后的任意两入口之间的最短道路长全满足不大于两连线点之间的1.4倍。最短路长为360.5394。道路设计图如图15所示图15以R2为交叉点的改善图在图15中，不存在三角形可继续优化，在此方案下，最短路程长为360.5394。通过比较最短路程长，最终选择图35作为最后方案，四个交叉点分别为,,,，总路程长为。道路设计图如图15所示。六、模型的评价及推广6.1模型优点(1)对于问题一，在建立模型求解之前，一方面运用边沿道路不计入修建道路总长的题目规定和最短道路长不大于两点连线1.4倍前提规定，将那些无需借助交叉点即可满足1.4倍前提规定的点从考虑范围内剔除，将8个点之间的两两互连问题简化为十组点之间的连通问题，大大简化了题目。(2)对于问题二，从交叉点的个数出发，分情况进行讨论求解，既考虑多种情况，又减少了解题难度。（3）对于问题三，引入费马点大大减少了计算的繁杂性。6.2模型缺陷（1）问题二中采用局部最优解逼近全局最优解，存在误差。（2）问题二及问题三没有计算更多交叉点的情况。6.3模型推广最短途径问题是现实生活中常见问题，本题的实际情景为公园内部建设道路。模型还可以推广到求解运送路线选择问题，商业利润估算问题和生产生活各个方面，所以该模型的建立具有重要意义。七、参考文献龚纯，王正林.精通matlab最优化计算.北京：电子工业出版社，2023.1司守奎，孙玺菁.数学建模算法与应用.北京：国防工业出版社，2023.8姜启源，谢金星，叶俊.数学模型[M].北京：高等教育出版社，2023.8维基百科费马点薛金星，薛毅.优化建模与LINDO/LINGO软件.北京：清华大学出版社，2023.7赵继俊,Lingo优化技术与Matlab优化工具箱[M].机械工业出版社，2023,201-212.八、附录附录1：各点之间的距离030140186.82141.42101.12100.5032.02300110158.11122.07101.12107.7055.90140110064.03107.70160.08180.28161.94186.82158.1164.03094.34172.41196.47201.56141.42122.07107.7094.34085110141.51101.12101.12160.08172.418502582.76100.50107.70180.28196.4711025075.6632.0255.90161.94201.56141.5182.760附录2：问题一Kruskal算法程序functionE=Kruskal(w)%图论最小生成树Kruskal避圈算法%w为连接权矩阵[m,n]=size(w);%m为w行数，n为w列数k=1;fori=1:n-1forj=i+1:n%为了提高效率ifw(i,j)~=0x(1,k)=w(i,j);%记录不为0的边长x(2,k)=i;%不为0的行数x(3,k)=j;%不为0的列数k=k+1;endendend%构造x为不为0的元素的信息，涉及边长，所在列数，行数k=k-1;%记录不为0的边数%环节一%冒泡法完毕边的从小到大排序fori=1:kforj=i+1:kifx(1,i)>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%给各点标号赋初值fori=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中边数fori=2:kifb==n-1%假如树中边数达成n-1break%算法终止endifl(x(2,i))~=l(x(3,i))%假如两顶点标号不同b=b+1;%将这条边加入EE(1,b)=x(1,i);E(2,b)=x(2,i);E(3,b)=x(3,i);forj=1:n%对于所有顶点ifl(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))*n^2;%M为充足大的正实数a=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifa(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((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<=1.4*50.55937*2;20*x9+3*y9-1000>=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)<=1.4*32.01562*2;20*x9+3*y9-1000>=0;-10*x9+7*y9+500>=0;5*x10-4*y10-800<=0;5*x10+2*y10-800>=0;5*x10+8*y10-1400<=0;y9>=0;y9<=100;y10>=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)<=1.4*53.85165*2;20*x9+3*y9-1000>=0;-10*x9+7*y9+500>=0;5*x10-4*y10-800<=0;5*x10+2*y10-800>=0;5*x10+8*y10-1400<=0;y9>=0;y9<=100;y10>=0;y10<=100;x11>=0;x11<=200;y11>=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)+@sqr