公交线路转乘选择的优化模型摘要：本文以奥运会的公交线路换乘为大背景，建立了在公汽线路、地铁以及步行三种方式中综合进行路线转乘的模型。此问题可以归结为两个站点之间的最短路问题，由于直接以站点构建最短路问题计算量较大，本文在处理三个问题时分别提出了相应的模型与求解算法，以乘坐时间最短为标准回答了问题一与问题二，对问题三提出了最短路模型。在问题一建模过程中，我们以任意两条线路是否可以直接换乘为突破口，建立了以每条线路为顶点，两条线路之间的换乘信息为弧的图，将问题一归结为弧长可变的最短路问题，提出了结合动态规划方法与分枝定界思想的算法。首先将题目所给出的路线与站点信息翻译为两条线路是否可以直接相交以及在何处相交的信息矩阵；其次以换乘时间最短或者费用最小为决策函数，建立动态规划问题；再次设计相应的算法进行求解。通过求解，以最短时间为目标，问题一的结果如下所示（以(1),(2)组为例，其它见正文表1）：组（1）：S3359→S1828，，最短时间73分钟，费用3元；组（2）：S1557→S0481，，最短时间106分钟，费用3元。同时文章对运算结果进行了相关分析。在问题二建模过程中，沿用问题一的求解思想，将新增加的地铁视为新的线路，将所有线路信息转化为新的转乘矩阵，同时根据新的背景得到新的乘车时间与费用计算方法，同样以最短时间为目标，相同的算法可以得到问题二的结果（以(5),(6)组为例，具体见正文表2）：组（5）：S0148→S0485，最短时间 87.5 分钟，费用 5 元；组（6）：S0087→S3676，，最短时间28分钟（已经加上地铁站到地面站点的步行时间，其中地铁运行时间20分钟），费用3元。在问题三建模过程中，由于增加了步行的信息，问题一、二的方法无法直接使用，文章建立了一个新的最短路问题。以每个站点为顶点，以两个顶点之间的最短路径（最短达到时间或者最小到达费用）为弧构造有向图，其中最短达到时间由问题二得到的两个站点之间使用公交网络的换乘时间与步行时间的最小值决定。从而将问题三归结为一个有向图的最短路模型，文章对此模型给出了算法建议。最后文章对所提出的模型进行了优缺点分析与推广评价。关键词：城市公交线路、图与网络、最短路模型、动态规划一、问题重述：近些年来，城市公共交通系统有了很大进展，使得公众的出行更加通畅、便利。绝大多数市民出行时首先会考虑选择公交设施，同时也面临如何在众多条线路中如何选择合适线路的问题。针对市场需求，要求开发一个解...
