公园道路规划问题

-.z.A题公园道路最优设计问题一、摘要本文讨论的是公园道路最优设计问题。在满足任意两入口之间最短道路长不大于两点连线的1.4倍的条件下，建立相应最短道路模型，使得修建总道路长度最短。又因公园边界已经存在修建好的道路，所以应尽量利用边界道路。针对问题一，12个入口和穿插点构成稀疏的网，依据Kruskal算法，构造最小生成树，在满足要求的情况下，得到最优道路设计方案〔图〕，使得公园新修路的总路程最小为364.1458米。针对问题二，先简化约束条件，分步增加穿插点个数，再采用逐步逼近的思想，求得满足条件的最短道路设计。运用迭代法结合C语言编程，得出较优道路设计方案〔图〕，使得公园新修路的总路程最小为358.529730米。针对问题三，假设湖四周已经有道路，尽量利用湖四周道路，在第二问的根底上，进展局部优化，分析道路与湖的穿插点，用迭代法逐步逼近，得到较优道路设计方案〔图〕，使得公园新修路的总路程最小为318.727931米。关键词：Kruskal算法局部优化逐步逼近非线性规划迭代算法二、问题的提出一矩形公园有假设干入口，公园四周的边存在已经建好的道路且道路长度不计入道路总长。现为满足公园任意两个入口相连，且任意的两个入口之间的最短道路长不大于两点连线的1.4倍，求使总道路长度和最小的最短道路，给出道路设计。现需要解决如下三个问题：1.假设公园内确定四个道路穿插点：A〔50，75〕，B〔40，40〕，C〔120，40〕，D〔115，70〕，建立模型给出算法，在满足条件下，确定使得公园内道路总路程最短的设计，计算总路程。2.假设公园内可任意修建道路，建立模型给出算法，在满足条件下，确定道路穿插点坐标，从而获得公园内道路总路程最短的设计，计算总路程。3.假设公园内有一矩形湖，新修的道路不能通过，但可以到达湖四周的边。在满足条件下，确定道路穿插点坐标，从而获得公园内道路总路程最短的设计，计算总路程。三、问题的分析针对问题一，给定四个确定道路穿插点，为使得设计的公园道路总路程最短。联系数据构造中的最小生成树问题——最小生成树是各边长度之和最短的连通路径。可以把入口，道路穿插点及边界构成的图看作是稀疏的网，求得所有边的长度，根据克鲁思卡尔算法，在未连通的情况下，依次取出最短的边，以此类推构造出最小生成树。建立最短路径模型，求得使总路程最小的设计。针对问题二，未规定穿插点的数目和位置，这就需要进展讨论分析。简化约束条件，逐步分析，增加穿插点的个数，用迭代的方法逐步逼近最优解，求得满足条件下的最短新修路的总路程。针对问题三，在问题二的根底上进展局部优化，再次用迭代法逐步逼近，得到最优解。值得注意的是边界道路不算在总设计道路里，但是算到两入口间最短道路长度里。四、模型假设1.假设公园各点处在同一个平面。2.假设所有点之间修建道路均为直线。3.穿插点不影响道路的修建。4.假设湖四周有已修建好的道路，且不计入道路总长。五、符号及变量说明符号及变量含义备注ij两点连线长度即两点间距离表示是否需要取ij两点连线长度最短总路径中在通过边界道路的总长度新建道路总长度ij两点最短路径长度k号入口局k+1号入口之间沿边界经过的路径长度为号入口到1号入口沿边界的最短路径六、模型的建立与求解6.1问题一模型与求解为描述方便，我们将穿插点分别定义为点9、10、11、12，如下图：为求得最短新修路的总路程，联系数据构造中的最短路径问题，最小生成树是各边长度之和最短的路径。可以把入口，道路穿插点及边界构成的图看作是稀疏网，求得所有边的长度，根据克鲁思卡尔算法，在未连通的根底上，依次取出最短的边，以此类推构造出最小生成树。可能的道路设计如图：〔图中标注的红字为构造最小生成树的次序〕构造的最小生成树是道路总路程最短的道路设计，但根据题意，需验证是否满足任意两入口之间最短道路长不大于两点连线的1.4倍。经过计算可知，入口1到入口5之间最短道路长大于两点连线1.4倍，不满足题目要求。所以，为满足题目要求，需改动入口1到入口5之间道路路径，又经过计算比拟可知，在可使得入口1到达入口5的路径中，只有选取入口5和入口12之间的道路可使得公园道路总路程最短。故最终新修道路总路程为364.1458米，道路设计图如下：6.2问题二的模型现公园内可以任意修建道路，故穿插点个数不确定。采用分步添加穿插点个数，逐步逼近的思想，分析公园道路总长度的变化情况。先简化约束条件为ij两点的线段距离；是对角线为0的对称矩阵，如下表：编号123456781030140186.815141.421101.118100.49832.0152300110158.113122.065101.118107.703355.9013140110064.031107.703160.078180.2776161.9414186.815158.11364.0312094.339172.409196.4688201.5565141.421122.065107.70394.339085110141.5096105.948101.118160.078172.4098502582.7647100.498100.498180.277196.46811025075.663832.01555.901161.941201.556141.50982.76475.6630为ij两点间的道路是否需要修建，；C：在同一边界上的两入口，需要利用边界通过的道路长度和；所以目标函数为新修路的总路程l的最小值min；约束条件是任意的两个入口之间的最短道路长不大于两点连线的1.4倍。设ij两点间的最短路径，则;判断两入口点的最短路径有个约束条件，但是1、2、3和5、6、7三入口点分别在同一条边界上，已经有道路，不需再考虑到约束条件里，则约束条件变为22个；再进一步简化约束条件，经过计算1、4,1、7,2、4,2、8,3、8,4、5,4、6,4、7,4、8,5、8，6、8,7、8都可以在满足约束条件下经边缘道路连通，所以不需考虑到约束条件里，约束条件进一步简化为10个。再进一步简化约束条件，因为1.4倍3-5加5-6小于1.4倍3-6，所以只要3、5点满足条件，3、6就满足条件，则3、6也不用考虑，同理3、7点也不用考虑，这样约束条件就只剩下8个。即1、5,1、6,1、7,2、5,2、6,2、7,3、4,3、5。约束条件：；假设没有交点，延续第一问的最小生成树思想，作出最小生成树，因1到6长度与2到6长度相等，故有两种可能的道路设计。方案一中的道路总长度为426.9344米。如下列图：方案二中的道路总长度为426.9344米。如下列图：二.现添加一个交点M〔9〕，如下列图所示：在无交点的根底上增加1个穿插点进展进一步优化，设穿插点为M〔*,y〕，我们利用C语言编程，采用逐步逼近的思想，在满足条件的情况下,找到了坐标为M〔114.5，32〕最短新修路的总路程为393.015325米。规划图如下：下面是对C程序逐步逼近思想的简单介绍〔程序见附录〕：〔1〕建立2个for循环，分别以M点的横纵坐标作为循环变量〔2〕先让M的纵坐标y由0加到100，M的横坐标*由35加到200，以1为步长进展逐步逼近，找到一点M〔112，34〕，此时新修路的总路程为393.181065米；〔3〕再进一步逼近，在已求出点的根底上，缩小寻找范围。以0.1为步长，求出M点〔114.5,32〕，此时最短新修路的总路程为393.015325米；三.添加一个交点作进一步优化在一个交点的根底上进一步优化，沿用一个交点的逐步逼近方法，求出M点坐标〔59，79〕，N点坐标〔173,44〕，最短新修路的总路程为358.573346米；再进一步逼近，在已求出点的根底上，缩小寻找范围。以0.1为步长，让N的纵坐标由75加到85,找到的最正确位置，再依次让N的横坐标由170加到180，M的纵坐标由40加到50，M的横坐标由75加到85，找到两点M〔59.7,77.6〕N〔173.1,43.6〕，此时最短新修路的总路程为358.529730米；四.在上图的根底上继续添加交点，不存在能使两条相邻的路径变短的第三个点，所以上图两交点的规划为问题二的最优解，最短新修路的总路程为358.529730米。6.3问题三的模型在问题二的根底上把湖考虑进去，如下列图：1、2、6、7、8五点离湖较远，且己规划的路径不受湖的影响，仅需考虑3、4、5与湖的关系，道路不能通过湖，但可以利用湖的四周已经有的道路进一步优化。为了利用湖已经有的道路，所以道路与湖的交点个数至少为2个，经分析，如果道路与湖的交点多于2个，则3、4点不满足约束条件，故连接湖与道路的交点必然有两个，共有四种情况。从入口5出发的道路与湖的交点可能在R1R4或R1R2上，从n点出发的道路与湖的交点可能在R2R3或R4R3上。两交点在湖对边和两交点在湖邻边均有两种情况，在湖对边的绕行距离和修建道路长度都会比在邻边时长，所以此处只考虑相邻的两种情况。延续之前的逐步逼近方法，设出道路与湖的交点P、Q的坐标和点N的坐标，用迭代逼近的思路，求出P、Q、N的坐标，求出最短道路长度318.727931米。第一种情况：与湖相交上边和右边，求出的结果N点坐标〔169.9,40.8〕、P〔165，45〕Q〔140,70〕，最短道路长度318.727931米。第二种情况：与湖相交于左边和下边，求出的结果N点坐标〔169.5,40.8〕、P〔165，45〕、Q〔140,69.9〕，最短道路长度324.866691米。所以最优方案为第一种情况的，N点坐标〔169.9,40.8〕、P〔165，45〕Q〔140,70〕，最短道路长度318.727931米。道路设计如下列图所示：七、模型的优缺点分析及推广优点：1.利用克鲁斯卡尔算法建立最小生成树模型，模型简单便于求解。2.运用逐步逼近的思想，利用c语言编写程序，解决了lingo因为变量过多而不能直接解决的非线性规划问题，方法简单可行。缺点：逐步逼近的方法具有一定的局限性，只能无限逼近最优解。推广：此模型可应用于各种最短道路或线路选取和规划问题、最小生成树问题。八、参考文献【1】严蔚敏、*伟民编著，数据构造，清华大学出版，2021【2】韩中庚，数学建模方法及其应用，高等教育，2005【3】姜启源、谢金星，数学建模，高等教育，2003九、附录9.1一个交点的第一次逼近以1为步长，缩小穿插点的查找范围：#include<iostream>//一个点的情况第一次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doubled25,a25,d35,a35,d18,d34,d26;a25=122.066;a35=107.703;d18=32.0156;d26=101.1187421;d34=64.0312;double*,y,*0,y0;*=50;y=0;doublet1,t2;doublel=1000;doublel0;doubleD[2][6];for(t2=-5;t2<=110;t2=t2+1){for(t1=-5;t1<=100;t1=t1+1){D[0][1]=sqrt((*+t1-A[1][0])*(*+t1-A[1][0])+(y+t2-A[1][1])*(y+t2-A[1][1]));D[0][2]=sqrt((*+t1-A[2][0])*(*+t1-A[2][0])+(y+t2-A[2][1])*(y+t2-A[2][1]));D[0][3]=sqrt((*+t1-A[3][0])*(*+t1-A[3][0])+(y+t2-A[3][1])*(y+t2-A[3][1]));d25=D[0][1]+D[0][3];d35=D[0][2]+D[0][3];if(d25<=1.4*a25)if(d35<=1.4*a35){l0=d35+d25+d18+d26+d34-D[0][3];if(l0<l){l=l0;*=*+t1;y=y+t2;}}}}printf("m点的大致横坐标\n");printf("%f\n",*);printf("m点的大致纵坐标\n");printf("%f\n",y);printf("大致需要修建道路最短长度\n");printf("%f\n",l);}程序运行结果如下：9.2一个点交点的第二次逼近以0.1为步长，缩小穿插点的寻找范围：#include<iostream>//一个点的情况第二次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doubled25,a25,d35,a35,d18,d34,d26;a25=122.066;a35=107.703;d18=32.0156;d26=101.1187421;d34=64.0312;double*,y,*0,y0;*=112;y=34;doublet1,t2;doublel=1000;doublel0;doubleD[2][6];for(t2=-5;t2<=5;t2=t2+0.1){for(t1=-5;t1<=5;t1=t1+0.1){D[0][1]=sqrt((*+t1-A[1][0])*(*+t1-A[1][0])+(y+t2-A[1][1])*(y+t2-A[1][1]));D[0][2]=sqrt((*+t1-A[2][0])*(*+t1-A[2][0])+(y+t2-A[2][1])*(y+t2-A[2][1]));D[0][3]=sqrt((*+t1-A[3][0])*(*+t1-A[3][0])+(y+t2-A[3][1])*(y+t2-A[3][1]));d25=D[0][1]+D[0][3];d35=D[0][2]+D[0][3];if(d25<=1.4*a25)if(d35<=1.4*a35){l0=d35+d25+d18+d26+d34-D[0][3];if(l0<l){l=l0;*=*+t1;y=y+t2;}}}}printf("m点的大致横坐标\n");printf("%f\n",*);printf("m点的大致纵坐标\n");printf("%f\n",y);printf("大致需要修建道路最短长度\n");printf("%f\n",l);}程序运行结果如下：9.3两交个点的第一次逼近以1为步长，缩小穿插点的寻找范围：#include<iostream>//两个点的情况第一次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doublea12,a67,d15,dn4,a15,d16,a16,d18,d25,a25,d26,a26,d27,a27,d34,a34,d35,a35;a15=141.421;a16=101.119;a25=122.066;a26=101.119;a27=107.703;a35=107.703;a34=64.03124;a12=30;a67=25;doubleN[2][2],N0[2][2];N[0][0]=35;N[0][1]=0;N[1][0]=120;N[1][1]=0;doublet1,t2,t3,t4;doublel=1000,l0=0;doubleD[2][6];for(t1=0;t1<=85;t1=t1+1){for(t2=0;t2<=100;t2=t2+1){for(t3=0;t3<=80;t3=t3+1){for(t4=0;t4<=50;t4=t4+1){D[0][1]=sqrt((N[0][0]+t1-A[1][0])*(N[0][0]+t1-A[1][0])+(N[0][1]+t2-A[1][1])*(N[0][1]+t2-A[1][1]));D[0][3]=sqrt((N[0][0]+t1-A[3][0])*(N[0][0]+t1-A[3][0])+(N[0][1]+t2-A[3][1])*(N[0][1]+t2-A[3][1]));D[0][4]=sqrt((N[0][0]+t1-A[4][0])*(N[0][0]+t1-A[4][0])+(N[0][1]+t2-A[4][1])*(N[0][1]+t2-A[4][1]));D[1][2]=sqrt((N[1][0]+t3-A[2][0])*(N[1][0]+t3-A[2][0])+(N[1][1]+t4-A[2][1])*(N[1][1]+t4-A[2][1]));D[1][3]=sqrt((N[1][0]+t3-A[3][0])*(N[1][0]+t3-A[3][0])+(N[1][1]+t4-A[3][1])*(N[1][1]+t4-A[3][1]));dn4=sqrt((N[1][0]+t3-200)*(N[1][0]+t3-200)+(N[1][1]+t4-50)*(N[1][1]+t4-50));d15=D[0][1]+D[0][3]+a12;d16=D[0][1]+D[0][4]+a12;d18=32.0156;d25=D[0][1]+D[0][3];d26=D[0][1]+D[0][4];d27=D[0][1]+D[0][4]+a67;d34=D[1][2]+dn4;d35=D[1][2]+D[1][3];if(d15<=1.4*a15){if(d16<=1.4*a16){if(d25<=1.4*a25){if(d26<=1.4*a26){if(d27<=1.4*a27){if(d35<=1.4*a35){if(d34<=1.4*a34){l0=d18+D[0][1]+D[0][3]+D[0][4]+D[1][3]+D[1][2]+dn4;if(l0<l){l=l0;N0[0][0]=N[0][0]+t1;N0[0][1]=N[0][1]+t2;N0[1][0]=N[1][0]+t3;N0[1][1]=N[1][1]+t4;}}}}}}}}}}}}printf("m点的大致横坐标\n");printf("%f\n",N0[0][0]);printf("m点的大致纵坐标\n");printf("%f\n",N0[0][1]);printf("n点的大致横坐标\n");printf("%f\n",N0[1][0]);printf("n点的大致纵坐标\n");printf("%f\n",N0[1][1]);printf("大致需要修建道路最短长度\n");printf("%f\n",l);}程序运行结果如下：9.4两个点的第二次逼近以0.1为步长，缩小穿插点的查找范围：#include<iostream>//两个点的情况第二次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doublea12,a67,d15,dn4,a15,d16,a16,d18,d25,a25,d26,a26,d27,a27,d34,a34,d35,a35;a15=141.421;a16=101.119;a25=122.066;a26=101.119;a27=107.703;a35=107.703;a34=64.03124;a12=30;a67=25;doubleN[2][2],N0[2][2];N[0][0]=59;N[0][1]=79;N[1][0]=173;N[1][1]=44;doublet1,t2,t3,t4;doublel=1000,l0=0;doubleD[2][6];for(t1=-5;t1<=5;t1=t1+0.1){for(t2=-5;t2<=5;t2=t2+0.1){for(t3=-5;t3<=5;t3=t3+0.1){for(t4=-5;t4<=5;t4=t4+0.1){D[0][1]=sqrt((N[0][0]+t1-A[1][0])*(N[0][0]+t1-A[1][0])+(N[0][1]+t2-A[1][1])*(N[0][1]+t2-A[1][1]));D[0][3]=sqrt((N[0][0]+t1-A[3][0])*(N[0][0]+t1-A[3][0])+(N[0][1]+t2-A[3][1])*(N[0][1]+t2-A[3][1]));D[0][4]=sqrt((N[0][0]+t1-A[4][0])*(N[0][0]+t1-A[4][0])+(N[0][1]+t2-A[4][1])*(N[0][1]+t2-A[4][1]));D[1][2]=sqrt((N[1][0]+t3-A[2][0])*(N[1][0]+t3-A[2][0])+(N[1][1]+t4-A[2][1])*(N[1][1]+t4-A[2][1]));D[1][3]=sqrt((N[1][0]+t3-A[3][0])*(N[1][0]+t3-A[3][0])+(N[1][1]+t4-A[3][1])*(N[1][1]+t4-A[3][1]));dn4=sqrt((N[1][0]+t3-200)*(N[1][0]+t3-200)+(N[1][1]+t4-50)*(N[1][1]+t4-50));d15=D[0][1]+D[0][3]+a12;d16=D[0][1]+D[0][4]+a12;d18=32.0156;d25=D[0][1]+D[0][3];d26=D[0][1]+D[0][4];d27=D[0][1]+D[0][4]+a67;d34=D[1][2]+dn4;d35=D[1][2]+D[1][3];if(d15<=1.4*a15){if(d16<=1.4*a16){if(d25<=1.4*a25){if(d26<=1.4*a26){if(d27<=1.4*a27){if(d35<=1.4*a35){if(d34<=1.4*a34){l0=d18+D[0][1]+D[0][3]+D[0][4]+D[1][3]+D[1][2]+dn4;if(l0<l){l=l0;N0[0][0]=N[0][0]+t1;N0[0][1]=N[0][1]+t2;N0[1][0]=N[1][0]+t3;N0[1][1]=N[1][1]+t4;}}}}}}}}}}}}printf("m点的大致横坐标\n");printf("%f\n",N0[0][0]);printf("m点的大致纵坐标\n");printf("%f\n",N0[0][1]);printf("n点的大致横坐标\n");printf("%f\n",N0[1][0]);printf("n点的大致纵坐标\n");printf("%f\n",N0[1][1]);printf("大致需要修建道路最短长度\n");printf("%f\n",l);}程序运行结果如下：9.5有湖的第一种情况有湖的优化情况1：#include<iostream>//有湖第一种情况第二次逼近#include<cmath>voidmain(){doubleA[6][2];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A[2][0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doubled35,d34,d5,dn,dn4,dn3;doubled18=32.0156,dm6=32.4205,dm5=64.3261,dm2=80.0615;doublea34=64.03124,a35=107.7033;double*,y,*0,y0,p,p0,q,q0;*=169;y=41;q=140;p=45;doublet1,t2,t3,t4;doublel=1000;doublel0;doubleD[1][3];for(t4=-5;t4<0;t4=t4+0.1){for(t3=0;t3<=5;t3=t3+0.1){for(t1=-5;t1<=4;t1=t1+0.1){for(t2=-5;t2<=5;t2=t2+0.1){dn4=sqrt((*+t1-200)*(*+t1-200)+(y+t2-50)*(y+t2-50));dn=sqrt((*+t1-165)*(*+t1-165)+(y+t2-p-t3)*(y+t2-p-t3));d5=sqrt((140-q-t4)*(140-q-t4)+(100-70)*(100-70));D[0][2]=sqrt((*+t1-A[2][0])*(*+t1-A[2][0])+(y+t2-A[2][1])*(y+t2-A[2][1]));d34=D[0][2]+dn4;d35=D[0][2]+dn+d5+(70-p)+(165-q);if(d34<=1.4*a34)if(d35<=1.4*a35){l0=dm2+dm5+d18+dm6+d5+dn+dn4+D[0][2];if(l0<l){l=l0;*0=*+t1;y0=y+t2;p0=p+t3;q0=q+t4;}}}}}}printf("n点的大致横坐标\n");printf("%f\n",*0);printf("n点的大致纵坐标\n");printf("%f\n",y0);printf("q点的大致*坐标\n");printf("%f\n",q0);printf("p点的大致*坐标\n");printf(