《公交线路选择模型(B陈晖 王新 郜燕)》由会员分享，可在线阅读，更多相关《公交线路选择模型(B陈晖 王新 郜燕)（22页珍藏版）》请在金锄头文库上搜索。
1、2007高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B 我们的参赛报名号为（如果赛区设置报
2、名号的话）： 所属学校（请填写完整的全名）： 信息工程大学信息工程学院 参赛队员 (打印并签名) ：1. 陈晖 2. 王新 3. 郜燕 指导教师或指导教师组负责人 (打印并签名)： 日期： 2007 年 9 月24 日赛区评阅编号（由赛区组委会评阅前进行编号）：2007高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公交线路选择模型摘 要本文首先根据不同需求分别以路径最短、换车次数最少和费用最小为优化目标。然后建立
3、多目标规划模型，求出多目标规划的非劣解，根据不同的需求，在非劣解中筛选出符合要求的多条线路，以供查询者选择。对问题一，针对路径最短，由于算法的局限性，本文采用遗传算法求出任意两点间的最短路径。针对换乘次数最少，费用最小，采用基于数据处理的广度优先搜索算法，得到换乘次数最少的线路（结果见正文），费用最小的线路（结果见正文）。然后本文对模型进行拓展，建立多目标规划模型，我们建立以路径最短、换车次数最少和费用最小的三个目标规划，再由以约束换乘次数的约束求非劣解方法，求解多目标规划模型，得到多条非劣解，对每个非劣解的适用范围做了评价。对问题二，将增加的铁路数据进行处理转化采用问题一的多目标规划模型。单
4、独考虑必须使用地铁的路径非劣解，得到换乘次数最少的线路（结果见正文） 路径最短的线路以及费用最低的线路（结果见正文）。再将此种情况得到的最佳路径与问题一得到的最优路径进行比较，得出最优解。对问题三，首先得到出任意两点之间只用步行和公交车的路径算法，以此之后得到对任意的经过任一条铁路，起点和终点的路径算法，得到所有的非劣解。之后利用问题一和二的结果综合考虑起点和终点之间的路径选择问题，转化为和问题二类似的多目标规划模型，求出步行时间最短、路径最短、换车次数最少和费用最小的四目标规划问题。关键词：多目标规划 最小换乘 最优路径 公交网络 广度优先搜索1 问题的重述我国人民翘首企盼的第届奥运会明年月
5、将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题： 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下对起始站终到站之间的最佳路线（要有清
6、晰的评价说明）。 同时考虑公汽与地铁线路，解决以上问题。 假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2 问题的分析问题一的分析由于不同的人需求不同，因此对于不同的查询者最优的公汽乘车线路不尽相同，有的人要求乘车路线路径最短，有的人要求换乘次数最少，有的人要求乘车所花的费用最低。因此这是一个多目标规划问题，共有三个目标，目标一为换乘次数最少，目标二为路径最短，目标三为费用最低。多目标规划问题通常有两种解决方法：加权法和约束法求非劣解。加权法是对各目标进行加权，以此将多目标规划转化为单目标规划求解。但对于查询者来说，各目标的权值难以确定，不便于乘客查询。而约束
7、法求非劣解，则可根据查询者的不同需求，在非劣解中挑选出相应的解。公汽的路线有三类：环线，上行线和下行线站点完全相同，上行线和下行线部分相同部分不同。在对公汽路线抽象时，将上行线和下行线作为两条线路，于是可将其全部路线抽象为单向路线。在此基础上采用广度优先的搜索算法求出非劣解。由于大多数人为省去换乘车的麻烦，都希望换乘次数尽量小，因此可以将换乘次数作为约束来求非劣解。换乘次数的上限由最短路时换乘次数决定，因为当换乘次数比最短路的换乘次数大时，不能得到非劣解。对于求解最短路的算法传统上多采用算法，但由于有个公交，站点太多，如果采用算法时间复杂度太高，算法的效率太低，而启发式算法的效率相对较高。满足
8、某一目标要求的非劣解可能会有多个，例如非劣解中有几条路线都满足费用最小，此时可在这些线路中进行二次筛选找出路径最短的线路。问题二的分析问题二是在问题一的基础上增加了两条地铁线路的多目标的规划问题，同样有三个目标：目标一为换乘次数最少，目标二为路径最短，目标三为费用最低。问题二中增加的地铁线路具有其独特性。首先，无论地铁线路间是否换乘票价均为3元，即在两条地铁线路之间换乘时无须另外付费。其次，同一地铁站对应的公汽站可通过地铁相互转乘而无需付费，这样使得本来相距很远的两个公汽能很快换乘。该城市的地铁由一条环形线和一条直线组成，并且两条线相互交叉，形成一个网络，其中有两个站点重合，因此任意两点铁路站
9、之间有且有一条时间和路径以及铁路之间换成次数均最佳的路线。将地铁线转化为普通的公交线路，这样只是在问题二的基础上增加了数据量，可同样采用问题一的方法，建立与问题一相似的模型。问题三的分析问题三是在问题二的基础上，增加了步行换乘时间这一目标的多目标规划问题。步行换乘时间是指从一个站步行到另一个站的时间。因此该问题变为四个目标：目标一为换乘次数最少，目标二为路径最短，目标三为费用最低，目标四为步行换乘时间最短。问题一和问题二种的换乘只限于同一站点之间的换乘，而问题三的换乘可以在不同站点之间，这在某些情况下可以减少乘车路线的路径。但另一方面，乘客却不想步行时间增加。问题三的数据量在问题二的基础上增加
10、了步行时间，可以把步行转化为新的路线加入原来的网络中，建立四目标规划模型，采用类似问题二的算法求解。3 模型的假设31 假设公民出行不借助其他交通工具，只考虑公交、地铁和步行；32 假设公交线网较为完善，任意两个交通区之间的公交出行无需借助其它交通工具即可完成。4 符号说明表示公交站点；表示地铁站点；表示相邻公汽站平均行驶时间；表示相邻地铁站平均行驶时间；表示公汽换乘公汽平均耗时；表示地铁换乘地铁平均耗时；表示地铁换乘公汽平均耗时；表示公汽换乘地铁平均耗时；表示地铁票价。5 模型的建立与求解5.1问题（一）模型的建立与求解通过问题一的分析，我们建立多目标规划模型。在该问题中建立三个目标函数：最
11、短路径、换乘次数最少和费用最低，然后分别求解。在此不考虑步行，即若乘客需要换乘，则就在下车的站转坐另一辆公交。公交网络的描述将公交网络抽象为图，并采用四元组1来表示。其中:表示节点集合，节点代表公交站点，个站点具有相应的编号表示公交线路集合，各线路具有相应的编号表示线路站点关系集合，是从线路的角度描述线路站点的关系。由于线路分为三种情况：环线，上行线是下行线站点相同，上行线下行线站点不完全相同。对于后两种情况，本文将其视为两条独立的线路，因此所有线路都可分解为是单向的线路。例如第条线路可表示为,其中和是该线路的始发站和终点站。为站点线路关系集合，是从站点的角度描述站点线路的关系。例如表示所有经
12、过站点的所有线路的集合。公共交通网可以抽象为连通网络图，中的每个顶点为不同的公交站点，对于中任意点，若有公交直达到点，则这两点之间就有边相连，记作，相应的有一个数称为该边的权。因此公交网络图为一赋权图。5.1.1目标函数的确定设起点为，迄点为，可行的公交路径集合为其中表示在起点选择线路到达，换乘到达，最终到达。设该路径换乘次数为，途径总站数为，并设在每条线路上的费用为。最短路径由于任意两个相连的公交站点之间的距离大约相等，因此它对最短路径的选择几乎没有影响。不妨设相邻两站点之间的距离均为。因此若要求最短距离，可以转化为求该路径途径的总站数。则线路的距离为。于是该问题的目标函数为换乘次数最少公交
13、网络的连通性不同于图论中的连通性。若求乘客从到的最短路径，需考虑乘客在每一点都换车，才能够直接采用算法，其计算结果可能让乘客换乘十几次才能到达目的地。而对于部分乘客来说，方便性是考虑的首要因素，不希望换乘次数太多。因此需建立基于换乘次数最小的最优路径模型。于是该问题的目标函数为费用最小另外，对于部分乘客来说，距离和换乘次数都是次要的，他们考虑乘坐的路线是费用最小的。于是该问题的目标函数为至此建立多目标规划模型； 5.1.2 模型的求解根据该多目标规划模型的特点，不需要给出一个普遍意义下的解，只需要给出一些针对不同乘客需求的解即可。为此，本文首先针对各个目标求解最优解。（一）针对要求最短路径的乘客建立模型由于任意两个相连的点之间的距离大约相等，因此它对最短路径的选择没有影响。不妨均设为，因此若要求最短距离，可以转化为求该路径途径的总站数。则线路的距离为，因此要求。利用遗传算法，并通过编程2可得任意两点间的最短路径。因此、 和的最短路径。表1 6对起始站终到站之间的最短路线首次登车线路中转站二次登车线路总站数总费用L436S1784L167343L084S1919L189323L13S2184L417434L159S0291L058262L308S00
