《最优路线设计终稿》由会员分享，可在线阅读，更多相关《最优路线设计终稿（23页珍藏版）》请在金锄头文库上搜索。
1、组员:颜定勇张烨郭涛最优线路的设计方案摘要本文研究的是最佳路线设计的问题。洪水退后由于洪水对以 前道路的破坏，某县领导班子一直决定针对全县各乡（镇）修一条高 级公路，解决全县的交通问题，以便于下乡考察灾情、组织自救 运 输救援物资等。要求高级公路尽可能地均衡的分布在全县个乡镇。为 了解决此问题，我们先用运用赋权图和Dijkstra和floyd最小距离 算法来设计线路，提出运用层次分析法（AHP）来进行路线方案的比 选。利用Dijkstra算法和层次分析法解决最优线路设计问题。此问题 分析分为两个类型，第一类是距离最短问题，第二类是路线最优问题。 根据建设成本，建成后的经济效益和服务的人口数量等
2、不同的准则目 标设计有不同的方案。另外，两个位置点边上的权表示距离，于是问题就成为在加权图 中寻找一条经过每个位置点至少一次的最短闭通路问题，即求最佳哈 密尔顿圈（H圈），也即是NP-完备问题。最后，我们对模型进行了适当改进与评价，使其更具有实用价值。关键词：公路路线、层次分析法、图论、Dijkstra算法、Floyd算法一、问题重述公路线路设计选择是道路建设中的重要一环，路线方案选择的合 理与否，直接影响到项目的经济性和技术性。而通常在路线设计过程 中，会有许多不同的方案，因此，如何从多个路线方案中设计出最佳 的路线方案就显得十分重要。一般在路线设计中，不仅要考虑路线的 走向是否合理、技术性
3、能指标的高低，而且还要考虑到其工程量的大 小、建设费用、施工难易程度、对环境的影响以及养护维修方便与否 等因素。通常人们对于路线方案的愿望有：希望道路的造价在保证质 量的前提下尽可能的低;希望道路建设后的社会经济效益要尽可能的 大；同时，在环境保护日益受到重视的情况下，还要考虑道路修建后 对周边环境的影响要尽可能的小；另外，在道路建设过程中，还要求 道路的线形指标要尽可能的高，施工难度要尽量小等。本文需解决的问题：为了加快某县城的发展，此县城准备修建一条高级公路，其地图 大致如图1所示，请你根据人口因素和线路距离因素，为此县城设计 一条比较合理的线路图。图中各个乡与乡之间的距离均已标注，设计线
4、路时可忽略村与乡之间的距离，首先需考虑乡与县之间距离即可。图一二、模型假设2.1由于地图上只标注了两点间距离，而未给出地面实际情况， 所以我们可以假设路面平坦，无需建造桥梁和隧道等，忽略建造难易 程度对路线选取的影响。2.2假设建造单位长度的道路成本相同，也即是建造成本与路线 长度成正相关。2.3假设建成后的经济效益与它所服务的人口数量成正相关，建 设对环境的影响暂时不考虑。2.4假设两点之间的高级公路可以建设成近似为直线，因此可以将路程大小近似为直线距离。2.5由于人口分布未知，我们可以假设人口分布均匀，因此，为使服务人口数量最大化，可以考虑使线路遍及各个乡。三、符号说明W ( i, j )
5、表示第i个乡镇邻接的第j个乡的距离w (o)为最远乡离到县城的距离y (i)为第i个乡的人口数u ( i )为第i个乡u (0 )为县政府所在地四、建立模型4.1通过问题的分析，建立目标规划模型，于是优化目标为：Min17工W ( i，j) 口士 MinW (0)且有i , j = 117MaxE y (i)i=i4.2模型的分析对于目标，为了使总距离最小，各个乡到县城路程最短，最好是每个乡到县城修建一条高级公路。如此虽然可以使各个乡离县城路程最小，但工程巨大，修建成本太高，占用面积太广，显然不符合现实需要，因此这一方案显然不可取，所以得考虑新方案。我们由假设可以将地图简化为下图（由于只考虑乡
6、对线路设计的影响，所以将村从地图上略去）。如图二所示：图二根据以上图形，以两乡之间的距离为权，并且按照一定的比例将距离缩小为以下数据，然后做出赋权图，如图三所示：OOOO并根据赋权图写出带权邻接矩阵:W二0111.21.1 OO 1 OO OO OO OO OO OO OO OO OO OO OO101 OO OO OO OO OO OO OO OO OO OO OO OO OO OO 1.51101 OO OO OO OO OO OO OO OO OO OO OO OO OO OO1.2 OO 1 01 OO OO OO OO OO OO OO OO OO OO OO OO OO1.1 OO
7、 OO 1 0 1.51 OO OO OO OO OO OO OO OO OO OO OOOO OO OO OO 1.50 OO OO OO OO OO OO OO OO OO OO OO1 OO OO OO 1 OO 01.2 CO OO OO OO OO OO OO OO OO OOOO OO OO OO OO OO 1.2 0 1.4 00 1.4 00 OO OO OO OO OOOO OO OO OO OO OO OO 1.4 0 1.7 00 oo OO OO OO OO OOOOOO OO OO OO OO OO OO OO 1.7 0 1.4 00 1.5 00 oo oo o
8、oooOO OO OO OO OO OO OO 1.4 CO 1.4 0 1.2 00 oo OO OO 1.3ooOO OO OO OO OO OO OO OO OO OO 1.2 0 1.3 1.2 00 OO ooooOO OO OO OO OO OO OO OO OO 1.5 oo 1.3 0 oo oo oo ooooOO OO OO OO OO OO OO OO OO OO OO 1.2 OO 0 1.21.1 1.5ooOO OO OO OO OO OO OO OO OO OO OO OO OO 1.20 oo ooooOO OO OO OO OO OO OO OO OO OO
9、OO OO OO 1.1 OO 01.1ooOO OO OO OO OO OO OO OO OO OO 1.3 oo OO 1.5 OO 1.102OO 1.5 oo OO OO OO OO OO OO OO OO OO OO OO OO OO 204.3模型求解：利用数学软件matlab求出各个乡距县城最短距离线路为: u0*uulJ uH u15 ;U0l u2:U0-+ u3:U0 一 u4 - u5:U0 一- u6 一- u7 - u8 一- u7 -u10 9 一 10 11 12 ull 一*u13 - u14。解得u1至u17到县城最小距离分别为1,1，1.2，1.1，2.6，
10、1，2.2，3.6 ,5，3.6， 4.8 ，6.1， 6 ，7.2, 5.6 ， 4.5 ，2.5。如此设计可以使每个乡都得到良好的服务，即服务人口数量达到最大 化，实现每个乡到县城的路线最短。最短线路图四如下：图四K结果分析及路线改进：以上路线虽是各个乡镇到县城最短路程,但由于某些地方建设费用过高，所以在实际生活中不太现实。例女M(0,3) = 1.2 , w(3,4) = 1 所以对路线做适当的修改，修改结果如下：u0ul, u17 ul u15 ;U u2:U0 u4 u u -_ u5:U0 u6 一 u7 - u8 u7 u10 u9 10 11 12 ullu13 u14。其路线
11、图五如下：0 4图五适当修改之后，可使建设成本适当减小。为判定这两条路线哪一条路线更优，我们采用层次分析法对路线 进行最优选定。首先建立层次分析法的三个层次，大致如下:目标层:准则层:目标层:权向量构造：采用19标度法，构造判断矩阵如下表1所示。其中第二层（准 则层，简称B层）对第一层（目标层，简称A层）的成对比较矩阵设 为矩阵BA,矩阵BA的取值如下：表1准则层对目标层的判断矩阵AB1B2B3B111/23B2215B31/31/51记判断矩阵的最大特征值为A ，与最大特征值相对应的特征向max量记为W （向量W要作归一化处理），那么向量W的分量w则为相应i元素排序的权值。为检验上面构造的判
12、断矩阵是否合理，还需要对判 断矩阵进行一致性检验。根据层次分析法，判断矩阵的一致性指标 CI为：CI =（九-n）/ （n - 1）max其中：人 为判断矩阵的最大特征值。n为判断矩阵的阶数。为判断max判断矩阵是否具有满意的一致性,还需要利用判断矩阵的平均随机一 致性指标RI。对于1-10阶判断矩阵，RI的取值列于下表3中。表3平均随机一致性指标RI的取值维数n12345678910RI0.000.000.580.901.121.241.321.411.451.49当判断矩阵的随机一致性比率CR=CI/RI0.1时，则认为判断 矩阵具有满意的一致性，否则需要调整判断矩阵，使之具有满意的一 致
13、性。本文采用数值计算软件Matlab来求解判断矩阵的最大特征值及 其特征向量，通过计算易得判断矩阵BA的最大特征值及其特征向量 如下：A =5.2294maxWba 二0.3000 0.4532 0.1165 0.0887 0.0416因此判断矩阵的一致性指标为：CI 二 0.0574， CR 二 0.0512 0.1。所以判断矩阵BA具有满意的一致性。即路线二通过一致性检验，改进路线满意程度更高。五、模型的改进与评价5.1由于人口分布未知，模型假设人口分布均匀；若各乡镇人口 分布不均匀，可以对每个乡镇人口在全县人口中所占比重的系数进行 修正，用修正来的系数乘以各乡镇所要修高级公路的长度，再使
14、各乡 镇的该乘积均匀。5.2该问题实际上是一个一般推销员问题，是一个已被论证的 NPC问题，至今仍无有效的算法。求最优路线我们通过武权图和 Dijkstra和floyd最小距离算法来设计线路，并运用层次分析法(AHP )来进行路线方案的比较，选出最优路线，简单易行、可操作 性强。5.3我们的策略改进方法也不能保证求得最优解，但已接近最 优。并且所提出的策略能大幅度减少人工计算量，运用计算机计算, 可以降低出错率。参考文献【1】杨桂元黄几立/主编，数学建模M,合肥：中国科学技术大 学出版社，2008.8【2】杨溪 王海龙谭学平，灾情巡视路线网络模型J，廿肃高师学 报，第4卷第2期(1999)【3】俞文，多旅行商路线的几个问题J，数学的实践与认识，第29卷第1期，1999年1月【4】百度数学建模论坛附件：所使用程序代码：function D,R二floyd(a)%输入参数a是距离矩阵,输出参数D是最短路矩阵,R是最短路的路径矩阵n二size(
