公交线路转乘选择的优化模型摘要本文以奥运会的公交线路换乘为大背景，建立了在公汽线路、地铁以及步行三种方式中综合进行路线转乘的模型。此问题可以归结为两个站点之间的最短路问题，由于直接以站点构建最短路问题计算量较大，本文在处理三个问题时分别提出了相应的模型与求解算法，以乘坐时间最短为标准回答了问题一与问题二，对问题三提出了最短路模型。在问题一建模过程中，我们以任意两条线路是否可以直接换乘为突破口，建立了以每条线路为顶点，两条线路之间的换乘信息为弧的图，将问题一归结为弧长可变的最短路问题，提出了结合动态规划方法与分枝定界思想的算法。首先将题目所给出的路线与站点信息翻译为两条线路是否可以直接相交以及在何处相交的信息矩阵；其次以换乘时间最短或者费用最小为决策函数，建立动态规划问题；再次设计相应的算法进行求解。通过求解，以最短时间为目标，问题一的结果如下所示（以(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元。在问题三建模过程中，由于增加了步行的信息，问题一、二的方法无法直接使用，文章建立了一个新的最短路问题。以每个站点为顶点，以两个顶点之间的最短路径（最短达到时间或者最小到达费用）为弧构造有向图，其中最短达到时间由问题二得到的两个站点之间使用公交网络的换乘时间与步行时间的最小值决定。从而将问题三归结为一个有向图的最短路模型，文章对此模型给出了算法建议。最后文章对所提出的模型进行了优缺点分析与推广评价。关键词：城市公交线路、图与网络、最短路模型、动态规划问题重述：近些年来，城市公共交通系统有了很大发展，使得公众的出行更加通畅、便利。绝大多数市民出行时首先会考虑选择公交设施，同时也面临如何在众多条线路中如何选择合适线路的问题。针对市场需求，要求开发一个解决公交线路选择问题的自主查询计算机系统，可以满足查询者的各种不同需求，对不同的起点和终点给出最佳的公交转乘路线。竞赛要求设计线路选择的模型与算法，解决以下三个问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。问题分析：从影响出行选择的因素看，每个人主要会从两个标准对线路进行选择与优劣衡量：从起点到终点所需要的总时间最短；从起点到终点需要花费的费用。从本质上讲，选择线路的问题可以归结为最短路问题，但是考虑到转乘线路需要时间，并且一条公交线路不能按照站点进行拆分，因此以每个站点构造路线图不利于解决问题。注意到从起点站到目标站关键是选择乘坐哪些公交线路，需要在公交线路中如何选择转乘线路，因此可以以公交线路为顶点，以两个站点之间是否可以转乘为弧构造图，而点到点之间最佳路线的选择可以转化为经过分别两个端点的公交线路集合之间的最短路问题。同时我们需要任意两个线路之间是否可以转乘的信息。在给出的线路信息中，我们发现主要有三类线路：下行线路与上行线路不同，下行线路是上行线路的原路返回，环形线路。为了区分同一条线路不同的运行方向，我们人为地将每一条线路变为两条线路，这样做既可以分清楚所换乘的是那条线路的哪个方向，同时也可以将两条线路换乘点的信息与每个站点在本条线路上的位置相联系，这样可以用来判断乘坐某条线路公交车从某个站点出发时，可以换乘哪些公交线路（换乘站点必须在乘车点沿着公交车运行方向的后方）。在公交线路信息中，与决策目标有关的元素还有每条线路的计费方式及每条线路乘坐时花费的时间。对于计费方式，我们按照单一票价与分段计价进行识别，分段计价与乘坐的站点数有关，这也是我们需要每个站点在每条线路上具体位置的原因；同样运行时间也与站点的具体