校车安排问题的论文25组 汪妮.docx
- 文档编号:16222439
- 上传时间:2023-07-11
- 格式:DOCX
- 页数:31
- 大小:89.79KB
校车安排问题的论文25组 汪妮.docx
《校车安排问题的论文25组 汪妮.docx》由会员分享,可在线阅读,更多相关《校车安排问题的论文25组 汪妮.docx(31页珍藏版)》请在冰点文库上搜索。
校车安排问题的论文25组汪妮
2011高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。
如有违反竞赛规则的行为,我们将受到严肃处理。
我们参赛选择的题号是(从A/B/C/D中选择一项填写):
B
我们的参赛报名号为(如果赛区设置报名号的话):
J1814
所属学校(请填写完整的全名):
西安财经学院
参赛队员(打印并签名):
1.汪妮
2.窦青梅
3.石颀研
指导教师或指导教师组负责人(打印并签名):
日期:
2012年5月27日
赛区评阅编号(由赛区组委会评阅前进行编号):
2011高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号(由赛区组委会评阅前进行编号):
赛区评阅记录(可供赛区评阅时使用):
评
阅
人
评
分
备
注
全国统一编号(由赛区组委会送交全国前编号):
全国评阅编号(由全国组委会评阅前进行编号):
校车安排问题
摘要
本文研究的事校车安排问题。
首先将50个区抽象成一张无向赋权图G(V,E),采用图论中的经典算法———Floyd算法求出任意两个区之间的最短距离。
基于G(V,E),我们对其余问题展开分析和研究。
对于站点分布问题,由于最短距离已经得出,只需按需选择出距离最短的n个区最为站点。
站点的选出可根据到所有点距离的总和这个相对值来确定。
对于满意度问题,我们综合考虑距离和各站点人数的因素抽象出一个求满意度的函数,分别求出这两个因素下的满意度,求和,得出最能是大家满意的n个站点。
对于车辆分配的问题,我们把车辆的分配比例转换成站点乘车人数的比例。
依据教职工们以距离最短为原则选择站点乘车。
由于每辆车不得多于47人,我们可以求出最少共需要54辆车,所以最终得到的三个站点车辆数的总和应该最但限度的接近54。
最终我们得出是那个站点安排的车辆数应该为16区安排18辆,21区安排20辆,32区安排17辆。
总共55辆车。
关键词:
Floyd算法满意度无向带权图
一、问题重述
问题1:
如要建立
个乘车点,为使各区人员到最近乘车点的距离最小,该将校车乘车点应建立在哪
个点。
建立一般模型,并给出
时的结果。
问题2:
若考虑每个区的乘车人数,为使教师和工作人员满意度最大,该将校车乘车点应建立在哪
个点。
建立一般模型,并给出
时的结果。
问题3若建立3个乘车点,为使教师和工作人员尽量满意,至少需要安排多少辆车?
给出每个乘车点的位置和车辆数。
设每辆车最多载客47人。
问题4;关于校车安排问题,怎样既可以提高乘车人员的满意度,又可节省运行成本。
二、问题分析
校车安排问题中,乘车人员主要考虑的因素是距离,而对于校车来说就是最少车辆数安排最多乘员的原则安排,所以可对该问题作出如下分析:
问题一:
该文主要考虑距离因素,本着距离最短的原则则将该问题简化成求最短路径的问题。
问题二:
要使教职工满意则须到乘车点的距离最短,要使大家都满意则需要考虑各个区的乘车人数。
综合考虑这两者问题,求出满意度,取满意度最大的前n位。
所以该问可简化为求满意度的一个抽象函数的问题。
问题三:
该文中车辆数的安排所考虑的因素是乘车人数,所以将车辆在3个站点的安排比例就转化成各站点乘车人数的比例。
根据人数,本着“不空车,不超载”的原则求出一个车辆数使得它尽可能的接近最小车辆数。
三、模型假设
1.假设未给出距离的两个区可以通过其他区间接到达。
2.每位教师及工作人员均选择最短路径乘车。
3.乘车点均建在各区内,不考虑各区内的距离。
4.教师及工作人员到各站点乘车的满意度与到该站点的距离有关系,距离近则满意度高,距离远则满意度低。
5.假设任意时刻任意站点均有车,不考虑教师及工作人员的等车时间。
6、假设车辆不超载。
7、假设所有人员均乘车。
四、符号说明
符号
表示意义
符号i
表示意义
Vi
第i个区域i=1,2,3,...50
dij
第i区与第j区的最短距离i=1,2,3,...50j=1,2,3,...50
D
任意两区的最短距离矩阵
rij
含义是从Vi到Vj的最短路要经过点号为rij的点.
R
任意两区最短距离路径矩阵
St
表示t区教师和工作人员到最近乘车点的距离
Pt
表示t区的乘车人数,
Bt
表示nt乘车点应安排的车辆数。
t=1,2,3
Wt
表示t区人数Pt乘以距离St
n
第i个区域i=1,2,3,...50
ni
第i个区域i=1,2,3,...50
Vi
第i个区域i=1,2,3,...50
dij
第i区与第j区的最短距离i=1,2,3,...50j=1,2,3,...50
D
任意两区的最短距离矩阵
rij
含义是从Vi到Vj的最短路要经过点号为rij的点.
五、模型建立与求解
第一步:
用Floyd算法求出距离矩阵D=(dij)v×v.
1.算法的基本思想
直接在图的带权邻接矩阵中用插入顶点的方法依次构造出
个矩阵D
(1)、D
(2)、…、D(
),使最后得到的矩阵D(
)成为图的距离矩阵,同时也求出插入点矩阵以便得到两点间的最短路径.
2.算法原理
(1)求距离矩阵的方法
把带权邻接矩阵W作为距离矩阵的初值,即D(0)=
根据题目所给各区距离表列出D(0)=
50×50距离矩阵
D
(1)=
,其中
是从Vi到Vj的只允许以V1作为中间点的路径中最短路的长度.
D
(2)=
,
其中
是从Vi到Vj的只允许以V1、V2作为中间点的路径中最短路的长度.
D(V)=
,
其中
是从Vi到Vj的只允许以V1、V2、…VV作为中间点的路径中最短路
的长度.即是从Vi到Vj中间可插入任何顶点的路径中最短路的长,因此
D(
)即是距离矩阵.
(2)求路径矩阵的方法
在建立距离矩阵的同时可建立路径矩阵R,R=
rij的含义是Vi到Vj的最短路要经过点号为rij的点.
每求得一个D(k)时,按下列方式产生相应的新的R(k)
即当Vk被插入任何两点间的最短路径时,被记录在R(k)中,依次求D(v)时求得R(v),可由R(v)来查找任何点对之间最短路的路径.
(3)查找最短路径的方法
若
,则点p1是点i到点j的最短路的中间点.然后用同样的方法再分头查找.若:
(1)向点i追朔得:
…,
(2)向点j追朔得:
…,
则由点i到j的最短路的路径为:
3.算法步骤
Floyd算法:
求任意两点间的最短路
D(i,j):
i到j的距离.
R(i,j):
i到j之间的插入点.
输入:
带权邻接矩阵w(i,j)
(1)赋初值:
对所有i,j,d(i,j)
w(i,j),r(i,j)
j,k
1
(2)更新d(i,j),r(i,j)
对所有i,j,若d(i,k)+d(k,j) d(i,k)+d(k,j),r(i,j) k (3)若k= ,停止.否则k k+1,转(2). 用Matlab编程得D(50)=(dij)50×50,其中dij即为两点最短距离,同时可求出路径矩阵 D(50)=(dij)50×50矩阵如下: 1 2 3 4 5 6 7 8 9 …… 48 49 50 1 0 400 450 700 910 1140 1110 1280 1480 …… 1110 1310 1510 2 400 0 850 300 510 740 710 880 1080 …… 710 910 1110 3 450 850 0 600 810 1040 1010 1180 1380 …… 1560 1760 1875 4 700 300 600 0 210 440 410 580 780 …… 1010 1210 1275 5 910 510 810 210 0 230 200 370 570 …… 1220 1420 1485 6 1140 740 1040 440 230 0 320 340 540 …… 1450 1650 1620 7 1110 710 1010 410 200 320 0 170 370 …… 1164 1364 1300 8 1280 880 1180 580 370 340 170 0 200 …… 1334 1534 1470 9 1480 1080 1380 780 570 540 370 200 0 …… 1534 1734 1640 … …… …… …… …… …… …… …… …… …… …… …… …… …… 48 1110 710 1560 1010 1220 1450 1164 1334 1534 …… 0 200 1100 49 1310 910 1760 1210 1420 1650 1364 1534 1734 …… 200 0 1300 50 1510 1110 1875 1275 1485 1620 1300 1470 1640 …… 1100 1300 0 第二步: 设置n个乘车点时的取点情况 算法思路: 我们假设教师和工作人员去乘车时都去最近的乘车点。 这样,他们走的路程越短,就越满意。 在我们设置好乘车点后,由于不考虑每个区的乘车人数,每个区人员到最近乘车点乘车,乘车所走最短距离相加所得的总和最小时,教师和工作人员乘车的总体满意度就最高。 步骤如下: dit表示t区到i区的最短距离, 当N=2时,以n1,n2区为乘车点时,St表示t区教师和工作人员到最近乘车点的距离,即min{dn1t,dn2t}。 S总 {dn1t,dn2t}, 因为有50个区,这样就有 种选择乘车点位置的方法,S总共有 个,用C语言编程选出最小值的S总,此时S总值对应的n1,n2值即为乘车点应选择的区。 当N=3时,以n1,n2,n3区为乘车点时,St表示t区教师和工作人员到最近乘车点的距离,即min{dn1t,dn2t,dn3t}。 S总 {dn1t,dn2t,dn3t}, 因为有50个区,这样就有 种选择乘车点位置的方法,S总共有 个,用C语言编程选出最小值的S总,此时S总值对应的n1,n2,n3值即为乘车点应选择的区。 当N<=50时,以n1,n2,n3…nn区为乘车点时,St表示t区教师和工作人员到最近乘车点的距离,即min{dn1t,dn2t,dn3t……dnnt}。 S总= (dit,djt…dpt), 因为有50个区,这样就有 种选择乘车点位置的方法,S总共有 个,用C语言编程选出最小值的S总,此时S总值对应的n1,n2,n3…nn值即为乘车点应选择的区。 问题二模型的建立及求解 算法思路: 我们假设教师和工作人员去乘车时都去最近的乘车点。 这样,他们走的路程越短,满意度就越高。 在我们设置好乘车点后,考虑到每个区的人数不同,小区内人数越多,满意度就越高。 这样,影响满意度的因素可认为是两个: 1.人到达乘车点的距离; 2.小区内人数。 且这两个因素对满意度的影响各占50%。 步骤如下: Pi表示i区的人数;Lij表示i区与j区的最短路径值。 当N=3时,假设乘车站点为i,用Lij表示每一个小区教师和工作人员到i乘车点的距离,即Si= Lij 假设乘车站点为i,用Pi表示每一个小区教师和工作人员数量,即 Pi。 。 则满意度I可用公式I=( Lij/ Si)*50%+(Pi/ Pi)*50%得到。 用软件计算I得值最小的2个i点应设为乘车站点。 当N=3时,假设乘车站点为i,用Wi表示每一个小区教师和工作人员到i乘车点的距离,即Si= Lij。 假设乘车站点为i,用Pi表示每一个小区教师和工作人员数量,即 Pi。 则满意度I可用公式I=( Lij/ Si)*50%+(Pi/ Pi)*50%得到。 用软件计算I得值最小的3个i点应设为乘车站点。 当N=n时(n应在小于50的范围内考虑,否则无意义。 ),假设乘车站点为i,用Wi表示每一个小区教师和工作人员到i乘车点的距离,即Si= Lij。 假设乘车站点为i,用Pi表示每一个小区教师和工作人员数量,即 Pi。 则满意度I可用公式I=( Lij/ Si)*50%+(Pi/ Pi)*50%得到。 用软件计算I得值最小的n个i点应设为乘车站点。 问题三模型的建立及求解 算法思路: 假设所有工作人员均乘车。 由问题二已确定了乘车点所在的区域,为n1,n2,n3区,其他任意区的教师及工作人员选择去某个乘车点乘车的依据是到乘车点的路径最小。 现在只需用C语言编程计算出去n1,n2,n3区乘车点的乘车人数,然后再计算出所需车辆数。 步骤如下: Bt表示nt乘车点应安排的车辆数。 t=1,2,3 三个站点为n1=16,n2=21,n3=32,设到n1站点乘车有p1人,n2站点乘车有p2人,n3站点乘车有p3人,每辆车最多载47人。 则总共需要车辆数: B=B1+B2+B3 设住在1区域到n1乘车的人数为a1,住在2区域到n1乘车的人数为a2……住在50区域到n1乘车的人数为a50 住在1区域到n2乘车的人数为b2,住在2区域到n2乘车的人数为b2……住在50区域到n2乘车的人数为b50 住在1区域到n2乘车的人数为c2,住在2区域到n3乘车的人数为c2……住在50区域到n3乘车的人数为c50 则p1=a1+a2+a3+……+a50 P2=b1+b2+b3+……+b50 P3=c1+c2+c3+……+c50 问题三结果: p1=824,p2=923,p3=755. 故B1=18,B2=20,B3=17. 即B=B1+B2+B3=55 故学校至少需要安排55辆车,16区安排18辆,21区安排20辆,32区安排17辆。 问题四 1、将区域划成块,每一块有专车在专门点接送。 各位教职工去自己所属的乘车点乘车。 2、在有些人员较少得点,可以没有站点负责,由有空位的车辆环路接送。 3、有的车辆有不满客的情况,所以可以换成小型客车。 六、模型评价 本文的主要优点: 1、本文根据问题要求利用优化的思想,一步一步地讨论了模型的建立情况,使所建立的模型最大限度的接近实际问题。 2、本文建立的模型具有一般性,其他的学校或单位均可采用,可以减少学校或其他单位的经费开销。 本文的主要缺点: 1、 数据导入MATALAB繁琐,要浪费大量时间,且容易出错。 2、 对现实中的一些特殊情况尽情了简化处理,与现实稍有偏颇。 3、本文中我们计算任意两各路口间的最短距离时,采用了Floyd算法,而Floyd算法的时间复杂度比较高,争对本文中的大批量数据处理时计算时间比较长。 七、模型推广 本模型可推广到公共站点设置、服务中心位置选择、垃圾运输等最短路径、建筑选址问题。 本模型利用计算机程序实现了对结果的精确定位,还可应用于各种与此类型相关的场合。 参考文献 [1]耿国华,《数据结构——C语言描述》(第二版)西安电子科技大学出版社2008。 [2]《MATLAB基础教程》孙祥,清华大学出版社2005。 [3]张志涌,精通MATLAB6.5版[M],北京: 北京航空航天大学出版社,2005。 [4]宋兆基、徐流美,MATLAB6.5在科学计算中的应用[M],北京: 清华大学出版社,2005。 [5]方世昌,《离散数学》(第三版)西安电子科技大学出版社2008. 附录A 表1各区距离表 区域号 区域号 距离(m) 1 2 400 1 3 450 2 4 300 2 21 230 2 47 140 3 4 600 4 5 210 4 19 310 5 6 230 5 7 200 6 7 320 6 8 340 7 8 170 7 18 160 8 9 200 8 15 285 9 10 180 10 11 150 10 15 160 11 12 140 11 14 130 12 13 200 13 34 400 14 15 190 14 26 190 15 16 170 15 17 250 16 17 140 16 18 130 17 27 240 18 19 204 18 25 180 19 20 140 19 24 175 20 21 180 20 24 190 21 22 300 21 23 270 21 47 350 22 44 160 22 45 270 22 48 180 23 24 240 23 29 210 23 30 290 23 44 150 24 25 170 24 28 130 26 27 140 26 34 320 27 28 190 28 29 260 29 31 190 30 31 240 30 42 130 30 43 210 31 32 230 31 36 260 31 50 210 32 33 190 32 35 140 32 36 240 33 34 210 35 37 160 36 39 180 36 40 190 37 38 135 38 39 130 39 41 310 40 41 140 40 50 190 42 50 200 43 44 260 43 45 210 45 46 240 46 48 280 48 49 200 表2各区人员分布 区域 人数 区域 人数 1 65 26 16 2 67 27 94 3 42 28 18 4 34 29 29 5 38 30 75 6 29 31 10 7 17 32 86 8 64 33 70 9 39 34 56 10 20 35 65 11 61 36 26 12 47 37 80 13 66 38 90 14 21 39 47 15 70 40 40 16 85 41 57 17 12 42 40 18 35 43 69 19 48 44 67 20 54 45 20 21 49 46 18 22 12 47 68 23 54 48 72 24 46 49 76 25 76 50 62 附录B 问题一的程序代码(任意两个区之间的最短路径D矩阵,路线R矩阵) function[D,R]=floyd(a) n=size(a,1); D=a fori=1: n forj=1: n R(i,j)=j; end end R fork=1: n fori=1: n forj=1: n ifD(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k D R End 问题一的程序代码(N=2时,乘车点的区域) #include intmin(intx,inty) { intz; z=x x: y; return(z); }/*比较两个数的值,并返回较小的值*/ voidmain() {inti,j,t,s=0; intu[50][50]={0}; inta[50][50]={此为D矩阵每个值按顺序排列} /*以任意两个区最短路径的值定义一个二维数组*/ for(i=0;i<50;i++) for(j=i+1;j<50;j++) { { for(t=0;t<50;t++) s=s+min(a[i][t],a[j][t]);/*当以i,j区作为乘车点时,其他每个区到最近乘车点的最短路径相加*/ } u[i][j]=s;/*其他每个区到最近乘车点的最短路径相加的和赋值给以i,j为下标二维的数组元素*/ s=0; } intn1=0,n2=0,m=10000000000; for(i=0;i<50;i++) for(j=0;j<50;j++) if(u[i][j]! =0&&u[i][j] {m=u[i][j]; n1=i+1; n2=j+1; }/*选出其他每个区到最近乘车点的最短路径相加的和为最小时的乘车点*/ printf("\n\n当建立两个乘车点时,乘车点应选择的区域为: \n\n"); printf("%d区和%d区\n\n各区人员到最近乘车点的最小距离总和为: \n%d\n\n\n\n",n1,n2,m); printf("请按从小到大顺序输入任意两个区,并以这两个区作为乘车点: \n"); scanf("%d%d",&i,&j); printf("则以%d区和%d区作为乘车点时,各区人员到最近乘车点的最小距离总和为: \n",i,j); printf("%d\n\n\n",u[i-1][j-1]);/*可以以其他任意两个区作为乘车点时,与最优解比较各区人员到最近乘车点的最小距离总和*/ } 问题一的程序代码(N=3时,乘车点的区域) #include intmin(intx,inty,intw) { intz; z=(x x: y) (x x: y): w; return(z);/*比较三个数的值,并返回较小的值*/ } voidmain() {
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 校车安排问题的论文 25组 汪妮 校车 安排 问题 论文 25
![提示](https://static.bingdoc.com/images/bang_tan.gif)