16217数学建模培训课件B20004011中南大学孙国生耿文杰张强.pdf

2007高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛

承诺书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网

上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的

资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参

考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规

则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B

我们的参赛报名号为（如果赛区设置报名号的话）：20004011

所属学校（请填写完整的全名）：中南大学

参赛队员(打印并签名)：1.孙国生

2.耿文杰

3.张强

指导教师或指导教师组负责人(打印并签名)：张鸿雁

日期：2007年9月24日

赛区评阅编号（由赛区组委会评阅前进行编号）：

2007全国大学生数学建模竞赛全国大学生数学建模竞赛全国大学生数学建模竞赛

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

评

阅

人

评

分

备

注

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

公交最优线路选择模型与算法的优化

摘要

将原始数据导入EXCEL中进行预处理后，再导入MATLAB数据库中，建立数据矩阵。

对公交网络进行数学描述，采用一个四元组G(V,P,R,L)来表示整个网络、节点、线

路之间的关系。

对于问题1，在不考虑乘客步行到邻近站点坐车的情况下，建立基于换乘次数最少

的公交网络乘车优化模型，并根据乘客的不同需求对所得到的线路进行二次优化，建立

了相应的模型，对于时间、费用、总车站数等条件相同的线路，引入舒适度再次进行优

选；在算法设计方面，首先采用常规的计算机搜索方法，通过分支定界法，减少了搜索

范围，提高了运算速度，能够解决直达以及一次转乘的情况，但对于二次转乘问题运算

量很大，速度较慢。在比较了目前常用的Dijkstra、Floyd、Moorepape等算法的基础上，

采用了Dijkstra的改进模型——基于点边拓扑关系的最优路径算法，改善了数据存储结

构，减少了运算量，较好的解决了多次换乘的问题。用MATLAB7.0编程得出6对站点间

的最佳乘车路线并根据不同需求给出了详细的评价说明。（见表1）

对于问题2，采用函数的映射方法将地铁站点与换乘的公汽站点进行映射处理，并

作为数组添加到数据矩阵中，将两条地铁线转化成两条特殊的公交汽车线路，建立了基

于乘车总时间最小的优化模型，然后依次选用转乘次数最少，费用最省为第二目标函数

在所得可行线路集内进行二次优化，并对问题1的算法进行了修正。最后，用C语言编

程得出了在考虑地铁的情况时6对站点的最优线路的选择，同样给出了详细的评价。（见

表2）

对于问题