2022年公园内道路设计问题

1、公园内道路设计问题 公园内道路设计问题 公园内道路设计问题公园内道路设计问题本质上是最短路径问题,该问题是现实生活中常见的的争论课题,在商业利润估算、生产生活、运输路线挑选等方面都有重要意义；本文对公园内道路设计 问题进行建模、求解及相关分析；对于问题一,依据题目中两个原就：边界道路不计入修建道路总长及最短道路长不大于两点连线1.4 倍,第一考虑将仅从边界走且满意小于1.4 倍的点找出,只考虑余下不能利用边界的入口点与题设中所给四个交叉点之间的最短路径；针对简化后的问题,图论模型可知,利用Kruskal 算法求得公园路径的最小生成树,再利用Floyd 算法求出无法利用边界的点两两之间的最短路径

2、,最终对仍不满意小于 最短道路总长为 395；1.4 倍要求的点进行局部优化,得出对于问题二,在问题一所求的最短设计方案基础上,排除考虑可在边界上经过的点及路径确定的P1P8,对余下的点P2、P3、 P4、P5、P6 进行争论,简化问题,得到不确定交叉点情形下的最短路径；对简化后的点间连线图引入费马点确定两个交叉点坐标,分别为 M59.06 ,77.59 、 N173.10 ,43.64 ；循环问题一求解方法,得出利用费马点优化后最短总路程为353.58 ,与问题一结果比较,395-353.58=41.42米,道路修建优化成效良好；对于问题三,公园增加矩形湖,修建的道路不能通过或者只能沿着湖边

3、修建,可以看成是对问题二方案增加约束条件；考虑到湖的影响,公园左边交叉点 M的路径不转变,对右边路径进行争论,分成两种方案设计,方案一路径不经过湖边,方案二路径沿着湖边经过,有三个交点；通过非线性规划对目标函数最短路径进行约束,求得最优值；通过比较得出方案一的交叉点坐标为N（ 187.2841 , 53.14394 ）, 设计道路总路程最短,为364.05 ；本文主要用最短路径争论公园内部道路建设问题,此类方法亦可推广到网线的布局、城市道路的修建、公共场所的修建等现实问题中；关键词： Kruskal算法 Floyd算法 费马点非线性规划一、 问题重述最短路径问题在现实生活中应用较多,现在要修建

4、一个有8 个入口的公园,即确定公园入口与园内交叉点的适当连线,使得公园的任意两个入口相连,但需满意道路总长度和最小,而且任意的两个入口之间的最短道路长不大于两点连线的1.4 倍；同时公园四周的边上存在已经建好的道路,且不计入道路总长；我们将主要设计对象假设为一个长 200 米,宽 100 米的矩形公园；依据题目所给数据,本文需解决的问题有： 1、假定公园内确定要使用4 个道路交叉点为：A50,75 ,B40,40 ,C120,40 ,D115,70 ）；问如何设计道路可使公园内道路的总路程最短；建立模型并给出算法；画出 道路设计,运算新修路的总路程； 2、现在公园内可以任意修建道路,如何在满意

5、条件下使总路程最少；建立模型并给 出算法；给出道路交叉点的坐标,画出道路设计,运算新修路的总路程； 3 、如公园内有 一条矩形的湖,新修的道路不能通过,但可以到达湖四周的边,以此为前提,重复完成上 一问题中的任务；二、 问题分析 2.1 问题一的分析问题一是求解在公园内确定4 个道路交叉点时,如何修建道路达到公园内道路总路程最短；由于题目中规定在边界点不算入道路总路程,第一可以将满意条件的点选出不加考 虑；对不行在边界运算的点进行分析,先画出最小生成树,再依据 Floyd 算法求得两两点 之间最短路径,最终进行优化使这些点满意任意的两个入口之间的最短道路长不大于两点连线的 1.4 倍,进而算出

6、最短道路总路程,并画出道路设计图； 2.2问题二的分析问题二是求解不确定交叉点,可在公园内任意修建道路的最小总路程；依据问题一方 法分析,求解修建道路最短总路程必需先确定交叉点位置；由于边界路程不计入总路程,第一把可在边界上经过的点排除考虑,得到简化后的入口点间路线图；在此基础上引入费 马点,通过求解费马点坐标来确定要增设的交叉点位置,再依据优化后的交叉点循环问题 一方法,求出最短总路程； 2.3 问题三的分析问题三是在问题二基础上添加了个矩形湖,因此,问题三可以看成是带约束条件的问 题二；由于新修的道路不能通过矩形湖,所以用非线性规划对路径进行约束规划,分两种 方案进行设计,一种路径不经过湖

7、边,另一种是路径沿着湖边经过,通过运算比较出最优 设计方案,满意道路总路程最短,并画出道路设计方案图； Pi D W D R Lij Lmin M N xi yi Z三、 符号说明 公园边界的入口点 i=1,2,3,4,5,6,7,8 道路入口点两两之间距离的 1.4 倍的矩阵 由最小生成树得出的邻接矩阵 道路入口点两两之间的距离矩阵 路径矩阵 i 点到 j 点的距离 最短总路程.P2P5P6中的费马点.P3P4P5中的费马点优化改进后的 .P2P5P6的费马点费马点横坐标费马点纵坐标各点到费马点的最短路径四、 模型假设 1、每个入口都是一个质点,不占空间位置； 2 、忽视道路拐弯处引起的路径

8、增长；3、假设全部道路都是直线； 4、假设公园中湖的四周没有修成的路；五、 模型建立与求解 5.1 问题一模型建立与求解 由题目已知,通过边界不修新路的点不运算路程,就可以先把满意两点间的路径不大 于两点直线距离 1.4 倍的点剔除,只需考虑不能利用边界的点与四个交叉点之间的关系；第一算出道路入口点两两之间的距离（附录一数据）,再运算出入口点两两之间距离 1.4 倍的距离矩阵 R8. 8,用于下面问题比较分析：.*45.*78.*. 1*82 . =.0119154198. 035116 .0106.如仅通过边界不修新路,运算出各点之间的路径距离如下表 之间路径距离1： 表 1- 通过边界各点

9、通过比较分析,可知除一些可从边界上经过且不用修新路的入口外,其余不行利 用边界的入口点路径有 PPPP2P5、P2P6、 P2P7、 1P5、1P6、1P8、P3P4、P3P5、P3P6、P3P7,对这些入口进行最短路径分析求解； 5.1.1 Kruskal法求最小生成树A、B、C、D ,求出这 12 个 1、P2.P点两两之针对 P8 及公园 4 个固定道路交叉点间的直线距离,见附录二数据；依据数据写出公园道路设计联通图的邻接矩阵,通过Kruskal 算法,解得如下表2 结果：表 2-Kruskal算法程序运行结果依据表 2 画出最小生成树如下图 5.1 ：图 5.1 最小生成树示意图 5.

10、1.2 Floyd 法求最短路径（1）写出最小生成树的邻接对角矩阵如下：.030 32 .0110 41.064 57.0 . .085 31. 029. W= . .0 . 0 .03765.0.（2）求路径矩阵R=rijv. v,其中： k-1k-1k-1.k,如dd+dijikkjk. r-1ij=.k -1 .rij,否就.1222.1233.3334.12121212. 9999= .6666. .1111.10101212. .3333.991111* * 2.10.11.3.12.9.6.1.12.9.12.12.、依据上述最短路径矩阵,针对需要考虑的入口P1P5、P1P6、P1

11、P8、P2P5、P2P6、P2P7、P3P4、P3P5、P3P6、P3P7 求出这些入口之间的距 离矩阵；（2）求距离矩阵把带权邻接矩阵W作为距离矩阵的初值,即D0=dijv. v=W D（0）= dij中 dij =min dij 是从 vi 到 vj 的只答应以 v1,v2 vv 作为中间点的路径中最短路的长度,即 使从 vi 到 vj 中间可插入任何顶点的路径中最短路的长度,因此 Dv即使距离矩阵；.*32108.*78.*. *6 .1*. 02516929 .=.0. *360 *0229961320 173 .143.87.151.30.94.205.65.102.30.0.由距离

12、矩阵中对需要考虑的入口与表 1 中两直线距离的 1.4 倍进行比较,得出 P1P5 及 P2P5 两条路径仍不满意两点间的路径不大于两点直线距离 1.4 倍的条件,故逐步分析比较,进行局部优化,经分析发觉,由于 需优化 P2P5 路径：P1P2 是可以沿边界走的,所以只P2P5 详细路径是 P2BADP5 ,可以考虑去掉 AD 边如转变路径为 P2BAP5 满意小于 1.4 倍条件,且在道路图 中可连接；如转变路径为 P2BP8P5 满意小于 1.4 倍条件,但是在道路 图中不行连接；所以我们选取第一条路径方案优化,且优化后最小路程为： Lmin=L18+L2B+LBA+L67+LA5+LA6

13、+L5D+LDC+LC3+L34=395 调整后最终的道路设计方案如图 5.1.2 所示：图 5.1.2 道路设计方案由上图数据运算检验得,任意两点间的路径不大于两点直线距离 1.4 倍,道路总长为395 米； 5.2 问题二模型建立与求解在本问题中,要求在公园内任意修路,交叉点不确定；第一考虑可以利用边界经过的入口,在问题一中分析得出 P6P7 可经过边界,可以排除考 1P2 及 P虑,其次 P也可以排除考虑；所以在交叉点不确定情形下,1P8 也是最短路径,只需要考虑点 P2、P3、P4、 P5、P6 间的最短路径；将上述点连接起来（满意两点之间最短距离）,得到无交叉点的优化道路图 5.2-

14、1 ：图 5.2-1 无交叉点的优化道路图在图 5.2-1 的基础上,再进一步针对已有的线路优化,设计出最短的道路,由此我们引入费马点的定义进行优化建模； 5.2.1 费马点优化模型定义：在一个三角形中,到三个顶点距离之和最小的点叫做这个三角形的费马点；性质：（1） 如三角形的三个角都小于1200,那么三条距离连线正好三等分费马点所在（2） 如三角形的三个角有一个大于1200,那么该钝角的顶点就是费马点；步骤：（1）平面内一点 P到 ABC三顶点的之和为PA+PB+PC,当点 P为费马点时,距离之和最小； 2.三内角皆小于120 的三角形,分别以 AB,BC,CA,为边,向三角形外侧做正三角形

15、 ABC1,ACB1,BCA1,然后连接 AA1,BB1,CC1,就三线交于一点P,就点 P就是所求的费马点； 3.如三角形有一内角大于或等于120 度, 就此钝角的顶点就是所求的费马点. 4当 ABC为等边三角形时 , 此时内心与费马点重合；据此,在改进后的图中,查找费马点：在 5.2-2 ：图 5.2.2 查找费马点.P2P5P6和.P3P4P5中查找费马点,如下图设 Mx1,y1 ,Nx2,y2 ,由费马点的定义,我们得到求解费马点的目标函数分别为： x1-352+y1-1002+x1-502+y12+x1-1202+y1-1002 20 x1+3y1-10000 约束条件为： 10 x

16、1-7y1- 5000 x2-1202+y2-1002+x2-1602+y22+x2-2022+y2-502 4y2-80005x2+8y2 - 14000约束条件为 : 5x2+2y2-8000运用 lingo 解得 M62.33 ,77.86 N173.10,43.64确定交叉点位置,循环问题一解法,通过 Kruskal 算法找出最小生成树,再用 Floyd算法运算最短路径,经分析,费马点优化后的两两最短路径中,只有 P1P6 不满意两点间的路径不大于两点直线距离 5.2.2 费马点改进模型1.4 倍这个条件,需要进行改进；在原目标函数基础上,再次利用费马点进行改进,目标函数不变, x1-

17、352+y1-1002+x1-502+y12+x1-1202+y1-1002 59 解得 Mc59.06循环问题一方法,全部路径均满意条件,求得改进优化后的道路设计图 5.2-3 ：在不确定交叉点情形下任意修路,既要满意两点间的路径不大于两点直线距离 1.4 倍,又使修路总路程最短,应取两个交叉点坐标位置 Mc59.06,77.59修路总路程最小为 353.58 米,与问题一结果比较,有很大改进； N173.10 ,43.64 , 5.3 问题三模型建立与求解本问题中,在其次问的基础上,考虑到了公园内部有一个人工湖,原设计的道路方案有些道路不能通过,只能到达湖的周边；因此,要对其次问得到的路线

18、设计进行局部优化,使其符合题设要求；增加一个矩形后的公园道路图 5.3-1 如下如下列图,其次问的设计路线中由于有了人工湖的存在导致 在人工湖左边的交叉点 Mc 路线没有什么阻碍,仍是其次问中得出的P2N 路线不能通过,而最优的,因此,本问题只考虑转变N 这个交叉点就行,对其进行局部优化,以达到实际情形和满意内部总路程最小的要求；下面用非线性规划设计两种方案进行优化： N（1）转变交叉点N位置,优化为N ,连接 P5N、P3N、P4,使三条路径不经过湖且满意题目条件；（2）转变交叉点 N位置,在矩形湖边上分别找三个点 a、b、c,连接 P5a、 P5b、 P5c,沿着湖边经过且满意题目条件；方

19、案（ 1）中的目标函数为： x-120+y-100 x-160+y+ 2x-200+y-50 100-y100-y2-2.75 或 -120-x120-x3y -2.25 9 x-1604y-501约束条件为 - 7x-2022120 x2022y100 -160+y+ -200+y-50 -160+y+ -200+y-50 x-160+y+ 2-200+y-50+85 x-200+y-50+110解得 minZN=156.1069 交叉点 N （187.2841 ,53.14394 ）所以修路总路程为 L 总=364.05 ,详细方案设计图 5.3-2 如下：图 5.3-2 方案二的目标函数

20、： Zabc=100-70+120-a+ b-502+（ 200-165 ）+c-160+ （45）+165-a+165-c+25 14 0a16545b70140c165 a=165b=50所以经过分析发觉,点 a 与点 R4重合,点 c 与点 R3重合,即方案二道路设计如图5.3-3 , min Z=184.2616,修路总路程为L 总=392.20424 ；通过以上分析,通过总路程比较可知方案一比方案二更优,由于它设计的公园内部道路路线更短,所以最终选用方案一用作公园道路设计,道路总路程为 364.05 ；六、 模型的评判与推广 6.1 模型优点（1）在问题一求解中,充分利用了边界条件和

21、1.4 倍的约束条件将不满意的点找出来分析争论,将复杂的问题进行了简化,减小了求解工作量；（ 2）在问题二中,模型引入了费马点的定义,通过查找费马点的方法来找道路交叉点,多次优化费马点坐标优化得到满意条件的道路设计图；这种方法简洁有用,易于懂得；（3）利用规划模型,以总路程最小为目标去解决实际的道路设计问题,操作简便；结合了问题二所得的结果,很好的利用了现有的数据；考虑较为全面,分析比较了两种情况道路的总长；使得问题更加优化； 6.2 模型缺点问题二结合问题一的结果,简化问题引用费马点的定义,便于解决问题,但在考虑交叉点时,没有去认真考虑交叉点为3、4 的情形； 6.3模型推广本文主要争论的是

22、公园内部道路建设问题,我们所使用的方法适用于大部分最短路径问题,包括网线的布局、城市道路的修建、公共场所的修建等问题；该模型对节省社会资源,便利人们活动等各方面问题有重大意义； 1 赵静,但琦等 . 数学建模与数学试验 M. 高等训练出版社,施普林格出版社 2 王海英,黄强,李传涛,褚宝增 . 图论算法及其 MATLAB实现 M. 北京航空高校出版社 3朱斌,林博,付思伟. 公园内道路的优化设计模型A. 高等数学争论, 20225 第16 卷第 3 期最小生成树邻接矩阵 12 个点两两之间距离 P1 P2 P3 P4 P5 P6 P7 P8 A B C D P1 P2 P3 P4 P5 P6

23、P7 P8 A B C D 0.00 30.00 140.00 186.82 141.42 136.78 161.78 32.02 107.63 71.23 196.57 172.82 30.00 0.00 110.00 174.03 173.23 106.78 131.78 62.02 77.63 41.23 166.57 142.82 140.00 110.00 0.00 64.03 117.39 181.32 206.32 172.02 152.17 151.23 56.57 86.98 204.03 174.03 64.03 0.00 181.42 245.35 270.35 236.

24、05 216.20 215.26 120.60 151.01 203.23 173.23 117.39 181.42 0.00 85.00 110.00 235.25 95.60 132.00 60.82 30.41 136.78 106.78 181.32 245.35 85.00 0.00 25.00 168.80 29.15 65.55 124.75 94.34 161.78 131.78 206.32 270.35 110.00 25.00 0.00 193.80 54.15 90.55 149.75 119.34 32.02 62.02 172.02 236.05 235.25 16

25、8.80 193.80 0.00 139.65 103.25 228.59 204.84 107.63 77.63 152.17 216.20 95.60 29.15 54.15 139.65 0.00 36.40 95.60 65.19 71.23 41.23 151.23 215.26 132.00 65.55 90.55 103.25 36.40 0.00 132.00 101.59 196.57 166.57 56.57 120.60 60.82 124.75 149.75 228.59 95.60 132.00 0.00 30.41 172.82 142.82 86.98 151.0

26、1 30.41 94.34 119.34 204.84 65.19 101.59 30.41 0.00运算各点两两之间的距离程序 function d=julix,y; n=lengthx;m=lengthy; for % 向量 x 为各点的横坐标,向量y 为各点的纵坐标i=1:n for j=1:m di,j=sqrtxi-xj2+yi-yj2; end end d d1=d*1.4 %d1为各点两两之间距离的1.4 倍距离的矩阵边界各点两两之间的最短路径距离程序 m=zeros8,8; %边界各点两两之间的最短路径距离 m1,2=30;m2,3=110;m3,4=90;m4,5=130;m

27、5,6=85;m6,7=25; m7,8=85;m1,8=45; for i=1:8 for j=1:8 ifmi,j=0 mj,i=mi,j; end end end for i=1:8 for j=1:8 ifmi,j=0 mi,j=inf; ifi=j mi,j=0; end end end end t,c=floydll; % 调用 floyd 函数, t 为边界各点两两之间的最短路径的距离矩阵,c 为路由矩阵； Kruskal 算法 function T c=Krusfd,flag % function T c=Krusfd,flag % 求最小生成树的 Kruskal 算法 % 边

28、权矩阵的产生方法： % 1 一般的边权矩阵,为 nxn 维；调用方式 T c=Krusfd % 2）边权矩阵的前两行分别记录图上全部边的起始顶点和终止顶点, % 无向边不重复记录；第三行记录对应边的权值；调用方式为 T c=Krusfd,1 % c:生成树的费用 ; % T: 生成树的边集合; if nargin=1 n=sized,2; m=sumsumd=0/2; b=zeros3,m; k=1; for i=1:n for j=i+1:n if di,j=0 b1,k=i;b2,k=j; b3,k=di,j;k=k+1; end end end else b=d; end n=maxma

29、xb1:2,:; m=sizeb,2; B,i=sortrowsb,3; B=B; c=0;T=; k=1;t=1:n; for i=1:m if tB1,i=tB2,i T1:2,k=B1:2,i; c=c+B3,i; k=k+1; tmin=mintB1,i,tB2,i; tmax=maxtB1,i,tB2,i; for j=1:n if tj=tmax tj=tmin; end end end if k=n 生成最小生成树的邻接矩阵 d=0.0000 30.0000 140.0000 186.8154 141.4214 101.1187 100.4988 32.0156 80.7775

30、44.7214 107.7033 118.0042 30.0000 0.0000 110.0000 158.1139 122.0656 101.1187 107.7033 55.9017 75.0000 41.2311 80.6226 95.5249 140.0000 110.0000 0.0000 64.0312 107.7033 160.0781 180.2776 161.9413 133.1353 126.4911 56.5685 83.2166 186.8154 158.1139 64.0312 0.0000 94.3398 172.4094 196.4688 201.5564 152

31、.0691 160.3122 80.6226 87.3212 141.4214 122.0656 107.7033 94.3398 0.0000 85.0000 110.0000 141.5097 74.3303 100.0000 60.0000 30.4138 101.1187 101.1187 160.0781 172.4094 85.0000 0.0000 25.0000 82.7647 29.1548 60.2080 104.0433 85.4400 100.4988 107.7033 180.2776 196.4688 110.0000 25.0000 0.0000 75.6637

32、47.1699 67.0820 125.2996 109.2022 32.0156 55.9017 161.9413 201.5564 141.5097 82.7647 75.6637 0.0000 70.7107 42.7200 120.9339 123.4909 80.7775 75.0000 133.1353 152.0691 74.3303 29.1548 47.1699 70.7107 0.0000 36.4005 78.2624 65.1920 44.7214 41.2311 126.4911 160.3122 100.0000 60.2080 67.0820 42.7200 36.4005 0.0000 80.0000 80.7775 107.7033 80.6226 56.5685 80.6226 60.0000 104.0433 125.2996 120.9339 78.2624 80.0000 0.0000 30.4138 118.0042 95.5249 83.2166 87.321