《2022年校车安排问题数学建模文件 .pdf》由会员分享,可在线阅读,更多相关《2022年校车安排问题数学建模文件 .pdf(13页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、论文题目:关于校车安排问题的数学建模姓名张克彬专业电气学院电气信息类班级10级 16 班学号311008001627 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 13 页 - - - - - - - - - 2 关于校车安排问题的数学建模摘要:校车的安排问题涉及到的问题很广泛,其中包括最短距离问题, 资源最优配置问题,最短时间问题等等。 这些问题关系到教师们的满意和运营商的利益,是应该认真考虑的。关于第一题,主要涉及最短路程问题。我们需要在50 个小区中选出 n 个点
2、作为乘车点, 然后计算并比较得出每个小区到这n 个乘车点的最短距离, 之后确定该小区所属的最近乘车点和之间的距离,将50 个小区与其所属的最近乘车点的距离相加得路程和,一共应该有C50n种方案。比较各种方案的路程和,和最小的就是应对应建立的点的位置。关于第二题,和问题一相似, 也是一个求最小路程和的问题, 解法基本相同。不同之处在于考虑人数以后, 应该用每个小区与所属的最近乘车点的距离与该小区的人数做乘积,并用所得积相加,得出的为最短路程。关于第三题, 是安排车次的问题。 第二题中已经计算出乘车点为3 个时乘车点应设立在对应的三个小区, 易算出每个乘车点应承担的乘客量,由此计算出没个乘车点应派
3、多少辆车运行。 (不足一辆车的乘客时应派一辆车)关于第四题, 矛盾主要集中在教师和工作人员都希望随到随走,而运营商又希望每一辆车都有尽可能多的上座率,由此来降低运营成本, 同时运营商的做法也是一个关乎节约资源保护环境的问题。解决这个矛盾应该合理调整发车时间与学校作息时间的关系(春夏季与秋冬季采用不同的发车时刻表),在淡季采用区间车集中乘客, 在高峰期与淡季采用不同载客量的汽车,与附近学校协商采用不同的作息时间并共同采购利用部分汽车等等具体方法。校车安排问题采用数学方法同时也应该考虑实际情况,是一个典型的数学应用的问题。关键词:最短路程人数车辆安排 Floyd算法 MATLAB 名师资料总结 -
4、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 13 页 - - - - - - - - - 3 1. 问题的提出许多学校都建有新校区, 常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多,往往需要安排许多车辆。 如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。现有如下问题请你设计解决。假设老校区的教师和工作人员分布在50 个区,各区的距离见表1。各区人员分布见表 2。问题 1:如要建立n个乘车点,为使各区人员到最近乘车点的距离最小,该
5、将校车乘车点应建立在哪n个点。建立一般模型,并给出2, 3n时的结果。问题 2:若考虑每个区的乘车人数,为使教师和工作人员满意度最大,该将校车乘车点应建立在哪n个点。建立一般模型,并给出2, 3n时的结果。问题 3 若建立 3 个乘车点,为使教师和工作人员尽量满意,至少需要安排多少辆车?给出每个乘车点的位置和车辆数。设每辆车最多载客47 人(假定车只在起始站点载人)。问题 4;关于校车安排问题,你还有什么好的建议和考虑。可以提高乘车人员的满意度,又可节省运行成本。表 1 各区距离表区域号区域号距离 (m) 1 2 400 1 3 450 2 4 300 2 21 230 2 47 140 3
6、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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 13 页 - - - - - - - - - 4 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 1
7、5 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -
8、 - - - 第 4 页,共 13 页 - - - - - - - - - 5 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
9、46 48 280 48 49 200 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 13 页 - - - - - - - - - 6 表 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 2
10、1 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 2. 模型的假设及符号说明2.1 模型的假设1假设未给出距离的两个区可以通过其他区间接到达。2每位教师及工作人员均选择最短路径乘车。3乘车点均建在各区内,不考虑区与区之间。4. 教师及工作人员到各站点乘车的满意度与到该站点的距离有关系,距离近则满意度高,距离远则满意度低。名师资料总结 - - -精品资料欢迎下载 - -
11、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 13 页 - - - - - - - - - 7 5. 假设任意时刻任意站点均有车,不考虑教师及工作人员的等车时间。6. 在乘车点区内的人员乘车距离为零。7. 根据实际情况,我们假设所设置的乘车点数不大于50。8. 假设所有人员均乘车。9. 假设每辆车只载一次人。10. 假设汽车中途不再载人。11. 假设每辆车的型号一致。12. 假设每个乘车点的乘车人数固定不变。2.2 符号说明P(i ) (1i 50)小区的编号Q (j ) (1j 50)n 个乘车点中的第j 个乘车点
12、L(ij )小区 P(i ) (1i 50)到乘车点Q(j ) (1j 50)的最短路程M (i) 小区到 P(i ) ( 1i 50)达 n 个乘车点中距离各自最近的乘车点的最短路程S(n)各小区到达n 个乘车点中距离各自最近的乘车点的最短路程之和D (n) 各小区到达n 个乘车点中距离最短的距离与该小区人数乘积的路程之和N(i )表示在小区P( i ) (1 i 50)内的总人数3. 模型建立和求解3.1 第一题的模型建立和求解当选取 n 个乘车点时,共有C50n种选择情况,对于每一种情况均可得出以下两个矩阵(其中的 M(1) M(2) M(3) M(4) M(50) 可能为同一个乘车点)
13、所以又 S(n)=M(1)+M(2)M+(3)+M(4)+ +M(50) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 13 页 - - - - - - - - - 8 针对 C50n种情况分别求出 S(n) 则目标函数 minS(n) 就是所求的最短路程,它所对应的 Q(j) 就是对应的 n 个作为站点的小区, 这样就可以解出所对应的小区。当n=2时就有 C502种选法, 用 matlab 对每一种情况进行运算, 可以得到 minS(2)时所对应的两个站点。当n=3时
14、就有 C503种选法, 用 matlab 对每一种情况进行运算, 可以得到 minS(3)时所对应的三个站点。 (运算程序详见附录二)当 3n50 时和上述相同计算就可以得出对应的n 各站点。任意两个小区的最短距离可以利用floyd算法(floyd算法简介见附录一)进行计算,下面列出1-10 小区之间的最短距离1-10 小区任意两区之间的最短距离区号1 2 3 4 5 6 7 8 9 10 1 0 400 450 700 910 1140 1110 1280 1480 1614 2 400 0 850 300 510 740 710 880 1080 1214 3 450 850 0 810
15、600 830 800 970 1170 1350 4 700 300 600 0 210 440 410 580 780 960 5 910 510 810 210 0 230 200 370 570 750 6 1140 740 1040 440 230 0 320 340 540 720 7 1110 710 1010 410 200 320 0 170 370 550 8 1280 880 1180 580 370 340 170 0 200 380 9 1480 1080 1380 780 570 540 370 200 0 180 10 1614 1214 1560 960 750
16、 720 550 380 180 0 当 n=2时,可以求出当乘车点建在18号小区和 31号小区时, 各小区人员到最近乘车点的距离最小,最短路程和为24338m 。当 n=3时,可以求出当乘车点建在15 号小区、 21号小和 31号小区时,各小区人员到最近乘车点的距离最小, ,最短路程 19660m 。3.2 第二题的模型建立和求解与第一题模型及求解的不同之处为将S(n) 替换为 D(n) D(n)=M(1)*N(1)+M(2)*N(2)+M(3)*N(3)+M(50)*N(50) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
17、 名师精心整理 - - - - - - - 第 8 页,共 13 页 - - - - - - - - - 9 针对 C50n种情况分别求出 D(n) 则目标函数 minD(n)就是所求的最短路程,它所对应的 Q(j) 就是对应的 n 个作为站点的小区, 这样就可以解出所对应的小区。当 n=2时,可以求出当乘车点建在24号小区和 32号小区时, 各小区人员到最近乘车点的距离最小。当 n=3时,可以求出当乘车点建在16 号小区、 23号小和 32号小区时,各小区人员到最近乘车点的距离最小。3.3 第三题的模型建立和求解为简化计算,按照第二题计算出的结论,应该在16 号小区、 23 号小和 32号小
18、区建立乘车点,则各个乘车点所需承担的乘客量可以算出,如下表格去 16 号小区坐车的点及其人数小区3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 25 26 27 28 合计人数42 34 38 29 17 64 39 20 61 47 66 21 70 85 12 35 48 76 16 94 18 932 去 23 号小区坐车的点及其人数小区1 2 20 21 22 23 24 43 44 45 46 47 48 49 合计人数65 67 54 49 12 54 46 69 67 20 18 68 72 76 737 去 32 号小区坐车的点及其人数小
19、区29 30 31 32 33 34 35 36 37 38 39 40 41 42 50 合计人数29 75 10 86 70 56 65 26 80 90 47 40 57 40 62 833 则所需车辆及对应站点为16 号小区23 号小区32 号小区所需车辆数20 16 18 3.4 第四题的模型建立和求解为解决教师和工作人员都希望随到随走,而运营商又希望每一辆车都有尽可能多的上座率, 由此来降低运营成本的矛盾,应该统计相应时间段乘车人数,从而在不同的时间段派出不同的车次进行运营,由于缺乏相关数据, 只做出大概方案:在早上 7:008:00、中午 12:0013:00、下午 14:00
20、15:00、下午 17:0018:00 以及晚上 21:0022:00 应集中 80% 甚至更高的运营车辆进行运营, 其他时间则均衡个发车时间的时间差发车。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 13 页 - - - - - - - - - 10 通过对第三题的解答可知, 每个站点都存在空座的情况, 所以我们建议在站点校车空座率较高的情况下时,在其他站点进行一次巡游。当校车型号单一时,很容易造成某些站点乘客难以乘车而其他某些站点又大量空座的情况,这种方案最大限度的
21、节省了成本,相当于所有乘客集中乘车。其他方案按照学校具体情况考虑。4. 结果的分析检验和改进方法1. 检验:对个小区乘客做满意度问卷调查,从而获得教师和工作人员的意见反馈,并由此得出所计算结果是否正确。2. 优点:模型结构简单,而且便于计算,模型的计算采用专业的数学软件,可信度较高,当数据量很大时,此优势更加突出。3. 缺点:模型的影响因素过于单一化,使得结果与实际情况有些误差。比如存在车载量未满开走或车辆等候教师及工作人员而停滞的现象。未考虑到天气(阴雨天)、时间(节假日)及每个人的具体情况。例外模型缺少实际调查的统计数据,缺乏说服力。4. 改进方法:应当在各个站点做统计并由此得出结论。5.
22、 参考文献1 姜启源 谢金星等,数学模型(第三版),高等教育出版社,2010。2 林旭梅 , 葛广英, MATLAB 实用教程,石油大学出版社,2010。3 同济大学应用数学系, 工程数学线性代数 ,高等教育出版社, 2008。4 未知,有关校车安排问题的数学建模,百度文库,2011。6. 附录附录一 Floyd 算法简介Floyd 算法是弗洛伊德( floyd )提出的一种解决每对节点之间最短路径问题的的算法。算法的基本思想: 直接在图的带权邻接矩阵中, 用插入顶点的方法依次构造出 v 个矩阵 D(1) 、D(2) 、D(v), 使最后得到的矩阵 D(v) 为图的距离矩阵,同时也求出插入点矩
23、阵以便得到两点间的最短路径。1. 在邻接矩阵 G中ijG表示第 i 个区域到第 j 个区域之间的距离;2. 用矩阵 R来记录插入点的信息,其中ijR表示第 i 个区域到达第j 个区域所要经过点的记录,把各个区域插入图中, 比较插入区域后的距离与原来的距离,m in(,)ijijikkjGGGG,如果ijG的距离变小, 则ijR=k,并把最短距离记录在矩阵D中。算法完成后则R中包含了最短通路的信息,ijD中包含了最短路径的信息。关于本文具体问题的算法(算法程序见程序1)如下:名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心
24、整理 - - - - - - - 第 10 页,共 13 页 - - - - - - - - - 11 1. 先根据题目所给的各个连通区域之间距离的数据为初始矩阵L(ij)赋值,其中没有给出距离的赋给无穷大,其中L(i,j)=0(i=j)。2. 进行迭代计算。对任意两点(ij),若存在k,使, L(ik)+L(kj)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end end end a; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -
25、 - - 第 11 页,共 13 页 - - - - - - - - - 12 附录三 问题一的解答程序sl=inf; for b=1:n for c=1:n for d=1:n if a(b,d)L sl=L;p1=b;p2=c; end end end sl,p1,p2 for i=1:n if a(i,p1)=a(i,p2) qulu(1,i)=p1; else qulu(1,i)=p2; end end qulu 附录四 问题二的解答程序sl=inf; s=a*n;n=zeros(i);i=50; n(1)=65;n(2)=67; n(3)=42;n(4)=34;n(5)=38; n(
26、6)=29;n(7)=17;n(8)=64;n(9)=39; n(10)=20;n(11)=61;n(12)=47;n(13)=33; n(14)=21;n(15)=70;n(16)=85;n(17)=12;n(18)=35; n(19)=48;n(20)=54;n(21)=49;n(22)=12; n(23)=54;n(24)=46;n(25)=76; n(26)=16;n(27)=94;n(28)=18;n(29)=29; n(30)=75;n(31)=10;n(32)=86; n(33)=70;n(34)=56;n(35)=65;n(36)=26; n(37)=80;n(38)=90;n
27、(39)=47;n(40)=40; n(41)=57;n(42)=40;n(43)=69; n(44)=67;n(45)=20;n(46)=18;n(47)=68;n(48)=72; n(49)=76;n(50)=62; for b=1:n for c=1:n for d=1:n 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页,共 13 页 - - - - - - - - - 13 if s(b,d)L sl=L;p1=b;p2=c; end end end sl,p1,p2 for i=1:n if s(i,p1)=s(i,p2) qulu(1,i)=p1; else qulu(1,i)=p2; end end qulu 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页,共 13 页 - - - - - - - - -