公交查询系统的最佳乘车方案研究与设计

1、公交查询系统的最佳乘车方案研究与设计摘要本文要求设计一个公交线路计算机自助查询系统，针对不同需求的出行者推 荐相应的最佳路线。这是一个多目标决策的网络优化问题，并且随着问题的深入 逐层递进，我们建立了三个多目标优化模型解决此问题。针对问题一，将三种不同的公汽线路抽象化，建立站点间直达线路信息存储 元胞结构。调查分析得岀，尽管乘客对公交线路的需求侧重点各有不同，但都包 括乘车次数少、时间短、费用少和拥挤程度低，以前三个量为目标，拥挤程度为 约束，建立多目标整数规划模型，根据多目标分层序列法，出于对乘客不同需求 的考虑，采用3种对每个需求侧重程度不同的策略，利用局部搜索算法，求岀6 条线路在3种不

2、同策略下的最优线路(最佳线路见表(1)至(3)o针对问题二，同时考虑公汽与地铁线路，将地铁站点与邻接的公汽站点抽象 为同一新站点，重新建立站点间直达线路信息存储元胞结构。在问题一的基础上 增加考虑地铁站对费用、换乘时间和行驶时间的影响，仍然以乘客对线路的三种 主要需求为目标，以拥挤程度为约束，建立多目标整数规划模型，利用matlab 软件编程求解得到3种不同策略下的最优路线(最佳线路见表(4)至(6)o针对问题三，增加考虑步行的出行方式，在公汽站点间当站点数目不超过2 时，可以以步行代替，从而减少换乘次数。在此基础上，按换乘次数少、时间短、 费用少的顺寻建立多目标整数规划模型，利用matlab

3、软件编程求解得到相应的 最佳路线。以线路s1557->s0481和s0148->s0485为例，最佳路线分别为： s1557-步行 2 站f s2143-l084-s1919-l043-s3077-l273,需 3 元,92 分钟; s0148->步行 1 站s3182-l308-s36-l157-s0722-步行 1 站->s0485,需 2 元，69分钟。关键字 元胞结构多目标整数规划 多目标分层序列法 局部搜索算法1 问题重述1.1问题背景传承华夏五千年的文明，梦圆十三亿华夏儿女的畅想，我国人民翘首企盼的 第29届奥运会明年8月将在北京举行!在观看奥运的众多方式之

4、中，现场观看无 疑是最激动人心的。届吋有大量观众到现场观看奥运比赛，其中大部分人将会乘 坐公共交通工具(简称公交，包括公汽、地铁等)出行。为了迎接2008年奥运 会，北京公交做了充分的准备，首都的公交车大都焕然一新，增强了交通的安全 性和舒适性，公交线路己达800条以上，使得公众的出行更加通畅、便利。但同 时也面临多条线路的选择问题。为满足公众查询公交线路的选择问题，某公司准 备研制开发一个解决公交线路选择问题的自主查询计算机系统。12待解决的问题这个系统的核心是线路选择的模型与算法，另外还应该从实际情况出发考 虑，满足查询者的各种不同需求。需要解决的问题有：1、仅考虑公汽线路，给出任意两公汽

5、站点之间线路选择问题的一般数学模型与 算法。并根据附录数据，利用模型与算法，求出以下6对起始站到终到站最佳路 线(要有清晰的评价说明)。(1)、s3359-s1828(2)、s1557->s0481(3)、s0971-s0485(4)、s0008-s0073(5)、s0148->s0485(6)、s0087->s36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问 题的数学模型。2 问题假设假设一：各路线公交车发车频度相同；假设二：相邻站点间平均行驶吋间一定；假设三：公交运行顺畅：无交通阻塞、无车辆故障、无道

6、路交通事故等意外情况;假设四：公交准点到达，不考虑红绿灯等待时间；假设五：乘客在起始站时不考虑拥挤程度，只在转乘时考虑拥挤程度；假设六：乘客到起始站乘车时，不考虑等车时间；假设七：同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，在此换乘 过程中不考虑换乘时间和费用。3. 符号说明4站点z间的最小换乘次数岭实际换车次数从站点j到站点丿的费用坊表示站点2到站点经过的站点数目叫j表示从起始站startp到终点站endp的站点数au表示从站点z上车时站点i距离startp的站点数表示从起始站i到终点站j公汽换乘公汽的次数4表示从起始站2到终点站丿公汽换乘地铁的次数z：表示从起始站i到终点站j地铁

7、换乘公汽的次数表示从起始站7到终点站丿地铁换乘地铁的次数站点i到站点丿的步行时间t邻近站点的时间上确界任意两个邻近站点平均步行时间t表示邻接公汽站点间的步行时间4. 问题分析这是一个多目标决策的网络优化问题。公交查询系统需要满足查询者各种不 同需求，给出最优方案，这是我们建立模型的根木出发点，有关问题的求解随着 规模扩大将逐层深入。对于问题一，题目给出的公汽线路主要分为上下行线、原路折回线及环行 线，线路不同，选择不同，故对每种线路需要进行抽象化处理。站点较多，信息 量较多，需要选择合适的存储方法存储数据，存储题中的线路名、车号和时间。 解决这些问题后，就要对乘客的出行需求进行调查，看看乘客出

8、行时主要考虑哪 些因素，根据调查结果可以选定主要的需求建立多目标规划模型。本题数据量较 多，一般的算法可能不能处理，所以要探索合适的算法，然后用matlab软件编 程求解，可以求岀不同需求的岀行者相应的公交路线。对于问题二，在问题一的基础上更进一步探讨同时考虑公汽和地铁线路的 情况。我们同样需要对地铁线路进行抽象化处理，基于假设七，同一地铁站与邻 接的公汽站可以进行归一化处理，因为这些站点间的换成无需支付地铁费并且时 间可以忽略不计，还要将地铁站相关信息和公交站相关信息合理存储。根据问题 一屮的乘客需求，同样建立多冃标规划模型，但由于有了地铁这种出行方式，在 乘车费用与车辆换乘方面有所不同。设

9、计合适的算法，编程求解得到不同需求的 乘客相应的最优路线。对于问题三，该问在问题二的基础上增加考虑步行对最优路线选取带来的 影响，可以把步行作为另一种交通工具进行考虑。根据实际情况对步行相关信息 做出合理的假设，由于步行这种出行方式不花费时间，对换乘次数以及换乘方式 都没有影响，只改变出行时间。所以在问题三中，我们对出行时间优先考虑，再 考虑换乘次数和乘车费用，同样建立多目标优化模型，运用matlab编程求解得 到任意站点间的最佳路线。5 问题一的解答问题一仅考虑公汽线路，我们建立了模型一进行求解。5.1问题一的数据处理 5.1. 1三种公汽线路的处理根据题屮信息，我们知道公汽线路分三种，下面

10、将这三种线路进行数据处理: 下行线是上行线原路返回这种线路有两个端点站，在两个端点之间双向行车，而且两个方向上的行车 路线相同，经过同样的站点序列，只是线路的方向不同；上行线与下行线的站点名不完全相同这种线路与下行线是上行线的原路返回不同，下行线与上行线经过的站点不 完全相同，但是起始站和终点站相同； 线路为环形线对环形线路的站点进行分析，把一个环形拉成一条直线，以该直线的终 点为对称点进行翻折，将终点左边的直线对称到右边，形成该直线的延长 线，如下：这种环形线原有的路线包括：12, 13, 14, 23, 24, 34, 21, 31, 41, 32, 42, 43,抽象成直线后的路线有：1

11、2, 13, 14, 23, 24, 34, 43, 42, 41, 32, 31, 21,与 原路线相同，所以这种抽象方法是合理的。5.1.2建立“公汽直达数据库dm ”从实际出发，结合公众出行心理，公汽线路选择应优先考虑两站点z间是否 有直达车，那么在查询系统内部应设有任两站点的直达线路表，以方便查询时优 先快速查询是否有直达车，若有，则直接输出所有直达车辆；若无，再搜索换乘 路线。在数据导入的过程中，首先考虑直接从文本文件导入matlab中，但是本题共 有3957个站点，520条公交线路，若每个队列的每个数据都是用双精度进行存 储，那么内存占用大，实际输岀时运行时间长，考虑到所存储的信息

12、量包括公汽 号、公交站点、乘车时间以及乘车费用等多个因素，所以采用matlab中的元胞数 组建立公汽直达数据库dm进行存储（建立数据库dm的代码详见附录一）,节 省存储空间。5. 2模型一的准备5. 2. 1公交乘客的出行需求公交线网优化的最终目的是尽最大可能满足乘客的出行需求。建立合理的线 网优化模型，重要的一点是通过对居民出行心理、行为进行调查研究，以确定模 型的优化目标和约束条件。居民公交出行需求，是居民对公交服务的期望。由于我们设计出来的系统需要满足查询者不同的需求，要建立合适的出行路 线选择模型，必须对公交乘客选择出行路径时需要考虑的因素进行调查分析。我 们对随州市居民的出行需求进行

13、调查结果，用excel画出居民对出行时的费用、 乘车时间、乘换次数、步行时间以及拥挤程度的统计结果如下图（1）:系列1图（1）:居民出行需求结果的统计我们可以看到，出行者对不同因素的看重比例是不同的，该市居民出行需求 对于北京这样的大城市也同样适用。由于一般情况下路程长短和所用时间是密切 联系的，乘客关注路程也是为了节约时间，所以问题中已经将路程的相关信息转 化成为吋间了，即只需考虑时间最短。因此我们的模型中对公交网络的优化需要 考虑四个主要优化目标：换乘次数最少，时间最短，费用最少，拥挤程度最低。5. 2. 2换乘次数的抽象根据公交线路的设计，尽管起始站和终点站位置相同，也可能有多种乘车方

14、式，这些乘车方式中可能是育达的，也可能要转乘一次，也可能需转乘两次，或 三次及三次以上，以startp表示起始站,endp表示终点站，那么某乘客从startp到劲dp的儿种乘车方式如下:直达的示意图startp换乘一次的示意图如果公交线路设计合理的话，那么几乎所有的站点均可以在转成两次以内达 fi的地，而且乘换次数过多，容易使乘客产生烦躁情绪，需要更长的时间和更多 的费用；因此在设计算法时，只搜索直达、换乘一次和换乘2次的乘车方案。5. 2. 3计算机系统自主查询路线的流程通过上述调查显示的统计结果得知，乘客乘车都会考虑换乘次数，时间，费 用以及拥挤程度的问题，但是不同的乘客对这些需求考虑的先

15、后次序不同，比如: 度假的乘客，一般会首先考虑乘车时间；所带行李较多的乘客，一般会首先考虑 拥挤程度和换乘次数等。一般情况下，人们往往会选择直达，也就说如果两站点之间有直达车 辆，乘客会选择肓达。由于肓达的车辆不止一辆，可以根据不同乘客的需 求，选择相应的最优方案。当没有直达车辆吋，乘客可以根据自己不同的 需求，选择属于自己的最优路线。根据上述分析，我们构建的公交线路选择问题的自主查询计算机系统应该考 虑不同乘客对不同需求的重视程度，根据上述分析，公交线路自主查询系统的流 程如下图(2)：换乘次数最短 时间最短 花费最少图(2):公交线路自主查询系统的流程图53模型一的建立我们要建立如图(2)

16、所示的公交线路自主查询系统，就要对不同行程需求的 乘客推荐相应的最佳路线，根据实际情况可以确定三个目标，分别为：换乘次数, 乘车时间，乘车费用。结合数据处理中的实际情况，不同的乘客对不同需求的重视程度不同，所以 对于不同的乘客，我们要给出相应的最佳路线，从三个方面综合考虑，分别给出 优先考虑乘换次数以及优先考虑乘车时间的最优推荐路线。我们考虑运用多冃标 优化设计的分层序列法建立模型，进行求解，在此引入多目标分层序列法。多目标分层序列法：将鸟个目标函数按重要程度排序g也,其中広的 优先级最高，应该首先得到满足，其次是心，直到得出满足所有的目标函数的解, 或是此吋的解只有一个。根据实际情况，可以根

17、据多目标优化设计的分层序列法对我们建立的三个目 标函数的顺序进行调整，得到不同乘客所对应的不同的最佳路线。当满足这些冃 标的路线不止一条时，我们选取离始发站最近的解，因为离始发站越近，公交的 拥挤程度相对越小。当以某个目标函数作为第灯个目标函数，即决策变量时，只需将该目标函数 的顺序进行调整，使之成为第人个目标函数。当目标函数有三个时，排序后共有 六种可能的情形，但不是每种情形都要考虑。根据调查结果，我们确定了乘客出 行时考虑较多的三种类型，在此分别称为策略一、策略二和策略三。策略一：按换乘次数最少、策略二按乘车时间最短、策略三：按换乘次数最小、乘车时间最短、 换乘次数最少、 乘车费用最少、乘

18、车费用最少的顺序考虑; 乘车费用最小的顺序考虑; 乘车吋间最短的顺序考虑。5. 3.1确定目标函数在建立的公汽直达数据库dm的基础上，分别确定三个冃标函数。target one :乘换次数最少设厶“表示站点之间的换乘次数，根据公交线路的设计，尽管起始站和终点 站位置相同，也可能有多种乘车方式，这些乘车方式中可能是直达的，也可能要 换乘一次，也可能需换乘两次。将换乘次数作为第/个目标，希望在满足该要求 的基础上再考虑其它方案，即在建立的公汽直达数据库dm中进行搜索，如果有直 达方案，仅在直达方案屮推荐满足其它fi标函数的最佳路线。那么冃标一要求厶“ 最小，即min lj otarget two

19、:乘车时间最少通过分析我们知道，乘车中的时间包扌4行驶时间和换乘时间。基于假设六, 乘客到起始站乘车时，不考虑等车时间。而车辆换乘的过程实际上包括换乘时间 和等车时间。公汽换公汽时间固定是5分钟，则换乘吋间(包括换乘过程中的等 车时间)为：5a.设实际换车次数为岭，那么实际乘车的数量为岭+ 1,所以行驶总时间为： 工讥岭+ 1)，其中九 “庐2ijee那么乘车时间为：工© (岭+1) + 5九ijee即第二个目标函数为： min为讥岭+1) + 5九ijeetarget three :乘车费用最少乘车费用分为单一票价与分段计价两种方式，用伤表示从站点，到站点 丿的计费方式，那么如=；

20、，其中1表示单一票价，2表示分段计费；又由于分 段计价的票价为：020站：1元；2140站：2元40站以上：3元，可设吊 表示站点i到站点/经过的站点数目，那么从站点i到站点/的费用坊为：1， 仏=1)_ 1,(,=2,l<s,<20)坊 _2,仏=2,20 vs产 40)3,(<7,7 =2,5. >40)那么行程总费用为：工坊(岭+1)ijee从而得到第三个目标函数为：跡工坊何+1)ijee综上我们建立的多口标整数规划口标函数为：min 址min工讥岭+ l) + 5ijeemin工肌岭+ 1)ijee5. 3. 2确定约束条件模型屮我们仅考虑换乘2次的路线，所以实

21、际换车次数岭应该大于换车次 数的最小值，但是小于2,即q 5vjj 52；当确定的最佳路线的换乘次数、乘车 时间和乘车费用相同时，考虑以拥挤程度的高低来确定最终的最佳路线。拥挤程度：实际生活中，当离起始站点越近时，车上的乘客越少。设©表 示从起始站startp到终点站endp的站点数0 , aif表示从站点2上车时站点i距离 s九切的站点数，那么知的最小值越接近州表示拥挤程度越高，知的最小值越 接近0表示拥挤程度越低。所以owm加6/. < /?,. o 所以模型一的约束条件为：0 < min ai <5十2ijee5. 3. 3确定模型一综上所述，可以确定多目标整

22、数规划模型为：min limin工讥岭+1) + 5九hjeemin工坨(岭+ 1)ijee0 < min au < nijjst九5岭s2、i,jw e5. 4模型一的求解5. 4. 1算法设计基于局部搜索和优化枚举的算法，我们充分利用公交网络自身的特点，采用 局部搜索思想，对三种不同的策略进行分类，在每种策略屮求出最优解。首先根 据乘客输入的起始点和终点，分别对存储的数据进行搜索，筛选出可行的线路； 然后根据三种不同的策略在选出的可行路线中，选出每种策略的最优方案。具体 算法实现过程如下：1) 输入起始点i,终点丿以及选择的策略种类4 "1,2,3；2）搜索从站点7可

23、乘坐公交线路的集合/?（：）,在终点可乘坐公交线路的集合r（j）；3）判断是否直达； /?或/?（刀是空集，说明两站之间没有线路可以到达 r（i）cr（j） = o,说明两站之间不能直达，转入4） rcr（j"o,说明两站之间可以直达，转入8）4）以起始点搜索直达下有站点的集合m ,以终点搜索直达上游站点集合5）判断是否是一次换车 mcnho,存在一次换车就可到达，转入8） m cn = 0,不存在一次换车就可到达，转入6）（注：mcn*0中，可能包含直达路线，要筛选剔出）6）扫描是否vmen ,若存在（m,z?）,则可以直达，若不存在，则将点力加入集合f ,集合f表示需要换车两次；

24、7）判断是否需要两次换车集合f不是空集，转入8）集合f是空集，不考虑8）基于三种不同的策略，推荐最优乘车线路5. 4. 2求解结果根据上面的算法思想，可以运用ma1tab软件进行编程（代码详见附录 二），由于我们釆用的是多目标分层序列整数规划模型，所以根据确定的三种 不同的策略，可以得到相应策略的最佳路线，表（1）至表（3）分别给出了三种不同 策略下题中要求解的六条线路的最佳路线。表（1）：策略一中六条线路的最佳路线线路换乘次数时间花费坐车路线距离始发站s3359-s182811013l436-s1784-l21717s1557-s04812763l084-s1919-l043-s3077-l

25、2732& 20s0971-s048511283l013-s2184-l41714s0008-s00731832l355-s2263-l34511s0148-s04852733l024-s1234-l505-s516- l10416, 23s0087-s36761652l454-s3496-l2096（注：策略一按换乘次数、乘午时间、乘午费用的顺序进行考虑）表（2）：策略二中六条线路的最佳路线线路时间换乘次数花费坐车路线距离始发站s3359-s18287323l324-s2027-l201-s458 -l0417, 10s1557-s04817623l084-s1919-l043-s3

26、077-l27328, 20s0971-s04856423l013-s345-l505-s516-l10417, 23s0008-s00733723l150-s1381-l290-s3645-l02031, 17s0148-s04857323l024-s1234-l505-s516- l10416,23s0087-s36764623l021-s88-l231-s427- l09714, 3（注：策略二按乘车时间.换乘次数、乘车费用的顺序进行考虑）表（3）：策略三中六条线路的最佳路线线路换车次数花费时间坐车路线距离始发站s3359-s182813101l436-s1784-l21717s1557

27、-s04812376l084-s1919-l043-s3077-l27328,20s0971-s048513128l013-s2184-l41714s0008-s00731283l355-s2263-l34511s0148-s04852373l024-s1234-l505-s516- l10416, 23s0087-s36761265l454-s3496-l2096（注：策略三按换乘次数、乘车时间、乘车费用的顺序进行考虑）5. 5模型一的结果分析比较表仃）至表（3）的结果，可以看到策略一和策略三的结果完全一样，这主 要是因为乘坐公交的费用变化不显著，每经过20个站点才增加一元钱，这样一来 在某

28、个范围内，乘坐公交的费用相差不会很远，所以对路线的选取不会有太大影 响。我们纵向比较三种策略的时间，将三种策略下的时间变化作图如下：13012011010090807060504030策略一六条线路时间的变化f/策略三六条线路时间的变化/一/. /x/- /策略二六条线路时间的变化1 1三条11.522.533.544.555.56六条线路图（3）：三种策略的时间比较由图可以看出，优先考虑时间和优先考虑换乘次数时，推荐的最优路线在乘 车时间上的波动很大，说明我们的策略分配是合理的。对于比较重视时间的乘客, 优先考虑时间，就会节约很多时间；对于不赶时间，觉得换乘麻烦而重视换乘次 数的乘客，相对来

29、说所需时间要多。以第三条线路s0971-s0485为例，优先考 虑乘车时间时，需要37分钟，而优先考虑乘换次数时，需要128分钟，即优 先考虑时间比优先考虑乘换次数在这条线路上可以节约91分钟。所以针对 不同的乘车需求，我们确定了不同的乘车策略是非常有必要的。6.问题二的解答问题二同吋考虑公汽与地铁线路，我们建立了模型二进行求解。6.1问题二的数据处理6.1. 1对两条地铁线路的处理基于对三种公汽线路路线的抽彖方法，用相同的方法对两地铁线路7；,7；进 行抽象化处理。7；：返回时沿原路返回，这种线路有两个端点站，在两个端点之间双向行车，而 r两个方向上的行车路线相同，经过同样的站点序列，只是线

30、路的方向不同； t2 :环行线路，根据对公汽线路中环形线路的抽象方法把地铁线路中的环形线路 拉成1条直线。6. 1. 2归一化处理由地铁换乘公汽信息数据文件可知，同一地铁站对应的任意两个公汽站之间 可以通过地铁站换乘(无需支付地铁费)，从而可以认为在实际情况中，同一地铁 站点与对应的公汽站点之间距离很近，为了简化该问题，可以将这些站点作为一 个站点进行考虑。我们将其抽象化处理如下图(4)：基于这种思想，在整个交通网络中将同一地铁站点及其紧邻站点分别做归一 站点处理，可以认为在新站点所代表的站点集中的任意站点间的距离可以忽略不 计，从而时间也可忽略不计。6.1.3建立“公汽、地铁直达数据库dm&

31、#39;"原公交站点有3957个，考虑地铁站点后，站点总数增加至3996个，如果按 照建立数据库dm的方法存储数据，那么数据更新的过程所需时间很长，不太实 际。所以采用将归一化处理后的站点以txt （详见附录三）的形式存储，把39个 地铁站加入到原来的dm数据库中，把归一化处理的新站点以函数的形式导入到 数据库，形成一个新的数据库dm地铁费用和地铁换乘公汽的等待时间均被 填充到元胞内，将新数据库中的站点称为新站点。那么建立dm'的实质是新站 点与新站点间的直达线路信息集。用户输入起点和终点后，系统内部先自动查找 两点所屈的新站点，然后查找新站点间可直达的线路，并给出起点及其附

32、近站点 直达终点及其附近站点的最佳乘车线路。6. 2模型二的建立按换乘次数最少、 按乘车时间最短、 按换乘次数最小、乘车时间最短、乘车费用最少的顺序考虑; 换乘次数最少、乘车费用最小的顺序考虑; 乘车费用最少、乘车吋间最短的顺序考虑。问题二同时考虑公汽与地铁线路，乘客的需求分析与问题一中相同，要建立 公汽、地铁线路计算机自主查询系统，对不同行程需求的乘客推荐相应的最佳路 线，仍然采用多目标分层序列法，确定三个目标，分别为：换乘次数，乘车吋间, 乘车费用。根据调查结果，我们考虑乘客出行时考虑较多的三种类型，在此分别 称为策略一、策略二和策略三。策略一策略二策略三6. 2.1确定目标函数在建立的公

33、汽、地铁直达数据库dat的基础上，分别确定三个目标函数。 target one :乘换次数最少设坊表示站点之间的换乘次数，根据公交线路的设计，尽管起始站和终点 站位置相同，也可能有多种乘车方式，这些乘车方式屮可能是直达的，也可能要 换乘一次，也可能需换乘两次。在建立的公汽、地铁直达数据库dvt屮进行搜 索，如果有直达方案，仅在直达方案中推荐满足其它fi标函数的最佳路线。那么 要求览最小，即m加l；jo target two :乘车时间最少基于假设六，到起始站等车的时间忽略不计，那么乘车时间包括行驶时间和 换车吋间。设石是各站最快直达时间，匕;是实际转车次数，则行驶时间为化;+ 1）在起始站点i

34、到终点站丿的过程中，设zf表示在此过程中从公汽站换乘公汽 站的次数，此时zje 1,39571，z#表示从公汽站换乘地铁站的次数，z学表示从 地铁站换乘公汽次数，z器表示从地铁站换乘地铁的次数，此时7jw |3958,3996| o 那么换乘时间为：5z：+6z： + 7z/+4z洛所以总的乘车吋间为：$化;+ 1） + 5z；+6z； + 7z扌+4zj即第二个目标函 数为：min 0（v； + l）+5zf+6zf+7z+4zftarget three :乘车费用最少问题一屮乘车费用分为两个部分，在问题二屮增加了地铁费用，用爲表示从站点i到站点./的计费方式，那么爲有三种取值，即4= 2其

35、中1表示单一3票价，2表示分段计费，3表示地铁票价；可设表示站点，到站点丿经过的站 点数目，那么从站点i到站点丿的费用磅为：t7；.=2,l<s.<20=2,20<s. <40qij = 2, s- > 404 = 3（4 < v； < 2）其中表示实际换乘次数。min工咖+ 1）11233 那么行程总费用为：工打（ + 1）i、jwe从而得到第三个目标函数为： 综上我们建立的多口标整数规划口标函数为：/；（ + l） + 5z；+6z；+7z：+4zf 工耽+ 1）ijeeminminmin6. 2. 2确定约束条件k = （a,b,c,d）,当=

36、aye 1,3957时，1表示在公汽站点丿换乘公汽，0表示在公汽站点丿不换乘公汽；当/c = b,；g 1,3957时，1表示在公汽站点/换乘地铁，0表示在公汽站点j不换乘地铁；当k = cj"3958,3996时, 1表示在地铁站j换乘公汽，0表示在地铁站丿不换乘公汽；当k = d时，1表示 在地铁站丿换乘地铁，0表示在地铁站丿不换乘地铁，而地铁换乘地铁只有当两 条地铁线路经过的站点相同吋，才可以换乘，由题中给出的地铁门线换乘公汽 信息与地铁卩2线换乘公汽信息可知：地铁线门，丁2只同时经过d12和d18。此 时丿分别等于3969, 3975o讨论乘客是否换乘的约束条件，乘客在公汽站

37、吋有三种不同的选择，分别为 不换乘公汽、换乘公汽和转乘地铁，三种选择不能同时进行，那么相应的约束条 件为：aj + b. < 1 丿 “1,3957乘客在地铁站d12和d18也相应的有三种不同的选择：不换乘地铁、换乘公汽和换乘地铁，三种选择不能同时进行，所以相应的约束条件为：cj + q/517 g 3969,3975实际生活中，当离起始站点越近时，车上的乘客越少。甸的最小值越接近© 表示拥挤程度越高，©的最小值越接近0表示拥挤程度越低，贝a宀j 另外也要考虑实际乘车次数的限制，在模型中我们仅考虑两次换乘以内的情形，所以综上约束条件为:a, + b. < 1 j

38、e 1,3957c. + d < 13969,3975jj0 < min a.- < %fje 1,3957zje395& 39966. 2. 3确定模型二综上我们确定多fl标整数规划模型为：min 览min 石( + l) + 5z；+6z#+7z+4z#min工仔必+ 1)ijee舛 + bjvlj g 1,3957ci + dj < 1 j g 39693975 0 < min q < n s.t <坊5匕;52z, j g 1,39577, ye 395&39966. 3模型二的求解模型二中的算法跟模型一中的算法一样，根据局部搜

39、索算法思想，可 以运用ma1tab软件进行编程(代码详见附录四)，由于我们采用的是多目标 分层序列整数规划模型，所以根据确定的三种不同的策略，可以得到相应策略的 最佳路线，表(4)至表(6)分别给出了三种不同策略下题中要求解的六条线路的最 佳路线。表(4)：策略一中六条线路的最佳路线线路换乘次数时间花费坐车路线距离始发站s3359-s182811013l436-s1784-l21717s1557-s04812763l084-s1919-l043-s3077-l2732& 20s0971-s048511283l013-s2184-l41714s0008-s00731832l355-s22

40、63-l34511s0148-s04852733l024-s1234-l505-s516- l10416,23s0087-s36760253d27-d365（注：策略一按换乘次数、乘车时间、乘车费用的顺序进行考虑）表（5）：策略二中六条线路的最佳路线线路时间换乘次数花费坐车路线距离始发站s3359-s182810113l436-s1784-l21717s1557-s04817623l084-s1919-l043-s3077-l2732& 20s0971-s04858523l084-s1919-l259-s211-l27323, 14s0008-s00736725l150-s1426-t

41、2-s528-l103& 2s0148-s04857323l024-s1234-l505-s516- l10416, 23s0087-s36762503d27-d365（注：策略二按乘午时间、换乘次数、乘午费用的顺序进行考虑）表（6）：策略三中六条线路的最佳路线线路换车次数花费时间坐车路线距离始发站s3359-s182813101l436-s1784-l21717s1557-s04812376l084-s1919-l043-s3077-l27328, 20s0971-s048513128l013-s2184-l41714s0008-s00731283l355-s2263-l34511s

42、0148-s04852373l024-s1234-l505-s516- l10416,23s0087-s36760325d27-d365（注：策略三按换乘次数、乘车时间、乘车费用的顺序进行考虑）6. 4模型二的结果分析比较表至（6）,对三种策略下的最优路线进行分析发现，对于线路 s3359-s1828和s1557-s0481无论是乘车时间、费用还是拥挤程度都是一样 的，但是对于有些路线，在不同策略下的相关信息会有很大的区别，比如： 线路s0971-s0485,在优先考虑乘车次数的策略下，所需时间为128分钟， 但是在优先考虑时间的策略下，所需时间为85分钟，相对减少了 43分钟， 可见对于那些

43、比较重视时间的乘客来说，优先考虑时间的策略要更优，所 以我们从乘客不同需求进行考虑，给出相应的最佳出行路线是合理的。7问题三的解答问题三将步行作为一种交通方式进行考虑，建立了模型三进行求解。7.1问题三的数据处理7. 1. 1关于步行的假设设站点i到站点）的步行时间为若t ,则称站点i与站点丿互称为邻 近站点，7是邻近站点的口寸间上确界，即乘客所能忍受的最长步行吋间，可令 t = 12分钟，规定步行后换乘车次只能在邻近站点或同一站点。1）所有站点之间的步行时间固定不变，并且不受外界其他因素的干扰；2）只有公汽站点间可以步行，地铁站点间不能步行；3）任意两个邻近站点平均步行吋间是心=5分钟。7.

44、1.2步行邻边化假设站点i到站点/的平均步行时间为彳门），定义以乘客所在的起始点为圆 心，以最长步行时间t对应的距离为半径的圆形区域称为起始点$加"的邻接圆 域。由假设知，邻接圆域内任意公汽站点b都与妣切相邻接，且b与也切的邻 接耗时为tstartp,b）q将邻接圆域抽象为下图：72模型三的建立问题三在问题二的基础上增加考虑了步行对最优路线选取的影响，我们把步 行作为一种花费为0,只需计算时间的交通工具。在仅考虑公汽或考虑公汽及地 铁的时候，我们都对有不同需求的乘客推荐相应的最佳路线，即考虑了三个策略。 但对于该问，步行并没有增加出行的花费，每个站点间平均步行时间为5分钟， 就算乘公

45、汽或地铁也要分别花费3分钟或2. 5分钊所以考虑步行对出行时间和 乘车费用的影响不大，但是步行一站或两站很可能会导致换乘次数的变化和换乘 站点的变化，所以我们只考虑以换乘次数作为第k个目标函数的多目标规划， 在优先考虑换乘次数的基础上，再考虑乘车时间次数和乘车费用，即前两问中的 策略一。7. 2.1确定目标函数target one :乘换次数最少把步行作为一种交通工具考虑后，对换乘次数并没有什么影响，所以换乘次 数同问题二，该目标函数为：min坊target two：乘车时间最短问题三跟问题二中乘车时间不同的是要考虑步行的时间，即包括行驶时间、 换乘时间和邻接公汽站点间的步行时间。4是各站最快

46、直达时间，是实际转车次数，则行驶时间为：石(+1)换乘时间同问题二,为:5zf+6z+7z”4zf设/表示邻接公汽站点间的步行时间，为乘车需要乘客步行的站数可能不止 一站，也有可能不步行，可令r表示乘客步行经过的站点数，则邻接公汽站点间 的步行时间为：t = kt.所以乘车时间为r (% +1) + 5 z； + 6 zf + 7 z； + 4 zf +仏从而得到第一个目标函数为：min %(% + l) + 5z；+6z#+7z点+4z,+m° target three :乘车费用最少步行并不能增加乘车费用，所以乘车费用的目标函数也跟问题二中相同，即 min 工马 w + 1)i,

47、jwe 综上，多目标整数规划目标函数为：min坊min 0 化;+1) + 5z； + 6z 譬 +7z 爲 + 4z 洛 + kt()min工马化；+ 1)i.jwe7. 2. 2确定约束条件步行对换乘问题，包括换乘次数以及换乘方式均没有影响，所以问题二中的 约束条件均适合问题三。另外我们假设任意两个邻近站点平均步行时间是 =5 分钟，乂邻近站点的时间上确界为7 = 12,即kt.<t,得到展0,1,2。所以约 朿条件为：a. + b,. <1 jg 1,3957 cj + d. < 1 jg 3969,3975 打石皿2zjg 1,3957f,./g 1395&

48、3996 kt0<t 0,1,27. 2. 3确定模型三综上，我们确定的多目标整数规划模型为：min tf(j (+1) + 5z + 6z + 7z + 4z + ktqmin坊伽工坊必+ 1)ijee舛+ bjwlj g 1,3957c +d <1 je 3969,3975jj0 < min 珀 < %subject to << v/ < 2zje 1,39577 j “3958,3996kt<t z: e 0,1,27. 3模型三的求解模型三中以换乘次数少、乘车吋间短、费用少为考虑的先后顺序建立的多目 标整数规划模型三，增加考虑步行后，一些

49、相隔2站以内的站点可以通过步行到 达。以题中给出的六条线路中的s1557-s0481, s0148-s0485为例,起始点s1557与 s3158, s0645, s0646相隔仅一站,与s2628, s2143, s3135相隔2站可以步行,终 点 s0481 与 s0872,s2101,s3919 相隔仅 一站， 与 s0492,s0903 , s1179, s0871,s3667, s3919相隔2站也可以步行。线路s0148-s0485也可以按照同 样的方法进行分析，在此分析的基础上可以运用matlab软件编程进行求解(代码 详见附录五)，以线路s1557-s0481, s0148-s

50、0485为例，得到优先考虑乘车时间的最 佳路线如下表(7):表(7):问题三中的最佳路线线路最优路线换 乘时 间花 费s1557-s0481从s1557步行2站到s2143-l084-s1919-l043-s3077-l2731923s0148-s0485从 s0148 步行 1 站到 s3182-l308-s36-l157-s0722 再步 行一站到s0485169274模型三的结果分析基于问题三数据处理中的假设(2),只有公汽站点间可以步行，地铁站点间 不能步行；所以步行这种出行方式的增加只会对公汽之间的换乘产生影响，所以 可以将模型三中的结果与模型一策略一中的结果对比，模型一中线路 s1

51、557-s0481, s0148-s0485相应的路线、乘车吋间、换乘次数如下表(8)：表(8):模型一中相应路线的结果线路最优路线换乘次数时间花费s1557-s10481l084-s1919-l043-s3077-l2732763s0148-s0485l024-s1234-l505-s516- l1042733将表与表(8)对比可以看出对于线路s1557-s0481,当转乘次数减小时， 总的岀行吋间变长，费用不变；但是对于路线s0148-s0485,当转乘次数减少吋, 不仅出行时间减少4分钟，而且费用也减少了一元。所以出行时，适当的选择步 行是一种很好的方式。8模型的评价、改进和推广模型的评

52、价优点：1、通过实际调查，确定了乘客对乘车的不同需求，以乘车时间、换乘次数、乘 车花费为目标建立多目标优化模型，使问题更加清晰，得岀的线路更全面合 理；2、将复杂的公交网转化为图论问题，在图论基础上求解出转乘次数不超过两次 时的所有可行方案，根据乘客的不同需求，给出最佳路线方案，模型实用性 较强；3、利用matlab元胞数组存储数据信息，缩小信息存储空间，并选用适当的搜索 算法，缩短运算时间，有较强的实用性；4、模型的现实意义强，具有很好的实用性和扩展性。缺点：1、在转乘次数超过2次的情况下，运用所建立的模型求解计算过程复杂，计算量 过大；故模型存在一定的局限性。2、由于在计算过程中题目给的平

53、均行驶及转车时间是非现实的，所以使得本模 型的应用于现实时存在偏差。模型的改进由于公交网木身就是一个复杂的连通图，数据信息量大，而我们所建立的模 型只考虑了乘客对乘车吋间，转乘次数，乘车费用以及拥挤程度的需求，可以适 当的考虑其他的需求，如：乘车途中的观光路线，线路屮经过的标志性建筑等因 素。从人性化的角度考虑，述可以把车辆的负载量，舒适度考虑进去。另外，本文是一个静态的交通系统，所有的信息都己经给定。通过本题的数 学模型，只要给出起始点和目的地，我们就可以通过算法求得应该走的路线，所 花的吋间以及乘车费用。但是在现实生活中，交通系统随吋都可能在发生变化, 如：上下班时候的某些线路运力不足，由

54、于交通事故某两个站点z间的线路暂时 中断，但是这些在本题中都没有能够反应出来，这样我们的路径推荐模型就可能 将用户带到已经中断或者是非常拥挤的线路中。所以从实际出发，应该建立动态 系统，将交通系统查询计算机网络化，每一个查询终端类比为一个路由器，同时 采用类似于路由算法的实吋更新算法。这样才能够根据最新的数据信息判断出最 优方案。模型的推广木文采用多目标规划模型确定北京的公交线路，多目标规划模型不仅可以应 用于公交线路的查询还可以运用到其他方面，比如：国防部门设计某种导弹吋， 一般都要求导弹的射程要远，精度要高，重量要最轻以及消耗燃料要最省等；在 物资调运过程中，既要考虑在运输过程中少走冤枉路

55、，同时又耍考虑节约运费等。9.参考文献1湖北大学生数学竞赛专家组，数学建模（本科册），华屮科技大学出版社, 2006. 2. 王沫然matlab与科学计算（第二版）电子工业出版社2005. 12.3沈雷张鑫马福诚一种公共交通的最优路径算法海洋测绘第25卷第6期 2005. 11,41-434姜启源谢金星叶俊数学模型（第三版）m北京：高等教育出版社200310.附录附录一：directmatrix.m%生成直达数据库dmclear all;clc%生成3996*3996的空直达矩阵dm=cell(3996/3996);%数据导入file=fopen('d :我的文档桌面1.1公汽线路信息.txt'/r1);icou nt=o;while 1fprintf('己导入d 彳亍n'jcount);icou nt 二 icou nt+l;tline=fgetl(file);if s