公园内道路设计

  • 格式:doc
  • 大小:1.14 MB
  • 文档页数:25

公园内道路设计问题暑期培训四摘要最短路程问题是现实生活中常见问题,在商业利润估算、生产生活、运输路线选择等方面都有重要意义。

本题的实际情景为公园内部建设道路,在保证公园边缘8个入口之间最短路径不大于两点之间距离1.4倍的前提条件下,使内部道路总长度最短。

对于问题一,考虑到最终结果只要求公园内部的道路总和最短,所以我们采用了“能用边缘就用边缘,不能用则采用最短路径,能借路就借路”的方法,算出任意两点间的距离,以道路总距离最短为目标,以两点之间距离的1.4倍作为约束条件,从而找到一个道路总距离最短的设计方案,最终算出结果为:394.56米。

对于问题二,由于没有限定道路结点,我们利用第一问的分析过程,先得出没有道路结点的最优路径,根据“Y型道路优于V型道路”,将已得道路的V型道路通过Lingo软件求出最优点改造成Y型道路,然后用同样的方法不断改造,进而得到最优化的道路设计方案,最终算出道路总长为:358.26米。

对于问题三,在问题二上增加一块不可利用的矩形区域,可继续借助问题二的模型,但要重新确定交叉点的范围。

此问题中,由于矩形湖在公园右边,承接问题二得知,该湖只影响右边的交叉点。

所以左边的交叉点位置不必改变,只需确定右边的交叉点即可。

并在此基础上利用问题二的模型继续求解。

最终解得的结果为:361.51米。

关键字:最短路径排除法 Y型道路 lingo软件问题重述西安某大学计划建一个形状为矩形或其他不规则图形的公园,不仅为了美化校园环境,也是想为其学生提供更的生活条件。

公园计划有若干个入口,现在你需要建立一个模型去设计道路让任意两个入口相连(可以利用公园四周的边,即默认矩形的四条边上存在已经建好的道路,此道路不计入道路总长),使总的道路长度和最小,前提要求是任意的两个入口之间的最短道路长不大于两点连线的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)。

图一现完成以下问题:问题一:假定公园内确定要使用4个道路交叉点为:A(50,75),B(40,40),C(120,40),D(115,70)。

问如何设计道路可使公园内道路的总路程最短。

建立模型并给出算法。

画出道路设计,计算新修路的总路程。

问题二:现在公园内可以任意修建道路,如何在满足条件下使总路程最少。

建立模型并给出算法。

给出道路交叉点的坐标,画出道路设计,计算新修路的总路程。

问题三:若公园内有一条矩形的湖,新修的道路不能通过,但可以到达湖四周的边,湖的方位如图二。

重复完成问题二的任务。

图二其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。

注:以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通,而不能连到四周的其它点。

问题分析对于第一问,该问题给出了公园内已知的四个交叉点A(50,75),B(40,40),C(120,40),D(115,70)。

在1、任意的两个入口之间的最短道路长不大于两点连线的1.4倍,2、道路会经过四个交叉点这两个前提下。

我们考虑的问题是:如何使公园内道路的总长度和最小。

考虑到最终结果只要求公园内部的道路总和最短,所以我们采用了“能用边缘就用边缘,不能用则采用最短路径,能借路就借路”的方法,算出任意两点间的距离,筛选出必须新建路的路口组合,以两点之间距离的1.4倍作为约束条件,从而找到一个最优化的设计方案。

对于第二问,在本问题中公园内可以任意修建道路,故若使总路程最短,则公园内的交叉点选取应遵循最优原则。

同时满足:1、任意的两个入口之间的最短道路长不大于两点连线的1.4倍;2、公园内新修的道路长最短两个前提条件。

由于没有限定道路结点,我们利用第一问的分析过程,先得出没有道路结点的最优路径,根据“Y型道路优于V型道路”,将已得道路的V型道路通过Lingo软件求出最优点改造成Y型道路,然后用同样的方法不断改造,进而得到最优设计方案。

对于问题三,该问题在是建立在问题二的基础上加入了一个矩形湖(如图所示),湖的四个点坐标分别R1(140,70) , R2(140,45) , R3(165,45) , R4(165,70) ,新建路径不能直接穿过。

验证问题二的路径是否穿过矩形湖,不穿过则问题得解,否则应分两种情况考虑。

此问题中,由于矩形湖在公园右边,承接问题二得知,该湖只影响右边的交叉点。

所以左边的交叉点位置不必改变,只需确定右边的交叉点即可。

并在此基础上利用问题二的模型继续求解。

模型假设1、 近似认为每个入口都是质点,不占用空间位置,从而m 、n 之间修的直线路线的程度即为|mn|。

2、 认为道路宽度为0,即所修的路都是线段,长分别是a 和b 的两条路线相交,则两条路的总长度是a+b 。

3、 认为公园的平面是完全平整无凹陷和凸起。

4、 在第三问中设计路线的总路程考虑路线中途径的湖的边界。

符号说明:,:,():,:i ij ij ij i D i j d i j d p i j p p 两路口仅通过边界线相连的最短距离;两路口间的直线距离;两路口通过方式连接的距离;第个路口。

模型建立与求解最终目标:公园内新建道路长度和最小约束条件:两入口间最短道路长不大于两点直接连线的1.4倍。

两个原则:1.能用边界道路则不新修路;2.“借路”,尽量用已修路,不新修路;解决思路:1.选择路线的顺序,由单一选择到多种选择; 2.比较所有可能情况,取最优。

(排除法) 对道路交叉点的理解:若两段路共线则其交点不是道路交叉点。

对需要新修路的路口对进行分析筛选:A B C D 分别为p9,p10,p11,p12在同一边界线上的两个路口一定满足约束条件,因此不对其进行考虑。

由上述表格数据分析知,需重新修路的路口组合为:1~5;1~6;1~8;p p p p p p 2~5;2~6;2~7;p p p p p p 3~4;3~5;3~6;3~7.p p p p p p p p问题一:(有且只有四个道路交叉点)对于p3:(1)若预与p4路口相连,最简单的办法就是34p p →,3434(34)64.03 1.489.64d p p d →=<=,则该路线可取。

(2)若预与p5路口相连,则可有以下两种选择: a: 345p p p →→;3535(345)158.37 1.4150.78;d p p p d →→=>=舍去。

b: 35p p →;3535(35)107.70 1.4150.78;d p p d →=<= b 路线可选。

(3) 若预与p6路口相连,有如下路线:356p p p →→;3636(356)192.70 1.4224.11;d p p p d →→=<=此路线可取。

(4)若预与p7路口相连,有如下路线:3567p p p p →→→;3737(3567)217.70 1.4252.39;d p p p p d →→→=<=此路线可取。

经过上述操作,道路设计图如下:204060801001201401601802000103040506070809010020ADCBP7P6P5P4P3P2P1P8图1-1对于p2:(1)若预与p5路口相连,则可有以下两种选择: a :235p p p →→;2525(235)217.70 1.4170.89;d p p p d →→=>=舍去。

b :2525(25)122.07 1.4170.89;d p p d →=<= b 路线可选。

(2)若预与p6路口相连,则可有以下两种选择: a :256p p p →→;2626(256)207.07 1.4141.57;d p p p d →→=>=舍去。

b :26p p →;2626(26)101.12 1.4141.57;d p p d →=<= b 路线可选。

(3)若预与p7路口相连,有如下路线:267p p p →→;2727(267)126.12 1.4150.78;d p p p d →→=<= 此路线可取。

经过上述操作,道路设计图如下:204060801001201401601802000103040506070809010020ADCBP7P6P5P4P3P2P1P8图1-2对p1:(1)若预与p5路口相连,有如下路线:125p p p →→;1515(125)152.07 1.4197.99;d p p p d →→=<= 此路线可取。

(2)若预与p6路口相连,有如下路线: 126p p p →→;1616(126)131.12 1.4141.57;d p p p d →→=<= 此路线可取。

(3)若预与p8路口相连,有如下路线: 18p p →;1818(18)32.02 1.444.82;d p p d →=<= 经过上述操作,道路设计图如下:204060801001201401601802000103040506070809010020ADCBP7P6P5P4P3P2P1P8图1-3由于公园内要使用A,B,C,D 四个道路交叉点,所以对上述道路设计的初步结果进行优化。

对p2与各路口的连接道路进行改进,将26p p →的连接路线改为26p B p →→,将25p p →的连接路线改为25p B p →→。

对改进路线进行如下分析:2525(25)141.23 1.4170.89d p B p d →→=<=; 2626(26)101.44 1.4141.56d p B p d →→=<=; 2727(267)126.44 1.4150.78d p B p p d →→→=<=; 1515(125)171.23 1.4197.99d p p B p d →→→=<=; 1616(126)131.44 1.4141.57d p p B p d →→→=<=; 由p2到p5,p2到p6,p2到p7改进后道路的路程总和为:265201.44B B B d d d ++=,而改进前的道路的路程总和为:2625223.19d d +=。

明显改进后比改进前新修的道路总路程减少了:223.19201.4421.75-=,则改进方案可取,改进后的道路设计图如下:204060801001201401601802000103040506070809010020ADCBP7P6P5P4P3P2P1P8图1-4若要将交叉点A 设计进入总道路中,则可将道路6B P →改进为6B A P →→。