校车安排问题的数学模型

1、目录11121.12222.122.222.322.423243545.145.1.145.1.245.2n55.2.155.2.255.3n65.3.165.3.265.4375.4.175.4.285.586979910蚂蚁文库校车安排问题摘要：本文针对高校新校区校车运行的安排问题，通过合理的抽象假设， 把校车安排问题抽象成由点线构成的网络模型，将问题转化为n- 重心问题的求解。在问题解决过程中使用了佛洛依德算法，分析、建模、求解过程中利用 MATLAB、 Excel 对数据进行分析处理，并用 C语言实现某些算法，最终得出结论。1.仅考虑距离因素时：设立两个乘车点时，乘车点应设在区域18

2、和区域 31；设立三个乘车点时，乘车点应设在区域15、区域 21 和区域 31。2. 综合考虑距离及教师总体满意度时：设立两个乘车点时，乘车点应设在区域19 和区域 32；设立三个乘车点时，乘车点应设在区域15、区域 21 和区域 32。3. 为使教师及工作人员尽量满意，至少需要安排 54 辆校车：其中区域 15 安排校车 17 辆；其中区域 21 安排校车 18 辆；其中区域 32 安排校车 19 辆。4. 通过对问题的求解可知当乘车点适当增加时， 教师及工作人员的满意度上升，可在学校条件允许的情况下在合适位置适当增加乘车点。关键词： 弗洛伊德算法；总体满意度； n- 重心问题。1蚂蚁文库1

3、、问题重述1.1 问题背景许多学校都建有新校区， 常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多， 往往需要安排许多车辆。 如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。（ 1）、建立 n 个乘车点，使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪 n 个点。（2）、考虑每个区的乘车人数， 为使教师和工作人员满意度最大， 该将校车乘车点应建立在哪 n 个点。（3）、建立 3 个乘车点，为使教师和工作人员尽量满意， 至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47 人。2、问题分析2.1 研究意义许多学校

4、都建有新校区， 常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多， 往往需要安排许多车辆。 如何有效的安排车辆及让教师和工作人员尽量满意。2.2 研究现状许多学校都建有新校区， 常常需要将老校区的教师和工作人员用校车送到新校区。2.3 存在问题如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。 由于受到车辆数目的限制， 即车辆花费的限制。 还有乘车点的限制。 我们只能在现有的条件下合理的安排乘车点和乘车数目使教师和工作人员尽量满意。2.4 解决方法老校区的 50 个区域的大小、 形状与问题的求解无关， 可将 50 个区域抽象为50 个点，区域

5、间的连接道路抽象为点的连线，据此建立网络模型，用佛洛依德算法求出任意两点间最短路径的距离，将问题的求解转化为 n- 重心问题，由模型逐步求解得到乘车点的位置。3、模型假设（1）假设老校区的教师和工作人员分布在50 个区，各区的距离见附录A。各区人员分布见附录B。2蚂蚁文库校区人数分布图1009080706050403020100123456 789 101112 1314 15161718 1920 2122 232425 262728 29 3031 3233 3435 3637 3839 40 414243 44 4546 474849 50（2）50 个区域抽象成 50 个点，附录 1

6、中标注距离的点间可以直接相通，未标注距离的点间无法直接相通，需通过其它点间接到达。（3）假设任一教师和工作人员的满意程度随距离的增加递减（4）乘车点只设在点上。（5）校车只在起始站点载人。4、符号约定A：点间距离的邻接矩阵；B：各点的最短距离矩阵dij :i点到 j 点的最短距离；dkij :i 到 j 的只以 (1.k)集合中的节点为中间结点的最短路径的距离；D a1 ,a2 , , an : 各个点到乘车点的总距离；D min : 最短总距离；: 乘客个体满意度；d : 某点到乘车点所走距离；D : 所有点中到乘车点的最大距离；F : 所有乘客的总体满意度；3蚂蚁文库Los ：重新安排乘车

7、点的人员安重排前所走的路程；m : 某区域的教师人数；M : 教师及工作人员总人数；E :距乘车点的平均路程 .5、模型建立与求解5.1 计算各点间的最短路程5.1.1数据分析首先对题目所给的各区距离做统计分析， 用 Excel 表格建立对应各点距离的邻接矩阵 A，即Aa11a12a150a21a250a501a502a5050.其中 aij 为点 i 到点 j 的距离。当 aij =，表示 i 点和 j 点不直接相通。5.1.2模型建立与计算用弗洛伊德算法计算任意两点间的最短距离。弗洛伊德算法的原理是动态规划， 设 d ijk为从 i 到 j 的只以 (1.k)集合中的节点为中间结点的最短路

8、径的长度,若最短路径经过点k，则：dkijdkik- 1dkkj-1若最短路径不经过点k，则：dkijdkij -1因此，有：dijkmin dkij -1， d kik-1d kkj-1弗洛伊德算法的 C 语言实现见附录 E。把邻接矩阵 A 作为弗洛伊德算法的输入矩阵，程序输出各点间最短距离矩阵 B（结果见附录 C）及取最短距离时各点间的走法（结果见附录 D）。4蚂蚁文库5.2 建立 n 个乘车点使各区人员到最近乘车点的距离最小的一般模型5.2.1模型建立dij 为网络中 i 点到 j 点最短路径的权，表示i ， j 两点的最短距离；ni 为网络中 i 点的权，表示 i 点的人数， 因为不考

9、虑人数对乘车点的影响，固取 ni1 ， i,j（1，50）。问题的模型为特殊情况（ni1 ）的 n- 重心模型：5050min fni dijdiji1i15.2.2模型求解任取 n 个互异点 a1 , a2 , an 为乘车点，则从各点到乘车点的总路程为：50Da1 ,a2 , ,anmi n dia 1 , dia 2 , dia ni 1则取50 个点的组合 C50n 做 a1 , a2 , , a n ，分别计算 Da1 ,a2 , ,an ，取使得Da1 ,a2 , ,an 取最小值的 a1 , a2 , , an 点即为所求乘车点。即：Dminmin Da1, a2 , ,a na

10、1 , a2 ,，, an 1250a1 , a2 , an 互异 .取 n=2，3，计算结果，算法的C 语言实现见附录 E。程序计算得：n=2 时，求得乘车点应设在区域18 和区域 31；n=3 时，求得乘车点应设在区域15、区域 21 和区域 31。5蚂蚁文库5.3 考虑每个区的乘车人数建立 n 个乘车点使各区人员到最近乘车点的距离最小的一般模型5.3.1模型建立dij 为网络中 i 点到 j 点最短路径的权，表示 i ， j 两点的最短距离； ni 为网络中 i 点的权，表示 i 点的人数， i ，j （ 1， 50）。问题的模型为 n- 重心模型：50min fni d iji1假设任

11、一教师和工作人员的满意程度随距离的增加递减，即去乘车点的距离越大越不满意，则当所有人走的总距离最短时整体的满意度最大。定义为乘客个体满意度 , 有：1d , 01D其中 d 为某点到乘车点所走距离，D 为任意两点最短距离的最大值。定义 F 为所有乘客的总体满意度，有：F1mdMD其中 m为某点的人数， M为所有教师人数。定义 E 为教师及工作人员至乘车点的平均路程，即：mdEM5.3.2模型求解任取 n 个点 a1 , a2 , a n 为乘车点，所有人到乘车点的总路程为：50Da1 ,a2 , ,anmin nid ia1 , ni dia 2 , nidiani 1则取50 个点的组合C5

12、0n做 a1 , a2 , an ，分别计算Da1, a2 , , an ，取使得Da1 ,a2 , ,an 取最小值的 a1 , a2 , an 点即为所求乘车点。即：Dminmin Da1 , a2 , ,an6蚂蚁文库a1 , a 2 ,，, an 1 250a1 , a 2 , an 互异 .取 n=2，3，计算结果，算法的 C 语言实现见附录 E。程序计算得：n=2 时，求得乘车点应设在区域19 和区域 32，总体满意度 F=77.94%；距乘车点的平均路程 E497。n=3时，求得乘车点应设在区域15、区域 21 和区域 32，总体满意度 F=82.70%；距乘车点的平均路程 E3

13、90。5.4建立 3 个乘车点的车辆安排5.4.1建立模型此问题为 n- 重心问题的进一步引申， 以车辆数和总体满意度为双目标函数；任取 3 个点 a1 , a2 , a 3 为乘车点，所有人到乘车点的总路程为：50Da1 ,a 2 ,a 3min ni dia 1 , ni dia 2 , ni dia 3i1分别找出此时到 ai 点距离最近的 k i 个点，计算这 k i 个点的总人数 S i 。（ i=1 ，2，3）则取 50 个点的组合 C350 做 a1 , a2 , a3 ，分别计算 Da1 ,a2 , a3 ，取使得 Da1 ,a2 ,a3 取最小值的 a1 , a2 , a3

14、点即为所求乘车点。即：D min 'min Da1 ,a2 ,a3对S i取余得到车载满后的剩余人员数Mod i，即：Mod isi mod 47重新安排乘车点的人员安重排前所走的路程为：3Los min ( Mod i Diaj )j 11i 50j1,2,37蚂蚁文库重安排乘车点的人员所走的最短路径Dmin 为：Dminmin (Mod a j 1 Mod a j 2 )D ia j 31 i 50j1, j 2, j 31，2，3 且j 1, j 2, j 3互异 .重新安排后所走总路径的最小值为:DminDmin ' DminLosa1 , a2 , a，3 1250a

15、1 , a 2 , a3互异 .以上算法最终通过C 语言程序实现。5.4.2模型求解将最短距离矩阵B 作为输入数据送入程序，计算得到结果：乘车点应设在区域15， 21，32；其中：15 区应安排 17 辆车，到 15 区乘车的的区域有： 5，6，7，8，9，10， 11，12，13，14， 15，16，17，18，25， 26，27；21 区应安排 18 辆车，到 21 区乘车的的区域有： 1，2，3，4，19，20，21， 22，23，24， 28，44，45，46，47， 48，49；32 区应安排 19 辆车，到 32 区乘车的的区域有： 29， 32，31，32，33，34，35，36

16、，37， 38，39，40，41，42， 43，50.总体满意度 F=82.48%。总体满意度较4.3 中的 82.70%略有下降。5.5建议定义 为成本增加率，有：kk其中 k 为总车辆数，k 增加的车辆数。计算得由 4.3 和 4.3 的用车数据算得 1.89 % ，即提高 0.22%的满意度增加了 1.89%的成本，不划算。由 4.3 ，4.4 及以上的结论可知适当增加乘车点数能增加教师和工作人员的总体满意度。 而减少校车数量与增加总体满意度相矛盾。 因此，在校车安排时应综合考虑教师的满意度和增加校车与乘车点的成本问题， 在条件允许的范围内尽量增加乘车点以提高总体满意度。8蚂蚁文库6、模

17、型的分析与评价本文就高校校车运行问题建立网络模型，进而转化为网络最短路径问题的求解及 n- 重心问题的求解，具有一定的科学性。但因某些实际因素（如满意度等）不能直接运用求解， 而作了一定的理想化假设， 所得结果与实际问题会存在一定偏差，需要通过与实际情况的比较进一步修正模型。7、模型的推广由模型的求解结果可以看出适当增加乘车点数能降低平均步行距离、增加教师和工作人员的总体满意度。 而减少校车数量与增加总体满意度相矛盾。 因此，在校车安排时应综合考虑教师的满意度和增加校车与乘车点的成本问题， 在条件允许的范围内尽量提高总体满意度。参考文献：1 数学模型编写组 . 数学模型 . 广州：华南理工大学

18、出版社， 2003 .2 湖北省大学生数学建模竞赛专组 : 数学建模 （本科册） . 华中科技大学出版社， 2006.3 王树禾 . 图论 . .科学出版社 . 2005.4 唐坤 . 车辆路径问题中的遗传算法设计. 华东大学学报， 2002.5 宁正元 ,王秀丽 . 算法与数据结构 . 清华大学出版社， 2006 年 1 月，第 1 版 .9蚂蚁文库附录 A： 各区距离表区域号区域号距离 (m)区域号区域号距离 (m)区域号区域号距离 (m)1240015172502931190134501617140303124024300161813030421302212301727240304321

19、024714018192043132230346001825180313626045210192014031502104193101924175323319056230202118032351405720020241903236240673202122300333421068340212327035371607817021473503639180718160224416036401908920022452703738135815285224818038391309101802324240394131010111502329210404114010151602330290405019011121

20、40234415042502001114130242517043442601213200242813043452101334400262714045462401415190263432046482801426190272819048492001516170282926010蚂蚁文库附录 B：各区人员分布区域人数区域人数16526162672794342281843429295383075629311071732868643370939345610203565116136261247378013663890142139471570404016854157171242401835436919484

21、467205445202149461822124768235448722446497625765062附录 C：用存储的点间最短距离矩阵备注：（x，y）处的值为 x 区域到 y 区域的最短距离11蚂蚁文库附录 D：各点间取最短距离的走法（因篇幅有限仅列出以1 点为出发点的路径）目的地最短路径2 1->23 1->34 1->2->45 1->2->4->56 1->2->4->5->67 1->2->4->5->78 1->2->4->5->7->89 1->2->

22、;4->5->7->8->910 1->2->21->20->19->18->16->15->1011 1->2->21->20->19->18->16->15->10->1112 1->2->21->20->19->18->16->15->10->11->1213 1->2->21->20->19->18->16->15->10->11->12-&g

23、t;1314 1->2->21->20->19->18->16->15->1415 1->2->21->20->19->18->16->1516 1->2->21->20->19->18->1617 1->2->21->20->19->18->16->1718 1->2->21->20->19->1819 1->2->21->20->1920 1->2->21-&

24、gt;2021 1->2->2122 1->2->21->2223 1->2->21->2324 1->2->21->20->2425 1->2->21->20->24->2526 1->2->21->20->24->28->27->2627 1->2->21->20->24->28->2728 1->2->21->20->24->2829 1->2->21->23-&

25、gt;2930 1->2->21->23->3031 1->2->21->23->29->3132 1->2->21->23->29->31->3233 1->2->21->23->29->31->32->3334 1->2->21->20->24->28->27->26->3435 1->2->21->23->29->31->32->3536 1->2->21-

26、>23->29->31->3637 1->2->21->23->29->31->32->35->3738 1->2->21->23->29->31->36->39->3839 1->2->21->23->29->31->36->3940 1->2->21->23->29->31->36->4041 1->2->21->23->29->31->36->4

27、0->4112蚂蚁文库42 1->2->21->23->30->4243 1->2->21->23->44->4344 1->2->21->23->4445 1->2->21->22->4546 1->2->21->22->48->4647 1->2->4748 1->2->21->22->4849 1->2->21->22->48->4950 1->2->21->23->29->31->50附录 E：部分程序代码/弗洛伊德算法/for (p=1;p<=Vertex;p+)for (q=1;q<=Vertex;q+)fin >> Mappq;/* 输入邻接矩阵至Mappq*/Distpq=Mappq;for (k=1;k<=Vertex;k+)