公交车数学建模

   本文是为了开发一个解决长沙市公交线路选择问题的自主查询计算机系统。在充分理解题意的基础上，我们从总体上把握，一致认为这是运筹学中的最短路问题。我们所提供的这个系统，对于当乘客输入起始站和终点站，点击查询结果后，查询机就能很快地给出乘车路线及乘车所需要的最短时间，并且还可以给出相应的乘车费用。也可以在有多个乘车站点的情况下，自主选择出最优乘车顺序以及相应的乘车最短时间和乘车费用。

公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，我们设计了一个解决公交线路选择问题的自主查询计算机系统。其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。

对于问题一，在仅仅考虑公共汽车的换乘的时候，我们以最短的乘车时间和最优的乘车费用作为两个目标函数，建立相应的双目标规划模型：和。

对于问题二，在问题一的基础上，我们添加了排列组合模型，全列出所有的乘车顺序情况，由问题一所建模型求出各种情况下的最优时间和最优路费，然后综合比较选出所有情况中的最优乘车顺序。

利用Dijkstra算法解出我们所需要的结果。我们同样利用了双目标函数的统筹规划原理，在Dijkstra的算法下 ， 解决了在公共汽车换乘的问题，求得最短时间问题，找到了最合适的公交路线，均为最短的乘车时间和最优的乘车费用，从而更加完善了我们的公交系统。

本文的特点是在建立模型和算法的基础上，进行编程，使其具备系统查询功能，克服了人工查询数据的繁杂过程，使得到的结果更为准确，同时，此程序可以进行推广使用，为解决日常生活中最优路径的选择问题提供了方法，给人们的出行带来方便。

关键词：最短行程  双目标 网络模型  Dijkstra算法 排列组合

一、 问题重述

公共交通作为长沙市交通网络中的重要组成部分，由于公共交通对资源的高效利用，使得通过大力发展公共交通，实行公交优先成为缓解日趋严重的道路交通紧张状况的必然选择。然而，面对迅速发展和不断更新的长沙市公共交通网，如何快速的寻找一条合理的乘车路线或换乘方案，成为长沙市居民和外地游客一个比较困惑的问题。根据长沙市居民和外地游客的需要研究公交出行路径优化算法，寻找并提供一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案，是公共交通系统中最基本最关键的问题。

一公务人员从长沙火车站（五一路火车站）下车在一天时间内到如下地点：长沙市、中南大学新校区、黄兴路步行街办事，并回到长沙火车站（五一路火车站）

1．设计按如下顺序：长沙火车站、长沙市、中南大学新校区、黄兴路步行街，并回到长沙火车站（五一路火车站）完成事务的乘坐公交车的可行方案，并给出相应的数学模型。

2．设计从长沙火车站出发遍历问题一中所有地点完成事务的乘坐公交车的可行方案，并给出相应的数学模型。

二 、基本假设

1、按常理，人们总是在换乘两辆公汽后就不会再换其他的公汽，本模型假定可以查到换乘两次公汽所行使的路线，至于其它线路，本模型也可以继续求出，但考虑到人们的观念，所以在换乘两辆车后就可以找到最优的路线，并且乘车费合理，可以被人民所接受。 

2、从一站乘L车到下一站换车时，不会再乘坐同一辆车。

3、最短的时间是人们首先考虑到的事情，所以在最短时间和最低费用相冲突的情况下，优先考虑最优时间问题。

4、随着长沙公交运输系统的完善，市民出行将更多采用公交系统，针对本次数学建模题目，步行作为次要因素便不予考虑。

5、基本参数设定

相邻公汽站平均行驶时间(包括停站时间)： 3分钟

公汽换乘公汽平均耗时： 5分钟

公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：

0～13站： 1元；

14～26站：2元；

27站以上：3元

三 问题的分析

考虑到本题的假设与要求，在公交线路的选择时，需要考虑乘车时间、换乘次数、乘车费用以及舒适度等因素。考虑人们出行乘车时的心理情况和对相关研究结果，可以认为“换乘次数”是大部分公交乘客在选择出行路线时优先考虑的因素，其次是距离长短和出行耗时。而出行耗时与换乘的次数，等车的时间以及距离的长短密切相关。因此，出行耗时和距离长短的要求可以转化为换乘次数最少的条件下出行距离最短的问题，我们以最短的行车时间和最低的乘车费用作为两个目标函数，建立相应的双目标规划模型。

问题一中涉及四个站点，对应四对起始-终止站。实质上就是求两站之间最佳路线的问题：要求我们在已知乘车顺序的情况下，给出任意两公汽站点之间最佳线路选择问题的一般数学模型与算法，并求出从起始站至终点站之间的最佳路线。反映在此题即是求出四对起始-终止站之间各自的最优路线，综合其方案即为问题一所求之答案。

问题二中各站点与问题一中相同，其区别在于有序到站与遍历各站。本质上来说问题一即是问题二的一种特殊情况，需要解决的是中间站点的到站顺序问题。根据排列组合的原理，共有种方案。可根据问题一所建模型逐条算出各方案所需时间与费用，总结比较后可得问题二最优方案。

四 问题的模型建立

问题一

符号说明：i:起始站台的号数

j:终点站台的号数

：从i站乘l车到j站

:第i个站台到第j个站台所用的最优时间权值（分钟）,

：目标函数最优乘车时间（分钟）

：目标函数最优的乘车费（元） 

：公汽的票价函数（元） 

：整型函数 ，其值为1或0

：换车的两站之间所隔的站台数

：各部分目标函数最优乘车时间之和

：各部分目标函数最优的乘车费之和

公交线路模型建立

    为了解决这类的最优路线问题，我们采用网络理论模型来建立求解。在所求的起始站到终点站最佳问题中，仅仅考虑乘公汽的情况，也涉及到许多情况，如直接乘直达车，不经任何的中转站的，换乘K辆车（k介于1到m-1指间）等。上面的网络图（图1）反映了我们的思路：

设我们所研究的问题共有n个公共汽车站点，并且我们有m个车，在第i个站点（起始站）到第j个站点（终点站）之间，我们不妨假设从1到n的乘车方法有直达车，换车并且可以换乘1辆，2辆，3辆 ……，那么为了解决问题的 方便，我们假设有

当车行使至第j站时，我们又作如下假设：

在题目给定的条件下，在仅考虑公交路线的情况下，我们可以的得到任意两站（i和j站）之间的最优乘车时间值，我们给出公式：

          （1）

在所求的结果中，寻找出最小值。

即所求的最优时间为行使的时间和换乘时间的和。 所求的最优时间要受到如下的7个条件约束：

以上目标函数是公交车行使的时间和换乘时间的和，其中是从第站点到第站点辆车所经过的总站点数，是转车次数。

表示出发站应满足的条件，即乘客必须乘某一车次前往某一站。

表示目的站应满足的条件，即乘客必须乘某一车次经某一站到达目的站。

表示在第j站作为中间站点时，若有车次经过则式子左边的值为0，若此站作为终点站则式子左边的值为1，即有进无出去的情况。

 表示第i站作为中间站点时，若有车次经过则式子左边的值为0，若此站作为起点站则式子左边的值为1，即车辆有出无进的情况。

表示车辆与某站点的关系，若某车辆既不进也不出某站点，此式子左右两边都为0，若车辆既从此站点进去同时也从此站点出来，则此式子左右两边都为1。

分为以下几种情况：

1）假如车辆没有经过某站点，此时的值为0，同时的值也为0，中间的式子为0;

2)假如车辆经过了某站点且没有转车，此时的值为1，同时的值也为1，中间的式子为0；

3）假如车辆经过了某站点且有转车的情况，对于转车前的车，此时的值为1，同时的值也为0中间式子为1；对于转车后的车有的值为0，同时的值也为1，中间式子为-1。这三种情况的结果符合模型前的换车函数。

上述目标函数是基于时间最短而得出的最佳路线，这是人们在实际生活中乘公交车最基本的要求，所以此项指标作为评价一条路径好不好的最重要的指标。但是同时人们也会考虑到乘车的花费多少，所以在选择公交车时会对路径和花费进行综合考虑，即要求到达目的地的时间最短且花费最小。下面我们针对这种情况给出了模型及其方案，并相应得出最短时间和最少花费。所以综合得出最终的模型为：

第二个目标函数是求最小花费，其中表示某一辆车从第i站点到第j站点中间所经过的站点数，表示票价函数，其函数式子为：         

其他的式子表示的含义同上面的约束条件中的解析。

        有                   

问题二

   符号说明： ：所需遍历站点数(起点、终点已确定，中间站点无重复)

              ：各站点第m种排列组合下的目标函数最优乘车时间

              ：各站点第m种排列组合下的目标函数最优的乘车费

可知此问题为问题一的普适情况。

因此，我们先假定所需遍历站点总数为，由排列组合原理，在起点、终点已知的情况下共可列出种路线。

根据问题一的模型可算出当中某一值时的目标函数最优乘车时间和目标函数最优的乘车费

    即               

 比较每种路线的结果后 

          得     

 便可知取最优时间路线或最优价格路线是所对应的值，从而选出最优情况的排列组合，此方案即为第二问之答案。

五 模型的求解

 5.1 模型一的求解

为求最优时间和费用的目标函数即：，

我们决定用Dijkstra算法来解决这类最短路问题，我们是通过LINGO软件来实现的。经过计算机的编程运行解决后，得到问题一的解决方案，下面是在仅考虑公共汽车之间的换乘问题，给替乘车者提供最优路线的方案。

乘车最优方案

5.2 模型二的求解

    在问题一的基础上，我们又需要在已知四个站点的情况下，根据排列组合所列的六种情况，综合比较得出遍历各站点的最优乘车方案。

乘车最优方案

乘车顺序为：长沙火车站—黄兴路步行街—中南大学新校区—长沙市—长沙火车站

六 模型的推广

通过对题目的解读我们不难发现这是一类运筹学中的最短路问题。我们建立了一个双目标的网络的模型。仔细分析我们建立的模型不难发现：这个模型不仅仅适用于乘公交车配置问题，即最短路和最低费用的问题，它对图论类的优化问题的求解都可以起到指导作用。

最短路问题是运筹学的图论的一个重要分支。它在解决乘公交车的路径选择，都发挥着重要的作用。

本文模型的建立是为了解决最优的公交路线的问题，既要考虑到乘车时间的最短问题，又要考虑到公交费用的问题。通过网络模型的建立最优化乘车路线。决策者要通过概念抽象、关系分析可将各类影响因子放入网络模型中，可以通过相关的计算机软件得到兼顾全局的最优解。

本题的求解是一个典型的运筹学最短路问题，我们模型的使用范围非常广泛，在工业、商业、交通运输、工程技术、行政管理等领域有着广泛的应用。

七  模型的优缺点

优点：

1、本题思想明确，使用简单的思想解决了复杂的问题，体现了高效的优点；

2、建立的最短路问题模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性；

3、模型的计算采用专业的数学软件，可信度较高；

4、对模型中涉及到的众多影响因素进行了一般性分析，使得论文有说服力。

缺点：

1、利用计算机在计算的过程中由于数据的庞大，严重影响了运行速度以及在以后的N次转车时会出现溢出。

2、由于在计算过程中题目给的平均行驶及转车时间是非现实的，所以使得模型的计算会有所偏差。

3、本模型只考虑了公交车的情况，没有考虑地铁和步行的乘车线路选择的影响。

参考文献

[1] 谢金星,优化建模与LINDO/LINGO软件.北京:清华大学出版社，180页-190页，2005年

[2]沈继英，数学建模.哈尔滨：哈尔滨工程大学出版社，1996年

[3] 吴翊，数学建模的理论与实践.长沙：国防科技大学出版社，1999年

[4]朱道元，数序建模案例精选. 北京：科学技术出版社，2005年5月

[5]李瑛，决策统计分析.天津：天津大学出版社，2005年3月

[6]刑曾萍，最佳专辑.北京：人民有邮电出版社，2002年

[7]王兵团，数学建模基础.北京：清华大学出版社 ，昆明大学出版社，2004年11月