2014年福建省高职院校技能大赛班车
班车的合理安排
摘要
本文针对人类社会生活中相当普遍的班车的合理安排问题,我们通过简化模型、分析数据、减少决策变量个数,研究如何使班车的安排更加合理,即运用我们的模型,说明每个班次用哪一辆班车,使得在满足需要的情况下,尽量节省每日的油耗成本。
根据题目分析,首先建立不同班车的座位所对应的油耗,列出不同班车在不同线路的费用
yijtipj
,并对每日班车发车时刻及班次编号进行简化,然后根
据条件要求每班次的车都应当保证有充足的座位,因此每日乘坐各班次的人数其取最大值。再对时间进行分析可知,三辆班车同时7:00时从市区去学校,所以要同时从三条路线出发,再根据乘车人数的情况52,28,42只有一种安排方式因此路线1,、2、3、10、11、12就确定了。
针对4—9次车的确定,第4班发车时间为9:00,则ABC三辆班车均可赶回继续下一班次。从市区到学校,走路线一所花时间为45分钟,根据人数情况可选ABC,再根据费用最低原则,首选C车为第4班次,同理对于第5班次,考虑时间以及要返回的人数,考虑油耗最少,因此选择C车。再对6—9班次进一步简化,假设哪个班次开什么车为
f45pjx1j45pjx2j70pjx3j70pjx4j
j1
j1
j1
j1
3
3
3
3
xi'j
并列出其最小费用关系式
,再根据要求写出约束条件,并用LINGO
软件求出最小费用为1395元。
关键词: 最小费用 LINGO软件 班次
一. 问题重述
某高校地处市郊,共设立了三条不同方向的接送线路,每天用班车接送居住在市区沿途线路的教职工。这三条线路市区与学校之间的平均运行时间依次分别需要45分钟、70分钟和50分钟。目前学校有三辆班车,分别是55座、45座和33座,根据经验和当前油价,这三辆班车的油耗大约分别是5元/分钟、4元/分钟和3元/分钟。
本学期学校拟定的每日班车发车时刻及相应的班次编号见表1,其中上行表示从市区到学校,下行表示从学校到市区。
由于周一至周五每日的课程安排不同,因此每日乘坐同一班次的人数也是不同的。据统计,每日乘坐各班次的教职工人数范围见表2。
请你们通过建立数学模型,编制出一个每日班车的合理安排表,说明每个班次用哪一辆班车,使得在满足需要的情况下,尽量节省每日的油耗成本。要求做到符合下面条件:
1、对各条线路而言,每日早晨07:00从市区用哪一辆班车到学校,下午17:00就用这辆班车回到市区;
2、如果从学校沿某线路到达终点站时,距离终点站返回学校的下一班车发车时刻尚早,则空车返回学校;同样在迫不得已时,也采取从学校空车到某线路的终点站,再沿途接人到学校; 3、每班次的车都应当保证有充足的座位。(保证每位乘车的教师有座,不能站着)
二. 问题分析
要使得在满足需要的情况下,尽量节省每日的油耗成本,并编制出每日班车的合理安排表,通过题目分析首先可以建立三个不同班车每分钟所对应的油耗(三个不同班车具体情况表,即相应的座位数和油耗数),以(三个)不同班车在(三种)不同线路的费用,并对每日班车发车时刻及班次编号进行简化。其次根据条件要求每班次的车都应当保证有充足的座位,(保证每位乘车的教师有座,不能站着),因此每日乘坐各班次的人数必须取最大值。(这样很容易就确定出早上7:00从市区到学校的那三个班次的车,再根据要求1:对各条线路而言,每日早晨07:00从市区用哪一辆班车到学校,下午17:00就用这辆班车回到市区,这样下午17:00点的车也可以确定。剩下的几个班次的车我们可以建立线性规划模型用Lingo来求解。)
三. 模型假设
1. 题目所给的数据真实可靠
2. 老师等车以及上车时间忽略不计 3. 沿途无堵车现象
4. 每日班车都能正常发车,无班车出现损坏等事件
四. 符号说明
tr 驾驶第r线路所需的时间, r1,2,3
2,3 pj 第j辆车每分钟的油耗钱元/分钟, j1,
xij 第i班次所开第j辆车
f 原6-9班次所花的费用(不考虑空车费的情况下)
五. 模型建立与求解
5.1模型一
根据对题目的分析,要使得在满足需要的情况下,尽量节省每日的油耗成本,并编制出每日班车的合理安排表。
分析题目我们可以建立不同班车的座位与油耗的对应关系和不同班车在不同线路所对应的费用。
假设三辆班车分别为A(55座)、B(45座)、C(33座)。不同班车的座位与油耗所对应关系表如下:
表1:三个班车对应的座位以及油耗
设线路1,2,3所需的时间为t1,t2,t3,班车A,B,C每分钟所需要的油耗价钱为
p1,p2,p3。
A,B,C三个不同班车在三个不同线路的油耗:
yrjtrpj
r1,2,3,j1,2,3
根据上式算出不同班车在不同线路的费用如下表:
表2:不同班车在不同线路的费用
通过对题目表1的分析,为简化模型,适当减少决策变量的个数,对每日班车发车时刻及班次进行编号。
注:班次1、2、3、4、8、9为上行发车,即从市区到学校。班次5、6、7、10、11、12为下行发车,即从学校到市区。
因为每班次的车都应当保证有充足的座位,保证每位乘车的教师有座,不能站着。所以题目中表2的乘车人数范围必须取最大值才能保证每位乘车的教师有座,处理得表4
出发,再根据乘车人数的情况52,28,42只有一种安排方式:
A车--车次1,线路二--C车--车次2,线路三--B车—车次3,
在满足有充足座位的条件下要让费用最低只能让耗油最多的开最近的路程,因此A车要走1号路线,B车走路线3,C车走2号路线。对各条线路而言,每日早晨07:00从市区用哪一辆班车到学校,下午17:00就用这辆班车回到市区,这样车次10、11还有车次4继续下一班次。从市区到学校,走路线一所花时间为45分钟,根据人数情况可选ABC,再根据费用最低原则,首选C车为第4班次。
即:线路一--C车--班次4。
当班次4到达学校时已经是09:45,此时有23名教师要从学校返回市区,考虑油耗最少可以选择C车一号路线。这样班次1、2、3、4、5、10、11、12
件可以将已有的数据进行简化得表6
分别表示A,B,
3,2,1设xij为第i次用第j辆车,其中i1,2,3,4,j1,2,3,(j
C三辆班车)pj:班车j每分钟油耗元/分钟, 依题意得:
minf45pjx1j45pjx2j70pjx3j70pjx4j (1)
j1
j1
j1
j1
3
3
3
3
根据题目列出其约束条件:
每个班次只能发一辆车,可得:
x11x12x131
x21x22x231x31x32x331x41x42x431
(2)
班次1、3都是在12:00从学校开往市区,则车辆必须按两条路线同时进行即:
x11x131x21x321 x13x331
同理班次2、4的车辆必须按两条路线同时进行即:
x21x411x22x421 x23x431
将其公式用LINGO软件计算:
3
3
3
3
minf45pjx1j45pjx2j70pjx3j70pjx4j
j1
j1
j1
j1
x11x12x131xxx1212223
x31x32x331
x41x42x431x11x131s.t. x21x321x13x331
x21x411xx12242x23x431
解之得:
所以我们建立模型二,把空车的费用考虑在内。 5.2模型二 考虑空车费用:
根据题意可知,班次6、7、8、9只有路线一、路线二两种行车路线,所以我们先算出这俩种行车路线的费用,即
S1t1(p1x11p2x12)t1(p1x21p2x22)t2(p1x31p2x32p3x33)t2(p1x41p2x42)
整理得:
S1tjpjx1jtjpjx2jtjpjx3jtjpjx4j (1)
j1
j1
j1
j1
3
3
3
3
再算出这些班次的车全部空车回学校的费用,因为空车回校区为了节省费用所以选择路线最短的行车路线,即路线一。依题意得:
S245(p1x11p2x12)45(p1x21p2x22)45(p1x31p2x32p3x33)45(p1x41p2x42)
整理得:
S245pj(x1jx2jx3jx4j)
j13
(2)
最后再计算出实际第i次用第j辆车是否是空车可得:
S345(p1x11x22p2x12x22)245(p1x11x41p2x12x42)2 (3)
当班车开出时,若是空车那么 x11x22的乘积就是1,反之不是空车时x11x22的乘
积就是0,因为班车开出去是要往返的,所以有空车出去必有空车回来,因此必须乘以2。 结合(1)(2)(3)得考虑到空车费的情况下的总费用为:
minytjpjx1jtjpjx2jtjpjx3jtjpjx4j45pj(x1jx2jx3jx4j)
j1
j1
j1
j1
j1
3
3
3
3
3
45(p1x11x22p2x12x22)245(p1x11x41p2x12x42)2
根据题意可列出其约束条件:
x11+x12=1;x+x=1;2122
x31+x32+x33=1;
x41+x42=1;x11+x31=1;s.t.
x+x=1;1232
x21+x41=1;
x22+x42=1;x+x=1;3141x41+x42=1;
用LINGO软件求得其最小值是:1395
六. 模型评价
优点:
1. 对所要解决的问题,给出分析表格,使得论文更一目了然 2. 运用简单模型,减少决策变量,使得论文更加通俗易懂 3. 该模型简单易用,针对校车的安排具有很好的推广作用 缺点:
1.模型考虑因素过于简单 2.堵车现象没有考虑进去
3.座位取最大值,无法使资源得到最优分配
七. 参考文献
1. 堵秀凤,张剑,张宏民, 《数学建模》. 北京:北京航空航天大学出版社 2011.8
2. 陈恩水,王峰, 《数学建模与实验》. 北京:科学出版社 2008 3. 郭培俊, 《高职数学建模》 杭州:浙江大学出版社 2010.12 4. 姜启源,谢金星,叶俊,《数学模型》第四版 北京:高等教育出版社 2011.1
5. 杨启帆,谈之亦,何勇,《数学建模》杭州:浙江大学出版社 1999.8
附录
1. 不考虑空车费用模型:
min=(5*x11+4*x12)*45+(5*x21+4*x22)*45+(5*x31+4*x32+3*x33)*70+(5*x41+4*x42)*70; x11+x12=1; x21+x22=1; x31+x32+x33=1; x41+x42=1; x11+x31=1; x12+x32=1; x21+x41=1; x22+x42=1; x31+x41=1; x32+x42=1;
@bin(x11);@bin(x21);@bin(x31);@bin(x41);@bin(x12);@bin(x13);@bin(x22);@bin(x23);@bin(x32);@bin(x33);@bin(x42);@bin(x43);
2. 考虑空车费用模型:
min=(5*x11+4*x12)*45+(5*x21+4*x22)*45+(5*x31+4*x32+3*x33) *70+(5*x41+4*x42)*70+(5*x21+4*x22)*45+(5*x11+4*x12)*45+ (5*x31+4*x32+3*x33)*45+(5*x41+4*x42)*45- (5*x11*x21+4*x12*x22)*45*2- (5*x11*x41+4*x12*x42)*45*2; x11+x12=1; x21+x22=1; x31+x32+x33=1; x41+x42=1; x11+x31=1; x12+x32=1; x21+x41=1; x22+x42=1; x31+x41=1; x41+x42=1;
@bin(x11);@bin(x21);@bin(x31);@bin(x41);@bin(x12);
@bin(x22);@bin(x32);@bin(x33);@bin
(x42);