乘公交,看奥运.doc

乘公交，看奥运数学模型摘要一、问题的重述问题的背景我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。问题的提出为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。我们需要解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用建立的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3769S2857 (2)、S1557S0481 (3)、S1879S2322(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。基本参数假设相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 6分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 5分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 8分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）二、问题的假设1、附录中的基本参数和线路信息都是真实可靠的2、公交的运行状况良好，不受天气、路况等其他因素的影响3、假设环行的运行情况如下：环行可以正反两个方向通行，但是在始发站和终点站必须换乘车辆。三、问题的分析本题主要是解决公交线路的选择问题，根据查询者的各种不同需求建立不同的模型。从实际情况出发考虑，不同人群的出行心理也不同。总体来看，乘客出行时最看重三类因素：换成次数最少、时间最少和费用最低。于是我们将这三个因素作为优化目标，建立不同的模型，满足不同人群的需求。由于本题的数据量很大，我们首先对数据进行分析、筛选、整合等处理，便于模型的建立。通过对数据的处理发现，在此公交系统中，共有520条线路，3957个站点，其中线路还分单行道、双行道（上行、下行）和环行道，计费也分为单一票制和分段计费两种。问题一：仅考虑公汽线路，要寻找任意两公汽站点之间最佳公交线路，就要满足乘客的不同需求，比如换成次数最少、时间最少、费用最低、路程最短等。为了简化问题，根据乘客最关心的问题，我们仅考虑在换成次数最少、时间最少、费用最低的条件下确定最佳公交线路。问题二：问题一仅考虑公汽线路，而问题二在问题一的基础上同时考虑公汽与地铁线路。这就使得转乘不仅仅是公汽转公汽，还包括公汽转地铁，地铁转地铁，地铁转公汽，使得转乘问题复杂化。为了得到用时最少的线路，我们可考虑建立了分步规划模型进行求解，将总用时最少这一规划问题，分成在每次搭乘都用时最少的分布规划问题。从而在综合考虑公汽与地铁的情况下确定了最佳线路。问题三：此问题在前两个问题的基础上又考虑了步行因素，四、符号的设定矩阵B：直达时两公汽站点的时间矩阵C：直达时两公汽站点的费用矩阵L：直达时两公汽站点时间最少的线路矩阵U：直达时两公汽站点费用最低的线路矩阵B1：转乘一次时两公汽站点的总时间矩阵C1：转乘一次时两公汽站点的总费用矩阵L11：时间最少时起始站到中转站的线路矩阵L12：时间最少时中转站到终点站的线路矩阵L13：记录时间最少时中转站的站点矩阵U11：费用最少时起始站到中转站的线路矩阵U12：费用最少时中转站到终点站的线路矩阵U13：记录费用最少时中转站的站点五、模型的建立问题一的模型建立与求解根据题目要求寻找任意两公汽站点之间最佳公交线路，不同人群的出行心理也不同。因此，选择最佳公交线路要结合不同人群的需求。从实际情况出发来看，人们出行最看重三类指标：时间、费用和转乘次数。（1）看重时间：公交耗时最少的线路最佳（2）看重费用：公交费用最低的线路最佳（3）看重转乘次数：公交转乘次数最少的线路最佳由于数据量庞大，直接对三者综合考虑会是的计算过于复杂，故将这三类指标分开来计算。一般情况下，如果两站点之间能够直达，人们会首选直达的线路。如果不能直达，人们会选择转乘一次或两次到达目的地。对于转乘三次及三次以上的线路不予考虑，因为转乘三次及三次以上的线路不管从时间还是费用方面考虑，都不是理想的最佳的线路。综上所述，我们建立了三个模型，分别为模型一（时间最少）、模型二（费用最低）和模型三（转乘次数最少），来满足不同人群的需求。同时，在仅考虑公汽线路的条件下，我们要建立公汽站点之间的直达矩阵A、转乘一次矩阵A1和转乘两次矩阵A2，通过这三个矩阵来判断两汽站点之间的直达或转乘情况。模型的建立模型一：时间最少在此模型中，我们将时间作为优化目标。对于比较看重时间的人来说，时间尽可能少使他们选择最佳线路的依据。模型的算法如下：步骤一：通过直达矩阵来判断两公汽站点是否可以直达，若可以直达执行步骤二，否则执行步骤三。步骤二：计算出直达、转乘一次和转乘两次的情况下，时间最少的线路并记录相应的时间和费用等信息。步骤三：利用转乘一次矩阵判断两公汽站点是否通过转乘一次到达目的地，若可以执行步骤四，否则执行步骤五。步骤四：计算出转乘一次和转乘两次的情况下，时间最少的线路并记录相应的时间和费用等信息。步骤五：利用转乘两次矩阵判断两公汽站点是否通过转乘两次到达目的地，若可以执行步骤六，否则停止。步骤六：计算出转乘两次的情况下，时间最少的线路并记录相应的时间和费用等信息。以上的算法可以利用MATLAB进行编程，将算法用程序语言表示出来。通过以上的算法，向询者提供不同转乘次数下耗时最少的线路及相应的时间和费用等信息。查询者根据自身需求，综合考虑选择适合自己的最佳线路。其算法的程图如下：输入两公汽站点判断是否直达判断是否能转乘一次判断是否能转乘两次计算时间最少的线路及相关信息计算时间最少的线路及相关信息计算时间最少的线路及相关信息将时间赋值为无穷大将时间赋值为无穷大比较所有的时间，记录时间最少线路及相关信息结束NNNYYY模型二：费用最低模型一将时间作为优化目标，为看重时间的人提供了多种选择。在模型二中，我们将费用最为优化目标，尽可能使得起始站到出发地的费用最低。模型二的建模思想和模型一基本相同，仅优化的目标不一样。模型的算法如下：步骤一：通过直达矩阵来判断两公汽站点是否可以直达，若可以直达执行步骤二，否则执行步骤三。步骤二：计算出直达、转乘一次和转乘两次的情况下，费用最少的线路并记录相应的时间和费用等信息。步骤三：利用转乘一次矩阵判断两公汽站点是否通过转乘一次到达目的地，若可以执行步骤四，否则执行步骤五。步骤四：计算出转乘一次和转乘两次的情况下，费用最少的线路并记录相应的时间和费用等信息。步骤五：利用转乘两次矩阵判断两公汽站点是否通过转乘两次到达目的地，若可以执行步骤六，否则停止。步骤六：计算出转乘两次的情况下，费用最少的线路并记录相应的时间和费用等信息。输入两公汽站点判断是否直达判断是否能转乘一次判断是否能转乘两次计算费用最低的线路及相关信息计算费用最少的线路及相关信息计算费用最少的线路及相关信息将费用赋值为无穷大将费用赋值为无穷大比较所有的费用，记录时间最少线路及相关信息结束NNNYYY模型三：转乘次数最少转乘次数的多少也会影响人们的公交线路的选择，对于老年人等出行不方便的人群来说，首要考虑转乘次数最少。就赶时间的人群来看，他们不会太在意转乘次数，如果转乘次数多一点，但时间相比较其他方式而言大大缩短，他们也会选择转乘次数多的公交线路。要使两公汽站点经过一次转乘能够到达，必须找到一个中转站，而且起始站到中转站、中转站到终点站要是直达的，这样才能满足转乘一次的要求。因此，找到中转站是解题的关键。转乘两次的思想同转乘一次基本相同，不同的是要找到两个中转站。如果两公汽站点之间存在直达、转乘一次和转乘两次的情况，该模型综合模型一和模型二将每种情况下的线路的时间、费用等信息一一列出来，提供给人们参考。六、模型的求解6.1 问题一综上所述，每一种模型的解不一定都是最优解，有可能是次优解，因为每一种模型只优化了单一目标。但是不同人群的需求也不一样，次优解也可以作为最佳路线。乘客可以根据每一种模型列出的结果，找到满足自己需求的最佳路线。以下是运用以上模型对问题一种6对起始站终点站之间的最佳路线的求解。利用MATLAB编程，得到三种模型的结果如下：起始站-终点站优化目标时间/分钟费用/元转乘次数S3769S2857时间最少2110费用最低3010转乘次数最少2110S1557S0481时间最少10832费用最低15932转乘次数最少10832S1879S2322时间最少3010费用最低3010转乘次数最少3010S0008S0073时间最少8421费用最低8421转乘次数最少8421S0148S0485时间最少10832费用最低11732转乘次数最少10832S0087S3676时间最少6621费用最低7221转乘次数最少6621由上面的结果可以得出，6对起始站终点站的最佳路线及相关信息：（1）S3769S2857耗时21min，费用1元，路线为L288（2）S1557S0481耗时108min，费用3元第一个中转站站点：S1919，第二个中转站站点：S3186起始站到第一个中转站的线路L084，第一个中转站到第二个中转站的线路L189，第二个中转站到终点站的线路L460。（3）S1879S2322耗时30min，费用1元，路线为L013（4）S0008S0073耗时84min，费用2元中转站站点：S0291起始站到中转站的线路L159，中转站到终点站的线路L059。（5）S0148S0485耗时108min，费用3元第一个中转站站点：S0036，第二个中转站站点：S2210起始站到第一个中转站的线路L308，第一个中转站到第二个中转站的线路L156，第二个中转站到终点站的线路L417。（6）S0087S3676耗时66min，费用2元中转站站点：S3496起始站到中转站的线路L454，中转站到终点站的线路L209。这6对起始站终点站的最佳路线的站点见附录一。6.2 问题二6.2.1 问题分析问题一是运用模型求解在仅考虑公交汽车之间相互转换的情况的最佳线路，但是随着公交的不断发展，更应该考虑将地铁加入到整个公交网络中来，形成公汽与公汽的混合网络。此时，问题更贴近实际，但问题也变得更加复杂。尤其是转乘不仅仅是公汽转公汽，还包括公汽转地铁，地铁转地铁，地铁转公汽，使得转乘问题复杂化。通过分析所给数据，我们发现所有的地铁站点都有与之对应的公汽站点，且文中假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，因此我们认为公汽与地铁之间的站点是可以是相互转换的。所以问题二的关键在于如何将所有的地铁线路与站点（和与之对应的公汽站点）转换为统一的公汽站点。6.2.2 问题求解首先，我们将所有的地铁站点D01至D39和其所对应的公汽站点用统一的公汽站点替代（3958至3996）。再将T1、T2的上下行转换成为单一票制为3元的公汽线路L521、L522，成为一个新的公汽线路。 例如：将D01所对应的公汽站点S0567，S0042，S0025替换为S3958L521上行的所有站点为：395839593960.39953996然后，我们参照问题一运用matlab变出相应程序，即可求出符合各模型的最佳线路。（程序参照附录2）6.2.3 得出结果首先，我们发现在问题一中的6对起始站终到站在新的公汽线路中会产生变动。其中第六组S0087S3676在新的公汽线路中表示为S3984S3993.所得六组数据如下表 同时考虑工期和地铁的情况下6组数据的最佳路线 （注：表中路线名为新公汽路线，521路、522路实为T1、T2）起始站-终点站优化目标时间/分钟费用/元转乘次数线路中转站S3769S2857时间最少2110288上行/费用最低3010288上行/转乘次数最少2110288上行/S1557S0481时间最少1083284下行、189下行、460下行3977、3186费用最低1473284下行、348下行、447上行28、3970转乘次数最少1083284下行、189下行、460下行3977、3186S1879S2322时间最少301013下行/费用最低301013下行/转乘次数最少301013下行/S0008S0073时间最少8121159下行、474上行3970费用最低8421转乘次数最少8121159下行、474上行3970S0148S0485时间最少88.55224下行、521上行、51上行3959、3978费用最低12332308上行、157下行、45下行36、1406转乘次数最少12332308上行、157下行、45下行36、1406S3984S3993时间最少2530522上行/费用最低7221转乘次数最少2530522上行/6.3 问题三6.3.1 问题分析6.3.2 问题求解6.3.3 得出结论附录附录一：（1）针对S3769S2857最佳路线的选择S3769S2857耗时21min，费用1元路线为L288：S3769S0132S0262S3806S3737S1505S2902S2857（2）针对S1557S0481最佳路线的选择S1557S0481耗时108min，费用3元第一个中转站站点：S1919，第二个中转站站点：S3186起始站到第一个中转站的线路L084：S1557S3158S2628S3408S2044S1985S2563S2682S0028S0029S0055S0051S1919第一个中转站到第二个中转站的线路L189：S1919S2840S1402S3186第二个中转站到终点站的线路L460：S3186S3544S2116S2119S1788S1789S1770S2322S992S2184S2954S3117S2424S1174S902S0903S2101S0481（3）针对S1879S2322最佳路线的选择S1879S2322耗时30min，费用1元路线为L013：S1879S3405S2517S3117S2954S0531S2184S2182S0992S2324S2322（4）针对S0008S0073最佳路线的选择S0008S0073耗时84min，费用2元中转站站点：S0291起始站到中转站的线路L159：S0008S3412S2743S3586S2544S0913S2953S3874S0630S0854S0400S2633S3053S0408S0145S3138S2684S2683S0291中转站到终点站的线路L059：S0291S3614S0491S2559S0990S3315S3898S1855S0073（5）针对S0148S0485最佳路线的选择S0148S0485耗时108min，费用3元第一个中转站站点：S0036，第二个中转站站点：S2210起始站到第一个中转站的线路L308：S0148S0462S0361S1797S2221S0302S2222S2737S1716S0128S2268S1308S139