最优公交线路的模型研究..doc

2007高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 北京化工大学 参赛队员 (打印并签名) ：1. 郑宇 2. 姜园博 3. 来斯惟 指导教师或指导教师组负责人 (打印并签名)： 郭秋敏 日期： 2007 年 09 月 24 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2007高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）：最优公交线路的模型研究 摘要 本文以乘车的路线为研究对象，根据乘客的不同需求，存在总时间、总费用、换乘次数三个目标函数。将求解目标函数最优值的问题转化为最短路径问题。 在仅考虑公汽线路的时间最短模型中，首先由已知信息建立有向赋权图，以公交站点为顶点，所有直通公交线路为边。对于时间，每条边的权值为公交车的运行时间加上转车时间。然后可直接采用Dijkstra算法求出任意两公汽站点之间最优线路。该模型方法比较简单，准确性高，可操作性强。且对图中的权值做相应的改变，可以将其转化为总费用最少模型以及换乘次数最少模型。 同时考虑公汽和地铁线路，存在公汽与地铁的换乘问题，基于该问题本文设计了另一种有向赋权图，以所有公汽站点和地铁站点为顶点，所有直接连通线路为边。以时间最短作为目标，边的权值设为两点间实际运动的时间。并相应地提出一种修改的Dijkstra算法，在拼接两条邻边时，会加上换乘时间。根据这种算法可得到任意两公交站点之间的较优线路，该算法效率较高。但在求解中发现，该方法并不能总求得最优解，因为到某一站点的最短路不仅仅由其前面的一个站点的最短路决定。基于这个问题，本文采用双层Dijkstra算法，在该算法中，考虑一站点对其以后两站的最短路径的影响。双层Dijkstra算法复杂度较高，但运用该算法可以得到更优化的线路。统计结果表明，修改的Dijkstra算法求得的最优解中，有5.7%的解可以被双层Dijkstra算法的最优解更新。类似的，双层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、95、53.5、86.5、30（分钟）；总费用最少的线路所需费用分别为3、3、3、2、3、2（元）；总换乘次数最少的线路所需换乘次数分别为1、2、1、1、2、0（次）。 最后，本文对模型