张佃中B20004018中南大学_崔蕾_吴林_孙种夷.doc

《张佃中B20004018中南大学_崔蕾_吴林_孙种夷.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、B题：乘公交，看奥运摘要针对题目所给的北京市部分公交线路，建立了多种不同目标规划下的优化模型，以满足不同类型的人们对于公交线路的不同需求。如乘车耗时短、换乘次数少、乘车耗时短以及乘车花费少。针对上述多种情况，主要考虑了三种优化模型，首先，从公交线路的图论性质着手，建立传统的最短路径问题的模型，以最短路径为约束条件，以最小换乘次数为目标函数，求得在满足路径最短的情况下，换乘次数最少的最佳乘车方案；接着，从乘客自身的心理出发，认为换乘次数是乘客选择乘车路线的第一考虑因素，以此为出发点，以最小换乘次数为约束条件，分别以乘车耗时最短和乘车花费最少为目标函数，建

2、立优化模型，求得在满足换乘次数最小的情况下，耗时最短或花费最少的最佳乘车方案。对于上述不同的模型，我们采用了不同的算法，对于第一种模型，我们采用了改进的Dijkstra算法求得最短路径，再通过将该路径上相邻两站点的线路进行合并删除，求得换乘次数最小的乘车方案。对于后两种模型，首先我们认为乘客所能接受的最大换乘次数为，接着引入直达矩阵T以及最小换乘矩阵Q，利用结论：矩阵中对应的元素表示通过（n-1）次换乘从节点的路径数。求得两站点之间满足最小换乘次数的路径，从这些路径中求得耗时最短或花费最少的乘车方案。其中对于题目所给的六个站点，同时满足乘车耗时最短和乘

3、车花费最少的最佳路径数分别为2，1，1，9，3，1，最短耗时分别为101，106，128，83，106，65min接着在此基础上，引入地铁系统，因为同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)，我们将地铁站附近的公交站点连同相应的地铁站近似同化为同一个站点，通过一定的修改站名的工作，将地铁系统并入到了公汽系统中，得到新的公交路径，在修改后的直达矩阵T的基础上求得不同目标下的最佳乘车方案。而在此种情况下，对于题目所给的六个站点，同时满足乘车耗时最短和乘车花费最少的最佳路径数分别为1，1，2，3，0，1，最短耗时分别为98，101

4、，09，77，88，25min而在问题3中，将步行作为一种出行方式，由步行方式把一些相距较近的站点连接起来。我们采用建立某站点邻集的方法，将站点联通矩阵R进行扩充，使R中记录有与每一站点相邻的结点的信息。再利用第2问的模型和方法求解相应的直达矩阵和一次及二次转乘矩阵，对于一次及二次的转乘矩阵里路径中含有步行段（即未转乘相应次数）的信息，转存至较低转乘次数的矩阵中。最后在模型推广中，我们进行了换乘次数对乘车耗时的敏感度分析，考虑增加一次换乘次数有时可有效减少乘车耗时。关键词Dijkstra算法最小换乘次数直达矩阵T1问题重述明年8月第29届奥运会在北京举

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

6、以下6对起始站→终到站之间的最佳路线，同时对所建立的模型进行评价。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、将交通线路进行扩大，加入二条地铁线路，进一步扩大了交通网络，在此基础上解决以上问题。3、进一步考虑所有站点之间的步行时间，建立任意两站点之间线路选择问题的数学模型。2基本假设1假设两站点之间的换乘次数最多为2次，超过2次认为两站点之间在公交网络中不连通。2假设在问题1中，公车换乘只发生在同一站点，即乘客在某

7、一站点下车，同时在相同站点上另外一辆车，进行换乘，不考虑距离较近的站点之间乘客通过步行换乘问题。3假设问题2中同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费).。4假设问题2中，地铁站附近的公交站点连同相应的地铁站近似同化为同一个站点。5假设在问题3中，相邻的两站点之间步行平均耗时为常数（由于相邻公汽站间行驶时间认为是平均的）。6假设在问题3中，人们可以接受的最大合理步行时间。3符号说明T——直达矩阵R——路径矩阵n——任意两站点i，j的最小换乘次数m——任意两站点i，j满足最小换乘次数的路径数r——任意两站点i，j耗时最少的最佳

8、路径数s——任意两站点i，j花费最小的最佳路径数4问题分析在城市的公共交通网络中，公交换乘是乘