公园内道路设计 数学建模

城市公园内的道路设计

孙多文 任强

摘 要: 本文就城市公园内道路的设计问题展开，是一个求最短路径的问题。该问题是日常生活中常见的问题，其中会涉及到商业利益以及生产生活，所以怎样对道路进行规划、怎样才能最大限度的节约开支、怎样合理的选择出行路线等方面都有着重要意义。对于这个问题，本文将给出相关的建模、求解及其分析。

通过分析，在满足题目要求的前提下，考虑以下几点：1、可以通过公园四周到达的点不必再去修路；2、尽可能的利用题中已存在的线。3、能少修路就少修路。

针对问题一：建立优化模型，在优化的时必须满足题目中的要求：1、设计的道路必须让任意两个入口相连；2、任意两个入口之间的最短道路长不大于两点连线的1.4倍。在此前提下给出符合题目要求的方案并不断的进行优化，采用几何作图法及完美匹配法在优化中去寻求最优解。

针对问题二：去掉了问题一中A、B、C、D（公园内的道路连接点）的约束，结合问题一的方案，可以相对简单的对问题二求方案，同样采用完美匹配的思想，通过几何作图对相关内线进行优化。

针对问题三：在问题一和问题二的前提下，对给出的矩形湖的坐标位置进行几何作图分析，发现该湖只影响部分入口的最优连接方法。同样，在满足题意的要求下，对这些受到影响的入口连线方法进行两两的完美匹配，从而给出最优解。

在处理这些问题时运用了MATLAB软件、绘图软件、EXCEL表格处理软件、公式编辑软件以及FLOYD算法，对篇论文在求解及数据处理等方面产生了很大方便。

关键词：floyd算法 完美匹配 不断优化 几何作图法 MATLAB软件

1

一、 问题重述

某城市决定在市中心建立一个公园。公园计划有若干个入口，现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的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，其中图2即是一种满足要求的设计，但不是最优的。

现完成以下问题：

问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。图2

2

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

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

其中矩形的湖为R1(140,70),R2(140,45),R3(165,45),R4(165,70)。 注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。 （图3）

二、 问题的分析

分析题目的特征及题中所给出的限制条件，可以知道，该题是一个与实际生活联系紧密有关城市公园内的道路设计问题。可以采用纯几何的做题思路及方法，给出符合题

3

意的方案，通过对方案的不断合理改进已达到题目的需求。

题目总的分析：

本文中明确指出：建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的1.4倍。根据此条件，则可得到以下影响该题总的做题理念：

1. 尽可能多的合理的利用公园四周已存在的边（公园四周的边不计入道路总长），减少在公园内不必要道路的产生。

2. 根据几何图形中点与点（两点之间直线最短）的性质；三角形边的性质；平行四边形的性质（对角线之和大于相对两边之和）则应优先考虑避免三角形的产生和平行四边形对角线的产生，尽可能多的利用已存在的边。 3. 处在同一边上的点不需要借助内线进行连接。 4. 能不修路，就不修路。 第一问的分析：

根据题目中给定的四个点及图（2）给定的一种可能的道路设计图，结合题目总的分析、几何图形的性质以及对相关数据的计算，可对图（2）进一步的处理优化，给出图三合理的设计方案。

第二问的分析：

在问题二去掉在问题一中四个点A、B、C、D的约束后，同样追求的是道路的长度和最小。结合第一问给出的方案，根据该题的做题理念，我们可以给出符合题意的两种方案，方案一、方案二。通过对两种方案的比较及回归实际生活，最终给出合理的方案图四。

第三问的分析：

该问同第一二问一样追求的是道路的长度和最小，给出公园内有一条矩形湖，对该矩形湖的位置坐标分析发现：该湖并不影响第二问中入口P1和入口P8、入口P2和入口P6、入口P3和入口P6、入口P3和入口P7的最有距离设计方案，而影响入口P2到入口P5、入口P3到入口P5、入口P3到入口P4在问题二中原有的设计方案，结合该题总的做题理念，最终给出图四合理的道路设计方案。

三、 模型的假设

在对模型建立中，为了建立合理模型进行以下假设：

（1） 将所有的入口视为质点，可以忽略道路宽度对坐标点及两点之间距离的影响。 （2） 问题中对数据的处理产生的细小误差可以在实际生活中忽略。 （3） 图中两点的连线可视为两入口距离。 （4） 题中给出的理想数据符合实际需要。 （5） 不考虑美观因素对道路设计的影响。

（6） 除了题中所提的要求外，道路规划不考虑其他因素。 （7） 湖的四周路已修好。

四、 符号说明

4

1.4dij--任意两入口之间连线的1.4倍

di,j-- 任意两点之间连线的长度 Sij--以边界为道路的两点间的最短距离

、、、、8）。 Pi--公园的八个入口 （i=1、2、3、

S--设计路线的总路程

五、 模型准备

5.1点

题中涉及到的道路交叉点、入口均视为点

5.2 内线

除方案中以有的边外，新增的边称为内线。 5.3 任意两点间的最短路径

本问题的一个重要的数据处理既是求出任意两点之间的距离，通过Floyd算法，分别给出已知点的横纵坐标，便可以求出任意两点之间的距离。

5.3 定位

矩形公园的四个顶点从原点起依次编为O、E、F、G。

5.4 公式

两点之间的距离公式：d?(y2?y1)2?(x2?x1)2 点到直线的距离公式：d?

Ax0?By0?CA?B22

六、模型建立与求解

本部分将依次针对三个问题进行合理规划，达到数据优化，使得道路

5

本文来源：https://www.bwwdw.com/article/4xs2.html