公交线路选择

1、公交线路选择摘要本文解决的是公交线路的选择问题，由于不同查询者有不同的需求，故我们提出了 换乘次数、出行时间以及乘车费用等三个指标建立模型求解，利用多目标规划中的层次 算法解决了公交换乘问题，建立换乘模型，并用题中6对起始点加以验证。首先对汽车线路中环路信息和原路返回信息进行了处理，保证各线路形式上的一 致，便于后面的计算求解。由文献【4】中调查结果可知，在一般的城市公交网络中人们坐公交出行，换乘次 数（可以忍受的换车次数）一般不会大于2次。对于问题一，只需考虑公汽线路，首先假设乘客最多换乘两次并且转乘时乘客只在 下车站点转车，在上述假设的前提下，建立了换乘次数最少、时间最短、费用最小三个 目

2、标函数，然后利用MATLAB编程进行搜索分别求得换乘次数最少，时间最短，费用 最小和综合考虑三种情况时以换乘次数最少为第一目标、以时间最少为第二目标、以费 用最少为第三目标这四种情况的最优解.。综合考虑三个目标函数：先考虑换乘次数、再考虑时间最后考虑费用求得结果如下： S3359到S1828需要换乘一次，所需要时间为101分钟，共有两条线路可以到达； S1557到S0481需要换乘两次，所需时间为135分钟，共有两条路线可以到达； S0971到S0485需要换乘一次，所需时间为129分钟，共有两条路线可以到达； S0008到S0073需要换乘一次，所需时间为84分钟，共有两条路线可以到达； S

3、0148到S0485需要换成两次，所需时间为192分钟，有一条路线可以到达； S0087到S3676需要换乘一次，所需时间为66分钟，共有一条线路可以到达；对于问题二，同时考虑公汽线路和地铁线路，也假设最多只有两次换乘情况，在此 假设下，确定了同问题一类似的目标函数，在利用MATLAB搜索求解时，先考虑一次 换乘情况，按题意此时可能存在地铁转地铁，地铁转公汽，公汽转地铁和公汽转公汽这 四种情况。但仔细考虑并结合题中条件后，我们发现在两次换乘时只可能存在公汽转乘 公汽转乘公汽、公汽转乘地铁转乘公汽等情况，利用穷举法可以求得任意两张点之间满 足不同查询者不同需求时的最佳路线。将问题一中的6组起始站

4、和终点站代入即可求出 满足不同查询者不同需求的最佳路线。（结果见正文）。对于问题三考虑到了步行时间即可能存在乘客从一个站点出发步行到临近站点去 转车的情况，在此问中引入了乘客换车步行距离的最大心里承受值w，用来表示当乘客 下车后走到其他站点去坐车时只要所走距离再其最大心里承受值范围内即可。在此前提 下，建立了与问题一类似的目标函数，并对算法进行了描述。关键词：多目标规划，搜索法，最大心里承受值，层次分析1、问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现 场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等） 出行。这些年来，城市的公交系

5、统有了很大发展，北京市的公交线路已达800条以上， 使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求， 某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考 虑，满足查询者的各种不同需求。1、1本文需要解决的问题有：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。 并根据附录数据，利用你们的模型与算法，求出以下6对起始站一终到站之间的最佳路 线（要有清晰的评价说明）。（1）、S3359-S1828（2）、S1557-S0481 （3）、S0971-S0485

6、（4）、S0008-S0073（5）、S0148-S0485 （6）、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题 的数学模型。附录：基本参数设定相邻公汽站平均行驶时间（包括停站时间）：3分钟相邻地铁站平均行驶时间（包括停站时间）：2.5分钟公汽换乘公汽平均耗时：5分钟（其中步行时间2分钟）地铁换乘地铁平均耗时：4分钟（其中步行时间2分钟）地铁换乘公汽平均耗时：7分钟（其中步行时间4分钟）公汽换乘地铁平均耗时：6分钟（其中步行时间4分钟）公汽票价：分为单一票价与分段计价两种，标记于线路后； 其中分段计价的

7、票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。2、模型的假设与符号说明2.1模型的假设假设一：换乘次数不能超过两次。假设二：忽略乘客在站台的等待时间。假设三：在单行线中，车行驶到终点时必须要下车。假设四：地铁之间的换乘不需要额外买票。假设五：模型一中假设不存在从一个公汽站下车到其附近公汽站转乘的情况。2.2符号说明i： 一次出行总的公汽乘车数；j: 一次出行总的地铁乘车数；x :表示乘第i辆公汽所需费用；D .:表示乘第j辆地铁所需的费用，且此处D . 3 .P：表示一次出行的总费用

8、；T：表示一次出行所需总时间；m :表示一次出行乘第i辆公汽车经过的站点数；n .:表示一次出行乘第j辆地铁的经过的站点数；CH :代表换乘数；K :第t次换乘站点；tstart : 所查找路线的起点；end :所查找路线的终点。3、问题分析本文研究的是公交线路选择问题，在选择公交线路时乘客通常会考虑三方面因素： 换乘次数、乘车所需时间、乘车所需费用。不同的顾客有不同的偏好，通过查阅南京 市做的一个公交乘客出行心理调查统计（结果如下图）可知41.16%的乘客在选择出行 路径时首先考虑的是换乘最少，其次考虑的是时间最短。而将时间最短作为出行时考虑 的首要条件的乘客只占18.60%。综上：我们以换

9、乘次数、乘车所需费用和乘车所需时间为评价指标建立模型选择最 佳公交线路。在求解过程中本应该为了满足不同顾客的不同需求列出换乘次数最少，换 成时间最少，所需费用最少和综合考虑这三个因素时，以换乘次数最少为第一目标、换 乘时间最少为第二目标、换乘费用最少为第三目标和以换乘次数最少为第一目标、换乘 费用最少为第二目标、换乘时间最少为第三目标等情况，但为了简化计算只考虑了前四 种情况。公交出行乘客心理调查车费最少 时间最短换车次数最少其他针对问题一：仅考虑公汽线路，要求给出任意两站点之间线路选择的数学模型。通 常总会存在某几个站点之间不能直达而乘客又需要从不能直达的某一站点到另一站点 到另一站点，这时

10、就需要考虑换乘问题，但并不是每一次换乘都是一下车就可以上车， 大多数换乘都需要等待时间，通常人们都是希望换乘次数越少越好，费用越少越好，所 用时间越短越好。故以换乘次数、乘车所需时间及乘车所需总费用为目标函数，建立了多目标规划模 型，然后利用MATLAB进行搜索分别求出换乘次数最少，时间最短，费用最少和综合 考虑三种情况时以换乘次数最少为第一目标、以时间最少为第二目标、以费用最少为第 三目标这四种情况的可行路径，并在可行路径中搜索出最优解。针对问题二：类似于问题一，在问题一的基础上引入了公汽与地铁，地铁与公汽之 间的换乘。我们在此处也只考虑小于三次换乘的情况。在地铁换乘地铁的时候，乘车线 路更

11、换，但费用不变。一次换乘情况，此时可能存在地铁转地铁，地铁转公汽，公汽转 地铁和公汽转公汽这四种情况。在两次换乘时则可能存在公汽转公汽转公汽、公汽转公 汽转地铁等情况，利用穷举法可以求得任意两张点之间满足不同查询者不同需求时的最 佳路线。在计算问题一中六组起始站到终点站之间的路线时，通过对数据的分析发现在一次 换乘时前五组起始站与终点站之间只可能出现汽车转乘汽车，而第六组则存在汽车转乘 地铁和汽车转乘汽车情况。并且在汽车转乘汽车时考虑到了同一地铁站附近多个站点的 转乘情况，即可能出现从某一地铁站附近汽车站下车后到该地铁站附近另一汽车站转乘 情况。在两次换乘时只存在汽车转乘地铁转乘公汽情况。故此

12、简化了搜索过程求得满足 不同查询者不同需求的最佳路线。针对问题三：该问在前两问的基础上引入了任意两站点之间的步行时间。引入步行 时间会对环形线路产生影响。在实际情况中，乘客为了降低行程换乘的次数和减少时间 和费用，通常会选择在下车的站点出寻找一个临近的站点去换乘。但步行时间必须在一 定范围内，如果超过一定范围，则要选择别的方法，故在此问中引入了乘客换车步行距 离的最大心里承受值，即当乘客从某一沾点出发到另一站点去乘车时，若步行距离小于 乘客换车步行距离的最大心里承受值即可接受。基于以上分析在此问中建立了同第一问 类似的多目标规划，并使用层次分析解法，分层次对寻找线路时满足换乘次数最少，时 间最

13、短，费用最低三种情况分别进行线路的搜索。得到最优的线路解。4、数据的处理4.1公汽线路信息的处理：4.1.1将公汽线路中的上下行线路换为两条通路，将原路返回的线路如：L003：S0417-S0272-S1973-S3425-S1433-S3476-S2337-S1027-S1065-S2974-S0234-S0521-S3737-S3806-S1682-S1684-S3925-S3897-S2489-S2488处理后即可得到：41727219733425143334762337102710652974234521373738061682和2488248938973925168416823806

14、373752123429741065102723373476两条线路。将环路信息转换为两条一模一样的环路：如：L017：S3748-S2160-S0732-S3078-S2808-S2816-S3028-S1123-S3029-S2764-S2543-S2742-S25 33-S1839-S2751-S2755-S2937-S1929-S1007-S0940-S1907-S2085-S0609-S0483-S0604- S2650-S3693-S1659-S2962-S0622-S0456-S0427-S0582-S0577-S1895-S3648-S0668-S30 81-S3078-S20

15、82-S0683-S2160-S3748转换为两条这样的环路即可：Loop1:S3748-S2160-S0732-S3078-S2808-S2816-S3028-S1123-S3029-S2764-S2543-S27 42-S2533-S1839-S2751-S2755-S2937-S1929-S1007-S0940-S1907-S2085-S0609-S0483- S0604-S2650-S3693-S1659-S2962-S0622-S0456-S0427-S0582-S0577-S1895-S3648-S06 68-S3081-S3078-S2082-S0683-S2160-S3748L

16、oop2:S3748-S2160-S0732-S3078-S2808-S2816-S3028-S1123-S3029-S2764-S2543-S27 42-S2533-S1839-S2751-S2755-S2937-S1929-S1007-S0940-S1907-S2085-S0609-S0483- S0604-S2650-S3693-S1659-S2962-S0622-S0456-S0427-S0582-S0577-S1895-S3648-S06 68-S3081-S3078-S2082-S0683-S2160-S37484.2地铁信息的处理地铁T1,T2中的各站点去掉其中的D和-然后导入处

17、理即可。4.3地铁与公汽换乘信息的处理以矩阵的形式导入，不存在站点的地方取0即可5、问题一的解答5.1模型一的建立由于乘客在考虑换乘次数、乘车费用和乘车时间三个因素时换乘次数占的比重较 高，一般情况下当从出发点到终点所需要换乘的次数超过2时，就要考虑另外的交通工 具。实际情况中，就算是类似上海那样城市的庞大的公交网中也很少有从起点到终点需 换乘公汽2次以上的。故我们在这只考虑换乘次数小于3次的情况。由此可知i=1,2,3, 4 （i表示一次出行总的乘车数，即i-1表示换乘次数）由于公汽票价分为单一票价与分段票价两种，由附录中的数据可知：1 单一票价10 m 20，1 221 m 40注：m表示

18、乘坐第i个公汽时所经过的汽车站点数。分以下几种情况考虑：【1】、当i=1时，乘客从出发点到目的地不需要换乘，故所需总费用P= x 1，总时间T = 3气【2】、当i = 2时，乘客从出发点到目的地需要换乘1次，此时P= X1 + X2,总时间T = 3 m + 5 + 3 m【3】、当i=3时乘客从出发点到目的地需要换乘2次，此时P = X 1 + x之+ X3,总时间T = 3 m + 5 + 3 m + 5 + 3 m【4】、当i=4时乘客从出发点到目的地需要换乘3次，此时P = x 1 + x2 + x3 + x4,总时间T = 3 m + 5 + 3 m + 5 + 3 m + 5 +

19、 3 m综上所述，得到问题一的多目标最优化模型为：最少换乘次数Min ii最少站数Min P = Z xkk = 1最少时间 Min T = 3Z m + 5(i - 1)k=15.2算法5.2.1换乘算法的情景描述：换乘一次、end表示终针对该问题我们考虑利用搜索算法寻找最有路径，在此只考虑直达、 换乘两次的情况：如下图(其中S表示第t个站点，S表示第p个站点,start表示起始站到站，乙表示第q条路线)Start(1)直达情况5.2.2换乘算法描述如下：1、输入起点站start和终点站end2、分别搜索起始站start和终点站end所在的线路L1和、，将它们分别存入数组， 然后再在这两个数

20、组中进行搜索，判断是否有相同的路线，若有则说明起始站和终点站 之间有直达路线，此时换成次数为0，然后再在所有直达路线中选出时间最少的路线即 可，若没有相同的路线则转入步骤3；3、 分别搜索l和L所经过的各站点并比较判断是否存在L经过的某站点S与L经q1q2q1tq2 过的某站点S为相同站点的情况，若存在则说明从起始站到终点站换乘一次就可以到达， 然后再将换乘一次的各个换成路线存储起来，从中选出时间最短的路线，若不存在1经 过的某站点S与L 2经过的某站点S为相同站点的情况，则转入步骤4；4、起始站所经过的各线路记为，终点站经过的各线路记为L，L经过的各站点记 q 1q 2q 1为S，L经过的各

21、站点记为S，分别搜索S和S所经过的各条路线找出相同路线则搜索 tq 2ptp出来的具有相同路线的两站点S和S即为两次换乘站点，然后在两次换乘各路线中选出耗时最少的路线。综合比较上述各种情况选出来的路线即为从起始站start出发到达终点站end。5.3问题一的求解5.3.1以考虑换成次数最少为目标函数求得结果如下：S3359到S1828需要换乘一次，所需要时间最少为为101分钟，共有两条线路可以到达； S1557到S0481需要换乘两次，所需时间最少为135分钟，共有两条路线可以到达； S0971到S0485需要换乘一次，所需时间最少为129分钟，共有两条路线可以到达； S0008到S0073需

22、要换乘一次，所需时间最少为为84分钟，共有两条路线可以到达； S0148到S0485需要换成两次，所需时间最少为192分钟，有一条路线可以到达； S0087到S3676需要换乘一次，所需时间最少为为66分钟，共有两条路线可以到达。具体结果见下表:起始站换乘线路中转站换乘线路终点站经过站点 总数时间 （min）价格（元）S3359L436S1784L217S1828341012S3359L436S1784L217S1828341012S0791L13S992L417S0485431292S0485L13S2322L417S0485441322S0008L159S2683L58S007328842

23、S0008L159S291L58S007128842S0008L159S3614L58S007128842S0008L159S491L58S007128842S0008L159S2259L58S007128842S0008L159S3315L58S007128842S0008L159S2559L463S007128842S0008L159S400L463S007128842S0008L159S2633L463S007128842S0008L159S3053L463S007128842S0008L355S2263L349S007128842S0008L355S3917L349S007128842

24、起始点起始线路中转站换乘线路中转站终点线路终点 八、经过站点数时 间价格换乘次数S1557L84S1919L402S3068L72S04814513532S1557L84S1919L403S3068L72S04814513532S0148L307S128L276S791L49S04856419232S0008L355S2303L349S007128S0008L463S2083L56S0071S0087L453S0087L453S3496L209S3676S1893L209S36762822248484667222225.3.2以时间最少为目标函数求得结果如下：S3359到S1828需要换乘两次

25、，所需时间为最少为36分钟，共有四条路线可以到达;S1557到S0481需要换乘两次，所需时间最少为135分钟，共有两条路线可以到达； S0971到S0485需要换成两次，所需时间最少为114分钟，共有两条路线可以到达； S0008到S0073需要换成两次，所需最少时间为27分钟，共有两条路线可以到达； S0148到S0485需要换成两次，所需时间最少为192分钟，有一条路线可以到达； S0087到S3676需要换乘两次，所需时间最少为54分钟，有两条路线可以到达。具体结果见下表:起始点起始线路中转站换乘线路中转站终点线路终点 八、经过站点 数时间费用S3359L14S1327L200S178

26、381S182812363S3359L14S1327L201S178381S182812363S3359L122S2247L435S1784434S182812363S3359L122S2247L436S1784434S182812363S1557L84S1919L402S3068144S0481451353S1557L84S1919L403S3068144S0481451353S0971L118S2648L301S1729208S0485381143S0971L118S2648L302S1729208S0485381143S0008L259S2743L158S3315116S00739273

27、S0008L259S2743L159S3315116S00739273S0148L307S128L276S79199S0485641923S0087L28S2361L442S1159418S367618543S0087L28S2361L443S1159418S3676185435.3.3以费用最少为目标函数求得结果与换乘次数最少一致5.3.4综合考虑三个目标函数：先考虑换乘次数、再考虑时间最后考虑费用求得结果如下：S3359到S1828需要换乘一次，所需要时间为101分钟，共有两条线路可以到达;S1557到S0481需要换乘两次，所需时间为135分钟，共有两条路线可以到达;S0971到S048

28、5需要换乘一次，所需时间为129分钟，共有两条路线可以到达;S0008到S0073需要换乘一次，所需时间为84分钟，共有两条路线可以到达；S0148到S0485需要换成两次，所需时间为192分钟，有一条路线可以到达；S0087到S3676需要换乘一次，所需时间为66分钟，共有一条线路可以到达。6、问题二的解答6.1模型的建立对于该问题，我们建立多目标规划模型，并使用分层次求解。在该问题中，需要考 虑公汽与地铁线路之间的混合路线。在这我们仍然考虑在乘客选择时从换乘次数，乘车 时间，乘车费用三个因素去分析，建立目标表达式。由于之前已经分析到，在乘客选择 线路的心理调查中换乘次数的比重占的较多，因此

29、我们把换乘次数作为首选目标。6.1.1目标一：换乘次数的考虑我们已经定义i表示乘车过程中乘坐总的乘公汽次数。j表示总的乘坐地铁的次数，根据假设有 i+ j 3，则此处换乘的次数CH= i + j - 1。则最小换乘次数为：CH = min i+j-16.1.2目标二：对乘车时间的考虑：通过分析，我们使用穷举法对不同的换乘次数的情况考虑，首先考虑直达的情况，在该情况下：总的时间为：3x m 乘坐公汽2.5 xn 乘坐地铁【1】当换乘次数CH = 1时，此时有公汽与地铁之间的换乘情况有四种:公汽换乘公汽，公汽换 乘地铁，地铁换乘地铁，地铁换乘公汽在该情况中总的行驶时间为：T = 3 x m + 3

30、 x m + 5【2】当换乘次数CH = 2时，针对公汽和地铁的同时换乘，总共有A 2 = 6，其中包括公3汽换乘地铁换乘公汽，公汽换乘地铁换乘地铁等在该换乘情况下，总的使用时间为：T = 3 x m + 6 + 2.5 x n + 7 + 3 x m综合考虑，总的时间的目标表达式为：12T = min &xm +Z 2.5 x n +Z t）其中t .为第i+j次换乘的平均耗时，且4 地铁换乘地铁；5 公汽换乘公汽； t = i +顶6 公汽换乘公汽；、7地铁换乘公汽；在该换乘情况下，必须满足i + j 3，即总的换乘次数不能超过三，如果超过则要考虑别的 交通工具。6.1.3目标三：对乘车费

31、用的考虑在针对乘车费用而考虑线路的选择时，前提条件也是总的换乘次数不能超过三次，我们 同样适用穷举法，最后得到总的费用为：P = min Z m +Z D 同样，i + j 3。综上所述：我们的到多目标规划的目标函数为：min CH ;m i 1T;min P ;其中i + j 3。6.2换乘算法的描述：此问中我们也假设最多出现最多出现两次换成情况，经分析发现起始6组起始站点都 不在在地铁站附近，故不可能出现从地铁站出发的情况，同理对终点站进行分析发现只 有最后一组即S3676在D36地铁站附近，故只有最后一组可能出现通过乘坐地铁到达目 的地的情况。根据以上分析采取如下算法：1、先考虑一次换乘

32、情况，对于前面五组起始站到终点站只存在公车转公车的情况，但 对于最后一组则存在公车转汽车和公车转地铁两种情况。先考虑公车转公车情况，利用搜索法先搜索出含有起始站的各路线乙,然后再搜索乙路线上在地铁站 d I附近的站点 s ，则乘客可以在此站点下车，接着再搜索出含终点站的各路线 . I，再搜索在.路线上且在地铁站 D I （注：从终点站出发搜索的地铁 站与从起始点出发搜索的地铁站相同）附近的站点，则乘客可以从此站点上车，由 此可以搜索出汽车换乘汽车的路线，然后再在搜索出的路线中进行筛选。2、对于最后一组的汽车换乘地铁情况，首先同上述1步中一样先搜索出含有起始站的各路线 L ，然后再搜索 L 路线

33、上在地铁站q 附近的站点 s , iiii并且要求地铁站q在T2路线上并且在D36之前，由此即可以搜索出S0087到S3676汽车转乘地铁的路线然后再利用时间和费用进行筛选即可得到最优路线。3、考虑到二次换乘情况只有可能是汽车换乘地铁再换乘汽车这种情况，同一次转乘中 汽车转乘汽车类似，不同的是从终点站出发搜索的地铁站与从起始站出发搜索的地 铁站不需要相同。同样也是从终点站和起始站两方向同时考虑：利用搜索法先搜索 出含有起始站的各路线乙,然后再搜索乙路线上在地铁站 q 附近的站点s ,则乘客可以在此站点下车，接着再搜索出含终点站的各路线 . ，再搜索在l 路线上且在地铁站q （注q与q在同一地铁

34、线路t上）附近的站点s， jji jkj则乘客可以在q上地铁q下地铁，然后再在公汽站S上车即可到达目的地，由此可以 搜索出汽车换乘地铁换乘汽车的路线，然后再在搜索出的路线中进行筛选。6.3问题二的求解6.3.1以换乘次数最少为目标函数求得结果如下：S3359到S1828需要转乘两次，时间最短为64分钟，最短时间下的路径有一条；S1557到S0481需要转乘两次，时间最短为112分钟，最短时间下的路径只有一条；S0971到S0485需要转乘两次，时间最短为89分钟，最短时间下的路径有十条；S0008到S0073需要转乘一次，时间最短为81分钟，最短时间下的路径有一条；S0148到S0483需要转

35、成两次，时间最短为83分钟，最短时间下的路径有五条；S0087到S3676需要转成一次，时间最短为23.5分钟，最短时间下的路径有一条。具体结果如下表：公汽换地铁换公汽起点起始路线第一次下 车站点第二次上车站点八、转乘线路第二次下车站 点八、第三次上工汽 点八、终止线路终点 ”、八、时 间S3359L473S856D28T2D34S578L167S182864S1557L84S978D32T2D24S537L5S0481112S0971L93S567D1T1D21S466L50S048589S0971L93S567D1T1D21S464L103S048589S0971L93S567D1T1D2

36、1S464L395S048589S0971L93S567D1T1D21S466L450S048589公汽换公汽:起点起始路 线第一次下车站 点八、第二次上车 站点终止路线终点 八、站点数时 间S0008L159S4002633947S00732781公汽换地铁：起始第一次下车转乘地铁换乘线起点路线站点站点路终点”、八、时间S0087L20S630D29T2S367623.5S0971 L93S567 D1 T1 D21S464L469 S0485 89S0971 L119S567 D1 T1 D21S466L50 S0485 89S0971 L119S567 D1 T1 D21S464L103

37、 S0485 89S0971 L119S567 D1 T1D21S464L395 S0485 89S0971 L119S567D1 T1D21S466L450 S0485 89S0971 L119S567D1 T1D21S464L469 S0485 896.3.2以时间最少为目标函数求得结果如下：S3359 到 S1828,S1557 到 S0481, S0971 到 S0485, S0148 到 S0483 与 S0087 到 S3676 与以换乘次数为目标结果相同。S0008到S0073需换乘两次，时间最短为76分钟，最短时间下的路径有两条。6.3.3以费用最少为目标函数求得结果与以换乘次

38、数为目标结果相同。6.3.4综合考虑以上三个目标函数，先考虑换乘次数在考虑时间最后考虑费用求得结果 与以换乘次数为目标求得结果相同。7、问题三的求解7.1模型的建立在该问中，假设已经知道任意两站点之间的步行时间。在实际情况中，当某个乘客 从某个站点出发时，并不是就是在下车的那个站点换车而是先步行一段路程后，在下车 站点的临近站点去换车。这样就增加了乘客选择路线的方案。而且会减少换乘的次数， 当然步行到附近的站点要看紧临站点的分布情况。同时我们考虑到乘客在换乘时的步行 距离不可能走很远，在此处我们定义巧为乘客换车步行距离的最大心里承受值。同上述问题，我们同样对该问题建立多目标分层求解的问题规划：

39、假设任意两站点之间s，s的步行行走时间为T，整个过程公汽经过的总的站点ij数为m，地铁经过的总的站点数为n。其中m为第i次公汽换乘经过的站点数，n为第i次换乘地铁的站点数。DG为地铁换乘公汽的次数，GD为公汽换乘地铁的次数， GG为公汽换乘公汽的次数，DD为地铁换乘地铁的次数。考虑到在整个路线选择过程 中，换乘次数的影响占的比重较大，所以对换乘次数的考虑应放在第一位.目标一：对换乘次数的考虑：总的换乘次数为：min CH = GD + DG + GG + DD且必须满足：GD + DG + GG + DD 3。目标二：对乘车时间的考虑：总的乘车时间为：min T = (2 3 x m + 2

40、2.5 x n + 5 x GG + 4 x DD + 7 x DG + 6 x GD + E T 由于考虑到乘客步行时间要满足要满足换乘步行距离的最大心理承受度，假设d(s ,s )表示任意两个站点之间的步行距离，即此处必须要满足d (s , s ) “。我们以 i ji jT .表示任意两站点的步行时间，为了和实际情况相符合，我们定义T e0,10 。即步 行时间在10分钟之内。在对时间的考虑的同时，也需要满足对换乘次数的考虑，即也 必须满足GD + DG + GG + DD 1；20D =3,考虑到地铁费用时，有一种情况就是当地铁换乘地铁时，不需要额外买票。 i总的乘车费用为：min P

41、= 2 X +2 D 综上所述，总的目标为:min CH;min T;min P;7.2模型的求解在基于上述关于换乘次数，时间，费用的基础上我们得到路线的选择方案为：输入起始点start和终点end;(直达的情况)判断起点和终点是否在同一条线路上，如果在则说明线路寻找 成功。如果没有，则转入下一步；(换乘一次的情况)寻找包含起始站点的线路集e(/)和包含终止站点的线路集 上的相同站点，如果有，则寻找成功，如果没有，则转入下一步；假设寻找得到包含起点start的线路集合e(I)和包含终止站点的线路集合s(J)， 在所有线路上的某一个站点E (I, U )处附近找一紧临的点V，并且满足d (U ,

42、 V) w， 如果V e s (J)，则寻找成功，如果不满足，转入下一步；寻找满足d (U , V ) w的点V的所有线路集R (K)，在R (K)上找一点K，如果满 足K e S (J)，则K就是第二次换乘点。如果不满足，则转入下一步；在K点附近找一紧临的站点L，并且满足d(K, L) W，并找出站点L上所有的 线路集合L(r)，在L(r)上寻找一点Q，如果Q e S (J)，则寻找成功，如果没有，则 跳出，查找失败。8、模型的优缺点8.1模型的优点：1、在问题求解过程中综合考虑了不同顾客的不同需求2、在问题二求解过程中计算汽车转乘汽车时，考虑了地铁站附近多个汽车站点的转 乘情况3、求解结果

43、比较准确8.2模型的缺点：1、问题一算法时间复杂度较高，在数据很多的情况下不利于计算2、在问题一和问题二中都只考虑了两次换乘情况3、在模型建立时，没有综合考虑对不同查询者的三种情况所占比重要求不同情况下 的线路查询。比如，某些个别查询者可能要求以费用最小为最重要目标，但同时也 要竟可能满足换乘次数最少和费用最低的情况。9、模型的改进1、在求解过程中用该将满足不同查询者不同需求的各种情况都列举出来并进行求解便 于乘客进行查询。2、还可以根据通过调查判断哪些站点离比较受顾客欢迎的地方较近可以考虑在这些站 点顾客比较愿意在这些站点下车并且此时顾客换乘的最大心里承受值是比较大的也 即顾客在这些站点下车

44、愿意走较长的路径到换乘站点。10、参考文献【1】薛定宇、陈阳泉等著，高等应用数学问题的MATLAB求解，清华大学出版社【2】彭祖赠等主编，数学模型与建模算法，大连海事大学出版社【3】王莉、李文权，公共交通系统最佳路径算法，东南大学学报，第34卷，第3期， 2004年3月【4】王健林，基于换乘次数最小的城市公交网络最优化算法，经济地理，第25卷第5 期，2005年9月11、附录附录一：数据处理源代码：clear;clc;fid=fopen(a.txt,rt);b=fscanf(fid,%s);n=size(b,2);i=1;l=0;while(i=n)if (b(i)= L)l=l+1;i=i+

45、4;if (b(i)= ,O)c(l)=0;i=i+5;elseif (b(i)=p)c(l)=1;i=i+7;endw=1;n1(1,l)=1;if (b(i)= El)i=i+3;elseif (b(i)=)i=i+3;h(l)=l;y(l)=0;elsey(l)=l;h(l)=0;endwhile(b(i)=L)for j=1:4;a(j)=eval(b(i + 1);i=i+1;ends(w,n1(w,l),l)=a(1)*1000+a(2)*100+a(3)*10+a(4);i=i+1;if(b(i)= -)n1(w,l)=n1(w,l)+1;i=i+1;elseif (b(i)=I

46、A)w=2;i=i+3;n1(w,l)=1;elseif (b(i)=E)break;elseif(w=1)if(h(l)=0)for k=1:n1(w,l)s(2,k,l)=s(1,k,l);endelsefor k=1:n1(w,l)n1(2,l)=n1(1,l);s(2,k,l)=s(1,n1(w,l)-k+1,l);endendendendelsei=i+1;end end y(l)=0;h(l)=0;t=1;m=1;for i=1:lfor j=1:2if(j=1)x(t,1)=i;if (c(i)=0)c1(t)=2;elsec1(t)=1;endif (y(i)=0)l1(t)=

47、3;elseif (h(i)=0)l1(t)=2;elsel1(t)=1;endelsec1(t)=0;l1(t)=0;endx(t,2:87)=s(j,1:86,i);n2(t)=n1(j,i);t=t+1;endendfor i=1:2*lfor j=1:87if(x(i,j)=0)x(i,j)=inf;endendendc1=c1;l1=l1;n2=n2;附录二：问题一源代码：判断是否存在地铁线为起始路线或地铁线为终止路线的情况:Function K(start1,end1)a=data(1:1040,:);k=1;t=1;for i=1:1040for j=1:86if a(i,j)=

48、start1b1(k)=i;b2(k)=j;k=k+1;else if a(i,j)=end1c1(t)=i;c2(t)=j;t=t+1;endendendendq=1;for i=1:k-1for j=1:t-1n1=b1(i);n2=c1(j);n3=b2(i);n4=c2(j);for r=1:86for p=1:86if a(n1,r)=0&a(n2,p)=0if a(n1,r)=a(n2,p)&n3p d1(q)=a(n1,r);d2(q)=n1;d3(q)=n2;d4(q)=r-n3+1+n4-p+1;q=q+1;endendendendendendfunction A(start

49、1,end1)a=data(1:1040,:);k=1;t=1;for i=1:1040for j=1:86if a(i,j)=start1b1(k)=i;b2(k)=j;k=k+1;else if a(i,j)=end1c1(t)=i;c2(t)=j;t=t+1;endendendendm=1;for i=1:k-1for j=1:t-1if b1(i)=c1(j)c3(m)=b1(i);m=m+1;endendendq=1;for i=1:k-1for j=1:t-1n1=b1(i);n2=c1(j);n3=b2(i);n4=c2(j);for r=1:86for p=1:86if a(n

50、1,r)=0&a(n2,p)=0if a(n1,r)=a(n2,p)&n3p d1(q)=a(n1,r);d2(q)=n1;d3(q)=n2;d4(q)=r-n3+1+n4-p+1;q=q+1;endendendendendq1 = 1;for i=1:k-1n3=b1(i);n5=b2(i);for j=1:86for p1=1:1040for p2=1:86if p1=iif a(n3,j)=0&a(p1,p2)=0if a(n3,j)=a(p1,p2)&jn5 e1(q1)=a(p1,p2); e2(q1)=p1; e3(q1)=n3; e7(q1)=j-n5+1; q1=q1+1;endendendendendendendq2 = 1;for i1=1:t-1n4=c1(i1);n6=c2(i1);for j1=1:86for p3=1:1040for p4=1:86if p3=i1if a(n4,j1)=0&a(p3,p4)=0&j1i2f1(q3)=e2(i2);f2(q3)=e1(i2);f