公交线路优化

1、2010高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A我们的参赛报名号为（如果赛区设置报名号的话

2、）：所属学校（请填写完整的全名）：河南科技大学参赛队员（打印并签名）：1.许光辉李贵涛蔡亚娟指导教师或指导教师组负责人（打印并签名）：日期：2010年8月18日赛区评阅编号（由赛区组委会评阅前进行编号）：2010河南科技大学数学建模选拔赛A题公交车线路优化设计摘要本文旨在研究公交线路优化设计问题，寻找出一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案。首先，我们依据“公交乘客心理调查结果”，明确影响乘客选择车次、路线的主要因素有三个：换乘次数、乘车时间和出行费用，确定各自所占的权重。之后登陆“洛阳公交网”全面收集和整理这三个影响因素的具体数据。对于问题一，己经给出确定的乘车路线

3、，直接找出两目的地的车次依次乘车。结果见论文第4页图1。对于问题二，我们先用“控制变量法”初次筛选出任意两个目的地之间的最优车次,然后运用排列组合的方法确定遍历四个目的地再回到出发点的可行方案共有A：=24种。结果见论文第6页表格4。对于问题三，我们先利用“控制变量法”对任意两个目的地间的车次情况进行优化,筛选出任意两个目的地之间的最佳乘车方案。然后乂在问题一、二的基础上通过对权重的设定和调整，将多目标规划问题转化为单一目标规划问题，利用“层次分析法”建立对各条线路进行评价的数学模型，最后用LINGO编程求解出最优乘车方案。问题三的中顺序经过这几个站点的最佳乘车路线是：TOC o 1-5 h

4、z33路、亠57路、,.39-53路、,69路.火车站市政府科大新区洛阳师院上海市场辭火车站遍历经过这儿个站点的最佳乘车路线是：14路、25路57路、火车站海市场步行街?河科大新区?洛阳市政府33路、52路、?洛阳师院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、依据上述数据，建立相应的数学模型，如图

5、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.5C

6、D39路一53路168239路一69路1682.568路一69路1762.5CE25路044163路一68路1562.563路一25路1502.5DE69路0561.561路一50路165261路103路1642表格2任意两站点间路线2、用“控制变量法”初次筛选出任意两个目的地之间的最优车次因为在任意的两个目的地之间都存在不同的车次供乘客选择，为了使该问题的模型简化，我们决定采用“控制变量法”对任意两个目的地之间的午次进行筛选。依次控制“换乘次数”、“乘车时间”、“出行费用”三个因素中的两个，通过比较另外一个因素得出两个目的地之间的最佳乘车车次。我们得到的筛选结果如下：AB33路0521AC6

7、8路0461AD52路0361AE14路0361BC57路0351.5BD33路0381BE70路0561CD39路53路1682CE25路0441DE69路0561.5表格3任意两站之间的最佳路线3、计算优化后可行方案的数量根据“排列组合”的知识我们知道，遍历四个目的地再回到出发点的可行方案共有A：=24种4、依据以上的结论，得到可行的遍历方案。如下表所示:换乘总时总费序号线路次数中途时间/分钟|Hj用1A-B-C-D-E-A152356856362476.52A-B-C-E-D-A0523544563622363A-B-D-C-E-A152386844362385.54A-B-D-E-C-

8、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.513AHD-B-C-E-A036383544361895.514AHD-B-E-C-A03638564446220

9、515A-D-C-B-E-A13668355636231616A-D-C-E-B-A136684456522565.517A-D-E-B-C-A03656563535218618A-D-E-C-B-A03656443552223619A-E-B-CHD-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遍历各站点的

10、所有可选路线（三）问题三的模型建立及求解1、问题一最优方案的确定我们由5.2.2可知，通过“控制变量法”可得各个目的地之间的最佳车次。我们可以利用该结果对问题一进行简化，进而得到问题一的最优乘车方案。如右图2所示：2、影响因素的权重分析及调整从5.1.1的分析可知，影响乘客选择车次、路线的主要因素有三个：换乘次数、乘车时间、出行费用。那么这儿个因素在乘客心中的重要性如何分布呢？这就有必要对洛阳市的公交乘客进行心理调查，然后对数据进行统计处理和分析。考虑到这次模拟训练时间紧迫，我们在此参考南京市做的一个公交乘客出行心理调查结果。其结果如图3。上海市场（乘14路火车站（乘33路）市政府（乘57路）

11、科大新区（乘39-53洛阳师范（乘69路）换乘最少41.16%时间最短30.93%费用最低18.61%其他因素9.30%换乘最少45%时间最短35%费用最低20%由于时间原因，我们对不同路线中白因此我们对前三类因素的比重做出调整,图23、建立评价方法的层次分析模型图5将决策问题分为3个层次：目标层0,准则层C,方案层P目标层是0最佳乘车方案准则层有三个因素：G换车次数、G时间、G费用。其各自权重系数分别为叫、叫、叫；从5.3.2的分析可知，叫二0.45、w?=0.35、vv3二0.2。方案层为24条路线，从玖（路线1）到f（路线24）。现在我们再对各个影响因素作详细分析：我们取换乘次数最少、总

12、费用最低、总时间最短分别为各个方面的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.tMaxM=m;*X+w2*Y+*Z

13、5、用LINGO软件编辑程序model:title最优乘车路线；sets:line/124/:y,zzm;endsetsdata:V71=O45;w2=0.35;w3=0.20;x=601006010060601001006060100100100100606010010060606010060100;y=70857575655590709055857010085806585858075751007090;z=70809090908080809080100909010080908080809090907080;enddatafor(line(i):m(i)=wl*x+w2*y+w3*z);ma

14、x=max(line:m);end运行结果见附录一。得出最优的乘车路线是第13条A-D-B-C-E-A和第22条A-E-C-B-D-A,再结合表格3中两站点间的最佳乘坐公交方案，得到最终路线如下：14路25路57路火车站厂n海市场步行街产口河科大新区洛阳市政府33路52路洛阳师院火车站（正序逆序皆可）六、模型评价和推广1、优点：（1）本文在分析过程中采用“图文并茂”的方式，形象直观；（2）从“洛阳公交网”上搜集到的数据科学、准确；（3）基于“层次分析法”建立的评价模型简单易懂，容易操作；（4）利用LINGO编程求解，快捷、鲜明。2、缺点：（1）洛阳市公交乘客的“心理调查结果”可能与南京市公交乘

15、客的“心理调查”有差异；（2）在对三个影响因素作详细分析时，缺乏理论解释；3、模型推广：我们所建立的模型具有很强的“可移植性”，可以通过编程开发相对应的选择乘车方案的软件，之后乘客在出行时只需要输入遍历的目的地，即可自动生成最优乘车方案。七、参考文献常志勇，层次分析法课件，2009年8月。陈龙，数学建模一公交线路选择模型，2010年8月17Ho洛阳公交公司，公交地图，2010年8月17Elo谢兆鸿等，数学建模技术，北京：中国水利水电出版社，2003年。八、附录附录一LINGO程序运行结果：Globaloptimalsolutionfoundatiteration:0Objectivevalue

16、: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.00000

17、0.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.0000

18、00Y(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.00000

19、0.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

20、)80.000000.000000Z(7)80.000000.000000Z(8)80.000000.000000Z(9)90.000000.000000Z(10)80.000000.000000Z(ID100.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

21、.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.500000.000000M(10)62.250000.000000M(11)94.750000.000000M(12)87.500000.000000M(13)98.000000.000000M(14)94.750000.000000M(15)71.000000.000000M(16)67.750000.000000M(17)90.750000.000000M(18)90.750000.000000M(19)7