2007B题公交系统快速查询的优化模型.doc

公交系统快速查询的优化模型与算法此题为2007年高教社杯全国大学生数学建模竞赛B题，获该年全国一等奖。 队员：刘倩，陈哲赳，贾艳华 指导教师：肖华勇 摘要 对北京将要举办的第29届奥运会，交通问题十分重要。研制一种快速查询系统，帮助用户特别是那些不熟悉北京交通的用户，快速查询从出发点到目标站如何到达及最优路线十分重要。本文针对该实际问题，提出该问题的一般数学表达模型及有效的算法。 对问题一，我们采用一个三维0-1矩阵完整的表达了任意两站点间的线路信息。建立了表达任意两站点到达情况的0-1决策变量，并以换乘次数最少，时间最少，费用最少为目标的多目标非线性规划模型。为求解该模型，我们提出了以换乘次数为步长的快速有哪些信誉好的足球投注网站算法。并用邻接矩阵的方法计算出该城市公交网络系统通过2次换乘，可以完成99.98%站点对的互达，最多通过3次换乘，可以全部实现任意站点对的互达。对该有哪些信誉好的足球投注网站算法，我们还进行了算法复杂性分析，分析表明，该算法对换乘次数不大情况下是快速有效的。利用该算法，我们得到了问题一的结果： 对(1)S3359→S1828,我们得到2条换乘1次，时间为101分钟，费用3元的线路。同时得到4条换乘2次，时间为76分钟，费用3元的线路.对(2)、S1557→S0481,我们得到1条换乘2次，时间为106分钟，费用3元的线路。对(3)、S0971→S0485, 我们得到1条换乘1次，时间为128分钟，费用3元的线路, 同时得到1条换乘2次，时间为106分钟，费用3元的线路….更详细结果见附录一. 对问题二，我们提出标准线路的概念，将地铁线路，地铁站和公交站，和地铁相连的公交站，都当作新增的线路来考虑。文中重新考虑该线路的费用与时间，得到与模型一统一的模型。在算法上，利用地铁站的特点，首先计算出地铁任意站间的时间矩阵和费用矩阵。对两公交站(起始点和目标点)通过地铁到达情况，分为四种情况计算，分别采用合理算法进行有哪些信誉好的足球投注网站。得到结果如下： 对(1)（2）两对点，乘坐地铁对最优解没有改善,对(3)得到7条时间为96 分钟，费用为5元的线路. 对(4)得到1条时间为65.5分钟，费用为5元的线路, 对(5)得到1条时间为87.5分钟，费用为5元的线路, 对(6)得到1条时间为35分钟，费用为3元的线路.这些为问题一中费用最小的最优线路，提供了一种时间更少的线路。更详细结果见附录二. 对问题三，我们仍然把步行当作一种新的线路加入到问题一和二模型中。这里考虑线路费用为0，时间为步行时间.在实际中，则考虑对公交线路的补充，当只需要乘坐1~2站时，考虑步行。且只考虑对不多于一次且步行时间少于30分钟的情况 关键词：非线性规划, 邻接矩阵, 最优解, 算法复杂性 1．问题重述 略 2．基本假设 1） 不考虑各路段公交流量限制，无道路拥挤、堵车等耽搁、延误事件发生。 2） 假设各线路公交按理想情况到站、发车，无抛锚等意外事件发生，公汽、地铁均运行正常。 3） 不考虑公交容量问题，即不出现因等车人数过多，乘客无法在预定时间内搭乘预定公汽的现象。 4） 环行公汽到达终点站后，乘客必须离开，若继续乘坐本环行路线的下一班次公汽，属于换乘情况。 5） 原题附录所提供的信息均真实可信。 3．符号说明 符号含义路线－站点关系矩阵第条公交线路上由起点站起的第个站点包含站点A的线路的集合包含站点B的线路的集合的交集由站点的出行费用换乘次数为次到达目标站点时所需的出行费用由站点的出行耗时换乘次数为次到达目标站点时所需的出行耗时集合中的车辆可以到达的站点集合 4．问题分析 近年来，公共交通工具（简称公交，包括公汽、地铁等）已逐渐成为人们日常出行的主要交通工具，我国各城市的公交系统也迅速发展，公众出行较为通畅、便利。但与此同时，搭乘公交时，乘客也面临着多条线路的选择问题。 在这种情况下，研制开发出一个解决公交线路选择问题的自主查询计算机系统，已成为一个非常值得研究与探讨的问题。 公交线路选择问题的研究，涉及乘客心理、路段流量、公交容量、换乘耗时、及站点分配等诸多因素。这些因素彼此约束，内在联系较为细微，各种因素难以精确分析并予以量化，处理起来较为复杂。而且，由于大中型城市的公交线路数、站点数都已达到百、千数量级，数据处理的繁琐性进一步增大了问题本身的难度。 考虑到题中提供的信息容量，以及问题处理的实际可行性与复杂度，我们在研究线路选择问题并建立模型时，无法对所有相关因素都进行研究、处理。 为了简化模型，我们仅从出行耗时、出行费用、换乘次数等几个着手点，结合乘客心理进行问题的研究与分析。 首先，我们来分析公交线路选择的几大特点： 特点一：乘客需求的多样化。乘客在进行公交路线选择时，考虑的因素多种多样，有的乘客会侧重考虑出