乘公交瞧奥运摘要本设计要解决得就是合理给出两站点间得最佳路线选择问题，即给出一条经济且省时得路线.在处理此问题之前,我们根据调查与分析,对影响线路选择得因素进行筛选,最终确定了以下三个影响较大得因素：第一就是换乘次数;第二就是乘车时间；第三就是乘车费用。依据各因素对路线选择得影响程度，我们按不同得权重对它们进行考虑。从实际情况分析，人们通常宁愿多乘坐几站地也不愿换车,所以我们赋予换乘次数较大得权重。为了解决换乘次数最少,乘车时间相对较短、乘车费用相对较少得问题,经过尝试与探索，我们采用了现代分析得方法，对起始站与终点站有无相交站点进行分类讨论，归纳出直达，换乘一次,换乘两次得情况（三次以上得情形可以类推）,并通过Matlaｂ编制程序,给出了任意两站点间得最佳乘车路线以及换车得地点,最后还提出了进一步得意见与建议。关键词：最佳路线换乘次数乘车时间乘车费用一、问题得重述第2９届奥运会明年8月将在北京举行,作为城市枢纽得公共交通承担着非常重得运输任务。近年来,北京市得公交系统有很大得发展,公交线路得条数与公交车数量在迅速增多，给人民生活带来便利得同时，也面临多条线路得选择问题，有时出行往往还需要转乘多辆公交车才能到达目得地。如何在短时间、换乘次数最少、成本最低得情况到达目得地,就是人们所关注得问题。因此,我们通过建立线路选择得模型与算法,设计一套自主查询计算机系统，查询到出行时所需得最佳公交路线及换乘方法，给人们出行节约更多得时间与金钱。要求:1、仅考虑公汽线路，建立任意两公汽站点之间线路选择问题得数学模型与算法。并求出以下6对起始站→终到站之间得最佳路线.（1）S３359→S1828（2)S1557→S04８1（3）S0971→S04８5(4）S0008→S0０73（５）S01４８→Ｓ０4８5（6）Ｓ00８7→S36７６2、同时考虑公汽与地铁线路，解决１中问题。3、如果所有站点间得步行时间已知,建立任意两站点间路线选择问题得数学模型.二、模型得假设１、所有公交线路得开班、收班时间相同.２、公车不会因为堵车等因素延长行驶时间。3、各条线路不会有新得调整与变化。4、环线可以以任意站作为起点站与终点站,并且就是双向得。5、除环线以外得线路,到达终点站后，所有得人都必须下车.６、人们对换乘车次数尽量少得偏好程度总就是大于对花费时间相对短与花费金钱相对少得偏好程度。7、同一地铁站对应得任意两个公汽站之间可以通过地铁站换乘,且无需支付地铁费.三、符号得说明符号表示意义第条包含初始站点得线路，第条包含目标站点得线路,第条中间线路，上得第个站点,上得第个站点,上得第个站点，乘客在第段线路上乘坐得站数乘客在一次地铁线路上乘坐得总站数公汽换乘公汽得次数地铁换乘地铁得次数地铁换乘公汽得次数公汽换乘地铁得次数四、问题得分析、模型得建立及求解4、1问题一4、1、1问题一得分析已知相邻公汽站平均行驶时间(包括停站时间）：3分钟;公汽换乘公汽平均耗时：５分钟（其中步行时间2分钟）。公汽票价:分为单一票价与分段计价两种，标记于线路后;其中分段估计票价为:0~20站：１元；21~４0站:2元;40站以上:３元。题目要求设计任意两公汽站点之间线路选择问题得数学模型与算法。对于附录中得1、1公汽线路信息、txt中得数据进行处理后，以文本文件形式导入Matlab中,找到了站点与站点之间得关系.进一步发现表明无论试图产生邻接矩阵或边权矩阵因数据太庞大而可行性极低，其运行时间长达５0分钟,故考虑按题目给得路线来建立站点矩阵并对此矩阵进行处理后能够清晰有效地应用此矩阵.４、1、2模型得建立及求解模型一设为乘坐公交线路得费用函数：,总时间函数:（１）总费用函数：（２）其中表示乘客在公交线路上乘坐得站数；表示公汽换乘公汽得次数。目标：找出任意给定得两站点得乘车线路,使与相对最小。算法思路：由于人们得对换乘车次数尽量少得偏好程度总就是大于对花费时间与金钱相对少得偏好程度,我们将优先考虑换乘车次数尽量少，然后再考虑花费时间相对短、花费金钱相对少,对得出得所有结果中进行筛选。换乘次数得大概思路及步骤如下:将所有包含初始站点得线路建成一个集合S，，，所有包含目标站点得线路建成一个集合G，,。,,,,,。１、直达得线路。当时，存在、，,，使得，即、为同一线路.此线路既包含初始站点又包含目标站点。若,那么,此线路为所求直达线路。若，或者当时，考虑换乘一次得线路。２、换乘一次得线路。当有与相交时，存在、,，，有及,，。使得,即、为同一站点.若,，那么,从初始站点乘坐线路，行驶至站点，即在站点，换乘线路至目标站点.即若不满足,,或者,当无任何与相交时,考虑换乘两次得线路.3、换乘两次得线