班车的合理安排论文.doc

2015年吉首大学数学建模竞赛承 诺 书我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性.如有违反竞赛规则的行为，我们将受到严肃处理.我们参赛的题目是： B题:班车的合理安排 参赛队员 (打印并签名) ：1. 田海军 2. 高柏松 3. 周金海 日期：2015年4月26日29班车的合理安排摘要 本文针对某高校和市区的班车运行的安排问题，通过合理的模型假设，把校车安排问题抽象成点线构成的网络模型，将问题转化为优化问题的求解。在问题解决过程中使用了模拟、贪心算法，在问题分析、模型的建立及求解过程中利用EXCEL、MATLAB、LINGO和C+软件对数据进行分析处理，最终得出结论.针对问题一：这是一个简单的数据分析问题，可由统计中的相关知识分析得出，根据路线1中各班次每天运送的教职工人数，利用excel可以求出路线一每天运送的人数，周一到周五的平均运送人数E=216.8人，方差为60.16；为了更加直观的观察，利用MATLAB画出了对应的图形（如图一），因此可以得出路线1每天运送的教职工人数存在显著差异.针对问题二：此问题是一个分配问题，首先考虑各班车的座位数是否满足每条路线各个时间段教职工的乘车人数，即车辆的座位数不小于教职工乘车的人数.这样就只需考虑怎么派车使得每天的油价费用最低，即让班次油耗最少.引入0-1变量，建立0-1规划模型，利用LIGNO和C+软件对模型进行求解和分析，得出每个班次具体是哪辆车，以及对应的时刻表、路线和方向（见表四）.针对问题三：在问题二的基础上，各终点站是相互连通的，因此到达有学校到达终点站是可以选择改变路线，而不是必须空车返回，在保证足够座位的情况下，建立0-1模型，利用C+软件对模型进行分析和求解，便可以得出班次对应的车辆,结果见（表五）.关键字： 上行 下行 油耗 线路 贪心算法 分配 0-1规划一.问题重述某高校地处市郊，共设立了五条不用方向的接送线路，每天用班车接送居住在市区沿途的教职工。这五条线路市区与学校之间的平均运动时间依次分别需要45分钟、70分钟、60分钟、20分钟和50分钟。目前学校配有五辆校车，分别55座、45座、40座、33座和26座，根据经验和当前油价，这三辆车的油耗大约分别是5元/分钟、4元/分钟、4元/分钟、3元/分钟和2元/分钟.题目具体要求：1、对各条线路而言，每日早晨07:00从市区用那一辆班车到学校，下午17:40就用这辆班车回到市区；2、如果从学校沿某线路到达终点时，距离终点站返回学校的下一班车时刻尚早，则空车返回学校；同样在迫不得己时，也采取从学校空车到某线路的终点站，再沿途接人到学校；3、每班次的车都应当保证有充足的座位。（保证每位乘车的教师有座，不能站着）；4、各条线路的终点站之间都有道路相连，平均运行时间题中都有给出，见附表2；5、周一至周五的课程安排不一样，每日的乘车人数也就不一样，根据事先统计，每日不同车次的人数见题中附件1.问题1:通过数据分析，说明线路1星期一至星期五平均每天运送的教职工人数是否存在显著差异？问题2:如果规定每辆班车都只在学校与某终点站之间运行，通过建立数学模型，编制出一个每日班车的合理安排表，说明每个班次用哪一辆班车，使得在满足需要的情况下，尽量节省每日的油耗成本.问题3:如果从学校沿某线路到达终点站时，距离该终点站返回学校的下一班车发车时刻尚早，或该终点站当日已经没有返回学校的班次，这时不必非得空车返回学校，可视情考虑安排到另一个线路的终点站，再沿途接人到学校.请重新建立数学模型，编制出一个在满足需要的情况下，尽量节省油耗成本的班车合理安排表.二.问题分析问题一的分析针对问题一，题目要求分析出线路1星期一至星期五平均每天运送的教职工人数是否存在显著差异。通过观察每日班车发车时刻及班次编号，我们发现路线一的班车车次分别是1、6、7、8、13、14、15号，由附表给班次人数统计表中给出的数据，可以利用Excel求出星期一到星期五每天运送的人数，接着求出这五天运送人数的平均值E=216.8人，方差为60.16，通过方差的大小可以看出星期一到星期五每天运送的人数存在显著性差异.问题二的分析针对问题二，规定每辆车只能在学校和某终点站之间运行，并且在迫不得已的情况下可以选择空车返回，在必须保证每位老师有座并且准时到达目的地的要求下，要考虑哪条路线用哪辆车使每天车辆的油耗值达到最小值，也就是最优分配.先利用MATLAB将不同路线满足座位的车辆给出来，再通过对不同路线班车的发车时刻表和每日乘客班次的人数统计表的分析，我们发现早上7:00每条路线都要从市区发车到学校，因此在满足座位的情况下，我们考虑不同班车在不同路线的油耗值，引入0-1变量并利用LINGO可以确定每天班次15号车次走那条路线使油耗值最小，又考虑到每日早晨07:00从市区用那一辆班车到学校，下午17:40就用这辆班车回到市区，从而1519号车次也确定下来.对于中间班次614号，考虑在满足座位的条件下，需要确定哪个车次安排哪辆班车可以使油耗最低，通过C+编程可以确定班车.由不同路线的发车时刻表可以分析出：班次6需要9:00按路线1从市区到学校，但8:10时五辆车已经全部到达学校，因此选择一辆车在8:10沿路线1空车返回，然后9:00在从市区沿路线1到学校；同样对班次7而言，在五辆车里面选择一辆满足条件的车按路线1回市区，考虑到与下一车次间隔时间太久，则空车返回学校；11:20后五辆车又全部在学校，从而可以选择三辆车在12:10分别沿路线1、2、4回市区，即车次810可以被确定；对车次1112来说，由于车次9在12:40还没到达市区，所以在11:20必须让剩下的两辆班车分别沿路线2、3空车返回市区，到12:40在原路返回学校；考虑到车次8到达市区的时间为12:55，因此可以让车次8的那辆车在13:00沿路线一返回学校，即车次13和车次8选择同一辆班车；车次9、10到达市区后原路空车返回学校，在15:50学校有五辆班车全部在学校，在满足条件的情况下选择一辆车15:50沿路线1回市区，到达后立即返回，17:20到达学校，即车次14也可以确定.问题三的分析针对问题三，各条线路的终点站有道路相连通，意味着从学校沿某线路到达终点站时，距离该终点站返回学校的下一班车发车时刻尚早，或该终点站当日已经没有返回学校的班次，这时不必非得空车返回学校，可视情考虑安排到另一个线路的终点站，再沿途接人到学校.有问题二的分析可以知道班次16,1519不会改变，因此只需我们考虑班次714的情况，利用C+编程可以确定各班次使用哪个班车，对于班次7，需要从五辆车中选一辆车沿路线1回市区，然后可以选择空车返回或者转移到路线2、3的终点站，班次810是从剩余的四辆中选择三辆在12:10分别沿路线1、2、4有学校发车到市区；班次11、12要根据班次7选择转移到线路2、3中哪个，所以确定好班次7，班次11、12就相应确定了；班次13与班次8是同一辆车；班次14可以从班次9、10中选择一辆车转到路线1，从而班次119都可以确定.三模型假设1.假设每辆班车都以相同的速度保持匀速行驶；2.忽略车辆在行驶过程中堵车、天气状况差等影响行驶的交通因素；3.车辆的行驶费用只考虑油耗产生的费用；4.周一到周五中每条路线教职工乘车的人数没有很大的变化；5.教职工按时在接车点等车，且不计上车时间；6.不同车次都能按时刻表发车；7.空车返回时在站点不停留时间，直接返回.四、符号说明符号符号意义E路线一周一到周五运送人数的平均值路线一周一到周五运送人数的方差一周的第i天第j个车次的所运人数路线一中第i天所运总人数i车走路线j所需的费用0-1变量M班车行驶产生的费用15和1519号班次的费用 6、7、14号班次的费用 812号班次的费用 各班车的油耗速度 各线路的行驶时间*其他未提及的符号会在文章中说明。五模型的建立与求解5.1.1模型一的建立 路线一中的在星期一至星期五每天运送人数分别记为，.则,平均值.方差.5.1.2问题一模型的求解将以上模型和路线一各班次人数输入Excel中，求出：平均值E=216.8人，方差.由方差的大小得知路线一每天运送人数存在显著性差异.另一方面为了更加直观的显示出每天运送职工人数和平均值的差别，可以通过MATLAB画出其相应的图，见图一.从图中也可以看出每天的运送人数波动比较大，因此存在显著性差异.图一5.1.3模型二的建立为使我们建立模型方便计算，我们简化表格减少决策变量，因为由条件知对各条线路而言，每日早晨07:00从市区用哪一辆班车到学校，下午17:40就用这两班车回到市区，所以我们把车次1、15,2、16，3、17，4、18,5、19合并，只需考虑车次1、2、3、4、5即可。所以得到每天发车班次及其时刻表:车次1；152；163；174；185；19611121314发车时刻7:00；17:407:00；17:407:00；17:407:00；17:407:00；17:4013:0012:4012:4013:0015:50表一五辆班车的油耗速度记为；座位数记为；五条路线的行车时间记为；因此每辆车子在不同路线上的费用.每天的总费用为.因为各班车是不相互影响的，所以达到最小，总费用就会最小.（1）对15号车次和1519号车次：在班车满足教职工都有座位即班车座位不小于相应班次对应的乘车人数的情况下，引入0-1变量，若第i辆车沿路线j行驶，记=1，否则记=0.每辆车最多只能选择一条路线，即对于，应有；另一方面，每条路线必须要有一辆班车，即对于,有；所以前五个班次和后五个班次的费用为目标函数.综上所述，这个问题的0-1规划模型为:, （2）对于614号班车，在座位满足的条件下，只要选择油耗费用最少就可以确定班车，通过分析我们得出：班次为6、7和14号的最小费用模型为，.班次13的班车可以由班次8选择的车确定，而对于班次812号来说，可以看成是五辆车选择五条路线，有费用的模型和相同.5.1.4模型二的求解利用题目中给的数据，带入上述模型可以的出不同车子的座位数及在五条线路上的耗油费用，如下表：线路1线路2线路3线路4线路5座位数车A22535030010025055车B1802802408020045车C1802802408020040车D1352101806015033车E901401204010026表二为了方便比较班车座位是否满足条件，将周一至周五每天各班次乘车人数以及路线作成表格如下.星期一：线路方向班次编号乘车人数班次编号乘车人数班次编号乘车人数班次编号乘车人数1上行1446251335下行713827141515452上行2251135下行92616243上行3261210下行17234上行420下行102418185上行542下行1940星期二：线路方向班次编号乘车人数班次编号乘车人数班次编号乘车人数班次编号乘车人数1上行1526201340下行712838141815402上行2281136下行92216263上行3221212下行17234上行422下行102018185上行540下行1942星期三：线路方向班次编号乘车人数班次编号乘车人数班次编号乘车人数班次编号乘车人数1上行1386151338下行723845141215452上行2211136下行93016253上行3251212下行17234上行420下行101718205上行540下行1938星期四：线路方向班次编号乘车人数班次编号乘车人数班次编号乘车人数班次编号乘车人数1上行1466181336下行716843141515422上行2221138下行92516263上行3211214下行17254上行418下行102218195上行542下行1938星期五：线路方向班次编号乘车人数班次编号乘车人数班次编号乘车人数班次编号乘车人数1上行1506201332下行721839141615502上行2241138下行92816223上行3221215下行17244上行422下行102418185上行542下行1942表三再将已知数据和0-1模型输入C+可以得出不同班次对应使用的班车，下表给出了对应班车的发车和达到时间，线路以及方向.星期一最低油耗M=4520元车辆编号发车及到达时间线路班次方向车A7：00-7:45线路11上行17：40-18:25线路115下行12:10-12:30线路410下行12:30-12:50线路4空车上行车B7：00-7:50线路55上行17:40-18:30线路519下行13:00-13:45线路113上行12:10-12:55线路18下行车C7：00-7:20线路44上行17:40-18:00线路418下行12:40-13:50线路211上行11:20-12:30线路2空车下行车D7：00-8:00线路33上行17:40-18:40线路317下行12:40-13:40线路312上行11:20-12:20线路3空车下行车E9:00-9:45线路16上行8:10-8:55线路1空车下行9:50-10:35线路17下行10:35-11:20线路1空车上行15:50-16:35线路114下行12:10-13:20线路29下行13:20-14:30线路2空车上行7：00-8:10线路22上行17:40-18:50线路216下行星期二最低油耗M=4540元车辆编号发车及到达时间线路班次方向车A7：00-7:45线路11上行17：40-18:25线路115下行12:10-12:30线路410下行12:30-12:50线路4空车上行车B7：00-7:50线路55上行17:40-18:30线路519下行13:00-13:45线路113上行12:10-12:55线路18下行车C7：00-7:20线路44上行17:40-18:00线路418下行12:40-13:50线路211上行11:20-12:30线路2空车下行车D7：00-8:10线路22上行17:40-18:50线路216下行12:40-13:40线路312上行11:20-12:20线路3空车下行车E9:00-9:45线路16上行8:10-8:55线路1空车下行9:50-10:35线路17下行10:35-11:20线路1空车上行15:50-16:35线路114下行12:10-13:20线路29下行13:20-14:30线路2空车上行7：00-8:00线路33上行17:40-18:40线路317下行星期三最低油耗M=4490元车辆编号发车及到达时间线路班次方向车A7：00-7:20线路44上行17:40-18:00线路418下行12:10-12:30线路410下行12:30-12:50线路4空车上行车B7：00-7:45线路11上行17：40-18:25线路115下行13:00-13:45线路113上行12:10-12:55线路18下行车C7：00-7:50线路55上行17:40-18:30线路519下行12:40-13:50线路211上行11:20-12:30线路2空车下行车D7：00-8:00线路33上行17:40-18:40线路317下行12:10-13:20线路29下行13:20-14:30线路2空车上行车E9:00-9:45线路16上行8:10-8:55线路1空车下行9:50-10:35线路17下行10:35-11:20线路1空车上行15:50-16:35线路114下行12:40-13:40线路312上行11:20-12:20线路3空车下行7：00-8:10线路22上行17:40-18:50线路216下行星期四最低油耗M=4520元车辆编号发车及到达时间线路班次方向车A7：00-7:45线路11上行17：40-18:25线路115下行12:10-12:30线路410下行12:30-12:50线路4空车上行车B7：00-7:50线路55上行17:40-18:30线路519下行13:00-13:45线路113上行12:10-12:55线路18下行车C7：00-7:20线路44上行17:40-18:00线路418下行12:40-13:50线路211上行11:20-12:30线路2空车下行车D7：00-8:00线路33上行17:40-18:40线路317下行12:40-13:40线路312上行11:20-12:20线路3空车下行车E9:00-9:45线路16上行8:10-8:55线路1空车下行9:50-10:35线路17下行10:35-11:20线路1空车上行15:50-16:35线路114下行12:10-13:20线路29下行13:20-14:30线路2空车上行7：00-8:10线路22上行17:40-18:50线路216下行星期五最低油耗M=4540元车辆编号发车及到达时间线路班次方向车A7：00-7:45线路11上行17：40-18:25线路115下行12:10-12:30线路410下行12:30-12:50线路4空车上行车B7：00-7:50线路55上行17:40-18:30线路519下行13:00-13:45线路113上行12:10-12:55线路18下行车C7：00-7:20线路44上行17:40-18:00线路418下行12:40-13:50线路211上行11:20-12:30线路2空车下行车D7：00-8:00线路33上行17:40-18:40线路317下行12:10-13:20线路29下行13:20-14:30线路2空车上行车E9:00-9:45线路16上行8:10-8:55线路1空车下行9:50-10:35线路17下行10:35-11:20线路1空车上行15:50-16:35线路114下行12:40-13:40线路312上行11:20-12:20线路3空车下行7：00-8:10线路22上行17:40-18:50线路216下行表四5.1.5模型三的建立在问题二的基础上，进一步考虑当终点站相连通时怎么分配车辆让费用最低.(1)分析发现：班次16和1519的模型和问题二中的模型一样，费用记为；(2)对于班次713,可以看成五辆车选择路线1两次，选择路线2、3、4各一次，因此其也是一个0-1规划模型, （3）班次14的费用模型为： ，5.1.6模型三的求解将题目中的相关数据和模型输入C+,得出每个班次对应的班车、总费用、线路、方向和发车时刻如下表：班次星期星期一星期二星期三星期四星期五1AABAA2EDEEE3DEDDD4CCACC5BBCBB6EEEEE7CCCCC8BBBBB9EEDED10AAAAA11CCCCC12DDEDE13BBBBB14EEEEE15AABAA16EDEEE17DEDDD18CCACC19BBCBB总费用/元44204440439044104430表五 *注明：1、 班次7到达市区后立即开往线路3的终点站，并且12:40作为班次12返回学校；2、 班次8到达市区后在终点站等到13:00并作为班次13返回学校；3、 班次9、10达到市区后空车返回学校.六.模型的检验对给出的结果，可以看出不同班次对应的车辆，只要验证所给车辆是否满足座位需求即可，我们利用MATLAB可以检验出所给车辆都满足需求，这保证了模型的准确性.七 模型的评价与推广6.1模型的优点1、 本文在第二三问针对要解决的相关问题，均给出了表格，使得论文更直观、更清晰，增加了文章的说服力；2、 在处理数据时，本文处理中简化了模型，减少每个环节决策变量个数，使得文章可信度高；3、 所构造模型结构简单，适应性强，第二问的处理办法有很好的推广作用；6.2模型的缺点1、 在对15和1519班次班车确定时，为保证每位教职工均有座位，解题中对其取最大值，有可能导致最终的结果并不是最优的配置。2、 本文模型偏重于理想化，忽略了一些实际存在的因素，例如沿途无堵车，正常行驶等等；3、 本文在对第三问模型建立时，可能在所得到最优结果的过程中与二分最优匹配相矛盾（与题目所给的所需座位数相关），在相关座位数发生一定变化时，可能不会存在最优安排方案；6.3模型的改进1、 减少理想化假设，考虑更多的实际因素，更能反映班车实际的安排情况，增强模型的推广性；2、 优化第三问714车次班车的确定模型，尽量消除因教职工所需要座位的数据变化对最优结果的影响；6.4模型的推广1、此模型可以用于城市公交车的车次安排，方便乘客的条件下尽可能的节约燃料，减少公交车的油耗费用.2、只要统计得到相应地区的乘车人数，可以利用此模型对车站车辆的车次及车辆座位的多少进行安排，方便乘客的同时，减少费用.八参考文献1数学模型, 姜启源,谢金星,叶俊编,高等教育出版社，2008.2MATLAB入门与实战，郭世健，邱志模，陆静芳等编，人民邮电出版社，2008.3运筹学第三版，刁在筠，刘桂真，宿洁等编，高等教育出版社，2013.4/view/63531d21a5e9856a56126077.html?qq-pf-to=pcqq.discussion附录%第一问代码%Excel 求平均值和方差：sum(B2:H2), sum(B3:H3) sum(B4:H4) sum(B5:H5) sum(B6:H6)var(B7:B12)%matlab 画图：x=1,2,3,4,5y=204,220,216,216,228;plot(x,y,k*)xlim(1,5)hold on;x=1:5;y=216.8*ones(1,5);plot(x,y)set(gca, XTick, 1 2 3 4 5)set(gca,XTickLabel,星期一,星期二,星期三,星期四,星期五)% 第二问代码：% 不同路线满足座位需求的车辆C=55,45,40,33,26;%车次所拥有的座位数%班次为1-5D=45,25,26,20,42;%星期一所需要的座位数%D=52,28,23,22,42;%星期二所需要的座位数%D=45,25,25,20,40;%星期三所需要的座位数%D=46,26,25,19,42;%星期四所需要的座位数%D=50,24,24,22,42;%星期五所需要的座位数%班次为8-12%D=27,26,24,35,10;%星期一所需要的座位数%D=38 22 20 36 12;%星期二所需要的座位数%D=45 30 17 36 12;%星期三所需要的座位数%D=43 25 22 38 14;%星期四所需要的座位数%D=39 28 24 38 15;%星期五所需要的座位数%N=225 350 300 100350;%180 280 240 80 280;%180 280 240 80 280;%135 210 180 60 210;%90 140 120 40 140;%8-12班次的路线选择N=225 350 300 100 250;180 280 240 80 200;180 280 240 80 200;135 210 180 60 150;90 140 120 40 100;%五辆车在五条路线上的耗能M=zeros(5,5);fori=1:5forj=1:5if(C(i)=D(j)M(i,j)=N(i,j);endendendM%0-1规划模型求解model:sets:person/1.5/;position/1.5/;link(person,position):c,x;endsetsdata:c=225,350,300,100,250,180,280,240,80,200,100000,280,240,80,100000,100000,210,180,60,100000,100000,140,120,40,100000;enddatamin=sum(link:c*x);for(person(i):sum(position(j):x(i,j)=1;);for(person(i):sum(person(j):x(j,i)=1;);for(link:bin(x);end %求解对应班次的班车及费用#include #include #include #include #include using namespace std;#define MAX_NUM_BANCI 20typedef struct nodecarint oil;int seat;int old_num;Car;typedef struct nodeline int need_minute; int belong_banci;Line;typedef struct noderesult int banci_num; char car_num;Result;bool comp_result(const Result &a,const Result &b) return a.banci_num b.banci_num;Car car6 = 0,2,26,5,3,33,4,4,40,3,4,45,2,5,55,1;Line line6 = 0,70,2,60,3,50,5,45,1,20,4;Line line_two6=0,70,11,70,9,60,12,45,8+13,20,10;int step_3_4_line_info6=0,2,2,3,1,4;int banci20=0,1,2,3,4,5,1,1,1,2,4,2,3,1,1;Result result20;int step_result610;int Week620=0,0,44,25,26,20,42,25,13,27,26,24,35,10,35,15,45,24,23,18,40,0,52,28,22,22,40,20,12,38,22,20,36,12,40,18,40,26,23,18,42,0,38,21,25,20,40,15,23,45,30,17,36,12,38,12,45,25,23,20,38,0,46,22,21,18,42,18,16,43,25,22,38,14,36,15,42,26,25,19,38,0,50,24,22,22,42,20,21,39,28,24,38,15,32,16,50,22,24,18,42;bool visit_car6;int result_count = 0,linecount = 0;int main() int i,j; for(i = 1;i=5;i+) memset(visit_car,false,sizeof(visit_car); memset(step_result,0,sizeof(step_result); result_count = 0; / at setp1 7:00 linecount = 1; while(linecount=5) for(j = 1;j= max(Weekilinelinecount.belong_banci,Weekilinelinecount.belong_banci+14) resultresult_count.banci_num = linelinecount.belong_banci; resultresult_count.car_num = A+carj.old_num-1; step_resulti1 += linelinecount.need_minute * carj.oil * 2; result_count +; linecount +; visit_carj = true; break; /at step2 8:10 for(j = 1;j= Weeki6) resultresult_count.banci_num = 6; resultresult_count.car_num = A + carj.old_num - 1; step_resulti2 += linebanci6.need_minute * carj.oil * 2; result_count+; break; /at step3 9:50 for(j = 1;j= Weeki7) resultresult_count.banci_num = 7; resultresult_count.car_num = A + carj.old_num - 1; step_resulti3 += linebanci7.need_minute * carj.oil * 2; result_count+; break; /at step4 11:20 12:10 linecount = 1; memset(visit_car,false,sizeof(visit_car); while(linecount=5) for(j = 1;j= Weeki line_twolinecount.belong_banci ) resultresult_count.banci_num = line_twolinecount.belong_banci; resultresult_count.car_n