2010高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。
如有违反竞赛规则的行为,我们将受到严肃处理。
我们参赛选择的题号是(从A/B/C/D中选择一项填写): A我们的参赛报名号为(如果赛区设置报名号的话):所属学校(请填写完整的全名):河南科技大学参赛队员(打印并签名) :1. 许光辉2. 李贵涛3. 蔡亚娟指导教师或指导教师组负责人(打印并签名):日期: 2010 年 8 月 18 日赛区评阅编号(由赛区组委会评阅前进行编号):2010河南科技大学数学建模选拔赛A 题 公交车线路优化设计摘要本文旨在研究公交线路优化设计问题,寻找出一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案。
首先,我们依据“公交乘客心理调查结果”,明确影响乘客选择车次、路线的主要因素有三个:换乘次数、乘车时间和出行费用,确定各自所占的权重。
之后登陆“洛阳公交网”全面收集和整理这三个影响因素的具体数据。
对于问题一,已经给出确定的乘车路线,直接找出两目的地的车次依次乘车。
结果见论文第4页图1。
对于问题二,我们先用“控制变量法”初次筛选出任意两个目的地之间的最优车次,然后运用排列组合的方法确定遍历四个目的地再回到出发点的可行方案共有4424A = 种。
结果见论文第6页表格4。
对于问题三,我们先利用“控制变量法”对任意两个目的地间的车次情况进行优化,筛选出任意两个目的地之间的最佳乘车方案。
然后又在问题一、二的基础上通过对权重的设定和调整,将多目标规划问题转化为单一目标规划问题,利用“层次分析法”建立对各条线路进行评价的数学模型,最后用 LINGO 编程求解出最优乘车方案。
问题三的中顺序经过这几个站点的最佳乘车路线是:火车站33−−−→路市政府57−−−→路科大新区−−−→39-53路洛阳师院−−−→69路上海市场14−−−→路火车站 遍历经过这几个站点的最佳乘车路线是:火车站−−−→←−−−14路海市场步行街−−−→←−−−25路河科大新区57−−−→←−−−路洛阳市政府−−−→←−−−33路洛阳师院52−−−→←−−−路火车站(正序逆序皆可) 【关键词】线路优化;乘客心理调查;控制变量法;遍历;目标规划;层次分析法; LINGO一、问题重述1、问题背景21世纪的中国快速发展,交通事业也应承而上。
中国人民先后告别了马车与草鞋,再见了单车与驾车,还有的为了社会的可持续发展,放弃了私家汽车,公共交通如日中天地发展起来,成为交通网络的重要组成部分。
现代的洛阳,亦是如此。
而随着公共交通的快速发展,这张交通网络也正变得错综复杂。
面对着如此复杂密集的交通网络,如何从中寻找出一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案,成为公共交通系统中最关键而又最基本的问题。
2、需要解决的问题问题一:从洛阳市火车站出发顺序经过洛阳市政府、河科大新校区、洛阳师院、上海市场步行街,并回到洛阳火车站的可行乘车方案。
问题二:从洛阳市火车站出发遍历洛阳市政府、河科大新校区、洛阳师院、上海市场步行街,并回到洛阳火车站的可行乘车方案。
问题三:从洛阳市火车站出发以顺序和遍历两种方式经过洛阳市政府、河科大新校区、洛阳师院、上海市场步行街,并回到洛阳火车站的最佳乘车方案。
二、问题分析本题目是一个公交出行最优路径选择问题,我们首先应该清楚各个目的地之间的公交线路情况,因此需要登录“洛阳公交网”查询、收集和整理相关数据信息(具体数据信息见附录)。
问题一已经给出确定的出行路线,我们只要知道相邻两个目的地之间的车次情况既可以作答。
问题二要求遍历四个目的地,我们可以先用“控制变量法”筛选出任意相邻的两个目的地的最佳车次,然后根据“排列组合”的知识确定达到各个目的地的先后顺序,最终确定乘坐公交的可行方案。
问题三需要求解出前两个问题的最优乘车方案,为此我们需要建立一个科学、合理的公交线路评价方法,然后定量分析出各种乘车方案的优劣。
三、基本假设1、公交车不受载客人数、天气等因素影响,能保持匀速行驶,平均速度12.76公里/小时。
2、不考虑公交车在行驶过程中因等待红灯、堵车等客观条件对消耗时间的影响,相邻两公交车的间隔时间为:5分钟。
3、司机的驾驶技术、服务态度及公交车的舒适度等因素对乘客选择公交车次没有影响。
4、洛阳市乘客的心理调查结果与南京市无明显差异。
5、该乘客在各个目的地停留时间与乘坐公交时间的和小于一天。
6、所有公交线路均双向。
(一)问题一的模型建立及求解1、对影响乘客选择车次、路线的因素作定性分析通常公交乘客出行时,主要考虑以下几个主要因素:换乘次数、消耗时间、出行费用、所需要的步行时间、司机的服务态度和公交车的舒适程度等。
下面对影响因素作如下解释:(1)换乘次数:乘客从出发地到目的地过程中所乘车的次数。
(2)消耗时间:乘客乘坐公交车所消耗的时间。
(3)出行费用:乘客从出发点地到目的地过程中所需要的费用。
(4)所需要的步行时间:乘客在换乘时所需要的步行时间。
(5)司机的服务态度和公交的舒适度:这些因素在该问题中不作定量分析。
从现实生活中可知,以上几个因素存在相关性,因此可以对上述因素对比后作出简化。
比如“换乘次数”与“所需要的步行时间”具有一定的正相关性。
综上所述,影响乘客选择车次、路线的主要因素有三个:换乘次数、乘车时间、出行费用。
所以,我们应着重做好对以上三方面数据的收集和整理。
3、依据上述数据,建立相应的数学模型,如图1所示:图1 顺序经过各站点路线(二)问题二的模型建立及求解1、整理A、B、C、D、E中任意两个目的地之间的车次情况:2、用“控制变量法”初次筛选出任意两个目的地之间的最优车次因为在任意的两个目的地之间都存在不同的车次供乘客选择,为了使该问题的模型简化,我们决定采用“控制变量法”对任意两个目的地之间的车次进行筛选。
依次控制“换乘次数”、“乘车时间”、“出行费用”三个因素中的两个,通过比较另外一个因素得3、计算优化后可行方案的数量根据“排列组合”的知识我们知道,遍历四个目的地再回到出发点的可行方案共有4 424A 种(三)问题三的模型建立及求解1、问题一最优方案的确定 我们由5.2.2可知,通过“控制变量法”可得各个目的地之间的最佳车次。
我们可以利用该结果对问题一进行简化,进而得到问题一的最优乘车方案。
如右图2所示:2、影响因素的权重分析及调整从5.1.1的分析可知,影响乘客选择车次、路线的主要因素有三个:换乘次数、乘车时间、出行费用。
那么这几个因素在乘客心中的重要性如何分布呢?这就有必要对洛阳市的公交乘客进行心理调查,然后对数据进行统计处理和分析。
考虑到这次模拟训练时间紧迫,我们在此参考南京市做的一个公交乘客出行心理调查结果。
其结果如图3。
图2由于时间原因,市政府 57路)上海市场 (乘14路)火车站 (乘33路) 洛阳师范(乘69路)科大新区 (乘39-53路)3、建立评价方法的层次分析模型图5将决策问题分为3个层次:目标层O ,准则层C ,方案层P 目标层是O 最佳乘车方案准则层有三个因素:C 1换车次数、C 1时间、C 1费用。
其各自权重系数分别为1w 、2w 、3w ;从5.3.2的分析可知,1w =0.45、2w =0.35、3w =0.2。
方案层为24条路线,从P 1(路线1) 到P 24(路线24)。
现在我们再对各个影响因素作详细分析:我们取换乘次数最少、总费用最低、总时间最短分别为各个方面的100分,然后采用数理统计的方法,对落入不同区间的数值赋予分值。
赋值原则如下表所示:准则层目标层方案层4、目标规划问题二原本是一个多目标规划问题,由于我们上述模型的建立,可以将其简化为单一的目标规划问题,即S.t Max M=1w *X+2w *Y+3w *Z5、用 LINGO 软件编辑程序model :title 最优乘车路线; sets :line/1..24/:x,y,z,m; endsets data :w1=0.45;w2=0.35;w3=0.20;x=60 100 60 100 60 60 100 100 60 60 100 100 100 100 60 60 100 100 60 60 60 100 60 100;y=70 85 75 75 65 55 90 70 90 55 85 70 100 85 80 65 85 85 8075 75 100 70 90;z=70 80 90 90 90 80 80 80 90 80 100 90 90 100 80 90 80 80 80 90 90 90 70 80; 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−−−→←−−−路火车站(正序逆序皆可) 六、模型评价和推广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: 最优乘车路线Variable Value Reduced CostW1 0.4500000 0.000000W2 0.3500000 0.000000W3 0.2000000 0.000000X( 1) 60.00000 0.000000X( 2) 100.0000 0.000000X( 3) 60.00000 0.000000X( 4) 100.0000 0.000000X( 5) 60.00000 0.000000X( 6) 60.00000 0.000000X( 7) 100.0000 0.000000X( 8) 100.0000 0.000000X( 9) 60.00000 0.000000X( 10) 60.00000 0.000000X( 11) 100.0000 0.000000X( 12) 100.0000 0.000000X( 13) 100.0000 0.000000X( 14) 100.0000 0.000000X( 15) 60.00000 0.000000X( 16) 60.00000 0.000000X( 17) 100.0000 0.000000X( 18) 100.0000 0.000000X( 19) 60.00000 0.000000X( 20) 60.00000 0.000000X( 21) 60.00000 0.000000X( 22) 100.0000 0.000000X( 23) 60.00000 0.000000X( 24) 100.0000 0.000000Y( 1) 70.00000 0.000000Y( 2) 85.00000 0.000000Y( 3) 75.00000 0.000000Y( 4) 75.00000 0.000000Y( 5) 65.00000 0.000000Y( 6) 55.00000 0.000000Y( 7) 90.00000 0.000000Y( 8) 70.00000 0.000000Y( 9) 90.00000 0.000000Y( 10) 55.00000 0.000000Y( 11) 85.00000 0.000000Y( 12) 70.00000 0.000000Y( 13) 100.0000 0.000000Y( 14) 85.00000 0.000000Y( 15) 80.00000 0.000000Y( 16) 65.00000 0.000000Y( 17) 85.00000 0.000000Y( 18) 85.00000 0.000000Y( 19) 80.00000 0.000000Y( 20) 75.00000 0.000000Y( 21) 75.00000 0.000000Y( 22) 100.0000 0.000000Y( 23) 70.00000 0.000000Y( 24) 90.00000 0.000000 Z( 1) 70.00000 0.000000 Z( 2) 80.00000 0.000000 Z( 3) 90.00000 0.000000 Z( 4) 90.00000 0.000000 Z( 5) 90.00000 0.000000 Z( 6) 80.00000 0.000000 Z( 7) 80.00000 0.000000 Z( 8) 80.00000 0.000000 Z( 9) 90.00000 0.000000 Z( 10) 80.00000 0.000000 Z( 11) 100.0000 0.000000 Z( 12) 90.00000 0.000000 Z( 13) 90.00000 0.000000 Z( 14) 100.0000 0.000000 Z( 15) 80.00000 0.000000 Z( 16) 90.00000 0.000000 Z( 17) 80.00000 0.000000 Z( 18) 80.00000 0.000000 Z( 19) 80.00000 0.000000 Z( 20) 90.00000 0.000000 Z( 21) 90.00000 0.000000 Z( 22) 90.00000 0.000000 Z( 23) 70.00000 0.000000 Z( 24) 80.00000 0.000000 M( 1) 65.50000 0.000000 M( 2) 90.75000 0.000000 M( 3) 71.25000 0.000000 M( 4) 89.25000 0.000000 M( 5) 67.75000 0.000000 M( 6) 62.25000 0.000000 M( 7) 92.50000 0.000000 M( 8) 85.50000 0.000000 M( 9) 76.50000 0.000000 M( 10) 62.25000 0.000000 M( 11) 94.75000 0.000000 M( 12) 87.50000 0.000000M( 13) 98.00000 0.000000 M( 14) 94.75000 0.000000 M( 15) 71.00000 0.000000 M( 16) 67.75000 0.000000 M( 17) 90.75000 0.000000 M( 18) 90.75000 0.000000 M( 19) 71.00000 0.000000 M( 20) 71.25000 0.000000 M( 21) 71.25000 0.000000M( 22) 98.00000 0.000000 M( 23) 65.50000 0.000000 M( 24) 92.50000 0.000000附录二公交车地图、时间及车次火车站—市政府上海市场—火车站科大新区——市政府科大新区——洛阳师院上海市场—科大新区洛阳师院—上海市场附录三公交车票价: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。