数学建模论文乘公交看奥运.doc

第18组：李姣 张华军 李醒乘公交，看奥运摘要 本文探讨的是北京市的公交线路选择问题，属于运筹学中的最短路问题。我们建立了多目标线性规划函数，运用软件Matlab并结合Floyd算法，求出了最优的乘车路线。 在问题一中，当仅考虑公汽线路时，我们建立了依次以最少的换乘次数、最短的时间、最省的费用为目标函数的多目标线性规划模型一。此时，引入决策变量并在约束条件的限制下，运用Floyd算法编程求解得到最优线路：起始站线路终点站换乘次数(次)时间（分钟）费用（元）S3359L324-S2281-L035S18281563S1557L028-S0001-L018S04811833S0971L324-S2281-L035S04851563S0008L052-S1961-L030S00731782S0087L216-S0002-L209S36761653S0148L024-S3217-L039-S0005-L014S04852463 在问题二中，当同时考虑公汽与地铁线路时，在模型一的基础上更改目标函数和约束条件，再次建立依次以最小的换乘次数、最短的时间、最省的费用为目标函数的多目标规划模型二。运用Floyd算法编程求解得到最优线路：起点线路终点次数时间费用S3359S3359-L015-S3068,D08-T1-D18-T2-D34,S0578-L167-S1828S182831015S1557S1557-L084-S0978,D32-T2-D24,S0537-L516-S0481S04813116.55S0971S0971-L094-S0567,D01-T1-D21,S0464-L104-S0485S04853965S0008S0008-L200-S2534,D15-T1-D12,S0609-L057-S0073S0073365.55S0087S0148-L024-S1487,D02-T1-D21,S0464-L104-S0485S3676387.55S0148S0087-L021-S0630,D29-T2-D36,S3676S04853334 在问题三中，公汽、地铁、步行交叉混合使用时，我们建立了3个最优化模型：换乘次数最少的优化模型、花费时间最短的优化模型、全程费用最省的优化模型。根据乘客的各种心理偏好，可以依情况选择最优路线。关键词：多目标线性规划 Floyd算法 决策变量 最优路线 1、问题重述1.1问题背景2004年在雅典奥运会上使用的info2004信息服务系统，为奥运期间来访的各国运动员、旅游观光者以及本国居民提供了便利，同时也将“数字奥运”、“科技奥运”、“人文奥运”融为一体，向世界宣告了信息化的广泛普及以及科技竞争的日益加剧。“数字奥运”作为奥运会的亮点，旨在建设各种与奥运相关的信息与基础通信设施和系统，营造良好的信息化环境，提供优质的信息服务，是“科技奥运”的时代特征，是“人文奥运”的弘扬手段，我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。如何通过高科技信息手段，建立一个公交查询服务系统，充分体现“以人为本”和“科技奥运”的理念，同时，进一步推动首都信息化的长期发展，实现“数字奥运”和北京生活的信息化的双重目标，提高我国的国际竞争力和影响力，便是值得我们深思的问题。1.2需要解决的问题针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。(1)S3359S1828 (2)S1557S0481 (3)S0971S0485(4)S0008S0073 (5)S0148S0485 (6)S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。1.3相关附录1.3.1基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。1.3.2公交线路及相关信息 （见数据文件B2007data.rar）2、问题分析 要设计一个公交线路自主查询服务系统，主要是为了满足乘客的各种心理需求。对大多数乘客来说，线路的查询普遍表现为对换乘次数、时间以及费用的查询。在现实生活中，大多数乘客都会首选能够直达的车，其次再去考虑相关因素。这样的心理偏好不仅仅适用于公汽线路和地铁线路，同样也适用于公汽和地铁混合的公交线路。因此，只要解决了最少的换乘次数、最短的时间、最省的费用这三个目标，那么本题便迎刃而解。对于问题一，当仅考虑公汽线路时，同样需要考虑三个因素：换乘次数、时间和费用。基于这3个因素，我们便可以建立一个多目标线性规划模型：最少的换乘次数、最短的时间、最省的费用。换乘次数，我们可以引入决策变量，以其值之和来表示整个过程的换乘次数。所需时间，则由行车时间、换车时间、起始等待时间这几部分构成。基于已知的相邻公汽站行驶时间和公汽之间的换乘时间，可以计算出行车时间和换车时间并可推导出起始等待时间。所需费用，按照单一票价制和分段计价制分别计算各阶段所需费用。在选择路线时，在换乘次数不超过2时，首选换乘次数最少的线路。若换乘次数超过2，再考虑时间最短的线路，最后考虑费用最省的线路。对于问题二，当同时考虑公汽线路和地铁线路时，同样需要建立一个以最少的换乘次数、最短的时间、最省的费用为目标的多目标线性规划模型。此时，换乘次数不受路线类别的影响，同样可以用决策变量的值之和来表示。所需时间也是由行车时间、换车时间、起始等待时间构成。经过推论，在等待公汽和等待地铁的时间不同，因此我们必须将时间分为两类：起始站是等待公汽的全程所需时间、起始站是等待地铁的全程所需时间。根据所求得的所需时间，所需费用也对应分为两类：起始站是等待公汽的全程所需费用、起始站是等待地铁的全程所需费用。在路线选择时，同样按照上述筛选方法找出最优路线。对于问题三，当公汽线路、地铁线路、步行混合一起时，为了能够找到任意两点之间的线路，那么我们可以建立3个分别以最少的换乘次数、最短的时间、最省的费用为目标的最优化模型。对于每条线路，都可以查找到这3个方面的信息。整个过程中，最优查询路线的选择流程可以用如下流程图来表示：3、符号说明：从起点到终点的换乘次数；：从起点到终点的费用；：从起点到终点的时间；：第阶段的初始状态变量；：第阶段当状态处于时的决策变量；：从始发点处上车时的所交的费用；：从上一站到站点处所交的费用：从起点到第一次换车时所经过的站点总数；：从上次换车到站点所经过的站点总数；：相邻地铁站的段数；：公汽换乘公汽的次数；：地铁换乘地铁的次数；：地铁换乘公汽的次数；：公汽换乘地铁的次数；：乘坐公汽的花费；：乘坐地铁的花费；：始发站是乘公汽时的全程花费时间；：始发站是乘地铁时的全程花费时间；：乘坐第辆公汽的费用；：乘坐第辆公汽所经过的站点段数；：乘坐地铁所经过的站点段数；：第次步行时起点和终点相隔站点段数为；4、建模前准备4.1线路换乘收集地铁线路间的换乘同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘4.2线路类别双循环路线：按原路返回单循环路线：不按原路返回5、模型假设假设一：乘客在乘车前考虑的因素主要是换乘次数、乘车时间、所用费用；假设二：不考虑天气变化，如风雪，大雾，冰雹，风沙等恶劣天气对公交线路的影响；假设三：题中所给的参数均为简化问题而作的假设，未必与实际数据完全吻合；假设四：题中所给的公汽线路信息、地铁线路信息、地铁线换乘公路信息是准确的；假设五：同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)；假设六：所有站点之间的步行时间已知；假设七：乘客下车后不再乘坐同一路公汽或同一列地铁到达下一个目的地；假设八：在公汽之间换乘时，整个过程的换乘次数不超过2次；假设九：当起始站之间相隔站点段不超过2时，采用步行；6、问题一的解答5.1相关定义说明定义1描述阶段的变量称为阶段变量，通常用表示。定义2某阶段的出发位置称为状态，通常用表示第阶段的初始状态变量；定义3描述决策的变量称为决策变量，通常用表示第阶段当状态处于时的决策变量。阶段、状态、决策的关系可以表示为下图：5.2目标函数的确定该模型是为了建立一个公汽查询服务系统，最终目的是为了满足乘客的各种需求，按照顾客的心理需求，依次需要满足3个目的：最少的换乘次数、最短的时间、最省的费用。因此我们建立的目标函数为：5.3目标函数表达式的确定目标一：换乘次数的确定引入决策变量，因此全程换车总次数可以用个阶段的和来表示，所以换乘次数的数学表达式为：其中目标二：所需时间的确定全程所需时间可以用行车时间、换车消耗时间、始点等待时间的和来表示。因此所需时间的数学表达式为：目标三：全程花费的确定如果以表示从始发点处上车时的所交的费用，表示从上一站到站点处所交的费用，那么行车全过程中，所付费用可以用起始站所交费用与中途各站点所交费用总和来表示。因此全程花费的数学表达式为：在首发站若采用单一票价制，则；若实行分段计价制，以表示从起始站点到第一次换车时所经过的站点总数，则：在站点处，若不换车，则；若换车，当实行单一票价制时，当实行分段计价制时，若以表示从上次换车到站点所经过的站点总数，则：5.4约束条件的确定由于是决策变量，且只有换车与不换车两种决策，因此：由于行驶过程中经过的站点都在无向赋权图的边上，因此：由于在一条行驶路线上，换乘次数最多比所有站点个数少1，因此：由于在这种情况下，换乘总次数不超过2次，因此：5.5模型一的建立综上可得，建立的多目标线性规划模型一为：目标函数5.6模型一的求解5.6.1算法的步骤步骤1：输入乘车参数1，起点；2，终点；步骤2：任一阶段起始站点可乘公汽线路集合为，终点站可乘公汽线路集合为；步骤3：判断或是否为空集，若空，则无车；若非空，则转入步骤4；步骤4：判断并是否为空集，若为空集，则没有直达车，此时考虑一次换车，用局部搜索法搜索一次中转站；步骤5：若通过搜索，未能找到与的交集，说明两者不能通过一次换乘而达到目的，则必须通过邻接矩阵进一步扩大搜索，使两者的中转站在某条线路上，则此时能通过二次换乘，达到目的地。步骤6：对于如果再进一步搜索而不能找到路径的两站点，则可以假设它们之间不能到达，或者即使能够通过大于两次转乘而达到目的两点，在实际价值中是不可取的，可以忽略或将其指定为两地不能通过线路直接到达。5.6.2求解结果中转1次时起始站线路1中转站线路2终点站转乘次数时间费用S3359L324S0007L002S18281573L324S2280L0021673L011S3728L0351603L324S2281L0351563L011S2800L0021762L011S1767L0351802S1557L028S0001L018S04811833S0971L013S1215L104S048511012L013S2607L1041953L024S3217L0451532L009S0009L0451672L013S1770L1761582L013S2607L1041772L013S2322L1761753S0008L052S3537L058S007311913L052S1787L05811433L052S0007L0301892L052S1961L0301782S0087L206S0008L209S36761733L216S0002L2091653L216S0491L2091893L216S3614L2091733中转2次时起始站线路一中转站一线路二中转站二线路三终点站转乘次数时间费用S0148L024S1487L378S3077L045S048521333L024S3217L039S0005L05021303L024S3571L378S3401L0172703L024S3217L039S0005L1042913L024S3217L028S0001L1762523L024S3217L039S0005L0142463L024S1487L378S3077L01421933综上，最优路线为：起始站线路终点站换乘次数(次)时间（分钟）费用（元）S3359L324-S2281-L035S18281563S1557L028-S0001-L018S04811833S0971L324-S2281-L035S04851563S0008L052-S1961-L030S00731782S0087L216-S0002-L209S36761653S0148L024-S3217-L039-S0005-L014S048524637、问题二的解答6.1目标函数的确定当同时考虑公汽和地铁线路时，在模型一的基础上同样需要考虑三个目标：最少的换乘次数、最短的时间、最省的费用。因此我们建立的目标函数为：6.2目标函数表达式的确定目标一：换乘次数的确定在综合考虑公汽线路和地铁线路时，所引入的决策变量不受选择路线的影响，因此全程换车总次数依然可以用个阶段的和来表示，所以换乘次数的数学表达式为：其中目标二：所需时间的确定（1）全程所需总时间 如果以表示始发站乘公汽的全程所需时间，以表示始发站乘地铁的全程所需时间，则全程所需时间的数学表达式为： （2）始发站乘公汽的全程所需时间 如果以表示相邻地铁站的段数，以、分别表示公汽换乘公汽的次数、地铁换乘地铁的次数、地铁换乘公汽的次数、公汽换乘地铁的次数，则始发站乘公汽的全程所需时间的数学表达式为：（3）始发站乘地铁的全程所需时间目标三：全程花费的确定（1）全程总花费如果以 表示始发站是乘公汽的花费，以表示始发站是乘地铁的花费，那么全程花费的数学表达式可以表示为：（2）始发站是乘公汽的花费如果以表示乘公汽时从始发点处上车时的所交费用，则实行单一票制时，当实行分段计价制时，以表示从公汽起始站点到第一次换车时所经过的站点总数，则在站点处，若不换车，则；若换车，当实行单一票价制时，当实行分段计价制时，若以表示从上次换车到站点所经过的站点总数，则：则乘公汽过程中的总花费为：（3）始发站是乘地铁的花费如果以表示首发站选择乘地铁，则在站点处，若不换车，则；若换车，当实行单一票价制时，当实行分段计价制时，若以表示从上次换车到站点所经过的站点总数，则：则乘地铁过程中的总花费为：6.3约束条件的确定在模型一的基础上，添加如下约束条件：公汽与地铁混合换乘的总次数等于全程换乘总次数，即：其中，所设定的参数都是正数，即：6.4模型二的建立综上可得，建立的多目标线性规划模型二为：目标函数 6.5模型二的求解6.5.1算法的步骤步骤1：输入乘车参数1，起点；2，终点；步骤2：任一阶段起始站点可乘公汽线路和地铁线路集合为，终点站可乘公汽线路和相关地铁线路集合为；步骤3：判断或是否为空集，若空，则无车；若非空，则转入步骤4；步骤4：判断并是否为空集，若为空集，则没有直达车，此时考虑一次换车，用局部搜索法搜索一次中转站；步骤5：若通过搜索，未能找到与的交集，说明两者不能通过一次换乘而达到目的，则必须通过邻接矩阵进一步扩大搜索，使两者的中转站在某条线路上，则此时能通过二次换乘，达到目的地。步骤6：对于如果再进一步搜索而不能找到路径的两站点，则可以假设它们之间不能到达，或者即使能够通过大于两次转乘而达到目的两点，在实际价值中是不可取的，可以忽略或将其指定为两地不能通过线路直接到达。6.5.2求解结果最优线路为：起点线路终点次数时间费用S3359S3359-L015-S3068,D08-T1-D18-T2-D34,S0578-L167-S1828S182831015S1557S1557-L084-S0978,D32-T2-D24,S0537-L516-S0481S04813116.55S0971S0971-L094-S0567,D01-T1-D21,S0464-L104-S0485S04853965S0008S0008-L200-S2534,D15-T1-D12,S0609-L057-S0073S0073365.55S0087S0148-L024-S1487,D02-T1-D21,S0464-L104-S0485S3676387.55S0148S0087-L021-S0630,D29-T2-D36,S3676S048533348、问题三的解答7.1换乘次数最少的优化模型的建立当公汽、地铁、步行交叉一起时，如果以表示起点和终点相隔站点段数，当采用步行。每步行一次就减少乘公汽或地铁一次，如果以表示全程步行的次数，则最小换乘次数的数学表达式可以表示为：其中，综上可得，最少换乘次数的表达式为：7.2所需时间最短的优化模型的建立（1）始发站是乘公汽时全程所需时间当始发站是乘坐公汽时，那么始点等待时间为3分钟。若以表示每相邻两个站点之间的步行时间，以表示第次步行时起点和终点相隔站点段数为，此时，全程所需时间可以用乘车时间、换车时间、步行时间、始点等待时间的和来表示：（2）始发站是乘地铁时全程所需时间当始发站是乘坐地铁时，那么始点等待时间为2分钟。（3）综上可得，全程所需时间的表达式为：7.3全程花费最省的优化模型的建立（1）乘坐公汽的费用若以表示乘坐第辆公汽的费用，以表示乘坐第辆公汽所经过的站点段数，以决策变量表示是否采用步行，则乘坐公汽的费用可以表示为：其中，（2）乘坐地铁的费用以表示乘坐地铁所经过的站点段数，则乘坐地铁的费用可以表示为：（3）全程最小费用9、模型的评价、改进与推广9.1模型的评价9.1.1模型的优点（1）此模型运用多目标线性规划函数并结合数学软件Matlab最优线路的选择问题，具有较高的可信度；（2）此模型科学准确地建立了三个最优化目标，找出了起始站到终点站之间的最少换乘次数、最短时间、最省费用的最优路线，充分满足了乘客的多样化需求，与现实生活紧密联系；（3）此模型所建立的函数简单、易于理解。9.1.2模型的缺点（1）该模型是按照乘客的心理需求依次按照最少换乘次数、最短时间、最省费用来求解，而未考虑同时满足这3个目标或其中2个目标时的最优化线路。因此未能满足所有偏好者的需求。（2）该模型在运用计算机进行算法运算时由于数据庞大，因此运行速度比较缓慢。9.2模型的改进根据马斯诺的需要层次理论，我们按照乘客的各种心理偏好依次将最少的换乘次数、最短的时间、最省的费用作为主要目标，同时也实现了行程通畅便利目标（目标一）和不同的行程需求目标（目标二和目标三）。在此基础上，为了使查询更加人性化，能够满足人们的高层次心理需求，我们可以设立人性化查询设计目标：站点负载压力最小、转乘车辆始发站点最多。如果以表示在站点处的负载压力权，以表示从站点到站点的负载压力，则可建立目标函数四：。如果以决策变量表示站点是否为始发站，以表示从站点到站点的始发站点数，则可建立目标函数五：。其中9.3模型的推广该模型解决的是一个典型的运筹学中的最短路问题，在公交优化配置过程中充分解决了最少换车次数、最短时间和最省费用的合理分配。图与网络优化属于运筹学的一个分支，此模型在解决图论问题上具有现实指导价值。该模型不仅仅适用于公交线路查询，也可以广泛运用于航空线路查询、航海线路查询。同时，不仅仅在交通运输业，在工业、商业、工程技术、行政管理等领域都有着广泛运用。10、参考文献1 姜启源.数学模型M.北京：高等教育出版社.1987.7.2 谢金星,优化建模与LINDO/LINGO软件.北京:清华大学出版社，2005年.3 朱道元，数序建模案例精选. 北京：科学技术出版社，2005年5月.4 薛毅，耿美英.运筹学与实验.北京：电子工业出版社，2008,9.5运筹学编写组.运筹学（第三版）.北京：清华大学出版社.2005年6月.6薛定宇、陈阳泉.高等应用数学问题的Matlab求解（第二版）.北京：清华大学出版社.2008年10月.附录 down_line(line_num,tt)=B(1,i);clear all%产生上行和下行的两个520100的矩阵，行号表示线路号，列号表示线路的每个站点，一条线路从第一列开始放置，后面不足的为0。up_line=zeros(520,200);%保存上行线down_line=zeros(520,200);%保存下行线P=zeros(520,1);%读线路文件，fid=fopen(D:shuju3.txt,r);%执行时，修改其中的路径为所读取的文件line_num=1;while line_num=0 & A(1,1)0&up_line(i,col)0&up_line(i,col-1)3958&up_line(i,col)0&down_line(i,col)0&down_line(i,col-1)3958&down_line(i,col)0 t=t+1; end end re(1,i)=t;endmax=1;t=1;for i=1:3957 if re(1,i)9 i; t=t+1; endendtmaxre_dec=zeros(3957,max);%max=16for i=1:3957 tt=1; for j=1:3957 k=relation_matrix(i,j); if k0 re_dec(i,tt)=j; tt=tt+1; end endendfid=fopen(d:line.m,w);A1=zeros(2,15);A2=zeros(2,15);A3=zeros(2,15);A4=zeros(2,15);disp(-公交线路查询系统-);disp(请输入起点与终点);begin_s=input(起点站);%输入,输入的数据格式:省去前面的字母和0end_s=input(终点站);%输入tt=1;for i=1:520 for j=2:200if up_line(i,j)=begin_s fprintf(fid,%d ,i); A1(1,tt)=i; A1(2,tt)=j; tt=tt+1;end endendfprintf(fid,n);tt=1;for i=1:520 for j=2:200 if down_line(i,j)=begin_s fprintf(fid,%d ,i); A2(1,tt)=i; A2(2,tt)=j; tt=tt+1; end endendfprintf(fid,n);tt=1;for i=1:520 for j=2:200 if up_line(i,j)=end_s fprintf(fid,%d ,i); A3(1,tt)=i; A3(2,tt)=j; tt=tt+1; end endendfprintf(fid,n); tt=1;for i=1:520 for j=2:200 if down_line(i,j)=end_s fprintf(fid,%d ,i); A4(1,tt)=i; A4(2,tt)=j; tt=tt+1; end endendfclose(fid);%转一次dd=0;fprintf(乘车路线：)fprintf(本系统只支持转乘两次以下的乘车方法！)fprintf(n n)for i=1:15 for k=1:15 for j=2:200 for d=2:200 if A2(1,i)=0&A4(1,k)=0 if up_l