最优公交线路的模型研究

《最优公交线路的模型研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优公交线路的模型研究摘要本文以乘车的路线为研究对象，根据乘客的不同需求，存在总时间、总费用、换乘次数三个目标函数。将求解目标函数最优值的问题转化为最短路径问题。在仅考虑公汽线路的时间最短模型中，首先由已知信息建立有向赋权图，以公交站点为顶点，所有直通公交线路为边。对于时间，每条边的权值为公交车的运行时间加上转车时间。然后可直接采用Dijkstra算法求出任意两公汽站点之间最优线路。该模型方法比较简单，准确性高，可操作性强。且对图中的权值做相应的改变，可以将其转化为总费用最少模型以及换乘次数最少模型。同时考虑公汽和地铁线路，存在公汽与地铁的换乘问题，基于该问题本文设计了另一种有向赋权图，以所有

2、公汽站点和地铁站点为顶点，所有直接连通线路为边。以时间最短作为目标，边的权值设为两点间实际运动的时间。并相应地提出一种修改的Dijkstra算法，在拼接两条邻边时，会加上换乘时间。根据这种算法可得到任意两公交站点之间的较优线路，该算法效率较高。但在求解中发现，该方法并不能总求得最优解，因为到某一站点的最短路不仅仅由其前面的一个站点的最短路决定。基于这个问题，本文采用双层Dijkstra算法，在该算法中，考虑一站点对其以后两站的最短路径的影响。双层Dijkstra算法复杂度较高，但运用该算法可以得到更优化的线路。统计结果表明，修改的Dijkstra算法求得的最优解中，有5.7%的解可以被双层Di

3、jkstra算法的最优解更新。类似的，双层Dijkstra算法也可以求解总费用最少模型和换乘次数最少模型。仅考虑公汽线路，6对站(1)S3359→S1828(2)S1557→S0481(3)S0971→S0485(4)S0008→S0073(5)S0148→S0485(6)S0087→S3676的总时间最短的线路所对应时间分别为64、99、103、59、102、46（分钟）；总费用最少的线路所需费用分别为3、3、3、2、3、2（元）；总换乘次数最少的线路所需换乘次数分别为1、2、1、1、2、1（次）。同时考虑公汽和地铁线路，本文求得6对起始站→终到站的总时间最短的线路所需时间分别为62、99、

4、95、53.5、86.5、30（分钟）；总费用最少的线路所需费用分别为3、3、3、2、3、2（元）；总换乘次数最少的线路所需换乘次数分别为1、2、1、1、2、0（次）。最后，本文对模型进行了评价和推广，使其能更好的应用于实际生产生活中。关键词双层Dijkstra算法，最短路径1421.问题分析1.1.问题背景及分析奥运会即将来临了，届时有很多观众希望方便快捷的到达各个比赛场地，公交出行成为很多人的首选。北京市的公交线路已达800条以上，因此乘客面临多条线路的选择问题。本文的核心是提出一个解决公交线路选择问题的方案。根据对实际情况的考虑并结合北京公交网和北京地铁网提供的线路搜索需求，本文认为查询

5、者的需求主要为总时间短、总费用低、换乘次数少。这三种需求对应的三个目标函数的最优解的求解与最短路径问题相似。现在如果把三个目标函数的最优解的求解转化为最短路径问题，就会遇到以下两个问题：（1）同时考虑公汽线路和地铁线路时，线路比较复杂，如何用已知的线路信息建立有向赋权图（2）建立有向赋权图之后，图论中传统的最短路径算法是否适用。如果不适用，是否可以对传统的最短路径算法做相应的改变，使其改变后可以求解已经建立的有向赋权图，或者是否可以提出新的算法用来求解已经建立的有向赋权图。基于这两个问题，考虑两种解决办法：（1）考虑简单的公交线路，即只考虑公汽线路。根据已知公汽线路的信息建立有向赋权图，使该有

6、向赋权图的最短路径问题可以直接求解（2）同时考虑公汽线路和地铁线路。首先，根据已知公交线路的信息建立有向赋权图，使得该有向赋权图包含实际情况中的任意一种情形。其次，对传统的最短路径算法做改变使它可以求解已经建立的有向赋权图。1.2.题中数据的两个问题及修正除L290外，其余环行公交线路所标的首站和末站均相同。而环行线L290的首站为S1477，末站为S1479。根据L066可知S1477和S1479为相邻两站，故认为此线路的最后少标了一个S1477，实际仍为环行线。普通线路L406的起点站和终点站相同，均为S1871。L406的第二站为S1008，倒数第二站为S0941，由L034可知，S10

7、08和S0941相邻，故认为数据没有问题。但是从实际情况看，这样的线路会被当作环线使用，而不会在S1871让乘客强制下车。所以我们把L406改成环线。2.模型假设2.1.总时间=乘客到达最后一个公汽站的时刻－乘客离开第一个公汽站的时刻；2.2.假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)；2.3.换乘交通工具所用时间分为等待时间和步行到站点时间两部分.(题目中给出了换