公交线路优化

2010 高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：河南科技大学参赛队员（打印并签名）：1.许光辉2. 李贵涛3. 蔡亚娟指导教师或指导教师组负责人（打印并签名）：日期：2010年8月 18 日赛区评阅编号（由赛区组委会评阅前进行编号）2010河南科技大学数学建模选拔赛A 题 公交车线路优化设计摘要本文旨在研究公交线路优化设计问题，寻找出一条或多条快速、经济、方便的从出 发点到目的地的最优乘车或换乘方案。首先，我们依据“公交乘客心理调查结果”，明确影响乘客选择车次、路线的主要 因素有三个：换乘次数、乘车时间和出行费用，确定各自所占的权重。之后登陆“洛阳 公交网”全面收集和整理这三个影响因素的具体数据。对于问题一，已经给出确定的乘车路线，直接找出两目的地的车次依次乘车。结果 见论文第4页图1。对于问题二，我们先用“控制变量法”初次筛选出任意两个目的地之间的最优车次， 然后运用排列组合的方法确定遍历四个目的地再回到出发点的可行方案共有 A 4 = 244 种。结果见论文第6页表格4。对于问题三，我们先利用“控制变量法”对任意两个目的地间的车次情况进行优化， 筛选出任意两个目的地之间的最佳乘车方案。然后又在问题一、二的基础上通过对权重 的设定和调整，将多目标规划问题转化为单一目标规划问题，利用“层次分析法”建立 对各条线路进行评价的数学模型，最后用LINGO编程求解出最优乘车方案。问题三的中顺序经过这几个站点的最佳乘车路线是:,33路 士”宀57路 工“亠土厂 39-53路宀 -69路 火车站市政府科大新区洛阳师院上海市场-1-4路- 火车站遍历经过这几个站点的最佳乘车路线是:-1-4路-2-5路-5-7路 -火车站-海市场步行街 河科大新区 洛阳市政府-3-3路-5-2路 -洛阳师院火车站（正序逆序皆可）【关键词】线路优化；乘客心理调查；控制变量法；遍历；目标规划；层次分析法； LINGO一、问题重述1、问题背景21 世纪的中国快速发展，交通事业也应承而上。中国人民先后告别了马车与草鞋， 再见了单车与驾车，还有的为了社会的可持续发展，放弃了私家汽车，公共交通如日中 天地发展起来，成为交通网络的重要组成部分。现代的洛阳，亦是如此。而随着公共交 通的快速发展，这张交通网络也正变得错综复杂。面对着如此复杂密集的交通网络，如 何从中寻找出一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案， 成为公共交通系统中最关键而又最基本的问题。2、需要解决的问题问题一：从洛阳市火车站出发顺序经过洛阳市政府、河科大新校区、洛阳师院、上 海市场步行街，并回到洛阳火车站的可行乘车方案。问题二：从洛阳市火车站出发遍历洛阳市政府、河科大新校区、洛阳师院、上海市 场步行街，并回到洛阳火车站的可行乘车方案。问题三：从洛阳市火车站出发以顺序和遍历两种方式经过洛阳市政府、河科大新校 区、洛阳师院、上海市场步行街，并回到洛阳火车站的最佳乘车方案。二、问题分析本题目是一个公交出行最优路径选择问题，我们首先应该清楚各个目的地之间的公 交线路情况，因此需要登录“洛阳公交网”查询、收集和整理相关数据信息（具体数据 信息见附录）。问题一已经给出确定的出行路线，我们只要知道相邻两个目的地之间的车次情况既 可以作答。问题二要求遍历四个目的地，我们可以先用“控制变量法”筛选出任意相邻的两个 目的地的最佳车次，然后根据“排列组合”的知识确定达到各个目的地的先后顺序，最 终确定乘坐公交的可行方案。问题三需要求解出前两个问题的最优乘车方案，为此我们需要建立一个科学、合理 的公交线路评价方法，然后定量分析出各种乘车方案的优劣。三、基本假设1、公交车不受载客人数、天气等因素影响，能保持匀速行驶，平均速度 12.76 公 里/小时。2、不考虑公交车在行驶过程中因等待红灯、堵车等客观条件对消耗时间的影响， 相邻两公交车的间隔时间为：5 分钟。3、司机的驾驶技术、服务态度及公交车的舒适度等因素对乘客选择公交车次没有 影响。4、洛阳市乘客的心理调查结果与南京市无明显差异。5、该乘客在各个目的地停留时间与乘坐公交时间的和小于一天。6、所有公交线路均双向。四、符号定义及说明序号符号说明1A洛阳火车站2B洛阳市政府3C河南科技大学新校区4D洛阳师范学院5E上海市场步仃街6第i个因素在最终评分中所占的权重7X考虑换乘因素后所得的分数8Y考虑时间因素后所得的分数9Z考虑费用因素后所得的分数10M考虑所有因素后最终的得分五、模型建立及求解（一）问题一的模型建立及求解1、对影响乘客选择车次、路线的因素作定性分析 通常公交乘客出行时，主要考虑以下几个主要因素：换乘次数、消耗时间、出行费 用、所需要的步行时间、司机的服务态度和公交车的舒适程度等。下面对影响因素作如 下解释：（1）换乘次数：乘客从出发地到目的地过程中所乘车的次数。（2）消耗时间：乘客乘坐公交车所消耗的时间。（3）出行费用：乘客从出发点地到目的地过程中所需要的费用。（4）所需要的步行时间：乘客在换乘时所需要的步行时间。（5）司机的服务态度和公交的舒适度：这些因素在该问题中不作定量分析。 从现实生活中可知，以上几个因素存在相关性，因此可以对上述因素对比后作出简 化。比如“换乘次数”与“所需要的步行时间”具有一定的正相关性。综上所述，影响乘客选择车次、路线的主要因素有三个：换乘次数、乘车时间、出 行费用。所以，我们应着重做好对以上三方面数据的收集和整理。火车站U 政府线线路17洛阳师范线路11线路12线路13线路182、整理 ABCDEA 中相邻两个目的地之间的车次情况：乘车区间路线序号乘坐公交换乘次数/次时间/分钟费用/元AB133路0521262路26路1502.5368路-26路1522BC457路0351.5570路-25路1482670路68路1482733路39路1542CD839路53路1682939路69路1682.51068路69路1762.5DE1169路0561.51261路50路16521361路103路1642EA1414路036115103路04511611路04711750路04711812路一19路1522表格 1 顺序经过各站点车次资料汇总3、依据上述数据，建立相应的数学模型，如图 1 所示：图 1 顺序经过各站点路线 二）问题二的模型建立及求解1、整理 A、B、C、D、E 中任意两个目的地之间的车次情况乘车区间乘坐公交换乘次数/次时间/分钟费用/元AB33路052162路26路1502.568路-26路1522AC68路046146路一34路1622.5AD52路036181路0361.533路0371AE14路0361103路045111路047150路047112路一19路1522BC57路0351.570路一25路148270路一68路148233路一39路1542BD33路038129路一58路146370路一58路1472.5BE70路056129路0521.5CD39路一53路168239路一69路1682.568路一69路1762.5CE25路044163路一68路1562.563路一25路1502.5DE69路0561.561路一50路165261路103路1642表格 2 任意两站点间路线2、用“控制变量法”初次筛选出任意两个目的地之间的最优车次因为在任意的两个目的地之间都存在不同的车次供乘客选择，为了使该问题的模型 简化，我们决定采用“控制变量法”对任意两个目的地之间的车次进行筛选。依次控制 “换乘次数”、“乘车时间”、“出行费用”三个因素中的两个，通过比较另外一个因素得 出两个目的地之间的最佳乘车车次。我们得到的筛选结果如下：AB33路0521AC68路0461AD52路0361AE14路0361BC57路0351.5BD33路0381BE70路0561CD39路-53路1682CE25路0441DE69路0561.5表格 3 任意两站之间的最佳路线3、计算优化后可行方案的数量根据“排列组合”的知识我们知道，遍历四个目的地再回到出发点的可行方案共有A 4 24 种44、依据以上的结论，得到可行的遍历方案。如下表所示：序号线路换乘 次数中途时间/分钟总时 间总费 用1A-B-C-D-E-A152356856362476.52A-B-C-E-D-AO523544563622363A-B-D-C-E-A152386844362385.54A-B-D-E-C-A052385644462365.55A-B-E-C-D-A152564468362565.56A-B-E-D-C-A1525656684627867A-C-B-D-E-A0463538563621168A-C-B-E-D-A0465656563625069A-C-D-B-E-A146685656362625.510A-C-D-E-B-A14668565652278611A-C-E-B-D-A04644563836220512A-C-E-D-B-A046565638522485.513A-D-B-C-E-A036383544361895.514A-D-B-E-C-A03638564446220515A-D-C-B-E-A13668355636231616A-D-C-E-B-A136684456522565.517A-D-E-B-C-A03656563535218618A-D-E-C-B-A03656443552223619A-E-B-C-D-A13656356836231620A-E-B-D-C-A136563868462445.521A-E-C-D-B-A136446838522385.522A-E-C-B-D-A036443538361895.523A-E-D-C-B-A136566835522476.524A-E-D-B-C-A036563835462116表格4遍历各站点的所有可选路线（三）问题三的模型建立及求解1、问题一最优方案的确定我们由 5.2.2可知，通过“控制变量法” 可得各个目的地之间的最佳车次。我们可以 利用该结果对问题一进行简化，进而得到问 题一的最优乘车方案。如右图 2 所示：2、影响因素的权重分析及调整从 5.1.1 的分析可知，影响乘客选择车 次、路线的主要因素有三个：换乘次数、乘 车时间、出行费用。那么这几个因素在乘客 心中的重要性如何分布呢？这就有必要对 洛阳市的公交乘客进行心理调查，然后对数 据进行统计处理和分析。考虑到这次模拟训 练时间紧迫，我们在此参考南京市做的一个 公交乘客出行心理调查结果。其结果如图 3。市政府乘 57 路）上海市场乘 14 路）科大新区乘 39-53 路）洛阳师范乘 69 路）换乘最少41.16%时间最短30.93%费用最低18.61%其他因素9.30%换乘最少45%时间最短35%费用最低20%由于时间原因，我们对不同路线中的 因此我们对前三类因素的比重做出调整,图23、建立评价方法的层次分析模型目标层准则层C（w）换乘次数0（乘车方案）C3(用)方案层 *路线线1路线2图5将决策问题分为3个层次：目标层O,准则层C,方案层P目标层是O最佳乘车方案准则层有三个因素：C换车次数、C时间、C费用。其各自权重系数分别为w、w、w ；从5.3.2的分析可知，w =0.45、w =0.35、12312w =0.2。3方案层为 24 条路线,从 P （路线 1） 到 P （路线24）。现在我们再对各个影响因素1 作详细分析：我24们取换乘次数最少、总费用最低、总时 间最短分别为各个方面的100分,然后采用数理统计的方法,对落入不同区间的数值赋 予分值。赋值原则如下表所示：表格5 换乘赋值原则换乘次数分值0100160表格 6 时间赋值原则时间区间分数(185, 195100(195, 20595(205, 21590(215, 22585(225, 23580(235, 24575(245, 25570(255, 26565(265, 27560(275, 28555表格7费用赋值原则费用分值51005.5906806.5704、目标规划问题二原本是一个多目标规划问题，由于我们上述模型的建立，可以将其简化为单 一的目标规划问题，即S.t Max M= w *X+ w *Y+ w *Z1235、用LINGO软件编辑程序model:title 最优乘车路线;sets:line/1.24/:x,y,z,m;endsetsdata:w1=0.45;w2=0.35;w3=0.20;x=6010060 100 60 601001006060100 100 10010060601001006060 6010060100;y=70857575 655590709055 85701008580658585 80757510070 90rz=7080 90 9090 80 8080908010090 90 100809080808090 909070 80;enddatafor(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路 洛阳师院火车站(正序逆序皆可)六、模型评价和推广1、优点：(1) 本文在分析过程中采用“图文并茂”的方式，形象直观；(2) 从“洛阳公交网”上搜集到的数据科学、准确；(3) 基于“层次分析法”建立的评价模型简单易懂，容易操作；(4) 利用LINGO编程求解，快捷、鲜明。2、缺点：(1) 洛阳市公交乘客的“心理调查结果”可能与南京市公交乘客的“心理调查”有 差异；(2) 在对三个影响因素作详细分析时，缺乏理论解释；3、模型推广： 我们所建立的模型具有很强的“可移植性”，可以通过编程开发相对应的选择乘车 方案的软件，之后乘客在出行时只需要输入遍历的目的地，即可自动生成最优乘车方案。七、参考文献1 常志勇， 层次分析法课件， 2009年8月。2陈龙，数学建模公交线路选择模型，2010年8月17日。3 洛阳公交公司，公交地图，2010年8月17日。4 谢兆鸿等，数学建模技术，北京：中国水利水电出版社，2003年。八、附录附录一 LINGO程序运行结果：Global optimal solution found at iteration: 0Objective value: 98.00000Model Title:最优乘车路线VariableValueReduced CostW10.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)Z( 1)Z( 2)Z( 3)Z( 4)Z( 5)Z( 6)Z( 7)Z( 8)Z( 9)Z( 10)Z( 11)Z( 12)Z( 13)Z( 14)Z( 15)Z( 16)Z( 17)Z( 18)Z( 19)Z( 20)Z( 21)Z( 22)Z( 23)Z( 24)M( 1)M( 2)M( 3)M( 4)M( 5)M( 6)M( 7)M( 8)M( 9)M( 10)M( 11)M( 12)M( 13)M( 14)M( 15)M( 16)M( 17)M( 18)M( 19)M( 20)M( 21)M( 22)M( 23)M( 24)98.0000065.5000092.5000090.0000070.0000080.0000090.0000090.0000090.0000080.0000080.0000080.0000090.0000080.00000100.000090.0000090.00000100.000080.0000090.0000080.0000080.0000080.0000090.0000090.0000090.0000070.0000080.0000065.5000090.7500071.2500089.2500067.7500062.2500092.5000085.5000076.5000062.2500094.7500087.5000098.0000094.7500071.0000067.7500090.7500090.7500071.0000071.2500071.250000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.000000附录二公交车地图、时间及车次火车站一市政府二IK虫克三包S Lo洛阳站I參塾袖盎国1S255車住E X卵當辭f I_ _ L古城建趣rtg!市政府东门r&ae 区I ir载曙1胡路起虐洛阳此车站區I步讦至洛阳站 直I 乘坐3SS 在市政府东门下车 區|步冇至洛阳市政府 终点洛阳市改府 厂杳看谍鉢点起点洛阳火车站乘坐诙在竝下车歩行至壬坝大道美茵街口乘坐2斶g在理西下车步行至洛阳市政府终点洛阳市政府屢坯耳685& 26路I 起点洛阳火车站I瓯乘坐遷(g在西宜区査下车通歩行至凯薩西跻解融路口臣乘坐26a 在市委酉门下车a 步行至洛阳市政府终点洛阳币政府火车站科大新区火车站洛阳师范上海市场火车站科大新区市政府师范学院市政府上海市场市政府科大新区洛阳师院上海市场科大新区洛阳师院上海市场附录三 公交车票价：2.5 元/人次：85 路1.5 元/人次：15，29，34，54，56，57，58，59，60，62，63，65，66，69，81 路1 元/人次：2，4，5，6，7，8，9，10，11，12，14，16，17，18，19，20，21，22，24，25，26，27，28，30，31，32，33，35，36，37，38，39，40，41，42，43， 46，48，50，51，52，53，55，61，63，64，68，70，80，82，83，86，101，102，103