数学建模论文公交线路优化选择模型及算法

1、公交线路优化选择模型及算法摘要本文主要是针对两公汽站点之间的最佳公交路线选择问题而建立模型，对于给定的三种不同的具体情况，我们建立了以总换乘次数最少，乘车所消耗总时间最短以及乘车费用最少的多目标规划模型。为建模方便，我们首先设定由起始站到终到站所经过的站点序列，并构建了各个站点换乘情况的0-1决策变量，将所有站点的换乘情况进行叠加得到总换乘次数。乘车所消耗的总时间和总乘车费用，在不同情况下计算方式不同。问题一只考虑公汽。由从起点到终点经过的站点数目和换乘次数可得到总消耗时间，同时引入计价因子表示公汽计价方式计算乘车费用。我们在5.1.5中设计了适当的算法并用visual c+编程计算，得到各个

2、目标值如下：按照起始站终到站, 换乘次数, 总时间, 总票价的顺序为s3359s1828, 1, 101, 3；s1557s0481, 2, 106, 3；s0971s0485, 1, 128, 3；s0008s0073, 1, 83, 2；s0148s0485, 2, 106, 3；s0087s3676, 1, 65, 2；详细结果及分析见5.1.6和附录1；同时我们还在5.1.7和5.1.8中讨论了适当增加换乘次数对乘车时间和费用的影响。问题二同时考虑加入地铁的情况。我们假定只有公汽换乘地铁和地铁换乘公汽两种情况。乘地铁消耗的时间类似乘公汽消耗时间可计算得出；因换乘消耗的时间与初始的交通方

3、式相关，我们引入了起点乘车方式因子。总乘车费用类似问题一的情况可得。利用visual c+编程计算，我们得到此时各目标值如下：起始站终到站, 换乘次数, 总时间, 总票价, s3359s1828, 2, 101, 5；s1557s0481, 2, 117, 5；s0971s0485, 2, 96, 5, 13, 20；s0008s0073, 2, 65.5, 5；s0148s0485, 2, 87.5, 5；s0087s3676, 0, 33, 3；详细结果及分析见5.2.6。问题三中我们基于问题二中所建立的模型，引入了步行因子，其在乘车所消耗总时间最短以及乘车费用最少两个目标中都得到了体现，

4、得到了任意两站之间选择路线的模型，见5.3.5中式（35），（36）。此外，我们还对模型进行了评价和推广。关键字：多目标规划模型，换乘点，计价因子，起点乘车方式因子，步行因子1 问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与

5、算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、s3359s1828 (2)、s1557s0481 (3)、s0971s0485(4)、s0008s0073 (5)、s0148s0485 (6)、s0087s36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2 问题分析随着2008年北京奥运会的来临，

6、北京的公共交通系统有了飞速的发展。目前北京有公交线路800条以上。这使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。题目中给出了6对起始站与终点站，要求我们求出由这些起始站到终点站的最佳路线。如何理解“最佳路线”体现乘车者不同的出发点，也是我们解决问题的前提。现有对于选择出行最佳路径的模型多为基于“出行距离最短”或“出行时耗最少”的最短路模型。而对于公交乘客而言，更多的乘客以“换乘次数最少”为首要着眼点，“出行距离最短”为第二目标2。因此，现在的问题是如何在现有的公交网络上寻找一条换乘次数最少、距离最短的线路。目前采用的常用方法是将公交路径的最短路径理解成广义费用的最小来考虑。在

7、这里，我们认为应该考虑换乘次数尽量少，乘车时间尽量少和车费最少这三个目标。具体讨论如下：汽车换乘会给乘客带来极大的不便：一方面，北京市的车流辆非常大，在高峰期很容易出现堵车的情况，所以乘客等车的时间可能远大于平均等候时间5分钟；另一方面，还可能出现公交车装载过于饱和的状况，这时乘客只能选择等候下一辆，这也有可能造成等候时间过长。因此，我们把换乘次数作为第一目标。人们在出行的时候，不会希望自己的大部分时间耽误在公交车上。因此，乘车过程消耗的时间也是重要的目标。对于不同的方案，这个时间的构成不尽相同，具体如下：当只考虑公共汽车线路的时候，即在乘客进行换乘的时候直接在前一辆车的下车站换乘车辆，这时乘

8、客在由起始站到终点站的过程中花去的总时间由公汽的行进时间和换乘所花去的时间两部分组成。公汽的行进时间由从起点站到终点站所停的站点数量立即可得，乘客在换乘中花去的时间可根据假设由换乘次数易得。这样我们就可以得到公汽换乘公汽时乘客从起始站到终点站所需要花去的时间。当同时考虑公汽与地铁线路，这里乘客在由起始站到终点站所花去的总时间就要看成由两大部分组成，即乘车的时间和换乘的时间。乘车的时间由公汽的行进总时间和地铁的行进总时间两部分组成，前面已经讨论过公汽的总行进时间，这里地铁的总行进时间可以类似得到。而换乘的时间较为复杂，包括了公汽换乘公汽，地铁换乘地铁，公汽换乘地铁以及地铁换乘地铁四个部分，各个部

9、分可以很类似得到，和前面讨论的公汽换乘公汽的计算方法类似。由上我们可分别得到在只考虑公汽和同时考虑公汽和地铁时乘客由起始站到终点站所消耗的总时间，这是第二个目标。另外，整个行程所需票价支出也会被某些乘客列入考虑范围。只考虑公汽与同时考虑公汽和地铁，票价的计算方法有所不同，作讨论如下：对于只考虑乘公汽到达的情况，北京市采用的是分段收费。我们可以从0开始编号，在不同范围内的站点数，收费情况不尽相同。首先，我们把收费情况考虑为一个分段函数。对于特定的起始站终到站的线路选择，我们只需要将乘客换乘公汽的站点与所到站点序列进行划段，这里也将起始站和终到站认作换乘点。进行划段以后，可以得到相邻两换乘站点之间

10、的站点数，计算各段的票价，再将各段票价叠加后可得整个乘车过程所需总票价。当同时考虑地铁和公汽时，我们也需要根据换乘点将起始站终到站的站点序列进行划分。所不同的是，若乘坐地铁，乘客只需要买一张票就可以了，换乘不收费，因此，如果在起始站终到站的站点序列中有地铁，对于地铁换地铁，我们则需要在前面计算的总票价上加上地铁票价3元即可得到起始站终到站的总票价。因此，我们得到了只考虑公汽和同时考虑地铁时乘客所要花费的总票价的表示方法，作为我们的第三个目标。综上，我们首先得到解决该问题的一个三目标规划模型。第三问要我们在假设又知道所有站点之间的步行时间的情况下，给出任意两站点之间线路选择问题的数学模型。该问是

11、建立在前两个问题的基础上的。对于发生的情况有很多种，如在将要到的站时发生堵车步行以节约时间，在下车站点需要走一到两站路才能到达目的地或者是换乘下一趟车的站点，在采用分段计价方式的情况下，多出一到两个站点是为了节省选择提前下车等多种情况。这里，根据1中的基本假设，我们只考虑，在采用分段计价方式的情况下，多出一到两个站点时为了节约选择提前下车的情况。3 基本假设(1) 附录中给出的数据真实可信，直到2008年8月不进行调整。(2) 附录中给出的各项假设真实可信。(3) 环线车和地铁t2均为单环。(4) 北京市公交路线畅通，不会出现长时间的堵车。(5) 将要到达站点只有1至2站时出现步行的情况。(6

12、) 在地铁站之间不出现步行的情况，单一票价制度的公汽不考虑步行的情况。4 符号说明符号意义站点序号换乘公汽的站点所对应的公汽站点序号换乘地铁的站点所对应公汽站点序号在行程过程当中所经过的站点编号序列换乘站点的站点编号起始站乘车方式因子步行因子经过站的公汽线路编号经过换乘点站的公汽线路编号经过站的公汽线路编号的集合经过换乘点站的公汽线路编号的集合换乘点采用第种换乘方式的集合在第站是否发生了第种换乘方式0-1决策变量由起始站到终点站经过的站点总数公汽分段计价函数5 模型建立和求解根据前面对于该问题的分析，该问题前两个问题主要是要我们对给定的6对起始站终到站在只考虑公汽和同时考虑公汽和地铁两种不同的

13、情况下，建立模型并进行求解给出各个线路的最佳选择，第三问要求我们在假设知道所有站点之间的步行时间的情况下，给出任意两站点之间线路选择问题的数学模型，各个问题分别具体讨论如下：5.1 只考虑公汽线路的模型以及求解根据4中的分析，我们需要首先建立一个以换乘次数最少，整个过程当中需要花费的总时间最少以及总票价最少三者作为目标的三目标规划模型。由于各条线路的讨论情况相同，首先我们需要假设出由起始站到终点站乘客经过的乘车线路序列，这里我们不妨设由起始站到终点站乘客所经过的站点序列为。其中分别为起始站编号、终到站编号、起始站到终到站经过的站点总数，为乘客经过的第站的编号。下面对各个目标进行分别讨论。5.1

14、.1 换乘次数为了计算换乘次数，我们首先设为经过站的公汽编号，其集合记为，表示如下 (1)设为公汽线路经过的站点编号集合。根据前面设定的乘客由起始站到终到站，我们可以通过比较相邻站点的公汽编号，来判断是否进行了公汽换乘，设为是否在第站发生了换乘，为0-1变量，由于起始站和终到站是我们假定的换乘点，取值为0，因此这里只需要考虑中间站的换乘情况，表示如下 (2)另设为换乘站点编号的集合，由于并不是所有的站点都是要进行换乘的，因此换乘点的站点编号集合应为行程中通过的所有站点的集合的子集，即相当于原来有一个序列为，其下标为连续的，我们从其中抽取出一个子列，记为。运用于该具体问题当中，换乘点的序列是由起

15、始站到终到站以及之间所有站点序列的子序列，可表示为 (3)为了后面方便处理，我们把该集合直接记为 (4)其基数为。因此我们可以得到换乘次数的目标函数，为 (5)5.1.2 行程总时间根据4的分析，在我们只考虑公汽的情况下，乘客由起始站终到站所花费的总时间由经过站点数量和换乘次数两部分决定。前面已经假定乘客经过的站点序列，根据题目中的假设，相邻公汽站平均行驶时间(包括停站时间)为3分钟，可以直接得到公汽的总时间为。对于公汽换乘公汽的换乘过程所花的时间，题目中已经给出公汽换乘公汽平均耗时为5分钟(其中步行时间2分钟)，而前面5.1.1中我们已经给出了换乘次数的表达式，因此可以得到换乘过程中所消耗的

16、时间为。综上，可以得到行程总时间最少作为该问的第二个目标，如下 (6)其中为经过总站点数量，为在第站是否发生公汽换乘公汽的情况。5.1.3 总票价根据前面4的分析，在只考虑公汽时，票价是以相邻两换乘点之间站点数量来决定的。设为换乘点在由起始站到达终点站站点序列的编号，为的整数，但不一定连续，其对应换乘点的站点编号为，易得相邻两换乘点之间的站点数为由于北京的公汽收费方式分为单一票制和分段计价两种方式，因此我们首先需要判断乘坐的公汽的收费方式，这由公汽线路本身决定。引入0-1计价方式因子来表示采用的收费方式，则 (7)若收费方式为分段计价，由题目所给资料得到020站：1元；2140站：2元；40站

17、以上：3元，设定票价收费分段函数 (8)因此我们可以得到总票价最少的目标，为 (9)其中为换乘总次数。这样我们就对各个约束条件进行了讨论，接下来对约束条件进行讨论。5.1.4 约束条件该问题中主要有三个约束，都针对换乘站点，即换乘之前乘坐的公汽要到达该站以，经过该站公汽数量要大于1以及将要换乘的公汽可以到达序列中的另外一点，分别讨论如下首先在换乘站点 之前所乘坐的公汽编号，其应属于所有经过站的公汽编号的集合，换乘站点公汽数量大于1，设为经过换乘点站的公汽编号的集合，其基数可表示为，因此得到换乘站点经过公汽辆数大于1的约束为 (10)设下一个换乘点序号为，对应站点编号为，可以得到换乘点的另一个约

18、束条件，为 (11) 5.1.5 多目标模型的建立综合5.1.15.1.4的分析，我们可以得到如下三目标规划模型目标函数 (12)约束条件 (13)5.1.6 模型求解算法描述与求解 算法描述根据5.1.5的模型，我们首先设计算法如下：1. 输入待查询站点的和。2. 从站点可直达的站点集合，可直达的站点集合，若 , 用表示从的直达线路，。为可行解集合。如以换乘次数为目标，转7.3. 若，则为一个可行解。如以换乘次数为目标，转7.4. ，所有可直达的站点集合为，若，则5. ，所有可直达的站点集合为，若，则6. 若，两次换乘不能得到可行解，需近一步搜索，结束。7. 若考虑以时间最短为目标得从可行解

19、集合中得到全局最优解，结束。 求解结果根据以上算法，我们采用visual c+进行编程求解，在编程过程中将换乘次数作为第一目标进行计算。由于对于特定的换乘次数目标值，计算得到的由各对起始站终到站的乘车方案很多，所以需要根据第二目标来找到里面满足总时间最短进行筛选，若总时间相同，只能根据第三目标总票价来确定出最佳路线。因此，我们采用图1流程筛选出最佳路线。换乘次数最少路线集合总时间最短路线集合票价最少路线集合最佳路线集合图1最佳路线筛选方案根据图1，可以得到题目中给出的各起始站终到站之间的以及目标值以及最佳乘车路线如下。表1只考虑公汽时的各个目标值起始站终到站换乘次数总时间总票价经过站点数s33

20、591557s04812106332s0971s04851128341s0008s0073183226s0148s04852106332s0087s3676165220同时可以得到各个起始站终到站乘坐公汽的部分最佳路线如下（其余见附录1）s3359s1828的最佳路线为：乘l436路下行：s3359-s2026-s1132-s2266-s2263-s3917-s2303-s2301-s3233 -s618-s616-s2112-s2110-s2153-s2814-s2813-s3501-s3515-s3500-s756-s492-s903-s1768-s955-s48

21、0-s2703-s2800-s2192-s2191-s1829-s3649-s1784-乘l167路下行：s1784-s1828s1557s0481的最佳路线为：乘l84路下行：s1557-s3158-s2628-s3408-s2044-s1985-s2563-s2682-s28- s29-s55-s51-s1919-乘l189路下行：s1919-s2840-s1402-s3186-乘l460路下行：s3186-s3544-s2116-s2119-s1788-s1789-s1770-s2322-s992-s2184-s2954-s3117-s2424-s1174-s902-s903-s2101

22、-s481s0971s0485的最佳路线为：乘l13路下行：s971-s3832-s3341-s2237-s3565-s3333-s1180-s3494-s1523- s1520-s1988-s1743-s1742-s1181-s1879-s3405-s2517-s3117-s2954-s531-s2184-换乘l417路下行：s2184-s992-s2322-s1770-s1789-s2119-s2116-s3544-s3186- s3409-s2717-s1402-s2840-s643-s2079-s1920-s2480-s2482-s2210-s3332-s3351-s485s0008s

23、0073的最佳路线为：乘l159路下行：s8-s3412-s2743-s3586-s2544-s913-s2953-s3874-s630 -s854-s400-s2633-s3053-s408-s145-s3138-s2684-s2683-s291-换乘l58路下行：s291-s3614-s491-s2559-s990-s3315-s3898-s1855-s0073s0148s0485的最佳路线为：乘l308路上行：s148-s462-s361-s1797-s2221-s302-s2222-s2737-s1716 -s128-s2268-s1308-s1391-s2272-s36-换乘l156

24、路上行：s36-s3233-s618-s617 -s721-s2057-s2361-s608-s399-s2535-s2534-s239-s497-s2090-s2082-s2210-s3332-换乘下行l417-s3332-s3351-s0485s0087s3676的最佳路线为：乘l454路上行：s87-s857-s630-s1427-s1426-s541-s978-s3389-s1919- s641-s2840-s3496-乘l209路下行：s3496-s1883-s1159-s2699-s2922-s3010-s583-s1987-s82-s36765.1.7 增加换乘次数对时间的影响结

25、果为了讨论换乘次数对于换乘时间的影响，我们将s3359s1828,s0971s0485, s0008s0073 ,s0087s3676增加一次换乘得到相应结果如下表2调整换乘次数后的各个目标值起始站终到站总时间总票价经过站点数s3359s182873321s0971s0485106332s0008s007367319s0087s367646312同时，我们可以给出题目中列出的6对起始站终到站路线时间最短的最佳路线如下：s3359s1828的时间最短的最佳路线为：乘坐l324上行：s3359-s2023-s2027-s1746 换乘l027环线:s1746-s3697-s3727-s0393-s

26、0391-s3177-s0004-s1967-s3674-s1522-s1520-s2992-s0903-s1768-s0955-s0480-s2704-s1784 换乘l167下行：s1784-s1828s0971s0485的时间最短的最佳路线为：乘坐l013上行: s0971-s3571-s1609换乘l140下行,s1609-s3242-s1481-s3426-s2553-s3903-s1553-s3531-s1967-s0012-s2636-s2113-s2112-s2833-s0618-s1327-s2303-s2263-s3037-s2654- 换乘l469上行s2654-s172

27、9-s3766-s1691-s1383-s1381-s1321-s2019-s2017-s2159-s0772-s0485s0008s0073的时间最短的最佳路线：乘坐l198上行: s0008-s1383-s1691-s3766换乘l296环线s3766-s1729-s2654-s3231-s3917-s2303-s1327-s0618-s3100-s2151-s3746-s3501-s2517-s2184换乘l345上行s2184-s3162-s2181-s0073s0087s3676的时间最短的最佳路线：乘坐l021下行s0087-s0088换乘l231环线s0088-s0609-s04

28、83-s0604-s2650-s3693-s1659-s2962-s0622-s0456-s0427换乘l097上行，s0427-s3676。5.1.8 结果分析根据5.1.6和5.1.7中的结果对比，我们可以将换乘次数增加1的4对起始站终到站的个目标值的变化，由于增加换乘自然会影响到总花费，但是考虑到公交花费占有的比重相对来说很小。因此只考虑乘车站点以及节约时间在调整换乘次数之间的对比情况，结合表1和表2的计算结果，我们不难得到下表3表3 调整换乘次数前后时间和站点数量对比量起始站终到站节约时间站点数量减少量s3359s18282811s0971s0485229s0008s0073167s0

29、087s3676198从表3可以看出，将换乘次数增加1，会使乘车所经过的站点数量大大减小，整个行程中所花费的总时间虽然是由在公汽上消耗的时间和换乘所消耗的时间两部分构成。但由于换乘次数为02，相差范围很小。因此行程中所消耗的总时间将直接由所经过站点数决定。这样站点数量的减少就会直接导致行程的所花去的时间大大减小。根据此分析结果，我们可以向时间观念比较强的乘客提出建议，在考虑乘车过程当中适当增加换乘次数，这样会大大节约时间。对题目中所给出的6条起始站终到站我们的乘车建议见5.1.7，5.1.8以及附录1。5.2 同时考虑公汽与地铁线路该问题与5.1类似，只是在考虑公汽的同时加入了地铁的因素在里面

30、，根据我们对题目附录2.1和2.2地分析不难发现，问题一当中给出的6对起始站终到站的站点中（除题中给出的第6对线路外），没有地铁换乘公汽的站点，因此我们可以肯定的是除题中给出的第6对线路外，乘客的起始站和终到站都是公汽站点。对于对应各个目标以及约束条件，我们在5.1的基础上进行讨论分析如下。5.2.1 换乘次数在5.1.1中，只需要对公汽换乘公汽进行讨论，但在这里面需要讨论四种换乘情况，为了方便下面的计算和模型建立，我们为四种方式进行了编号入下表表4各种方式编号情况表编号换乘情况第站点换乘方式为公汽换乘公汽第站点换乘方式为地铁换乘地铁第站点换乘方式为地铁换乘公汽第站点换乘方式为公汽换乘地铁对于

31、行程序列中的一个站点来说只会出现发生和不发生两种情况。因此我们首先定义各个方式的0-1变量如下 (14)另设采用第种方式进行换乘的换乘站点编号的集合，可表示为 (15)其基数为。因此，我们可以得到换乘次数最少的目标，为 (16)5.2.2 行程消耗总时间在5.1.2中，我们只考虑公汽的情况。而在此问中，除了要考虑公汽的情况以外还要考虑地铁与地铁之间、地铁换乘公汽、公汽换乘地铁三种情况。同样地，在该问题当中，行程消耗的总时间包含两部分，即在车上的时间和换乘所花的时间。首先刻画在车上花去的时间，其包含在公汽和地铁上两部分的时间，由于地铁换乘公汽和公汽换乘地铁是成对出现的，先后顺序不同，具体讨论如下

32、设分别为地铁换乘公汽和公汽换乘地铁的站点集合中的站点编号元素，设起始点编号为0。若起始乘坐的是地铁，那么首先出现的二者换乘方式必然为地铁换公汽，可以得到二者交叉换乘序列示意图如下图2起始点乘地铁示意图此时在公汽上消耗的时间可表示为若起始乘坐的是公汽，那么首先出现的二者换乘方式必然为公汽换地铁，可以得到二者交叉换乘序列示意图为图3起始点乘公汽示意图此时在公汽上消耗的时间可表示为 (17)为了将两种不同情况进行融合，我们引入起始因子来刻画起始站乘坐车辆的情况 (18)因此可以在公汽上花去的时间，设为，为 (19)类似地，可以得到在地铁上花费的总时间，设为，为 (20)再讨论在换乘过程中所消耗的时间

33、，在一个站点，若换乘，则只可能出现换乘一次另一个交通工具的情况。设换乘矩阵为，对应换乘矩阵中各分量表示的换乘方式平均耗时矩阵为，其中至多一个等于1，因此对于第站换乘所花的时间为。所有站点换乘所花的总时间，设为，为 (21)综上可以得到行程消耗的总时间最少的目标为 (22)5.2.3 行程花费的总费用由于加入换乘地铁主要是为了防止出现多次公汽换公汽的情况，因此我们不妨认为不出现公汽换乘公汽的情况，只需要计算乘坐各段公汽需要支付的票价和乘坐地铁所要花费的票价，下面一一进行讨论。根据5.1.3，直接得到各段公汽需要支付的总票价为 (23)其中为地铁换乘公汽的总次数。对于乘坐地铁所要花费的票价，题目中

34、告诉我们地铁与地铁之间换乘是不收费的，只有在地铁换乘公交的时候会收取3元的费用，因此可以得到乘坐地铁需要花费的费用为。综上可以得到行程花费最小的目标函数为(23)5.2.4 约束条件在一个特定的站点，若换乘，则只可能出现换乘一次另一个交通工具的情况，为 (24)从另一方面来说，在地铁换乘公汽和公汽换乘地铁的时候，对应的换乘点应该有相应的公汽和地铁站。为了表示这一约束，我们设地铁站所达到的公交站点的集合，这可以由题目所给附录2.1和2.2中得到。因此我们只需要约束地铁换乘公汽的集合中的元素在换乘站有公汽站与该地铁站对应。设为一包含站点公汽站点的集合，这些元素为同一地铁站可换乘的公汽站点。由此得到

35、地铁换乘公汽的条件为 (25)对于公汽换乘地铁的情况，前面已经设定该种换乘方式对应的换乘点集合为，二者能够换乘的条件为集合中的元素属于所有地铁站点公汽站点的集合即可，为 (26)5.2.5 同时考虑公汽和地铁的多目标模型建立根据5.2.15.2.4的分析，我们可以得到同时考虑公汽和地铁的三目标规划数学模型，如下目标函数 (27)约束条件 (28)5.2.6 模型求解算法及结果 算法描述1. 输入待查询站点的和。2. 可从地铁换乘的公交站点集合，若，则最优方案 , 表乘地铁从的最优线路，为可行解集合。转5.3. ，若，则，则4. 则可行解的集合就可以表示为： ，其中表示从站点到的直达线路，表示从

36、站点到的直达线路。5. 考虑以时间最短为目标得从可行解集合中得到全局最优解。 求解结果根据算法，我们采用visual c+进行编程计算可得到如下结果表5同时考虑公汽和地铁时的各个目标值起始站终到站换乘次数总时间总票价公汽站点数地铁站点数s3359s1828210152012s1557s0481211752710s0971s048529651320s0008s0073265.55173s0148s0485287.551119s0087s36760333010 同时可以得到各个起始站终到站的最佳路径分别如下s3359s1828的最佳路线为：乘l015上行-s3359-s2266-s3917-s23

37、03-s1327-s3068(d08)-换乘地铁t1-d08- d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-换乘地铁t2-d33-d34(s0578)-换乘l167下行s0578-s3095-s0096-s0095-s1193-s0105-s1194-s1189-s2801 -s0590 -s1240 -s1241-s1784-s1828s1557s0481的最佳路线为：乘l084下行s1557-s3158-s2628-s3408-s2044-s1985-s2563-s2682-s28-s29 -s0055-s0051-s1919(d20)-换乘地铁t2-d

38、20-d19-d18-换乘t2-d18-d33 -d34-d35-d36-d37-d38-d39-d24(s0537)-换乘l516上行-s0537-s2651-s3013 -s1808-s1173-s0910-s3517-s0453-s2424-s1174-s0902- s0903-s2101-s0481 乘l363下行s1557-s3158-s2628-s3408-s2044-s1985-s2563-s2682-s2735-s29 -s0055-s0051-s1919-换乘地铁t2-d20-d19-d18-换乘t2-d18-d33-d34 -d35 -d36-d37-d38-d39-d24

39、(s0537)-换乘l516上行-s0537-s2651-s3013-s1808 -s1173-s0910-s3517-s0453-s2424-s1174-s0902-s0903 -s2101-s0481 s0971s0485的最佳路线：乘l094上行（或l119下行）s971-s3571-s1609-s0345-s1419-s2389-s0567(d01)-换乘地铁t1-d01-d02-d03-d04-d05-d06-d07-d08-d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19-d20-d21(s0466)换乘l051上行（或l450下行）-s046

40、6-s3189-s2810-s2385-s0071-s0485 乘l094上行（或l119下行）s971-s3571-s1609-s0345-s1419-s2389-s0567(d01)-换乘地铁t1-d01-d02-d03-d04-d05-d06-d07-d08-d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19-d20-d21(s0464)换乘l104上行（或l395下行）-s0464-s964-s3189-s2810-s2385-s0485s0008s0073的最佳路线：s0008-s3412-s2743-s2544-s2953-s0778-s2534

41、(d15)换乘t1-d15-d14-d13 -d12(s0609)-换乘l057上行-s0609-s0483-s0604-s2650-s3470-s2619-s2340 -s3162-s2181-s0073 s0148s0485的最佳路线：乘l024下行：s0148-s0927-s2830-s2070-s1487(d2)换乘t1-d2-d3-d4-d5 -d6-d7-d8-d9-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19-d20-d21(s466)换乘l051上行(或l450下行)s466-s3189-s2810-s2385-s0071-s0485 s008

42、7s3676的最佳路线：乘地铁t2-d27-d28-d29-d30-d31-d32-d18-d33-d34-d35-d365.2.7 结果分析这里进行分析比较的时候，由于乘坐公交消费在乘客考虑选择线路时所占有的比重很小，因此这里只对换乘次数和行程总时间进行比较分析，并根据分析结果给出我们的建议。根据5.1.6，5.1.7，5.2.6的求解结果，我们在下表6中做出如下比较表6同时考虑公汽和地铁与只考虑公汽各目标值对比情况表起始站终到站只考虑公汽换乘1次的情况只考虑公汽换乘2次的情况同时考虑公汽和地铁换乘的情况站点数总时间站点数总时间站点数总时间s3359s182832101217320+1210

43、1s155710117s0971s0485281283210613+2096s0008s00732683196717+365.5s01481987.5s0087s3676206512460+1033注：同时考虑公汽和地铁换乘的情况中站点数一栏表示的“公汽总站点数+地铁站点数”，如“20+12”即为整个行程过程中所经过的公汽站总数为20，地铁站的总数为12.从表6我们可以看出：1） 六条线路中s0971s0485，s0008s0073，s0148s0485，s0087s3676四条线路在同时考虑公汽和地铁换乘的情况下，经过的站点数量和总时间

44、都得到了大大的减少。2） 同时考虑公汽和地铁换乘的情况下，s0087s3676线路可以直接通过地铁到达目的地。同时整个行程消耗的总时间比起只考虑公汽换乘1次和2次分别减少了32分钟，13分钟。因此，对于这样的线路来说，选用地铁作为交通工具是最为省时，省力的途径。3） 另外，我们不难看出在同时考虑公汽和地铁换乘的情况下，线路s3359s1828，s1557s0481的总时间和总站点数比起只考虑公汽时反而有所增加。所以，对于有些线路来说，采用地铁并不一定是最省时间的交通方式。我们建议，乘客尽量考虑自己的线路情况来选择公交工具。5.3 任意两站点之间线路选择问题的数学模型本问要求我们在前两问的基础上

45、，加入步行的情况在内，给出任意两个站点的路径选择问题。这里就要考虑三种交通方式，即公汽，地铁以及步行，还有其间的换乘转化关系。对于公汽和地铁及二者之间的换乘的情况，我们在5.1和5.2当中已经进行了详细的讨论，下面主要对步行进行讨论。发生步行的情况，主要考虑到在发生在换乘点前后，若换乘前乘坐的是分段计的公汽，为了节约起见，乘客就要根据自己所要经过的站点数进行考虑。从前面我们知道北京分段计价的公汽的计价规则为：020站：1元；2140站：2元；40站以上：3元。因此当乘客乘坐经过的站点数量为21，22，41，42的时候，乘客就会考虑只乘坐20，40个站以降低票价。乘客选择步行的概率与20和40个

46、站点有密切关系，我们不妨认为，当乘客所乘坐的站点数为21，22，41，42时，乘客会选择在第20站和40站下车进行步行12个站点来到达目的地，发生点在换乘点之前。首先引入步行因子来描述换乘点前一段公汽所经过的站点数目 (29)5.3.1 换乘次数和5.2.1一样，我们只考虑了地铁换乘公交与公交换乘地铁两种换乘情况，因此加入步行的因素在里面，换乘总次数不会受到影响。刻画换乘次数最少的目标也和5.2.1一样。5.3.2 行程消耗总时间加入步行的成分在里面，必将影响这个行程的总时间。这时整个行程所消耗的时间由三部分组成：公交车上消耗的时间，换乘消耗的时间以及步行所消耗的时间。根据我们的讨论分析发现，

47、步行时间仅发生在公汽换乘地铁之前，由所乘公汽所经过的站点数量或。对于站点数量不满足21，22，41，42的部分，可以直接采用5.2.2中的方法进行计算，为 (30)但是很显然，上式包含了站点数量满足21，22，41，42的情况，需要借助步行因子来除去这些情况所消耗的时间，只需要乘以即可，其只有在步行因子，即不发生步行的情况下为1，因此得到在公汽换乘地铁时不发生步行的情况所消耗的时间为 (31)接下来需要单独计算在换乘点之前发生步行时，换乘之前所消耗的时间，这个事件有两部分构成，一部分是在公汽上的时间，另一部分是步行的时间。在公汽上消耗的时间相当于是经过20和40个站所消耗的时间，结合步行因子，

48、可以很容易得到在公汽上消耗的时间，为。对于步行时间，由于题目中没有具体给出北京市的公交站分布情况图，但可以知道两个相邻站点之间的距离是一定的，因此这里我们不妨假设平均两相邻站点之间的步行时间为，另外我们可以直接由公汽换乘地铁的换乘点与前以换乘点之间所经过的站点数量得到需要步行的站点数量。结合步行因子，我们可以将步行时间表示为 (32)另外，由于加入步行的成分，对于换乘点的数量没有影响，换乘时间的计算与5.2.2种计算方法相同，为。由于地铁是统一计费3元，所以没有必要考虑地铁站之间的步行，计算时间的方法与5.2.2相同。综上，我们可得到加入步行情况时，使整个路程所花的总时间最少的目标为 (33)

49、5.3.3 行程中的乘车费用这里需要综合5.2.3和5.3.2的思想，分析如下。首先考虑在换乘点之前不进行步行部分的花费费用，为 (33)其中，为起点因子，为票价因子。换乘点之前进行步行的情况所花费的费用只需要按照经过站点20站或者40站的票价进行支付即可，即要支付的票价与步行因子相同，由于乘坐地铁部分是按照统一计价3元，所以这里没有必要在地铁站点之间考虑换乘的情况，因此乘坐地铁所花费的费用和5.2.3一样，为。综上，我们得到了考虑步行情况的任意两个站点之间所花费的总费用目标函数为 (34)5.3.4 关于约束条件这里约束条件和前面5.2.4一样，并未发生改变。5.3.5 任意两站点之间的路线

50、选择模型综合5.3.15.3.4种的分析，我们可以得到任意两站点之间的路线选择模型，具体如下 (35)约束条件 (36)6 模型评价和推广6.1 模型优缺点评价6.1.1 优点 本题中的模型建立完全是基于组内成员讨论，结合问题进行分析建立的，体现了一定的新颖性和原创性。 根据有关资料中提供的信息，分析出该问题中需要考虑的几个问题的几个主要目标，并确定将各个目标的重要程度，为模型求解带来了极大的方便。 巧妙地根据模型的特点设计出简单易行的算法。 算法优点：1. 基于生成树思想的截尾深度优先搜索，算法简单易行，所有结果均可在数秒内得出。2. 针对换乘次数和耗费时间分别为目标的检索，得到的为全局最优

51、解，结果的可靠性强。6.1.2 缺点由于比赛的时间有限，我们对该问题进行了一些简化，应该需要更加深入地思考这个问题，做出更为符合实际情况的结果以及模型。6.2 模型推广该问题中的模型可以运用于多路径的选择问题和指派问题。7 参考文献1张永梅，韩焱，陈立潮，城市公交查询系统的研究与设计，计算机应用，第25卷第2期，2005年 2月。2向万里，刘洪升，城市公交网络出行路径选择的计算机算法研究，兰州交通大学学报(自然科学版)，第25卷第1期，2006年 2月。3胡霍真，戴光明，李颖，公交车网络的最短路径算法及实现，微机发展，第l5卷第9期，2005年9月。4姜启源，数学模型（第三版），北京，高等教育

52、出版社，2003年8月。5谭浩强，c语言程序设计(第二版)，北京，清华大学出版社，2002年12月附录附录以换乘次数作为第一目标，只考虑乘坐公汽时，各起始站终到站的最佳路线s3359s1828的最佳路线为：乘l436路下行：s3359-s2026-s1132-s2266-s2263-s3917-s2303-s2301-s3233 -s618-s616-s2112-s2110-s2153-s2814-s2813-s3501-s3515-s3500-s756-s492-s903-s1768-s955-s480-s2703-s2800-s2192-s2191-s1829-s3649-s1784-乘l

53、167路下行：s1784-s1828s1557s0481的最佳路线为：乘l84路下行：s1557-s3158-s2628-s3408-s2044-s1985-s2563-s2682-s28- s29-s55-s51-s1919-乘l189路下行：s1919-s2840-s1402-s3186-乘l460路下行：s3186-s3544-s2116-s2119-s1788-s1789-s1770-s2322-s992-s2184-s2954-s3117-s2424-s1174-s902-s903-s2101-s481乘l363路下行：s1557-s3158-s2628-s3408-s2044-s1985-s2563-s2682-s2735- s29-s55-s51-s1919-乘l189路下行s1919-s2840-s1402-s3186-乘l460路下行：s3186-s3544-s2116-s2119-s1788-s1789-s1770-s2322-s992-s2184-s2954-s3117-s2424-s1174-s902-s903-s2101-s481s0971s0485的最佳路线为：乘l13路下行：s971-s3832-s3341-s2237-s3565-s3333-s1180-s3494-s1523- s1520-s19