公园道路设计问题副本.doc

公园道路设计问题 摘要 对于大学校园来说，公园不仅是校园景观的必要，也是广大老师和学生校园生活的必要。随着近些年，国家经济的发展，教育投入的增加，以及高校的进一步扩招，许多大学都陆陆续续建起了新校区或者是分校，校园建筑正是许多老师和学生共同关注的。一方面，校园建筑要注重美观，注重校园特色，方便出行；另一方面，处于经济上的考虑，建筑成本也是不可忽视的一个重要因素。本文就是通过图论和多种模型的建立优化，达到以上目的，构建出一条最短路径，解决以上问题。 我们建立了多种最短路径问题模型，首先通过给排除法选择出一些需要通过新建道路来连接的入口，它们分别是（1—5，6，7，8）（2—5，6，7）（3—5，6，7），所以我们只需建立模型，构建新的路径满足条件，连接以上入口之间即可得到了最终的结果。 针对问题一：我们建立了基于floyd算法的综合评价模型。我们根据题目所给的的信息，主要通过任意两点边线距离是否可用进行第一步筛选，选出个直连路径。根据题目所提供的原则，我们选取了路长和利用效率相结合的权值，并且构建了一种满足题目要求的路径，长度为472.5m 针对问题二：我们建立了一种基于蚁群算法的数学模型来求解。把主要路径进行分类，然后以入口为单位综合评价了各个点对点间路径使用频率的情况。 通过建立约束函数选择初步出要选用的路径，在根据所选择的路径，通过最佳路径算法求出修路过程中的路程及由其产生的一系列影响。列出路线综合筛选方程，比较选择出，即为我们所需要的最优旅游路线。 针对问题三：与问题二对比后发现问题三可以直接对问题二结果修正后得到。考察湖泊对参照问题二的影响，在蚁群算法的基础上建立综合比较方程，全面的评估了湖泊对路径的影响。对相关路径修正后得出结果。 关键词： 图论 floyd算法 综合评价 最佳路径 蚁群算法 一、问题背景 对于大学校园来说，公园不仅是校园景观的必要，也是广大老师和学生校园生活的必要。随着近些年，国家经济的发展，教育投入的增加，以及高校的进一步扩招，许多大学都陆陆续续建起了新校区或者是分校，校园建筑正是许多老师和学生共同关注的。一方面，校园建筑要注重美观，注重校园特色；另一方面，处于经济上的考虑，建筑成本也是不可忽视的一个重要因素。现有一所大学，正是如此，他们计划建一个矩形公园，公园计划有若干出口，现在处于成本的考虑，要去设计道路让任意两个入口相连，使得总长度最小，且两个入口之间的最短道路不大于两点连线的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，其中图2即是一种满足要求的设计，但不是最优的。 现在完成以下问题： 问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。 问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。 问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二?的任务。 其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。 注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。 图 1 公园及入口示意图 图 2 一种可能的道路设计图 二·问题分析 统观问题后，我们发现问题均为最短路径问题。且问题一、问题三均建立在问题二基础上针对各问题我们决定先解决问题二，个问题对应方法如下： 针对问题一：我们建立了基于floyd算法的综合评价模型。首先针对所有数据进行整理，考虑到在满足题目要求下总路程尽可能短，且边线不计入总路程，故尽可能运用边线距离可使计算简化，列表将所有十二个点两两直线距离、边线距离列表求出整理筛选出48个直连路径。随后，将数据代入建立基于floyd算法的综合评价模型。得到最短路径。 针对问题二：属最短路径问题，最优路径问题。建立蚁群算法模型。蚁群算法是求解交通路网中两点间的最短路径，是智能系统中一个重要的功能, 能够更为准确快速地找到最优解, 我们尝试采用带有方向引导信息的蚁群算法来实现该功能.实验结果表明, 该方法能较为准确地找到交通路网中两点间最短路径的最优解。 针对问题三：与传统蚁群问