2007年B题公交查询系统的最佳乘车方案研究与设

2007年B题公交查询系统的最佳乘车方案研究与设时间:2009-03-2516:04来源:竞赛组委会作者:海航（青岛）汤点击:319次本文是2007年-高教社杯获得者。将站点实体间的线路选择抽象为图论最短路模型采用0-1整数规划表述。建立直达数据库Q作为数据基库，根据用户需求建立不同目标的0-1规划模型运用邻接算法与公交查询系统的最佳乘车方案研究与设计海军航空工程学院（青岛）汤志高、王继利、曹莹瑛指导教师曹华林【摘要】本文将站点实体间的线路选择抽象为图论最短路模型采用0-1整数规划表述。建立直达数据库Q作为数据基库，根据用户需求建立不同目标的0-1规划模型运用邻接算法与Lingo分别求解，最终方案集通过多目标分层序列排序输出到用户终端。第一问，在数据处理阶段将直行、环行线路分别抽象为2、4条路线(见5.0)。建立查询系统时考虑服务器要同时响应多个请求，计算任务繁重，采用空间换取时间的策略，先建立站点至站点直达数据库Q来描述两两可直达站点的所有线路，用户查询时，系统首先查询Q，得到所有直达车方案。在没有直达车情况下，针对不同用户需求，目标考虑：转乘次数、总耗时、总费用、转站车辆是否始发、转乘站点负载量；在Q的基础上，量化不同目标为有向赋权图的不同权矩阵(见5.2.0)，以所求顶点到顶点的路径是否包含xij弧为决策变量，上述5项用户需求为目标，始、终点连通为约束建立0-1整数线性规划模型(见5.2.3模型Ⅰ)。为了能够为用户提供多种备选方案，我们首先使用基于Dijkstra的邻接算法求解，得到不同目标下的多种优化方案；对于邻接算法不易求解的多次转乘最优方案，我们采用Lingo软件直接求得全局最优解；两种方法求解步骤见(5.3.1)，综合方案集见(5.3.2表1.1~1.6)，其中6条线路时间最短目标分别为67、102、106、62、105、49(分钟)；两种求解方法的优劣在5.4中给出了详细评价。第二问考虑公汽与地铁混排方案，首先把各地铁站点和周围的公汽站点集抽象为同一新站点，把已知公汽线路到达都映射到，计算新直达数据库，再结合地铁的费用与地汽换乘等待时间就可以把地铁线与公汽线结合，建立多目标0-1整数线性规划模型(见6.2.3模型Ⅱ)；对于转乘次数少于等于2次的方案仍可通过邻接算法求解；对于邻接算法不易求解的多次转乘最优方案，虽然模型规模较大但约束与目标线性程度较好，还可用Lingo软件求解得出6条线路的全局最优解；综合方案集(见6.3.2表2.1~2.6)，其中6条线路时间最短目标分别为65、102、98、56.5、89.5、30(分钟)；随后我们在6.4与6.5中给出了模型具体的评价与应用。第三问综合考虑所有站点间步行与乘车情况，将其抽象为最短路问题下的叠加有向赋权图，在此基础上以换乘次数为主要约束，以总行程时间(包括步行)最短、转站车辆始发数最大、转乘站点负载量最小、费用最低为目标，建立多目标0-1整数线性规划模型(见7.3模型Ⅲ)，并给出了求解的一般步骤与算法。最后本文还对实现查询系统的具体方案给出了建议，对各模型在实际中的应用价值进行了详细讨论，并提出了改进方案。关键字：邻接算法有向赋权图直达队列表分层序列法叠加有向赋权图1问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2问题分析本题主要在三种不同情况下，研究任意两站点之间的线路选择问题。联系实际，公众乘坐公交车主要考虑的因素包括转乘次数、行程时间、车站始发情况、车站的车次负载量及乘车费用等因素。为满足一般公众的乘车需求，主要按照公众对不同乘车信息的重视程度，确定出最佳的乘车路线。仅考虑公汽线路的情况下，首先，需要根据题目给出的公交线路信息数据，对每条线路进行抽象处理，将分上下行的线路、双向行驶的线路和环行线路抽象为两条。然后，主要考虑公众最关心的乘车因素，即转乘次数。在最少转乘次数的基础上考虑共众对其他因素的需求，按照先后顺序考虑行程时间、车站始发情况、车站的车次负载量及乘车费用，给出供公众选用的多种参考方案。并考虑以时间为主要目标的情况下，建立最优化模型确定任意两站点行程时间最短的方案。在考虑问题二的情况下，根据地铁与邻近站点可换乘的信息，可将每个地铁站点及其对应的所有公交站点抽象成一个点处理。对于两条地铁线路可按照与问题一相同的抽象方法处理。在此基础上按照相同的思路确定任意两站点间的最佳方案。考虑公交及地铁站点的实际分布情况，有时会出现步行小段距离再转车的情况更能节省时间或转车次数。因此，研究此种情况下的出行方案对节省出行时间具有重要的实际意义。3模型假设[1]假设车站不重名；[2]假设各路经上公交车发车频度相同；[3]假设相邻站点间平均行驶时间一定；[4]假设不出现交通阻塞，公交运行顺畅；[5]假设不出现车辆故障及道路交通事故；[6]假设始发终点出入地铁需要步行4分钟；[7]假设公交准点到达，不考虑红绿灯等待时间。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内建元胞结构，当元胞内队列不存在时不占用空间，具体元胞结构设计如下：Cell{1,1}Cell{1,2}车号费用耗时L001227L076318Cell{1,3}Cell{2,1}Cell{2,2}Cell{2,3}图1.1元胞结构示意图上图中Cell{1,2}代表Q中第1行第2个元胞（即从站点S0001到站点S0002的直达公交线路信息），元胞中队列的每一行代表一辆直达车信息。5.2模型Ⅰ分析与建立从查询系统设计角度考虑，当输入起讫点后，系统内部通过Q查询无结果时，系统内部应自动搜寻换乘次数最少的路线，若换乘次数相同时有多种转乘方案，则系统应显示所有转乘路线方案（包括转乘次数、行程总时间、途径总站点数、转乘站点及路线、是否始发、行程总费用、转承站点负载压力）以供查询者自主选择。同时，系统应向查询者推荐“时间最短”，“费用最省”，“转乘站始发站最多”，“负载压力最小”的不同目标下的最佳路线。5.2.0基于不同目标的有向赋权图定义引用图论相关知识，将题中所提供的公汽网络抽象成一个有向赋权图,中的每个顶点为每个不同的站点,如果从中的顶点到有直达路线，那么这两点之间就用有向边相连,记做，方向为从指向，表示可从直达，相应的有一个数称为该有向边的权，这样公汽网络就抽象为一个有向赋权图。赋权图中的权可根据不同的目标进行定义，本模型在确定不同目标时，将其分别定义为（具体分析见5.2.2）时间：其分量为费用：其分量为始发：其分量为负载：其分量为5.2.1最少换乘次数的确定在用户输入起点与终点后，系统需要立即给出至少要转乘几次才能够到达目的地，这样就需要建立以下矩阵。统计Q中各元素长度，可得任意两站点的直达线路数。由此可构造表示两两站点间直达路线数目的直达线路数矩阵，通过矩阵运算可得到任两站点间换乘线路数矩阵，进而得到任两站点间的最少换乘次数矩阵，从而可得任两站间所需的最少换乘次数。1）直达线路数矩阵的建立引入直达线路数矩阵，其矩阵元素表示第个站点到第个站点直达线路数，其中，当=时为无效路径，设定值为0，即：(1.1)以表示所有公汽所经过的的站点总数，则直达线路数矩阵可表示为：2）换乘线路数矩阵的建立直达矩阵为阶方阵，矩阵的2次幂中元素表示任两站点间通过1次转乘的路线数，即：其中，表示第个站点到第个站点通过1次转乘的路线数，下面以第1行第2个元素为例对中元素意义进行举例说明：《例》：假设上式中等号右边仅、，其余为0，说明仅第1个站点可直达到第3个站点，第3个站点可直达到第2个站点，那么，即第1站点可通过一次换乘到达2站点，换乘点为站点3。以表示方阵的次幂，为站点→的直达路线数，则：(1.2)其中，元素为通过次换乘从站点→的线路数。如表示从站点4到站点3有1条两次换乘路线，其换乘站点可通过运算参数记录得到。3）最少换乘次数矩阵的建立引入矩阵，其矩阵元素为使得的的最小值，，即：(1.3)则-1表示从站点→必要的最少换乘次数，以矩阵表示最少换乘次数矩阵，则：(1.4)其中，元素表示从站点→必要的最少换乘次数。基于最少换乘次数矩阵C，每对起始站→终到站的最少换乘次数如下：表1.0最少换乘次数表线路编号123456起始站S3359S1557S0971S0008S0148S0087终到站S1828S0481S0485S0073S0485S3676最少换乘1211215.2.2基于最短路理论的模型分析我们结合实际，主要考虑用户如下几个需求因素：目标一：换乘次数最少；目标二：行程时间最短；目标三：行程费用最少；目标四：转乘车辆始发最多；目标五：站点负载压力最小。目标分析目标一：换乘次数最少基于5.2.0建立的有向赋权图，引入0-1决策变量表示弧是否在起点与终点的路上，则：若与之间无直接相连的弧，但可通过中间节点转跳，表明由站点到之间不可直达，但可通过转乘到达，则由到之间换乘次数为经过的总弧数减1，即换乘次数最小可表示为：(1.5)目标二：行程总时间最短时间权值，则乘车总时间