2008.8.14动态规划变分法B200404033宋玉晶张兆丰王飞

《2008.8.14动态规划变分法B200404033宋玉晶张兆丰王飞》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最佳公交线路乘车方案摘要对问题1：建立了以换乘次数最少、总行程时间最短以及费用最少的多目标模型，并设计了相应的求解算法:首先只考虑换乘次数最少的单目标，引入直达矩阵(T矩阵)和最小换乘矩阵(Q矩阵)，得到求解最少换乘次数。然后依次考虑总时间与总费用最少，即在公汽网络中利用改进的算法，以Q矩阵限制T标号产生的冗余信息，得到一条综合考虑换乘次数、耗时、费用相结合的公汽路径寻优新算法，用该算法求出问题1的6对起始站→终到站之间的最佳路线：如（1）中最佳线路为（最少费用：3元；最少耗时：101分钟），其他详见表（一）。对于问题2，注意到地铁站的加

2、入使得该地铁站附近的公交站变连通，将地铁线路变成广义的公汽线路，类似与问题一的处理思想建立了以换乘次数为第一目标，耗时为第二目标、费用为第三目标的数学模型二，利用改进的算法求出问题1的6对起始站→终到站之间的最佳路线如（最少费用：3元，最少耗时：101分钟），其他详见表（三）。由于在路径选择时,公交出行者总希望选择最快捷的线路(即综合考虑时间、费用的交通阻抗值最小的线路)出行,公交线路交通阻抗值是指乘客在公交线路上出行的出行时间、费用、方便性(如换乘)等综合费用指标，由此改进得到模型四。改进的思路是将乘公汽和乘地铁的费用分别折算成价值时间

3、，并对这两种价值时间进行加权处理，将模型二中的三个目标转换为单目标。即以阻抗值为最小求最优路径。同样依据改进的算法求出问题1的6对起始站→终到站之间的最佳路线：如（最少费用：3元，最少耗时：73分钟），其他的详见表（四）～表（七）。对于问题3，我们将步行路线也转换成广义的公汽路线，这样广义的公汽路线上的费用为0，通过引入0-1变量，在模型二的基础上建立模型三。关键词：换乘交通阻抗算法多目标1、问题的简述与分析1.1问题重述：我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通

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

5、说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。1.2问题分析：公交换乘问题的实质就是给出起始点、目标点后，给用户提供乘车方案。若视地铁线为公交线路（地铁站的加入有使得该地铁站附近的公交站变连通等特性），这样一来，问题一和问题二的研究并没有什么本质不同。所谓乘车方案是一个站点、

6、线路的交替序列，该序列说明从起点出发乘坐何线路，途中如何换乘，直至到达终点。公交换乘问题的实质就是给出起始点、目标点后，给用户提供乘车方案。通过对公交乘客的出行心理进行调查研究，其结果表明，“换乘次数”是大部分公交乘客在选择出行路线时首先考虑的因素，其次是出行耗时和距离长短。而出行耗时与换乘的次数、等车的时间、公交车沿途停靠站点耗时以及距离的长短密切相关。因此，对于出行耗时和距离长短，可转化为换乘次数最少的基础上公交车沿途行驶距离长短和停靠站点多寡的问题。讨论的公交换乘算法就是以“换乘次数最少”为首要目标，“出行耗时和距离最短”为次要目标

7、，乘车费用最小为第三目标，来寻求公交出行的最佳路径。公交乘客出行和汽车司机运货所考虑的因素是不同的，汽车司机运货关心的是如何选择最近距离，最大程度的省时省油；而公交乘客出行更多考虑的是出门的方便性和舒适性，所以道路网络中的最短路径和公交线路的最短路径的意义是不同的。道路网络中的最短路径只要找出两点之间路径距离为最短即可。但是在公交网络中，乘客不会为了寻找距离最短路径而随意换车。因为从一条线路换乘到另一条线路是费时又费力的，在很多情况下，换乘另一趟车需要步行到另一个站台，这就有一段的步行距离的代价，而且在站台等车也是要消费时间的。所以对于公

8、交乘客来说，最短路径的意义并不在于路程是否最短，而在于换乘的次数要最少。于是就有了一种基于换乘次数为最小，在公交网络中最短路径算法的思路。算法的思想描述如下：根据人们的出行习惯，在选择从S站到