数学建模2007B_一等奖论文 城市公交线路选择模型

《数学建模2007B_一等奖论文 城市公交线路选择模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、城市公交线路选择模型作者：王天临，卢章疑，程治宇摘要：公共交通作为城市交通网络中的重要组成部分，是城市内部人流的主要传输载体，对降低车辆流量、舒缓交通负载与堵塞、改善车流效率发挥至关重要的作用。因此，如何为乘客快速地寻找一条经济、合理、方便的最优乘车路线，是一项很重要而且富有实际意义的课题。考虑到数据库技术的发展，数据库的运算效率大大提高，因此我们用数据库的方法来表示公交网络。导入Access的初始信息包含线路名、站点名、站点序列、行驶方向和收费方式等重要因素，从而简单、清晰地描述公交网络。我们也详细地描述了影响最终路线的因素，包括换乘次数、出行费用、出行时间和

2、满意度等。我们首先考虑了求最短路问题中的Dijkstra算法。Dijkstra算法是根据贪心算法设计而成，它在每一步都选择局部最优解以期望产生一个全局最优解，可以计算出给定点到图中所有点的最短距离，从而确定出起始点和目标点之间的最短路径。所以，我们根据Dijkstra算法构建了模型一。然而，由于Dijkstra算法所要处理的数据结构相当复杂、算法时间长而且最短路径可能包含很多次转乘，我们发现其并不适合在短时间内给出最令人满意的路线。而且，在实际应用中，乘客更加关注转乘次数的多少，所以我们在模型二中应用了智能化搜索算法，认为转乘次数超过两次的路线是没有实际意义的。

3、因此我们讨论了直达、换乘一次和换乘两次等情况下的算法，并且通过SQL编程实现算法，找到了各种情况下对应的较优解。随后，我们把换乘次数、出行时间和出行费用纳入到满意度评价算法中，考虑到乘客的个人偏好，通过对各条路线的比较，得到最佳路线。当考虑地铁因素时，我们对这一模型展开了进一步的分析和讨论，将地铁线路考虑成与公汽线路为同等级别的线路，仅仅在具体的线路名、站名上、收费方式等因素上有所区别，进而对模型二作了推广。在最后的问题回答与模型分析中，我们通过计算机编程求解，得到了很多组较优的路线，我们取了其中最好的两组路径，在换乘次数、出行时间和出行费用各方面作了深入的探讨

4、和研究，最终确定出最佳路径。当考虑到步行因素时，我们根据Dijkstra算法重新设计了一种改进算法，建立了模型三。通过对各站点创建衍生点的做法，将各条线路的换乘时间转化成了各个衍生点之间线路的权值，在很大程度上简化了换乘时间的算法。而且，我们将目标转化为总时间的最小，即为总距离的最小，我们可以通过控制路线经过衍生点的数量来控制换乘次数。这样能有效地抑制传统Dijkstra算法可能出现的多次换乘的弊端，实现了对最短路算法的优化。在模型分析的过程中，我们理解到很多种路线并不存在绝对的最优解，只存在相对的最优解，即考虑到用户的偏好程度而决定的相对满意度最高的路线。我们

5、也发现，加入地铁因素后，有更多的线路出行时间缩短了，同时出行费用增加了，这说明这两者是一对矛盾的共同体，在这种情况下，个人偏好程度将决定最佳路线的选择。最后，我们在模型评价中把所做的三种模型作了比较，得出了如下结论：Dijkstra算法是最完备的算法，但是比较繁琐，容易带来换乘次数多的麻烦；智能化搜索算法很便捷，但是算法的完备性略有不足；Dijkstra算法的改进算法是一种完备的、全面的算法，而且可以较好地实现，属于最好的算法之一。关键词：Dijkstra算法；智能化搜索算法；换乘次数；最佳路径1本文获全国一等奖，上海一等奖。一、问题重述我国人民翘首企盼的第29

6、届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的

7、模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、问题的分析城市公共交通系统以其覆盖面广、经济快捷的特点，目前仍然是绝大多数出行者的首选方式，也是各地城市政府大力发展的一种交通方式。如果能够提供一种服务，为市民特别是外来旅游、出差、

8、就医等急需了解本地道路情