公园道路最优设计问题-同济大学YK.pdf

论文题目：公园内道路最优化设计模型 摘要 模型针对公园内道路设计这一实际问题，在固定的八个入口之间针对不同的限制条件进 行道路规划，并保证任意两点之间的最短路径长度不超过两点间直接连线长度的1.4倍。 在给定公园内四个道路较差点的限制条件下，将已有 12个点构成无向图，利用kruskal 算法求解最小生成树。对解得的最小生成树使用Floyd算法得出任意两点之间的最短路径长 度，再与限制条件进行对比，针对个别不能满足限制条件的点，对局部重新求解最小生成树， 不断对比，最终得到能够满足限制条件的最优方案。 在任意设计道路的前提下，借鉴斯坦纳问题已有的结论，和椭圆、圆的几何性质，初步 确定可能存在于公园内部的道路交叉点的数量、位置和连接方式，在此条件下对可能存在的 各种最短路径方案使用非线性规划的方法求解，最终将得到的各组解进行比较，选取新建道 路总长最小的方案为最优方案。 在公园中存在湖的情况下，我们以上面求得的最优方案为基础进行修正，仍然使用非线 性规划的方法得到可能存在的多组解，并比较得出新建道路总长最小的方案作为最优方案。 在任意修建道路的前提下，综合考虑道路长度最短和避免行人践踏草坪。我们同样以任 意修建道路时的最优方案为基础进行修正。并引入新的假设，将人穿越草坪的概率与连点间 直接连线的长度与两点间道路长度的比值联系起来。同时为简化问题，假定人的视野有限且 范围较小，并结合实际在最有可能出现穿越草坪的位置建设长椅、花坛等公共设施，减小人 穿越草坪的可能，从而保护草坪，最终得到道路设计方案。 【关键词】最小生成树 kruskal算法 Floyd算法 非线性规划 斯坦纳问题 1 一．问题重述 在公园矩形区域[0,200]x[0,100]边界有给定八个 “入口”点 （20,0）（50,0）（160,0） （200,50）（120,100）（35,100）（10,100）（0,25），对道路进行设计使得在下列条件中都能 分别满足总路径长度最小和任意两点间最短道路长度不超过两点连线的1.4倍。 问题一为，在给定公园内四个道路交叉点（50,75）（40,40）（120,40）（115,70）的条 件下设计道路满足上述要求并给出算法、道路设计图以及总路程； 问题二为，在公园内任意修建道路，使其满足上述条件，并给出算法、交叉点坐标、道 路设计图以及总路程； R R R R 问题三为，在不能通过 （140,70） （140,45） （165,45） （165,70）四点1 2 3 4 所围成的矩形区域，但可以通过边界的条件下设计道路满足上述条件，并给出算法、交叉点 坐标、道路设计图及总路程； 问题四为，重新给出假设，并在此条件下设计道路满足上述条件的同时，能够最好的保 护草坪免受践踏。 二．符号说明 A={ ， ， ， ， ， ， ， ， ，···， } ~ 为公园入口 A A A A A A A A A A A A 1 2 3 4 5 6 7 8 9 n 1 8 的八个点， ~ 为公园内部路径的交叉点 A A 9 n d d  d   11 12 1n  d d  d d  21 22 2n  D=  距离矩阵， 是 到 的直线距离 ij       dij Ai Aj   d d  d