《论文：乘公交 看奥运 - 07年全国数学建模竞赛论文》由会员分享，可在线阅读，更多相关《论文：乘公交 看奥运 - 07年全国数学建模竞赛论文（25页珍藏版）》请在金锄头文库上搜索。
1、07年B题：乘公交，看奥运我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根
2、据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地
3、铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合乘公交，看奥运摘要：本文是为了开发一个解决北京市公交线路选择问题的自主查询计算机系统。在充分理解题意的基础上，我们从总体上把握，一致认为这是运筹学中的最短路问题。我们所提供的这个系统，对于当乘客输入起始站和终点站，点击查询
4、结果后，查询机就能很快地给出乘车路线及乘车所需要的最短时间，并且，还可以给出相应的乘车费用。所以，我们想到了建立网络模型来解决。对于问题一，在仅仅考虑公共汽车的换乘的时候，我们以最短的乘车时间和最优的乘车费用作为两个目标函数，建立相应的双目标规划模型：对于问题二与问题三我们同样建立了相应的数学规划模型，具体模型见正文。并利用Dijkstra算法解出我们所需要的结果。我们同样利用了双目标函数的统筹规划原理，在Dijkstra和回溯的算法下 ， 解决了在公共汽车和地铁之间换乘的问题，求得最短时间问题，找到了最合适的公交路线，均为最短的乘车时间和最有的乘车费用，从而更加完善了我们的公交系统。关键词：
5、最短行程 双目标 网络模型 Dijkstra算法一、 问题重述 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路
6、选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间
7、2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。【附录2】公交线路及相关信息 （见数据文件B2007data.rar）二 、基本假设1、按常理，人们总是在换乘两辆公汽后就不会再换其他的公汽，本模型假定可以查到换乘两次公汽所行使的路线，至于其它线路，本模型也可以
8、继续求出，但考虑到人们的观念，所以在换乘两辆车后就可以找到最优的路线，并且乘车费合理，可以被人们所接受。 2、从一站乘L车到下一战换车时，不会再乘坐同一辆车。3、最短的时间是人们首先考虑到的事情，所以在最短时间和最低费用相冲突的情况下，优先考虑时间问题。三、基本符号说明为了便于问题的说明，我们用一些符号来代替问题中出现的一些基本变量。其它的一些变量，在文中会陆续说明。i:起始站台的号数j:终点站台的号数：从i站乘l车到j站:第i个站台到第j个站台所用的最优时间权值（分钟）, :目标函数最优的乘车费（元） ：公汽的票价函数（元） ：整型函数 ，其值为1或0：换车的两站之间所隔的站台数四 问题的分
9、析考虑到问题的假设与要求，我们以最短的行车时间和最低的乘车费用作为最佳的路线和方案。题目第一问要求我们根据附录数据，仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法，并求出6对起始站终到站之间的最佳路线。实质上就是求两站之间最佳路线问题。由于题中给的数量较多，逐条路线去求最佳路线的问题是不可能的，所以我们决定用Dijkstra算法求出最佳的路线。题目的第二问要求我们在第一问的基础上同时考虑公汽与地铁线路的问题，并求出第一问所要解决的问题，实际上是将地铁看成一辆新增加的公交车，并同时考虑新增加的公交车站的问题。题目第三个问题是要求我们在假设知道所有站点之间的步行时间的情况下
10、，给出任意两站点之间线路选择问题的数学模型。 图1 最短路程问题的网络图五 问题的模型建立5.1 问题一的模型建立 为了解决这类的最优路线问题，我们采用网络理论模型来建立求解。在所求的起始站到终点站最佳问题中，仅仅考虑乘公汽的情况，也涉及到许多情况，如直接乘直达车，不经任何的中转站的，换乘K辆车（k介于1到m-1指间）等。上面的网络图（图1）反映了我们的思路：设我们所研究的问题共有n个公共汽车站点，并且我们有m个车，在第i个站点（起始站）到第j个站点（终点站）之间，我们不妨假设从1到n的乘车方法有直达车，换车并且可以换乘1辆，2辆，3辆 ，那么为了解决问题的 方便，我们假设有当车行使至第j站时
11、，我们又作如下假设：在题目给定的条件下，在仅考虑公交路线的情况下，我们可以的得到任意两站（i和j站）之间的最优乘车时间值，我们给出公式： （1）即所求的最优时间为行使的时间和换乘时间的和。 所求的最优时间要受到如下的7个条件约束：以上目标函数是公交车行使的时间和换乘时间的和，其中是从第站点到第站点辆车所经过的总站点数，是转车次数。表示出发站应满足的条件，即乘客必须乘某一车次前往某一站。表示目的站应满足的条件，即乘客必须乘某一车次经某一站到达目的站。表示在第j站作为中间站点时，若有车次经过则式子左边的值为0，若此站作为终点站则式子左边的值为1，即有进无出去的情况。 表示第i站作为中间站点时，若有
12、车次经过则式子左边的值为0，若此站作为起点站则式子左边的值为1，即车辆有出无进的情况。表示车辆与某站点的关系，若某车辆既不进也不出某站点，此式子左右两边都为0，若车辆既从此站点进去同时也从此站点出来，则此式子左右两边都为1。分为以下几种情况：1）假如车辆没有经过某站点，此时的值为0，同时的值也为0，中间的式子为0;2)假如车辆经过了某站点且没有转车，此时的值为1，同时的值也为1，中间的式子为0；3）假如车辆经过了某站点且有转车的情况，对于转车前的车，此时的值为1，同时的值也为0中间式子为1；对于转车后的车有的值为0，同时的值也为1，中间式子为-1。这三种情况的结果符合模型前的换车函数。上述目标
13、函数是基于时间最短而得出的最佳路线，这是人们在实际生活中乘公交车最基本的要求，所以此项指标作为评价一条路径好不好的最重要的指标。但是同时人们也会考虑到乘车的花费多少，所以在选择公交车时会对路径和花费进行综合考虑，即要求到达目的地的时间最短且花费最小。下面我们针对这种情况给出了模型及其方案，并相应得出最短时间和最少花费。所以综合得出最终的模型为： 第二个目标函数是求最小花费，其中表示某一辆车从第i站点到第j站点中间所经过的站点数，表示票价函数，其函数式子为： ，其他的式子表示的含义同上面的约束条件中的解析。5.2 问题二模型的建立问题二中要求考虑乘客可以乘坐地铁交通工具，因此我们依据问题一中的模
14、型，考虑如下因素：1）乘客选择的交通工具为公交或地铁，此时相应地有变量：2）乘客可由公交车转乘地铁，此时相应地有变量及约束条件：3）乘客可由地铁转乘公交车，此时相应地有变量及约束条件：4）乘客可由地铁转乘地铁，此时相应地有变量：5）乘客在公交站可不换公交车、或可转乘公交车、或可转乘地铁，但三种选择不可同时进行，因此相应的有约束条件，6）乘客在D12及D18地铁站可不换地铁线、或可换乘公交车、或可换乘地铁线，但三种选择不可同时进行，因此相应的有约束条件：综合以上因素，即相应的新的乘车时间及票费的计算，我们建立如下的双目标规划模型：5.3 问题三的模型建立问题三中要求考虑乘客可以采用步行方式，因此
15、我们依据问题二中的模型，考虑如下因素：1）乘客选择的交通工具为公交或地铁或步行，此时相应地有变量：2）乘客可由公交车转为步行方式3）乘客可由地铁转为步行方式 5）乘客在公交站可不换公交车、或可转乘公交车、或可转乘地铁，或转为步行方式，但四种选择不可同时进行 6）乘客在D12及D18地铁站可不换地铁线、或可换乘公交车、或可换乘地铁线、或改为步行方式，但四种选择不可同时进行，因此相应的有约束条件：综合以上因素，即相应的新的乘车时间及票费的计算，建立如下的双目标规划模型： 六 模型的求解6.1 模型一的求解为求最优时间和费用的目标函数即：，我们决定用Dijkstra算法来解决这类最短路问题，我们是通过LINGO软件来实现的。经过计算机的编程运行解决后，得到问题一的解决方案，下面是在仅考虑公共汽车之间的换乘问题，给替乘车者提供最优路线的方案。
