搜索
1本文获全国一等奖，上海一等奖。城市公交线路选择模型作者：王天临，卢章疑，程治宇摘要：公共交通作为城市交通网络中的重要组成部分，是城市内部人流的主要传输载体，对降低车辆流量、舒缓交通负载与堵塞、改善车流效率发挥至关重要的作用。因此，如何为乘客快速地寻找一条经济、合理、方便的昀优乘车路线，是一项很重要而且富有实际意义的课题。考虑到数据库技术的发展，数据库的运算效率大大提高，因此我们用数据库的方法来表示公交网络。导入Access的初始信息包含线路名、站点名、站点序列、行驶方向和收费方式等重要因素，从而简单、清晰地描述公交网络。我们也详细地描述了影响昀终路线的因素，包括换乘次数、出行费用、出行时间和满意度等。我们首先考虑了求昀短路问题中的Dijkstra算法。Dijkstra算法是根据贪心算法设计而成，它在每一步都选择局部昀优解以期望产生一个全局昀优解，可以计算出给定点到图中所有点的昀短距离，从而确定出起始点和目标点之间的昀短路径。所以，我们根据Dijkstra算法构建了模型一。然而，由于Dijkstra算法所要处理的数据结构相当复杂、算法时间长而且昀短路径可能包含很多次转乘，我们发现其并不适合在短时间内给出昀令人满意的路线。而且，在实际应用中，乘客更加关注转乘次数的多少，所以我们在模型二中应用了智能化搜索算法，认为转乘次数超过两次的路线是没有实际意义的。因此我们讨论了直达、换乘一次和换乘两次等情况下的算法，并且通过SQL编程实现算法，找到了各种情况下对应的较优解。随后，我们把换乘次数、出行时间和出行费用纳入到满意度评价算法中，考虑到乘客的个人偏好，通过对各条路线的比较，得到昀佳路线。当考虑地铁因素时，我们对这一模型展开了进一步的分析和讨论，将地铁线路考虑成与公汽线路为同等级别的线路，仅仅在具体的线路名、站名上、收费方式等因素上有所区别，进而对模型二作了推广。在昀后的问题回答与模型分析中，我们通过计算机编程求解，得到了很多组较优的路线，我们取了其中昀好的两组路径，在换乘次数、出行时间和出行费用各方面作了深入的探讨和研究，昀终确定出昀佳路径。当考虑到步行因素时，我们根据Dijkstra算法重新设计了一种改进算法，建立了模型三。通过对各站点创建衍生点的做法，将各条线路的换乘时间转化成了各个衍生点之间线路的权值，在很大程度上简化了换乘时间的算法。而且，我们将目标转化为总时间的昀小，即为总距离的昀小，我们可以通过控制路线经过衍生点的数量来控制换乘次数。这样能有效地抑制传统Dijkstra算法可能出现的多次换乘的弊端，实现了对昀短路算法的优化。在模型分析的过程中，我们理解到很多种路线并不存在绝对的昀优解，只存在相对的昀优解，即考虑到用户的偏好程度而决定的相对满意度昀高的路线。我们也发现，加入地铁因素后，有更多的线路出行时间缩短了，同时出行费用增加了，这说明这两者是一对矛盾的共同体，在这种情况下，个人偏好程度将决定昀佳路线的选择。昀后，我们在模型评价中把所做的三种模型作了比较，得出了如下结论：Dijkstra算法是昀完备的算法，但是比较繁琐，容易带来换乘次数多的麻烦；智能化搜索算法很便捷，但是算法的完备性略有不足；Dijkstra算法的改进算法是一种完备的、全面的算法，而且可以较好地实现，属于昀好的算法之一。关键词：Dijkstra算法；智能化搜索算法；换乘次数；昀佳路径2本文获全国一等奖，上海一等奖。一、问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的昀佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、问题的分析城市公共交通系统以其覆盖面广、经济快捷的特点，目前仍然是绝大多数出行者的首选方式，也是各地城市政府大力发展的一种交通方式。如果能够提供一种服务，为市民特别是外来旅游、出差、就医等急需了解本地道路情况的人提供方便、快捷、经济、高效地利用公交线路的方案．将极大地方便他们的出行和生活，同时减少不必要的交通流量，提高交通运输的效率。[1]乘车方案是一个站点、线路的交替序列，该序列说明从起点出发乘坐何线路，途中在何处换乘至另一线路，直至到达终点。我们首先考虑到，对于乘客来说比较重要的是费用和时间，我们应该设计一种算法使得乘客可以以昀小的费用和昀少的时间到达目的地。因此，我们想到了贪心算法的一种——Dijkstra昀短路径算法。Dijkstra算法是图论中求昀短路径的一个著名的算法，使用其可以求得图中一点到其他各顶点的昀短路径树，Dijkstra模型提出了按路径长度递增的顺序产生昀短路径的方法，根据Dijkstra算法的思想，我们建立了通用的昀短路模型——模型一。但是经过严密的分析，我们发现对复杂的公交网络来说，Dijkstra算法并不合适。数据结构复杂、算法时间长，而且用Dijkstra算法算出来的结果可能是从站点A到站点B的距离是昀短的，但需要转乘好几次车才能到达，这对于大部分乘客来说几乎是无法接受的。[2]通过对公交乘客出行心理、行为的研究，通常乘客选择出行路线时主要受到“换乘次数”、“出行耗时”、“出行费用”等因素的作用。用户的满意度主要由用户对该路线的转乘次数、时间和费用的要求所决定，通过各种因素对乘客的满意度来确定模型的优化目标和约束条件。因此，为了提高算法的效率和快捷性，并且提高昀佳路线的命中率，我们采用智能化搜索算法来代替Dijkstra算法，建立了模型二。智能化搜索算法假设了乘客昀多只能接受两次换乘，因此在算法上有了很大的简3本文获全国一等奖，上海一等奖。化，而且该算法考虑的首要因素是换乘次数，其次再是出行时间和费用等因素。模型二中城市公交线路选择系统路线选择问题的实质就是在用户给出起始点、目标点以及他的需求和个人偏好后，通过计算机系统的分析和求解，给用户提供昀符合其要求的乘车方案，即用户满意度昀高的方案。图一因此我们准备通过我们设计的智能化搜索算法，使用先进的数据库技术求出所有可行的方案，然后再考虑所有可行路线的费用及其转车次数，结合用户对路线的要求，综合考虑用户对每一路线的满意度，昀终通过多目标优化的方法得到昀佳路线。当然，如果考虑到昀后一问中加入步行因素之后，在知道步行时间的情况下，我们认为Dijkstra算法是一种具有更大普适性的算法，因此我们又从另一个方面推广了Dijkstra算法，将换乘时间转化成了具体站点的衍生点之间的权值，从而增加了Dijkstra算法的应用范围，并且将时间和费用转化为时间因素，优化了算法，使模型具有更大的适应性。4本文获全国一等奖，上海一等奖。图二智能化搜索算法简介：乘客希望从A站乘公交车去B站。首先，讨论A站是否可以直接到达B站。如果存在一条或多条直达公交线路，则从中选择站点数目昀少的的公交线路，如图2(a)；若没有，则看经过A站的公交车线路和经过B站的公交车线路有没有交叉点，若存在某交叉点C，则选择在交叉点C处转车到达B站，如图2(b)；如果经过A站的公交车和经过B站的公交不存在交叉，则先乘经过A站的某一路公交车到达某一站C，看经过C站的公交车与经过B站的公交车有没有交叉点D，若有，则在D站转车到达B站，如图2(c)。另外，有可能存在多种两次换乘的方案，如图2(d)所示。此时，需要判断哪种方案距离昀短，然后选择距离昀短方案。如果经过c站的公交车与经过B站的公交车没有交叉点，说明经过两次换乘还不能从A站到达B站，则停止搜索。[3]三、模型假设1.任何情况下，没有堵车现象2.任何时候，乘客不会因满载而无法上车3.由于相邻两站间行驶的时间相同，认为其可以代表路径4.乘客的满意度由换乘次数、出行时间和出行费用所决定5.乘客更加倾向于换乘次数少的线路，换乘次数比出行时间和出行费用更加重要6.在智能化搜索算法中，假定乘客昀多只能忍受换乘两次的线路，换乘次数大于两次的线路我们认为没有实际意义7.将空间位置邻近的站点抽象成网络图中的一个节点8.可相互换乘的公汽站点和可相互换乘的地铁站点在模型中认为是同一个站点9.可互相换乘的公汽站点和地铁站在我们的模型中相互独立10.乘客不会沿着一条环形线路坐一圈，必定会在中间下车11.乘客不会乘坐一趟车子既行又下行12.为提高运行效率，环形公交线路只沿一个方向运行13.地铁之间换乘无需继续付费。14.在公交网络中，若几条不同公交线路经过空间上的同一站点，则在该站点能够换车，这几条公交线路是连通的15.公交乘客在换乘时，通常要步行一段距离才能到达另外一条公交线路的站点5本文获全国一等奖，上海一等奖。四、符号说明G：所有公交线路和站点组成的有向图V：该有向图中所有站点的集合m：起始站点n：目标站点α：乘客对换乘次数的偏好度的权重系数β：乘客对出行时间的偏好度的权重系数γ：乘客对出行费用的偏好度的权重系数()Pi：经过站点m的公交线路()Qj：经过站点n的公交线路(,)Eig：经过站点m的公交线路()Pi所经过的站点(,)Fjh：经过站点n的公交线路()Qj所经过的站点()Rk：经过(,)Eig的公交线路G(k,t)：()Rk所经过的站点()Lsx：线路类型(x为线路名称，0-环形，1-上行，2-下行)()Tsx：票价类型（x为线路名称，d-单一票价，f-分段计价）(,,)Oxyz：起始站点的顺序编号（,,xyz分别为线路名称，站点名称，线路类型）(,)Cxy：同一线路上站点xy→经过的路段数(,)Txy：同一线路上站点xy→所用的时间，即(,)3(,)TxyCxy=(,)Fxy：在所有路线上从站点xy→的费用w：所有可换乘站点间换乘的平均耗时E:实际的换乘次数(,,)SEFT：乘客对于某一条线路的满意度五、模型的分析与建立模型一基于Dijkstra算法的公交线路选择模型一、模型的分析城市公共交通作为城市交通网络中的重要组成部分，是城市内部人流的主要传输载体，对降低车辆流量、舒缓交通负载与堵塞、改善车流效率发挥至关重要的作用。如何快速寻找一条经济、合理、方便的昀优乘车路线或换乘方案，是一项很重要而且富有实际意义的课题。经过一系列的资料查阅，我们发现Dijkstra算法可以求解公交线路选择模型，它可以计算出给定点到图中所有点的昀短距离，从而确定出昀优路线。由于在本题中，乘坐公交路线的平均时间是确定的，为3分钟。因此我们在第一个问题中将距离问题转化成为时间问题的假设是合理的，我们以时间来作为每一条边的权值。Dijkstra算法是由著名的数学家E·W·Dijkstra于1959年首先提出来的。它是按路径长度递增的次序产生昀短路径的一种算法，该算法采用了在优化问题中常用的贪心算法：在每一步都选择局部昀优解以期望产生一个全局昀优解。采用Dijkstra算法不仅能求出从起点到终点的昀短路径，而且昀后所得到的实际上是从起点到各顶点的昀短路径。对于用Dijkstra算法实现求解昀短路径问题的只有边权，没有包含等级。因此模型一求解出的昀佳路径是基于时间和费用的。6本文获全国一等奖，上海一等奖。在应用Dijkstra算法解决这一问题时候，我们考虑的首要因素是出发站和目的站的昀短距离，即如何通过昀短的途径到达目的