《公园道路设计问题_-_副本》由会员分享，可在线阅读，更多相关《公园道路设计问题_-_副本（27页珍藏版）》请在金锄头文库上搜索。
1、公园道路设计问题摘要对于大学校园来说，公园不仅是校园景观的必要，也是广大老师和学生校园生活的必要。随着近些年，国家经济的发展，教育投入的增加，以及高校的进一步扩招，许多大学都陆陆续续建起了新校区或者是分校，校园建筑正是许多老师和学生共同关注的。一方面，校园建筑要注重美观，注重校园特色，方便出行；另一方面，处于经济上的考虑，建筑成本也是不可忽视的一个重要因素。本文就是通过图论和多种模型的建立优化，达到以上目的，构建出一条最短路径，解决以上问题。我们建立了多种最短路径问题模型，首先通过给排除法选择出一些需要通过新建道路来连接的入口，它们分别是（15，6，7，8） （25，6，7） （35，6 ，
2、7） ，所以我们只需建立模型，构建新的路径满足条件，连接以上入口之间即可得到了最终的结果。针对问题一：我们建立了基于 floyd 算法的综合评价模型。我们根据题目所给的的信息，主要通过任意两点边线距离是否可用进行第一步筛选，选出个直连路径。根据题目所提供的原则，我们选取了路长和利用效率相结合的权值，并且构建了一种满足题目要求的路径，长度为 472.5m 针对问题二：我们建立了一种基于蚁群算法的数学模型来求解。把主要路径进行分类，然后以入口为单位综合评价了各个点对点间路径使用频率的情况。通过建立约束函数选择初步出要选用的路径，在根据所选择的路径，通过最佳路径算法求出修路过程中的路程及由其产生的一
3、系列影响。列出路线综合筛选方程，比较选择出，即为我们所需要的最优旅游路线。针对问题三：与问题二对比后发现问题三可以直接对问题二结果修正后得到。考察湖泊对参照问题二的影响，在蚁群算法的基础上建立综合比较方程，全面的评估了湖泊对路径的影响。对相关路径修正后得出结果。关键词： 图论 floyd 算法 综合评价 最佳路径 蚁群算法一、问题背景对于大学校园来说，公园不仅是校园景观的必要，也是广大老师和学生校园生活的必要。随着近些年，国家经济的发展，教育投入的增加，以及高校的进一步扩招，许多大学都陆陆续续建起了新校区或者是分校，校园建筑正是许多老师和学生共同关注的。一方面，校园建筑要注重美观，注重校园特色
4、；另一方面，处于经济上的考虑，建筑成本也是不可忽视的一个重要因素。现有一所大学，正是如此，他们计划建一个矩形公园，公园计划有若干出口，现在处于成本的考虑，要去设计道路让任意两个入口相连，使得总长度最小，且两个入口之间的最短道路不大于两点连线的 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，其中
5、图 2 即是一种满足要求的设计，但不是最优的。现在完成以下问题：问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70） 。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二 的任务。其中矩形的湖为R1(140,70),R2(140,45),R3
6、=(165,45),R4=(165,70)。注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。图 1 公园及入口示意图图 2 一种可能的道路设计图二问题分析统观问题后，我们发现问题均为最短路径问题。且问题一、问题三均建立在问题二基础上针对各问题我们决定先解决问题二，个问题对应方法如下：针对问题一：我们建立了基于 floyd 算法的综合评价模型。 首先针对所有数据进行整理，考虑到在满足题目要求下总路程尽可能短，且边线不计入总路程，故尽可能运用边线距离可使计算简化，列表将所有十二个点两两直线距离、边线距离列表求出整理筛选出 48 个直连路径。随后，将数据代
7、入建立基于 floyd 算法的综合评价模型。得到最短路径。针对问题二：属最短路径问题，最优路径问题。建立蚁群算法模型。蚁群算法是求解交通路网中两点间的最短路径，是智能系统中一个重要的功能, 能够更为准确快速地找到最优解, 我们尝试采用带有方向引导信息的蚁群算法来实现该功能.实验结果表明 , 该方法能较为准确地找到交通路网中两点间最短路径的最优解。针对问题三：与传统蚁群问题相近，我们依旧采用蚁群算法。在蚁群算法的基础上建立综合比较方程，全面的评估了湖泊对路径的影响。对相关路径修正后得出结果。三、模型假设1:假设目标公园是一个平面2：公园内地理环境全部相同3：每个拐角处都为一个点4：公园内每处的景
8、色都一样，即没有特定的区域5：每一条道路赋给一定量的权值，总的结果优化为路径权值的权值四、符号系统公园入口 P1P8(简记为阿拉伯数字 18 )道路交叉点 AB (简记为阿拉伯数字 912)两点连接路径 X-Y蚁群算法中的符号系统N 表示网络中的节点数; M 是蚁群中蚂蚁的数Q 为常量; T 表示循环次数 和 为两个参数, 分别反映了蚂蚁在运动过程中所积累的信息 和启发信息在蚂蚁选择路径中的相对重要性. 五、模型建立路径的权值优化系统对于每条线路的考察有 3 个方面1）这条线路的长度2）这条线路的利用率3）这条线路的可替换性我们主要通过这 3 个方面的比较，选取合适的路径来进行建模，得到最短的
9、路径。 问题一：公园内确定要使用 4 个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70） 。1.1 准备阶段基础数据处理与整理我们将 112 点任意两点间直线距离、边线距离计算整理，逐步筛选 48 个必选通路：见附表（1） （2）1.2 基于 floyd 算法的最短路线问题（1）floyd 算法建立实际上，问题一可以看成是在给定的加权图中，求最短路径的问题。 Floyd 算法的基本思路是：从图的带权邻接矩阵 A=a(i,j)nn 开始，递归地进行 n 次更新，即由矩阵 D(0)=A，按一个公式，构造出矩阵 D(1)；又用同样地公式由 D(1)构造出 D(
10、2)；最后又用同样的公式由 D(n-1)构造出矩阵 D(n)。矩阵 D(n)的 i 行 j 列元素便是 i 号顶点到 j 号顶点的最短路径长度，称 D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵 path 来记录两点间的最短路径。递推公式为： D(0)=A；D(1)=dij(1)nn，其中 dij(1)=mindij(0),di1(0)+d1j(0)；D(2)=dij(2) nn，其中 dij(2)=mindij(1),di2(1)+d2j(1)；D(n)= dij(n) nn，其中 dij(n)=mindij(n-1),di, n-1 (n-1)+d n-1,j(n-1)；采用循环迭代
11、可以简便求出上述矩阵序列，具体算法如下：D(i,j):dij(k)；Path(i,j)：对应于 d(i,j)(k)的路径上 i 的后继点，最终的取值为 i 到 j 的最短路径上 i 的后继点。输入带权邻接矩阵 A=a(i,j)nn1） 赋初值对所有 i,j,d(i,j)=a(i,j)；当 a(i,j)=无穷大时，path(i,j)=0，否则path(i,j)=j；k=1。2） 更新 d(i,j)，path(i,j)对所有 i,j，若 d(i,k)+d(k,j)=d(i,j)，则转 3） ；否则 d(i,j)=d(i,k)+d(k,j)，path(i,j)=path(i,k)，k=k+1，继续执
12、行 3） 。3） 重复 2）直到 k=n+1。MATLAB 源程序见附源程序（1）（2）数据的数值化处理a=000 030 inf inf inf inf inf 032 inf 044 inf inf 030 000 110 inf inf inf inf inf inf 041 inf inf inf 110 000 090 inf inf inf inf inf inf 056 inf inf inf 090 000 032 inf inf inf inf inf 081 087inf inf inf 032 000 inf inf inf inf inf inf 030inf inf
13、inf inf inf 000 025 083 030 inf inf inf inf inf inf inf inf 025 000 085 047 inf inf inf032 inf inf inf inf 083 085 000 070 042 inf infinf inf inf inf inf 030 047 070 000 036 inf 065044 041 inf inf inf inf inf 042 036 000 080 infinf inf 056 081 inf inf inf inf inf 080 000 030inf inf inf 087 030 inf i
14、nf inf 065 inf 030 000; 注：a 矩阵是所用点之间的间距和可连接性分析通过 MATLAB 的数据处理我们得到了以下结果ans =【 0 30 140 204 175 110 117 32 80 44 124 14530 0 110 174 172 107 124 62 77 41 121 142140 110 0 64 96 181 198 172 151 136 56 86204 174 64 0 32 157 174 197 127 161 81 62175 172 96 32 0 125 142 165 95 131 60 30110 107 181 157 125
15、 0 25 83 30 66 125 95117 124 198 174 142 25 0 85 47 83 142 11232 62 172 197 165 83 85 0 70 42 122 135 80 77 151 127 95 30 47 70 0 36 95 6544 41 136 161 131 66 83 42 36 0 80 101124 121 56 81 60 125 142 122 95 80 0 30145 142 86 62 30 95 112 135 65 101 30 0】对于以上结果的分析我们可以得到一个较为合适的结果即连接以上的点（P1,P8） （P2,P10）
