B题交流

深蓝世界

九月我们再一次参加了全国大学生的数学建模竞赛,团队的力量是值得信奉的,现将我们关于B题的摘要和主要结果贴出以交流之用.

公交线路优选模型

摘 要
  
出行线路的选择是一个古老而现实的问题,为实现从出发点到目标点的最优路线选择，要考虑站点、费用等因素。因为乘车费用、时间是站点的线性函数，确定路线就是确定站点的有序集。
本文采用集合的方法将已知线路转化为有序集合（以运行方向为序），将转乘（即两条线路之交）化为两个集合作交集。从而确定候选路线，再通过功能函数对所选路线分费用、时间、站点、转乘次数分别寻优。
确定候选路线的核心是建立转乘一次的模型。因为多次转乘可化为多个一次转乘。
一次转乘可表述为含出发点S 的线路集中的某个线路 与含目的点 的线路集中的某个线路 存在交点 ，且 是 的后续点， 是 的前续点。根据这个模型设计算法，计算题目中所给6对点的结果见表1，其中1、3、4、6转乘一次，2、5转乘2次。如果把其它交通工具（如地铁）的站点数据转化成有序集合。模型仍可适应多种公交的路线选择，只要修改诸如费用、时间的功能函数。第二问得以解决（见表2）
进一步，考虑步行，使得在一定范围内的所有站点是通过步行相连的（原来没有公交相连），即：可将在一个 邻域内的所有站点视为一个站点（增加步行时间）。在模型Ⅰ的基础上，通过对地铁站附近的公交站合并（看成一个站点），并对实例进行计算，有相当理想结果（见表3）
再进一步，如果将 放大，即：将城市公交系统划分为若干区域，每个区域内的站点数将大大减少，区域内的查询和区域间的查询均变得简单起来。甚至可以直接利用Dijkstra算法求解。



关键词：最佳线路、有序集、Dijkstra算法、换乘

深蓝世界

题号        公车转站点和经过的线路        时间        费用        经过站点数        转乘次数
1        S3359->L436B->S1784->L167B->S1828        101        3        32        1
        S3359->L436B->S1784->L217B->S1828        101        3        32        1
2        S1557->L084B->S1919->L417A->S2424-L254A->S0481        112        3        34        2
3        S0971->L013B->S2184->L417B->S0485        128        3        41          1
4        S0008->L159B->S2683->L058B->S0073        83        2        26        1
        S0008->L159B->S2083->L057A->S0073        83        2        26        1
        S0008->L159B->S2683->L474A->S0073        83        2        26        1
5        S0148->L308A->S0036->L156A->S3233->L045B->S0485        121        3        37        2
        S0148->L308A->S0036->L157B->S1406->L045B->S0485        121        3        37        2
6        S0087->L454A->S3496->L209B->S3676        65        2         20        1

结果说明：
如表1中1题S3359->L436B->S1784->L167B->S1828理解为：从出发点S3359乘L436下行车到站点S1784，转乘L167下行车到达终点站S1828。

结果评价：
第1，3，4，6对起止点只需转乘一次即可。第2，5对起止点则需两次转车。
分别用直达、转乘一次、转乘二次，以满足经过站点最少，费用最少的功能函数分别计算的。因此提供的出行方案是分别站点最少，费用最少的。从结果看，同一线路得出的结果各项指标相差不大。

深蓝世界

题号        公车转站点和经过的线路        时间        费用        站数        转乘
次数
1        S3359->L15A->S3068->D8->D34->S0578->L167B->S1828        103.5        5        31        3
        S3359->L436B->S1784->L217B->S1828（不含地铁）        101        3        32        1
2        S1157->L437A->S2361->D11->D25->S525->L516A->S481        90.5        5        25        3
        S1557->L084B->S1919->L417A->S2424-L254A->S0481
（不含地铁）        112        3        34        2
3        S971->L94A（L119B）->S567->D1->D21->S466->L51A（或L450B）->S0485        96        5        31        2
        S0971->L013B->S2184->L417B->S0485（不含地铁）        128        3        41          1
4        S0008->L200A->S2534->D15->D25->S0525->L103A->S0073        53.5        5        13        3
        S0008->L159B->S2683->L058B->S0073（不含地铁）        83        2        26        1
5        S148->L024B->S1487->D2->D21->S464->L469B->S485        87.5        5        28        2
        S0148->L308A->S0036->L156A->S3233->L045B->S0485（不含地铁）        121        3        37        2
6        S0087->L021A->S0630->D29->D36->S0427->L097A->S3676        33.5        5        9        2
        S0087->L454A->S0541->S0540->L462A->S3676
（不含地铁，经过D31站公汽转公汽）        38        2        13        2
        S0087->D27->D36->S3676（不含公汽）        22.5        3        9        0

线路说明：
如表2中1题S3359->L15A->S3068->D8->D34->S0578->L167B->S1828理解为：从出发点S3359乘L15上行车到站点S3068，步行至地铁站点D8，乘坐地铁至站点D34，然后步行至站点S0578，转乘L167下行车到达终点站S1828。

结果评价：
分别用转乘一次、转乘二次，以满足经过站点最少，费用最少作为功能函数分别计算。因此提供的出行方案是分别站点最少，费用最少的。从经过看，同一线路得出的不同结果各项指标相差比较大。

深蓝世界

5.3 含步行的综合出行策略

一、分析
分析第二问第6个数据S0087→S3676的第二个运行结果，发现一个有趣的现象：结果为：S0087->L454A-S0541->S0540->L462A->S03676。并不含乘坐地铁，全部为公汽线路，且只要换乘一次，途经总站数仅为13，比第一问公汽之间转乘运行结果要好得多。
因为第二问在引入地铁时地铁站附近的不同公汽站之间的换乘相当于同一公汽站的换乘（仅增加了步行时间），具体来说地铁站D31附近的公汽站S0211，S0539，S0541，S0540可以看成一个公汽站。
这样提示我们：如果提供若干公汽站点聚集在一起的信息，那么在进行公汽之间的转乘时可以有更为便捷的线路。也就是说只要提供一定半径范围内各公汽站点的聚集信息，将获得更好的查询结果。
为了解决这类问题 ，将第一问进行扩展，将一定范围内的所有公汽站合并成一点。预期获得更准确的查询。
   设 是同一范围内的不同公汽站点，其构成集合为：
（K=1……n），有F（ ）=0，从公汽站点 到公汽站点 的最佳路线可表示为：  ，其中寻找S 、S   ，F为费用或时间或站点数功能函数,具体实现有如下两种方法:


1、算法F5.3.1
① 将线路向量 (r=1……520)中的站点 全部替换成
② 采用问题一的算法F3.2.2,计算从 到 的最佳线路。
2、算法F5.3.2
①分别计算 、 所有的线路集合   
     ②        （w﹥i）
               （u﹤j）
       如果有 、 则路线  =  是一条备选线路
     ③计算 F（ ）+F(S  )并保存最小值的路线
     ④回到②
算法F5.3.1与算法F5.3.1都是换乘一次的情况,如果换乘一次不能达到目的地,则可以参照前面的算法设计换乘二次或多次的程序。
算法F5.3.1简单，可以利用F5.1.1的程序直接计算,但需要替换原始的线路数据,可能影响实时计算速度。


算例1：出发点为S2336目标点为S0722

分别采用算法F5.1.1和F5.3.2计算有如下结果:
表3：合并站点计算实例
题号        公车转站点和经过的线路        时间        费用        经过站点数        转乘次数
F5.1.1        S2336->L006B->S1110->L389B->S0722        68        2        21        1
F5.3.2        S2336->L6-S0236->S0239->L1080->S722        35        2        8        1

很明显：F5.3.2找到的路线比F5.1.1找到的路线效果好得多。
因为S0236 、S0239没有公汽线路直接相通，F5.1.1无法找到通过他们的线路。但S0236 、S0239是地铁站 D17附近的两个公汽站，算法F5.3.2把一个邻域范围内的所有站点看成是直接相通的。因此F5.3.2获得了更好的结果。

机器爬虫

楼主的结果和我们的差不多，只是你没有计算初次等车的时间(公汽三分钟，地铁两分钟），和公汽通过地铁站台换乘公汽的时间（仅有走路的两分钟），既然题目给出了换乘时间还特别标出走路时间，就表示需要考虑这两点

下面是我们的答案

问题一

题号    时间    费用    站数    转乘        公车转站点和经过的线路

1       104     3       32  1   S3359->L436 下行 ->S1784->L167 下行 ->S1828
1       104     3       32  1   S3359->L436 下行 ->S1784->L217 下行 ->S1828

2       109     3       32  2   S1557->L084 下行 ->S1919->L189 下行 ->S3186->L460      ->S0481
2       109     3       32  2   S1557->L363 下行 ->S1919->L189 下行 ->S3186->L460      ->S0481

3       131     3       41  1   S0971->L013 下行 ->S2184->L417 下行 ->S0485

4       86      2       26  1   S0008->L159 下行 ->S0400->L474 上行   ->S0073
4       86      2       26  1   S0008->L159 下行 ->S2633->L474 上行   ->S0073
4       86      2       26  1   S0008->L159 下行 ->S3053->L474 上行   ->S0073
4       86      2       26  1   S0008->L159 下行 ->S2683->L058 下行 ->S0073
4       86      2       26  1   S0008->L159 下行 ->S0291->L058 下行 ->S0073
4       86      2       26  1   S0008->L159 下行 ->S3614->L058 下行 ->S0073
4       86      2       26  1   S0008->L159 下行 ->S0491->L058 下行 ->S0073
4       86      3       26  1   S0008->L159 下行 ->S2559->L058 下行 ->S0073
4       86      3       26  1   S0008->L159 下行 ->S2559->L464 上行   ->S0073
4       86      3       26  1   S0008->L159 下行 ->S3315->L058 下行 ->S0073
4       86      2       26  1   S0008->L355 下行 ->S2263->L345 上行   ->S0073
4       86      2       26  1   S0008->L355 下行 ->S3917->L345 上行   ->S0073
4       86      2       26  1   S0008->L355 下行 ->S2303->L345 上行   ->S0073
4       86      2       26  1   S0008->L463 下行 ->S2083->L057 上行   ->S0073

5       109     3       32  2   S0148->L308 上行   ->S0036->L156 上行   ->S2210->L417 下行 ->S0485
5       109     3       32  2   S0148->L308 上行   ->S0036->L156 上行   ->S3332->L417 下行 ->S0485
5       109     3       32  2   S0148->L308 上行   ->S0036->L156 上行   ->S3351->L417 下行 ->S0485

6       68      2       20  1   S0087->L454 上行   ->S3496->L209 下行 ->S3676


问题二

题号    时间    费用    站数        转乘        公车转站点和经过的线路

1       104     3       32  1   S3359->L436 下行 ->S1784->L167 下行 ->S1828
1       104     3       32  1   S3359->L436 下行 ->S1784->L217 下行 ->S1828

2       109     3       32  2   S1557->L084 下行 ->S1919同S1919->L189 下行 ->S3186->L460      ->S0481
2       109     3       32  2   S1557->L363 下行 ->S1919同S1919->L189 下行 ->S3186->L460      ->S0481

3       131     3       41  1   S0971->L013 下行 ->S2184->L417 下行 ->S0485

4       83      2       25  1   S0008->L159 下行 ->S0400同S2633->L474 上行   ->S0073

5       88.5    5       28  2   S0148->L024      ->S1487同D02->T1      ->D21同S0466->L051 上行   ->S0485
5       88.5    5       28  2   S0148->L024      ->S1487同D02->T1      ->D21同S0466->L450 下行 ->S0485
5       88.5    5       28  2   S0148->L024      ->S1487同D02->T1      ->D21同S0464->L104 上行   ->S0485
5       88.5    5       28  2   S0148->L024      ->S1487同D02->T1      ->D21同S0464->L395 下行 ->S0485
5       88.5    5       28  2   S0148->L024      ->S1487同D02->T1      ->D21同S0464->L469 下行 ->S0485

6       24.5    3       9  0    S0087同D27->L522 环形  ->D36同S3676

[ 本帖最后由 机器爬虫 于 2007-9-25 11:13 编辑 ]

qingquan1

哈哈！楼上的都很厉害
路过帮顶！

dianslmm

机器爬虫的答案比深蓝世界更好、更正确。

yangxh7

不错不错～～

bjyk2008

楼上的好厉害!
我想说转一次车并非花时间和钱最少,比如从3359到1828转二次车比转一次车少花近半小时
  如 3359-乘15-中转2903-乘201-中转481等-乘41-到1828       总用73分     花3元

bjyk2008

楼上的好厉害!
刚才打错了
我想说转一次车并非花时间和钱最少,比如从3359到1828转二次车比转一次车少花近半小时
  如 3359-乘15-中转2903-乘201-中转458等-乘41-到1828       总用73分     花3元