运筹学作业-地铁网络换乘最优计算2.doc

1、运筹学作业-地铁网络换乘最优计算一、 问题背景北京做为首都，是全国的政治、经济、文化中心，更是全球最具活力及竞争力的城市之一。近些年来随着城市的快速发展，城市的规模及人口数量不断攀升，城市的地域也不断的扩张，城市面临着不断增大的人口流动及交通拥塞的严峻挑战，城市也需要增加更多的轨道交通来完成人们在城市内的迁移，这就形成了日益复杂的地铁网络，下图为北京城市最近的轨道交通网络。二、 问题提出复杂的交通网络，一方面带给人们更快捷的交通方式；一方面，交通复杂交错，换乘往往是一个很大的问题，也就是说，从任何一个地铁站上车，到目的地铁站下车，如何实现最优换乘，所经过的地铁站点顺序，及换乘方式，人们所花费的

2、时间最小？本着这个问题，本文提出了一种地铁网络换乘的最优算法，根据路径权重值计算最短路线。地铁站点间的拥挤状况、站点距短离、换乘状况等条件都会成为路线选择中的考虑条件，这些条件在本文中简单地规划为站点之间的路径权值，且选择了北京轨道交通Line1、Line2、Line5、Line10、Line13 等5条典型的线路，并通过最短算法计算地铁任意两点间的最短路径。本讨论中，假设某人从A3地铁口进,目的站点是E10，请问，最优路径是什么？最短距离是多少？三、 相关数据以下表格是每个站点相关的距离权重数据，以每个站点间的距离为权重，由于站点的数量及站间权重不一样，因此总会有一条最佳的路线。权重可以代表

3、距离，或者拥挤程度，或者其它因素，具体应用的可以根据实际应用情况选择。A线站点距离站点距离站点距离A1X110X2X35X1A38X3A96A3A46A9X44A4A56X4A117A5A64A6X25B线站点距离站点距离站点距离B1B27B7X35B13B148B2B35X3B96B14X17B3X66B9X86X1B168X6X75X8B117B16B175X7B66B11B125B17X56B6B75B12B136X5B18C线站点距离站点距离站点距离C1X1015X12C85C13C146X10C36C8C95C14X26C3C46C9X65X2X84C4C56X6C116X8C171

4、0C5C66C11C126C6X126C12C136D线站点距离站点距离站点距离D1X98D7X126D13D146X9D37X12X118D14D156D3D48X11D108D15D167D4D56D10D117D16X48D5D66D11D126D6D75D12D136E线站点距离站点距离站点距离X5E15E6E77E1X96E7E86X9E35E8X1010X11X78E3E410X10E107E4E56E10E116E5E68E11X118四、 模型建立一） 问题分析：最优换乘的目的就是基于从出发点到目的站点所经过的距离最小为原则。在本次讨论中，将最优换乘的方式分为两种：其一是源目站

5、点均是在同一地铁线上；另外一种则是源目不在一条线上，需要换乘。因此，前者就无需在本文中讨论（线内距离是固定的，无必要再优化）; 而后者，因涉及到多种路径，需要进行路径规划优选，可以将问题转化为计算源目的点的最短距离，这需要采用最短路径算法来实现。二） 路径网络图分解，由于需计算A3-E10间距离，因此，计算中需要拆解成源目的站点与相关换乘站点间距离，以及换乘站点之间的距离。如下图。三） 由于换乘次数的影响会也会影响到最优计算，且根据对图网分析可得，任意两站点间最少要通过两次换乘来实现，因此，在本文的分析中，只需考虑两换乘的情况，在所有的情况中选到择最优的一条。五、 路径计算，采用枚举法列出从A

6、3-E10的所可能经过的线路(只考虑最少次换乘的情况)，计算它们的路径权重，并从中选择路径权重最小的值。A3-X1-X5-X9-X10-E10：97A3-X1-X5-X6-X7-X11-E10：80A3-X1-X8-X3-X7-X11-E10：91A3-X2-X3-X7-X11-E10：64A3-X2-X6-X12-X10-E10：97A3-X2-X3-X4-X11-E10：104由以上的给计算结果可以看出，最优选的路径线路为：A3-X2-X3-X7-X11-E10六、 总结，本文提出了一项关于地铁网络最优换乘计算方法的问题，目的就是为了计算源目的站点间最短路径线路，包括最少换乘要求。此题虽然是一个简单的路径计算问题，但实际应用中可以包括很多应用，包括最短里程、票价、最快线路、较少拥挤线路等。为现实应用中提供了一个解决城市交通运输问题的最简单模型。