公交线路优化

2010高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：河南科技大学参赛队员(打印并签名)：1.许光辉2.李贵涛3.蔡亚娟指导教师或指导教师组负责人(打印并签名)：日期：2010年8月18日赛区评阅编号（由赛区组委会评阅前进行编号）：2010河南科技大学数学建模选拔赛A题公交车线路优化设计摘要本文旨在研究公交线路优化设计问题，寻找出一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案。首先，我们依据“公交乘客心理调查结果”，明确影响乘客选择车次、路线的主要因素有三个：换乘次数、乘车时间和出行费用，确定各自所占的权重。之后登陆“洛阳公交网”全面收集和整理这三个影响因素的具体数据。对于问题一，已经给出确定的乘车路线，直接找出两目的地的车次依次乘车。结果见论文第4页图1。对于问题二，我们先用“控制变量法”初次筛选出任意两个目的地之间的最优车次，然后运用排列组合的方法确定遍历四个目的地再回到出发点的可行方案共有A424种。结果见论文第6页表格4。 4对于问题三，我们先利用“控制变量法”对任意两个目的地间的车次情况进行优化，筛选出任意两个目的地之间的最佳乘车方案。然后又在问题一、二的基础上通过对权重的设定和调整，将多目标规划问题转化为单一目标规划问题，利用“层次分析法”建立对各条线路进行评价的数学模型，最后用LINGO编程求解出最优乘车方案。问题三的中顺序经过这几个站点的最佳乘车路线是: 33路57路39-53路 69路火车站 市政府 科大新区 洛阳师院 上海市场14路火车站遍历经过这几个站点的最佳乘车路线是: 14路 25路 57路 火车站 海市场步行街 河科大新区 洛阳市政府33路洛阳师院52路火车站(正序逆序皆可)【关键词】线路优化；乘客心理调查；控制变量法；遍历；目标规划；层次分析法；LINGO一、问题重述问题背景21世纪的中国快速发展，交通事业也应承而上。中国人民先后告别了马车与草鞋，再见了单车与驾车，还有的为了社会的可持续发展，放弃了私家汽车，公共交通如日中天地发展起来，成为交通网络的重要组成部分。现代的洛阳，亦是如此。而随着公共交通的快速发展，这张交通网络也正变得错综复杂。面对着如此复杂密集的交通网络，如何从中寻找出一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案，成为公共交通系统中最关键而又最基本的问题。需要解决的问题问题一：从洛阳市火车站出发顺序经过洛阳市政府、河科大新校区、洛阳师院、上海市场步行街，并回到洛阳火车站的可行乘车方案。问题二：从洛阳市火车站出发遍历洛阳市政府、河科大新校区、洛阳师院、上海市场步行街，并回到洛阳火车站的可行乘车方案。问题三：从洛阳市火车站出发以顺序和遍历两种方式经过洛阳市政府、河科大新校区、洛阳师院、上海市场步行街，并回到洛阳火车站的最佳乘车方案。二、问题分析本题目是一个公交出行最优路径选择问题，我们首先应该清楚各个目的地之间的公交线路情况，因此需要登录“洛阳公交网”查询、收集和整理相关数据信息（具体数据信息见附录）。问题一已经给出确定的出行路线，我们只要知道相邻两个目的地之间的车次情况既可以作答。问题二要求遍历四个目的地，我们可以先用“控制变量法”筛选出任意相邻的两个目的地的最佳车次，然后根据“排列组合”的知识确定达到各个目的地的先后顺序，最终确定乘坐公交的可行方案。问题三需要求解出前两个问题的最优乘车方案，为此我们需要建立一个科学、合理的公交线路评价方法，然后定量分析出各种乘车方案的优劣。三、基本假设公交车不受载客人数、天气等因素影响，能保持匀速行驶，平均速度12.76公里/小时。不考虑公交车在行驶过程中因等待红灯、堵车等客观条件对消耗时间的影响，相邻两公交车的间隔时间为：5分钟。司机的驾驶技术、服务态度及公交车的舒适度等因素对乘客选择公交车次没有影响。洛阳市乘客的心理调查结果与南京市无明显差异。该乘客在各个目的地停留时间与乘坐公交时间的和小于一天。所有公交线路均双向。四、符号定义及说明序号序号符号说明1A洛阳火车站2B洛阳市政府3C河南科技大学新校区4D洛阳师范学院5E上海市场步行街6第i个因素在最终评分中所占的权重7X考虑换乘因素后所得的分数8Y考虑时间因素后所得的分数9Z考虑费用因素后所得的分数10M考虑所有因素后最终的得分五、模型建立及求解（一）问题一的模型建立及求解1、对影响乘客选择车次、路线的因素作定性分析通常公交乘客出行时，主要考虑以下几个主要因素：换乘次数、消耗时间、出行费用、所需要的步行时间、司机的服务态度和公交车的舒适程度等。下面对影响因素作如下解释：换乘次数：乘客从出发地到目的地过程中所乘车的次数。消耗时间：乘客乘坐公交车所消耗的时间。出行费用：乘客从出发点地到目的地过程中所需要的费用。所需要的步行时间：乘客在换乘时所需要的步行时间。司机的服务态度和公交的舒适度：这些因素在该问题中不作定量分析。从现实生活中可知，以上几个因素存在相关性，因此可以对上述因素对比后作出简化。比如“换乘次数”与“所需要的步行时间”具有一定的正相关性。综上所述，影响乘客选择车次、路线的主要因素有三个：换乘次数、乘车时间、出行费用。所以，我们应着重做好对以上三方面数据的收集和整理。2、整理A—B—C—D—E—A中相邻两个目的地之间的车次情况：表格1顺序经过各站点车次资料汇总3、依据上述数据，建立相应的数学模型，如图1所示：火火车站市政府科大新区上海市场洛阳师范线路1线路2线路3线路4线路5线路6线路7线路16线路17线路18线路14线路15线路11线路12线路13线路10线路9线路8图1顺序经过各站点路线（二）问题二的模型建立及求解1、整理A、B、C、D、E中任意两个目的地之间的车次情况：表格2任意两站点间路线2、用“控制变量法”初次筛选出任意两个目的地之间的最优车次因为在任意的两个目的地之间都存在不同的车次供乘客选择，为了使该问题的模型简化，我们决定采用“控制变量法”对任意两个目的地之间的车次进行筛选。依次控制“换乘次数”、“乘车时间”、“出行费用”三个因素中的两个，通过比较另外一个因素得出两个目的地之间的最佳乘车车次。我们得到的筛选结果如下：A—A—B33路521A—C68路0461A—D52路0361A—E14路0361B—C57路0351.5B—D33路0381BB—E70路0561C—D39路→53路1682C—E25路0441D—E69路0561.5表格3任意两站之间的最佳路线3、计算优化后可行方案的数量根据“排列组合”的知识我们知道，遍历四个目的地再回到出发点的可行方案共有A424种4、依据以上的结论，得到可行的遍历方。如下表所示：换乘 总时总费序号 线路 次数 中途时间/分钟 间 用A-B-C-D-E-A 1 52356856362476.5A-B-C-E-D-A O 5235445636223 6A-B-D-C-E-A 1 52386844362385.5A-B-D-E-C-A 0 52385644462365.5A-B-E-C-D-A 1 52564468362565.5A-B-E-D-C-A 1 5256566846278 6A-C-B-D-E-A 0 4635385636211 6A-C-B-E-D-A 0 4656565636250 6A-C-D-B-E-A 1 46685656362625.5A-C-D-E-B-A 1 4668565652278 6A-C-E-B-D-A 0 4644563836220 5A-C-E-D-B-A 0 46565638522485.5A-D-B-C-E-A 0 36383544361895.5A-D-B-E-C-A 0 3638564446220 5A-D-C-B-E-A 1 3668355636231 6A-D-C-E-B-A 1 36684456522565.5A-D-E-B-C-A 0 3656563535218 6A-D-E-C-B-A 0 3656443552223 6A-E-B-C-D-A 1 3656356836231 6A-E-B-D-C-A 1 36563868462445.5A-E-C-D-B-A 1 36446838522385.5A-E-C-B-D-A 0 36443538361895.5A-E-D-C-B-A 1 36566835522476.5 24 A-E-D-B-C-A 0 3656383546211 6表格4遍历各站点的所有可选路线（三）问题三的模型建立及求解1、问题一最优方案的确定我们由5.2.2可知，通过“控制变量法”可得各个目的地之间的最佳车次。我们可以利用该结果对问题一进行简化，进而得到问题一的最优乘车方案。如右图2所示：2、影响因素的权重分析及调整从5.1.1的分析可知，影响乘客选择车次、路线的主要因素有三个：换乘次数、乘车时间、出行费用。那么这几个因素在乘客心中的重要性如何分布呢？这就有必要对洛阳市的公交乘客进行心理调查，然后对数据进行统计处理和分析。考虑到这次模拟训练时间紧迫，我们在此参考南京市做的一个公交乘客出行心理调查结果。其结果如图3。火车站(乘33路)上海市场（乘14路）市政府（乘57路）科大新区（乘39-53路）洛阳师范（乘69路）图20.00%5.000.00%5.00%%10.0015.00%20.00%25.00%30.00%35.00%40.00%45.00%费用最低时间最短换乘最少其他图3由于时间原因，我们对不同路线中的“其他”类因素暂时不能做出准确的定量评价，因此我们对前三类因素的比重做出调整，使其权重系数和为1。调整后的结果如下：图4换乘最少 45%时间最短 35%费用最低 20%3、建立评价方法的层次分析模型C2(2C2(2w)时间C3(3w)费用O(乘车方案)准则层……目标层方案层P2路线2P1路线1P24路线24C1(1w)换乘次数将决策问题分为3个层次：目标层O，准则层C，方案层P目标层是O最佳乘车方案准则层有三个因素：C换车次数、C时间、C费用。 1 1 1其各自权重系数分别为w、w、w；从5.3.2的分析可知，w=0.45、w=0.35、1 2 3 1 2w=0.2。3方案层为24条路线，从P（路线1）到P（路线24）。现在我们再对各个影响因作间最短分别为各个方面的100分，然后采用数理统计的方法，对落入不同区间的数值赋予分值。赋值原则如下表所示：表格5换乘赋值原则换乘次数换乘次数分值0100160表格6时间赋值原则时间区间时间区间分数（185，195］100（195，205］95（205，215］90（215，225］85（225，235］80（235，245］75（245，255］70（255，265］65（265，275］60（275，285］55表格7费用赋值原则费用分值51005.5906806.570目标规划问题二原本是一个多目标规划问题，由于我们上述模型的建立，可以将其简化为单一的目标规划问题，即S.tMaxM=w*X+w*Y+w*Z 1 2 3用LINGO软件编辑程序model:title最优乘车路线;sets:line/1..24/:x,y,z,m;endsetsdata:w1=0.45;w2=0.35;w3=0.20;x=601006010060601001006060100100100100606010010060606010060100;y=70857575655590709055857010085806585858075751007090;z=70809090908080809080100909010080908080809090907080;enddata@for(line(i):m(i)=w1*x+w2*y+w3*z);max=@max(line:m);end运行结果见附录一。得出最优的乘车路线是第13条A-D-B-C-E-A和第22条A-E-C-B-D-A，再结合表格3中两站点间的最佳乘坐公交方案，得到最终路线如下： 14路 25路 57路 火车站 海市场步行街 河科大新区 洛阳市政府33路洛阳师院52路火车站(正序逆序皆可)六、模型评价和推广优点：本文在分析过程中采用“图文并茂”的方式，形象直观；从“洛阳公交网”上搜集到的数据科学、准确；（3）基于“层次分析法”建立的评价模型简单易懂，容易操作；（4）利用LINGO编程求解，快捷、鲜明。缺点：洛阳市公交乘客的“心理调查结果”可能与南京市公交乘客的“心理调查”有差异；在对三个影响因素作详细分析时，缺乏理论解释；模型推广：我们所建立的模型具有很强的“可移植性”，可以通过编程开发相对应的选择乘车方案的软件，之后乘客在出行时只需要输入遍历的目的地，即可自动生成最优乘车方案。七、参考文献常志勇，《层次分析法课件》，2009年8月。陈龙，数学建模—公交线路选择模型，，2010年8月17日。洛阳公交公司，公交地图，，2010年8月17日。[4]谢兆鸿等，《数学建模技术》，北京：中国水利水电出版社，2003年。八、附录附录一LINGO程序运行结果：Globaloptimalsolutionfoundatiteration:0Objectivevalue:98.00000ModelTitle: 最优乘车路线VariableValueReducedCostW10.45000000.000000W20.35000000.000000W30.20000000.000000X(1)60.000000.000000X(2)100.00000.000000X(3)60.000000.000000X(4)100.00000.000000X(5)60.000000.000000X(6)60.000000.000000X(7)100.00000.000000X(8)100.00000.000000X(9)60.000000.000000X(10)60.000000.000000X(11)100.00000.000000X(12)100.00000.000000X(13)100.00000.000000X(14)100.00000.000000X(15)60.000000.000000X(16)60.000000.000000X(17)100.00000.000000X(18)100.00000.000000X(19)60.000000.000000X(20)60.000000.000000X(21)60.000000.000000X(22)100.00000.000000X(23)60.000000.000000X(24)100.00000.000000Y(1)70.000000.000000Y(2)85.000000.000000Y(3)75.000000.000000Y(4)75.000000.000000Y(5)65.000000.000000Y(6)55.000000.000000Y(7)90.000000.000000Y(8)70.000000.000000Y(9)90.000000.000000Y(10)55.000000.000000Y(11)85.000000.000000Y(12)70.000000.000000Y(13)100.00000.000000Y(14)85.000000.000000Y(15)80.000000.000000Y(16)65.000000.000000Y(17)85.000000.000000Y(18)85.000000.000000Y(19)80.000000.000000Y(20)75.000000.000000Y(21)75.000000.000000Y(22)100.00000.000000Y(23)70.000000.000000Y(24)90.000000.000000Z(1)70.000000.000000Z(2)80.000000.000000Z(3)90.000000.000000Z(4)90.000000.000000Z(5)90.000000.000000Z(6)80.000000.000000Z(7)80.000000.000000Z(8)80.000000.000000Z(9)90.000000.000000Z(10)80.000000.000000Z(11)100.00000.000000Z(12)90.000000.000000Z(13)90.000000.000000Z(14)100.00000.000000Z(15)80.000000.000000Z(16)90.000000.000000Z(17)80.000000.000000Z(18)80.000000.000000Z(19)80.000000.000000Z(20)90.000000.000000Z(21)90.000000.000000Z(22)90.000000.000000Z(23)70.000000.000000Z(24)80.000000.000000M(1)65.500000.000000M(2)90.750000.000000M(3)71.250000.000000M(4)89.250000.000000M(5)67.750000.000000M(6)62.250000.000000M(7)92.500000.000000M(8)85.500000.000000M(9)76.5