《数学建模论文乘公交看奥运》由会员分享，可在线阅读，更多相关《数学建模论文乘公交看奥运（23页珍藏版）》请在金锄头文库上搜索。
1、第18组：姣 华军 醒乘公交，看奥运摘要 本文探讨的是市的公交线路选择问题，属于运筹学中的最短路问题。我们建立了多目标线性规划函数，运用软件Matlab并结合Floyd算法，求出了最优的乘车路线。 在问题一中，当仅考虑公汽线路时，我们建立了依次以最少的换乘次数、最短的时间、最省的费用为目标函数的多目标线性规划模型一。此时，引入决策变量并在约束条件的限制下，运用Floyd算法编程求解得到最优线路：起始站线路终点站换乘次数(次)时间（分钟）费用（元）S3359L324-S2281-L035S18281563S1557L028-S0001-L018S04811833S0971L324-S2281-L
2、035S04851563S0008L052-S1961-L030S00731782S0087L216-S0002-L209S36761653S0148L024-S3217-L039-S0005-L014S04852463 在问题二中，当同时考虑公汽与地铁线路时，在模型一的基础上更改目标函数和约束条件，再次建立依次以最小的换乘次数、最短的时间、最省的费用为目标函数的多目标规划模型二。运用Floyd算法编程求解得到最优线路：起点线路终点次数时间费用S3359S3359-L015-S3068,D08-T1-D18-T2-D34,S0578-L167-S1828S182831015S1557S1557
3、-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 在问题三中，公汽、地铁、步行交叉混合使用时，我
4、们建立了3个最优化模型：换乘次数最少的优化模型、花费时间最短的优化模型、全程费用最省的优化模型。根据乘客的各种心理偏好，可以依情况选择最优路线。关键词：多目标线性规划 Floyd算法 决策变量 最优路线 1、问题重述1.1问题背景2004年在雅典奥运会上使用的info2004信息服务系统，为奥运期间来访的各国运动员、旅游观光者以与本国居民提供了便利，同时也将“数字奥运”、“科技奥运”、“人文奥运”融为一体，向世界宣告了信息化的广泛普与以与科技竞争的日益加剧。“数字奥运”作为奥运会的亮点，旨在建设各种与奥运相关的信息与基础通信设施和系统，营造良好的信息化环境，提供优质的信息服务，是“科技奥运”的
5、时代特征，是“人文奥运”的弘扬手段，我国人民翘首企盼的第29届奥运会明年8月将在举行，届时有大量观众到现场观看奥运比赛，其部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。如何通过高科技信息手段，建立一个公交查询服务系统，充分体现“以人为本”和“科技奥运”的理念，同时，进一步推动首都信息化的长期发展，实现“数字奥运”和生活的信息化的双重目标，提高我国的国际竞争力和影响力，便是值得我们深思的问题。1.2需要解决的问题针对市场需求，某公司准备研制开发一个解决
6、公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。(1)S3359S1828 (2)S1557S0481 (3)S0971S0485(4)S0008S0073 (5)S0148S0485 (6)S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之
7、间线路选择问题的数学模型。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公交线路
8、与相关信息 （见数据文件B2007data.rar）2、问题分析 要设计一个公交线路自主查询服务系统，主要是为了满足乘客的各种心理需求。对大多数乘客来说，线路的查询普遍表现为对换乘次数、时间以与费用的查询。在现实生活中，大多数乘客都会首选能够直达的车，其次再去考虑相关因素。这样的心理偏好不仅仅适用于公汽线路和地铁线路，同样也适用于公汽和地铁混合的公交线路。因此，只要解决了最少的换乘次数、最短的时间、最省的费用这三个目标，那么本题便迎刃而解。对于问题一，当仅考虑公汽线路时，同样需要考虑三个因素：换乘次数、时间和费用。基于这3个因素，我们便可以建立一个多目标线性规划模型：最少的换乘次数、最短的时间
9、、最省的费用。换乘次数，我们可以引入决策变量，以其值之和来表示整个过程的换乘次数。所需时间，则由行车时间、换车时间、起始等待时间这几部分构成。基于已知的相邻公汽站行驶时间和公汽之间的换乘时间，可以计算出行车时间和换车时间并可推导出起始等待时间。所需费用，按照单一票价制和分段计价制分别计算各阶段所需费用。在选择路线时，在换乘次数不超过2时，首选换乘次数最少的线路。若换乘次数超过2，再考虑时间最短的线路，最后考虑费用最省的线路。对于问题二，当同时考虑公汽线路和地铁线路时，同样需要建立一个以最少的换乘次数、最短的时间、最省的费用为目标的多目标线性规划模型。此时，换乘次数不受路线类别的影响，同样可以用
10、决策变量的值之和来表示。所需时间也是由行车时间、换车时间、起始等待时间构成。经过推论，在等待公汽和等待地铁的时间不同，因此我们必须将时间分为两类：起始站是等待公汽的全程所需时间、起始站是等待地铁的全程所需时间。根据所求得的所需时间，所需费用也对应分为两类：起始站是等待公汽的全程所需费用、起始站是等待地铁的全程所需费用。在路线选择时，同样按照上述筛选方法找出最优路线。对于问题三，当公汽线路、地铁线路、步行混合一起时，为了能够找到任意两点之间的线路，那么我们可以建立3个分别以最少的换乘次数、最短的时间、最省的费用为目标的最优化模型。对于每条线路，都可以查找到这3个方面的信息。整个过程中，最优查询路
11、线的选择流程可以用如下流程图来表示：3、符号说明：从起点到终点的换乘次数；：从起点到终点的费用；：从起点到终点的时间；：第阶段的初始状态变量；：第阶段当状态处于时的决策变量；：从始发点处上车时的所交的费用；：从上一站到站点处所交的费用：从起点到第一次换车时所经过的站点总数；：从上次换车到站点所经过的站点总数；：相邻地铁站的段数；：公汽换乘公汽的次数；：地铁换乘地铁的次数；：地铁换乘公汽的次数；：公汽换乘地铁的次数；：乘坐公汽的花费；：乘坐地铁的花费；：始发站是乘公汽时的全程花费时间；：始发站是乘地铁时的全程花费时间；：乘坐第辆公汽的费用；：乘坐第辆公汽所经过的站点段数；：乘坐地铁所经过的站点段
12、数；：第次步行时起点和终点相隔站点段数为；4、建模前准备4.1线路换乘收集地铁线路间的换乘同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘4.2线路类别双循环路线：按原路返回单循环路线：不按原路返回5、模型假设假设一：乘客在乘车前考虑的因素主要是换乘次数、乘车时间、所用费用；假设二：不考虑天气变化，如风雪，大雾，冰雹，风沙等恶劣天气对公交线路的影响；假设三：题中所给的参数均为简化问题而作的假设，未必与实际数据完全吻合；假设四：题中所给的公汽线路信息、地铁线路信息、地铁线换乘公路信息是准确的；假设五：同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)；假设六：所有站点之间
13、的步行时间已知；假设七：乘客下车后不再乘坐同一路公汽或同一列地铁到达下一个目的地；假设八：在公汽之间换乘时，整个过程的换乘次数不超过2次；假设九：当起始站之间相隔站点段不超过2时，采用步行；6、问题一的解答5.1相关定义说明定义1描述阶段的变量称为阶段变量，通常用表示。定义2某阶段的出发位置称为状态，通常用表示第阶段的初始状态变量；定义3描述决策的变量称为决策变量，通常用表示第阶段当状态处于时的决策变量。阶段、状态、决策的关系可以表示为下图：5.2目标函数的确定该模型是为了建立一个公汽查询服务系统，最终目的是为了满足乘客的各种需求，按照顾客的心理需求，依次需要满足3个目的：最少的换乘次数、最短
14、的时间、最省的费用。因此我们建立的目标函数为：5.3目标函数表达式的确定目标一：换乘次数的确定引入决策变量，因此全程换车总次数可以用个阶段的和来表示，所以换乘次数的数学表达式为：其中目标二：所需时间的确定全程所需时间可以用行车时间、换车消耗时间、始点等待时间的和来表示。因此所需时间的数学表达式为：目标三：全程花费的确定如果以表示从始发点处上车时的所交的费用，表示从上一站到站点处所交的费用，那么行车全过程中，所付费用可以用起始站所交费用与中途各站点所交费用总和来表示。因此全程花费的数学表达式为：在首发站若采用单一票价制，则；若实行分段计价制，以表示从起始站点到第一次换车时所经过的站点总数，则：在站点处，若不换车，则；若换车，当实行单一票价制时，当实行分段计价制时，若以表示从上次换车到站点所经过的站点总数，则：5.4约束条件的确定由于是决策变量，且只有换车与不换车两种决策，因此：由于行驶过程中经过的站点都在无向赋权图的边上，因此：由于在一条行驶路线上，换乘次数最多比所有站点个数少1，因此：由于在这种情况下，换乘总次数不超过2次，因此：5.5模型一的建立综上可得，建立的多目标线性规划模型一为：目标函数5.6模型一的求解5.6.1算法的步骤步骤1：输入乘车参数1，起点；2，终点；步骤2：任一阶段起始站点可乘公汽线路集合为，终点站可乘公汽线路集合
