2007全国大学生数学建模B题_公交查询系统特等奖

2007全国大学生数学建模B题_公交查询系统特等奖！公交查询系统的最佳乘车方案研究与设计【摘要】木文将站点实体间的线路选择抽象为图论最短路模型采用0-1整数规划衣述。建立直达数据库Q作为数据基库,根据用户需求建立不同口标的0-1规划模型运用邻接算法与分别求解,最终方案集通过多目标分层序列排序输出到用户终端。第一问,在数据处理阶段将直行、环行线路分别抽象为、条路线见建立査询系统时考虑服务器要同时响应多个请求,计算任务繁重,采用空间换取时间的策咯,先建立站点至站点直达数据库Q米描述两两可直达站点的所有线路,用户査询时,系统首先查询Q,得到所有直达车方案在没有自达车情況下,针对不同用户需求,目标考虑:转乘次数、总耗时、总费用、转站车辆是否始发、转乘站点负载量;在Q的基础上,量化不同目标为有向赋权图的不同权矩阵见,以所求顶点到顶点的路径是否包含弧为决策变量上述项用户需求为目标,始、终点连通为约朿建立0-1整数线性规划模型见模型Ⅰ为了能够为用户提供多种备选方案,我们首先使用基于的邻接算法求解,得到不同目标下的多种优化方案;对于邻接算法不易求解的多次转乘最优方案,我们采用软件自接求得仝局最优解:两种方法求解步骤见,综合方案集见表其中条线路时间最短目标分别为分钟两种求解方法的优劣在中给出了详细评价第二问考虑公汽与地铁混排方案,首先把各地铁站点和周围的公汽站点集抽象为同一新站点,把已知公汽线路到达都映射到,计算新直达数据库,再结合地铁的费用与地汽换乘等待时间就可以把地铁线与公汽线结合,建立多日标0-1整数线性规划模型见模型Ⅱ;对于转乘次数少于等于次的方案仍可通过邻接算法求解;对」邻接算法不易求解的多次转乘最优方案,虽然模型规模较人但约東与目标线性程度较好,还可用软件求解得出条线路的全局最优解;综合方案集见表其中条线路时间最短目标分别为、分钟;随后我们在与中给出了模型具体的评价与应用。第三问综合考虑所有站点间步行与乘车情况,将其抽象为最短路问题下的叠加有问赋权图,在此基础上以换乘次数为主要约東,以总行程时间包括步行最短、转站车辆始发数最人、转乘站点负毂量最小、费用最低为目标,建立多目标0-1整数线性规划模型见模型Ⅲ,并给岀了求解的一般步骤与算法。最后本文还对实现査询系统的具体方案给出了建议,对各模型在实际中的应用价值进行了详细讨论,并提出了改进方案。关键字:邻接算法有向赋权图直达队列表分层序列法叠加有向赋权图1问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行,届时有大量观众到现场观看奧运比赛,其中大部分人将会乘坐公共交通工具(简称公交,包括公汽、地铁等)出行。这些年来,城市的公交系统有了很大发展,北京市的公交线路已达800条以上,使得公众的出行更加通畅、便利,但同时也面临多条线路的选择问题。针对市场需求,某公司准备硏制开发一个解决公交线路选择问题的自主査询计算机系统。为了设计这样一个系统,其核心是线路选择的模型与算法,应该从实际情况出发考虑,满足查询者的各种不同需求。请你们解决如下问题:1、仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附汞数据,利用你们的模型与算法,求出以下6对起始站亠终到站之问的最佳路线(要有清哳的评价说明)(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S04854)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路,解决以上问题3、假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型。2问题分析本题主要在二三种不同情況下,研究仁意两站点之间的线路选择问题。联系实际,公众乘坐公交车主要考虑的因泰包括转乘次数、行程时间、车站始发情况、车站的车次负毂量及乘车费用等因素。为满足一般公众的乘车需求,主要按照公众对不同乘车信息的重视程度,确定出最佳的乘车路线。仪考虑公汽线路的情况下,首先,需要根据题目给岀的公交线路信息数据,对每条线路进行抽象处理,将分上下行的线路、双向行驶的线路和环行线路抽象为两条。然后,主要考虑公众最关心的乘车因素,即转乘次数。在最少转乘次数的基础上考虑共众对其他因素的需求,按照先后顺序考虑行程时间、车站始发情氿、车站的车次负载量及乘车费用,给出供公众选用的多种参考方案。并考虑以时间为主要目标的情况下,建立最优化模型确定任意两站点行程时间最短的方案。在考虑问题二的情况卜,根据地铁与邻近站点可换乘的信息,可将每个地铁站点及其对应的所有公交站点抽象成一个点处理。对于两条地铁线路可按照与问题一相同的抽象方法处理。在此基础上按照相冋的思路确定任意两站点问的最佳方案。考虑公交及地铁站点的实际分布情况,有时会出现步行小段距离再转车的情况更能节省时间或转车次数。因此,研究此种情况下的出行方案对节省出行时间具有重要的实际意义。3模型假设[1]假设车站不重名L2」假设各路经上公交车发车频度相同;[3]假设相邻站点间平均行驶时问一定;[4]假设不出现交通阻塞,公交运行顺畅;「5]假设不出现车辆故障及道路交通事故[6]假设始发终点出入地铁需要步行1分钟;L7」假设公交准点到达,不考虑红绿灯等待时间。4符号系统弧是否在该有向赋权图|站点→的总乘车时间;第个站点是否为→的始发站;站点→的乘车费用。5公汽站点之间线路选择模型(问题一)木节主要研究任意两公汽站点间线路选择的数学模型与算法。分别在不同行程需求下推荐最佳路线,给出更为人性化的站点负载压力及转乘点是否为始发站的提小。●通畅、便利目标:换乘次数最少不同的行程需求:行程耗时最少行程费川最少●人性化查询设计:转乘站点是否为始发站提示;站点负载压力提小基于此,本部分共分如下四小节5.0:数据处理,将三种公汽线路进行了图论抽象处理5.1:建立了可査询两站之间直达线路的“公汽直达数据库Q”;5.2:建立基于有向赋权图与最短路理论的0-1规划模型;5.3:针对模型分别使用不同方法求解,得到多种适合不同用户的方案集。5.0数据处理—三种公汽线路抽象处理根据题中信息,公汽线路分三种,下面将这三种线路进行数据处理:(1)下行线、上行线原路返回这种线路有两个端点站,在两个端点之间双向行车,而且两个方向上的行车路线相同,绎过同样的站点序列。由于线路的方向不同,因此,卜行线和上行线可以抽象成两条线路处理(2)线路为环行线实际中环形路线一般是双环,但在对这两条线路进行抽象时,为保证任意两站点距离最近,把每条线路再抽象成2条(如图所示)(3)下行线与上行线经过站点不同由于下行线与上行线经过站点不同,显然,该种线路需要抽象成两条线路处理5.1“公汽直达数据库”的建立从实际出发,结合公众出行心理,公汽线路选择应优先考虑两站点之间是否有直达午,那么在查询系统内部应设有任两站点的直达线路表,以方便查询时优先快速查询是否有直达车,若有,则直接输岀所有直达车辆;若无,再搜索换乘路线。在建立Q的时候,数据结构的选择非常重要,本题共有3957个站点,若Q內每个队列的毎个数据都使用奴精度实犁储存,实际在 MATLAB等软件内内存占用大约为2GB,这显然超越现阶段个人电脑极限,所以根据实际情况可以采用不同数据结构,本文采用MATLAB内建元胞结构,当元胞内队列不存在时不占用空问,具体元胞结构设计如下:车号费用耗时图1.1元胞结构示意图上图中Cel11:1,2}代表Q中第1行第2个元胞(即从站点S0001到站点S002的直达公交线路信息),元胞屮队列的每一行代表一辆直达车信息。5.2模型Ⅰ分析与建立从査询系统设计角度考虑,当输入起讫点后,系统内部通过Q査询无结果时,系统内部应自动搜寻换乘次数最少的路线,若换乘次数相同时有多种转乘方案,则系统应显小所有转乘烙线方案(包括转乘次数、行程总时间、途径总站点数、转乘站点及路线、是否始发、行程总费用、转承站点负载压力)以供査询者自主选择。同时,系统应冋査询者推荐“时间最短”,“费用最省”,“转乘站始发站最多”,“负载压力最小”的不同目标下的最佳路线。5.2.0基于不同目标的有向赋权图定义引川图论相关知识,将题中所提供的公汽网络抽象成一个有向赋权图中的每个顶点为每个不同的站点,如果从中的顶点到有直达路线,那么这两点之间就用冇向边相连,记做∈,方向为从指向,表示可从直达,相应的有一个数称为该有向边的权,这样公汽网络就抽象为一个有向赋权图。赋权图中的权可根据不同的目标进行定义,本模型在确定不同冂标时,将其分别定义为(具休分析见5.2.2)站点至站点的直达时间时间:其分量为+∞无直达线路站点至站点的直达费用费用:-()。其分量为+∞无直达线路始发:=()其分量为站点至站点的直达线路是否始发+∞无直达线路站点的负载量负载(),其分量为+∞无直达线路5.2.1最少换乘次数的确定在用户输入起点与终点后,系统需要立即给出至少要转乘几次才能够到达目的地这样就需要建立以下矩阵。统计中各元素长度,可得任意两站点的直达线路数。由此可构造表示两两站点间直达路线数目的直达线路数矩阵,通过矩阵运算可得到任两站点间换乘线路数矩阵,进而得到任两站点间的最少换乘次数矩阵=(),,从而可得任两站间所需的最少换乘次数1)直达线路数矩阵的建立引入直达线路数矩阵其矩阵元素表示第个站点到第个站点直达线路数,其中,当时为无效路径,设定值为,即:以表示所有公汽所经过的的站点总数,则直达线路数矩阼可表示为2)换乘线路数矩阵的建立直达矩阵为×阶方阵,矩阵的次幂屮元素表示任两站点问通过次转乘的路线数,即:其中,表示第个站点到第个站点通过次转乘的路线数,下面以第行第个元素为例对中元素意义进行举例说明:《例》:假设上式中等号右边仅=其余为,说明仅第个站点可直达到第个站点,第个站点可直达到第个站点,那么,即第站点可通过一次换乘到达站点,换乘点为站点。以表示方阵的次幂,为站点→的直达路线数,则其中,元素为通过次换乘从站点→的线路数。如=表示从站点到站点有条两次换乘路线,其换乘站点可通过运算参数记录得到。3)最少换乘次数矩阵的建立引入矩阵,其矩阵元素为使得≠的的最小值,∈∞,即:则1表示从站点→必要的最少换乘次数,以矩阵表示最少换乘次数矩阵,则其中,元素表示从站点→必要的最少换乘次数。基于最少换乘次数矩阵C,每对起始站→终到站的最少换乘次数如下:表1.0最少换乘次数表线路编号起始站终到站最少换乘5.2.2基于最短路理论的模型分析我们结合实际,主要考虑用户如下几个需求因素:目标一:换乘次数最少;目标二:行程时间最短;目标三:行程费用最少;目标四:转乘车辆始发最多;目标五:站点负载压力最小。目标分析目标一:换乘次数最少基于5.2.0建立的有向赋权图,引入0-1决策变量表示弧是否在起点与终点的路上,则弧位于顶点至顶点的路|若与之间无直接相连的弧,但可通过屮问节点转跳,表明由站点到之问不可直达,但可通过转乘到达,则由到之间换乘次数为绎过的总弧数减1,即换乘次数最小可表示为:目标二:行程总时间最短时间权值=(),则乘车总时间为公汽换公汽时间固定是5分钟,则换乘时间为行程总时间包括起始站点等待的3分钟,行程总时间最短表示为目标三:行程总费用最少设表示→车辆属性表小单一票制1元分段计价设表示→所过站数,那么一直达费用权=()表示为:行程总费用最少可表示为:∑目标四:转乘车辆始发最多为考虑所选路线中转乘站点是否为所需转乘车始发站,我们引入变量表示第个站点是否为→的始发站,即始发权=()第个站点是弧线路的始发站从→个站点的路线中转乘点为所转乘车的始发点最多的路线可表示为:目标五:站点负载压力最小首先假设终点站是奥运场馆,乘坐公车的人大多数都到达终点站,因此转车站点离始发站的站点数越少越好(人少):负载压力=转乘站点离始发站的站点数一转乘站点离终点站的站点数注:若终点站不是奥运场馆则可以通过对负载取绝对值表示离始发或终点越近转车越方便。oC始发终点如图所示,站点的负载压力-2-3--1,显然负载越小越好。根据式1.1,表示进入第个站点的径数,表示从第个站点出站的径数矩阵,以表示第个站点的负载压力权=()线路负载压力最小可表示为:约束分析1)换乘次数约束基于对日标一的分析,可得在有向赋权图中换乘次数表达式,以表示乘客所能接受的最大换乘次数,则换乘次数约束可表示为:)c∈∞且为整数其屮,参数为人为设定值,分以下三种情况当设定=时,为严格约束不能换乘2」当设定=∞时,为无乘车次数约束,即可无限次换乘;[3]当设定为不为0的常数时,为约束换乘次数在次以内的情况;《注》:参数可根据不同的计算需求进行自由选取。仅从数学模型角度考虑,为使模型更具通用性,的选取可到∞。从实际角度出发,查询系统中的值可由合询用户自己设定,当最小换乘次数小于时,输出无解。2)最短路起讫点约束由于为有向图,则其中顶点分为“起点”、“中间点”、“讫点”三类,对」起点只有出的边而无入的边,对于中间点既有入的也有出的边,对于讫点只有入的无出的边对有向图而言,若求顶点的最短路径,以表示进入第个顶点的边,以表示出第个顶点的边,则中的三类点约束可表示为:()eDE