公园内道路设计.docx

公园内道路设计问题

暑期培训四

摘要

最短路程问题是现实生活中常见问题，在商业利润估算、生产生活、运输路线选择等方面都有重要意义。本题的实际情景为公园内部建设道路，在保证公园边缘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)。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。

问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。

问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，湖的方位如图二。重复完成问题二的任务。

0 20 40 60 80 100 120 140 160 180 200

图二

其中矩形的湖为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)，新建路径不能直接穿过。验证问题二的路径是否穿过矩形湖，不穿过则问题得解，否则应分两种情况考虑。此问题中，由于矩形湖在公园右边，承接问题二得知，该湖只