1、 公园内道路设计问题 摘要 公园内道路设计问题本质上是最短路径问题，该问题是现实生活中常见的的研究课题，在商业利润估算、生产生活、运输路线选择等方面都有重要意义。本文对公园内道路设计问题进行建模、求解及相关分析。 对于问题一，根据题目中两个原则：边界道路不计入修建道路总长及最短道路 长不大于两点连线 1.4倍，首先考虑将仅从边界走且满足小于 1.4倍的点找出，只考虑余下不能利用边界的入口点与题设中所给四个交叉点之间的最短路径。针对简化后的问题，图论模型可知，利用 Kruskal算法求得公园路径的最小生成树，再利用 Floyd算法求出无法利用边界的点两两之间的最短路径，最后对仍不满足小于 1.4
2、倍要求的点进行局部优化，得出最短道路总长为 395。 对于问题二，在问题一所求的最短设计方案基础上，排除考虑可在边界上经过的点及路径确定的81 PP，对余下的点65432 PPPPP 、进行讨论，简化问题，得到不确定交叉点情况下的最短路径。对简化后的点间连线图引入费马点确定两个交叉点坐标，分别为 59.7706.59 ，M 、 64.4310.173 ，N。循环问题一求解方法，得出利用费马点优化后最短总路程为 353.58， 与问题一结果比较，395-353.58=41.42 米，道路修建优化效果良好。 对于问题三，公园增加矩形湖，修建的道路不能通过或者只能沿着湖边修建 ，可以看成是对问题二方
3、案增加约束条件。考虑到湖的影响，公园左边交叉点 M的路径不改变，对右边路径进行讨论，分成两种方案设计，方案一路径不经过湖边，方案二路径沿着湖边经过，有三个交点。通过非线性规划对目标函数最短路径进行约束，求得最优值。通过比较得出方案一的交叉点坐标为N（ 187.2841，53.14394） ,设计道路总路程最短，为 364.05。 本文主要用最短路径讨论公园内部道路建设问题，此类方法亦可推广到网线的布局、城市道路的修建、公共场所的修建等现实问题中。 关键词： Kruskal 算法 Floyd 算法 费马点 非线性规划 一、 问题重述 最短路径问题在现实生活中应用较多，现在要修建一个有 8 个入口
4、的公园，即确定公园入口与园内交叉点的适当连线，使得公园的任意两个入口相连，但需满足道路总长度和最小，而且任意的两个入口之 间的最短道路长不大于两点连线的 1.4 倍。同时公园四周的边上存在已经建好的道路，且不计入道路总长。我们将主要设计对象假设为一个长 200 米，宽 100 米的矩形公园。 根据题目所给数据，本文需解决的问题有： 1、假定公园内确定要使用 4 个道路交叉点为： A(50,75)， B(40,40)， C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总 路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。 2、现在公园内可以任意修建道路，如何在
5、满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。 3、若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，以此为前提，重复完成上一问题中的任务。 二、 问题分析 2.1 问题一的分析 问题一是求解在公园内确定 4 个道路交叉点时，如何修建道路达到公园内道路总路程最短。由于题目中规定在边界点不算入道路总路程，首先可以将满足条件的点选出不加考虑。对不可在边界计算的点进行分 析，先画出最小生成树，再根据 Floyd 算法求得两两点之间最短路径，最后进行优化使这些点满足 任意的两个入口之间的最短道路长不大于两点连线的 1.4 倍，进而算
6、出最短道路总路程，并画出道路设计图。 2.2 问题二的分析 问题二是求解不确定交叉点，可在公园内任意修建道路的最小总路程。根据问题一方法分析，求解修建道路最短总路程必须先确定交叉点位置。由于边界路程不计入总路程，首先把可在边界上经过的点排除考虑，得到简化后的入口点间路线图。在此基础上引入费马点，通过求解费马点坐标来确定要增设的交叉点位置，再根据优化后的交叉点循 环问题一方法，求出最短总路程。 2.3 问题三的分析 问题三是在问题二基础上添加了个矩形湖，因此，问题三可以看成是带约束条件的问题二。由于新修的道路不能通过矩形湖，所以用非线性规划对路径进行约束规划，分两种方案进行设计，一种路径不经过湖
7、边，另一种是路径沿着湖边经过，通过计算比较出最优设计方案，满足道路总路程最短，并画出道路设计方案图。 三、 符号说明 iP公园边界的入口点 (8,7,6,5,4,3,2,1i) D 道路入口点两两之间距离的 1.4 倍的矩阵 W由最小生成树得出的邻接矩阵 道路入口点两两之间的距离矩阵 R 路径矩阵 ijLi点到 j点的距离 min 最短总路程 M 652PPP中的费马点 N543中的费马点 cM 优化改进后的652 PPP的费马点 ix费马点横坐标 iy费马点纵坐标 Z 各点到费马点的最短路径 cM四、 模型假设 1、每个入口都是一个质点，不占空间位置； 2、忽略道路拐弯处引起的路径增长； 3
8、、 假设所有道路都是直线； 4、假设公园中湖的四周没有修成的路。 五、 模型建立与求解 5.1 问题一模型建立与求解 由题目已知，通过边界不修新路的点不计算路程，则可以先把满足两点间的路径不大于两点直线距离 1.4 倍的点剔除，只需考虑不能利用边界的点与四个交叉点之间的关系。首先算出道路入口点两两之间的距离（附录一数据），再计算出入口点两两之间距离 1.4 倍的距离矩阵88R，用于下面问题比较分析： 0106011635019815411902822752411320227252224151900781511421122115404514114219826219642088R若仅通过边界不修新
9、路，计算出各点之间的路径距离如下表 1： 表 1-通过边界各点之间路径距离 P1 P2 P3 P4 P5 P6 P7 P8 P1 0 30 140 230 240 155 130 45 P2 30 0 110 200 270 185 160 75 P3 140 110 0 90 220 295 270 185 P4 230 200 90 0 130 215 240 275 P5 240 270 220 130 0 85 110 195 P6 155 185 295 215 85 0 25 110 P7 130 160 270 240 110 25 0 85 P8 45 75 185 275 1
10、95 110 85 0 通过比较分析，可知除一些可从边界上经过且不用修新路的入口外，其余不可利用边界的入口点路径有51 PP、61、81 PP、52 P、62P、72 P、 43 PP、53、63、73，对这些入口进行最短路径分析求解。 5.1.1 Kruskal 法求最小生成树 针对 1P、 2.8及公园 4 个固定道路交叉点 A、 B、 C、 D ，求出这 12 个点两两之间的直线距离，见附录二数据。根据数据写出公园道路设计联通图的邻接矩阵，通过 Kruskal 算法，解得如下表 2结果： 表 2-Kruskal 算法程序运行结果 经分析： 根据表 2 画出最小生成树如下图 5.1： 起点
11、 1 1 2 2 3 3 5 6 6 A A C 终点 2 8 3 B 4 C D 7 A B D D 图 5.1 最小生成树示意图 5.1.2 Floyd 法求最短路径 （ 1）写出最小生成树的邻接对角矩阵如下： 03100653700029031850057640411 1 0032300W（ 2） 求路径矩阵 vvijrR ，其中： 否则，若,1 1111kijkkjkikkijkij r dddkr12119999951111991211121231212123333991092999222212121091066121212101011118111111166666766666699
12、99976599991212121212665121212123333333343331111211211111143221031010110101033212222822222211212R根据上述最短路径矩阵，针对需要考虑的入口51 PP、61、81 PP、 、 52P、62 P、72P、43、53、63、73求出这些入口之间的距离矩阵。 （ 2）求距离矩阵 把带权邻接矩阵 W 作为距离矩阵的初值，即 WdD vvij 00 （ 0） =(（ v） )其中 （ v） = min （ 1） + （ 1） + （ 1） ,其中 （ v） 是从 到 的只允许以 1， 2 作为中间点的路径中最短路
13、的长度，即使从 到 中间可插入任何顶点的路径中最短路的长度，因此 即使距离矩阵。 03001021320659636020522910314001191509154194094125662916925030611329623511085015112121521623627024518108757151152172206181117640143167417862132107173174110017319771108321621372032041403001212D由距离矩阵中对需要考虑的入口与表 1 中两直线距离的 1.4 倍进行比较，得出 51 PP及 52 P两条路径仍不满足 两点间的路径不
14、大于两点直线距离 1.4倍的条件，故逐步分析比较，进行局部优化，经分析发现，因为 21P是可以沿边界走的，所以只需优化52 PP路径： 52 PP具体路径是52 PDAB ，可以考虑去掉DA边 若改变路径为 52 PABP 满足小于 1.4 倍条件，且在道路图 中可连接。 若改变路径为582 PP 满足小于 1.4 倍条件，但是在道路 图中不可连接。 所以我们选取第一条路径方案优化，且优化后最小路程为： 39534356567218min LLLLLLLLLLL CDCDAABAB调整后最终的道路设计方案如图 5.1.2 所示： 图 5.1.2 道路设计方案 由上图数据计算检验得，任意 两点间
15、的路径不大于两点直线距离 1.4 倍，道路总长为 395 米。 5.2 问题二 模型建立与求解 在本问题中，要求在公园内任意修路，交叉点不确定。首先考虑可以利用边界经过的入口，在问题一中分析得出 21PP及76 P可经过边界，可以排除考虑，其次81 PP也是最短路径，也可以排除考虑。所以在交叉点不确定情况下，只需要考虑点65432 PPPPP 、间的最短路径。将上述点连接起来（满足两点之间最短距离），得到无交叉点的优化道路图 5.2-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，为边，向三角形外侧做正三角形 1, 1ACB,BC,然后连接AA,BB, 1CC,则三线交于一点 P,则点 P 就是所求的费马点 。
