校车安排问题、杜廷宇

1、校车安排问题摘要问题一，运用题目给出的各区距离，建立了邻接矩阵，用了 floyd 算法求任意两点的最短路径，确定了最短距离矩阵。根据距离矩阵，以各区域到最近乘车点的距离之和为最小目标，筛选出乘车点 n=2 时，选择乘车点在 18 和 31，归属区到乘车点的距离l总为 24492。n=3 时，选择的乘车点在 15,21,31，归属区到乘车点的距离l总为 19660。问题二，结合问题一中的距离矩阵，建立了与距离有关的满意度函数模型。根据每个区乘客的满意度不同，每个区的人数也不同，建立了平均满意度函数 模型。当n = 2 时，选择的 2 个乘车点为区域 24 和区域 32，平均满意度为0.7239。

2、当n = 3 时，选择的三个乘车点为区域 16、区域 23 和区域 32。平均满 意度为 0.7811。问题三，首先根据题目给出的各区人数，求出了最少需要 54 辆。求得满意度最大的情况下的 3 个乘车点车辆使用情况，将其与最少需要车辆进行比较， 得出三个站点所在的区域分别为 2、16、31，对应的车辆数分别为12、19、23。问题四，结合前三问的求解，考虑到了教职工每天上班时间，教职工乘车人数，等车时间，车辆型号大小等方面，根据实际情况给出了建议与考虑。关键字：校车安排 乘车点 距离矩阵 满意度一、问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校

3、区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。现有如下问题请你设计解决。假设老校区的教师和工作人员分布在 50 个区。各区的距离见表 1。各区人员分布见表 2。问题 1：如要建立n 个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪n 个点。建立一般模型，并给出n = 2, 3时的结果。问题 2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪n 个点。建立一般模型，并给出n = 2, 3时的结果。(假定车只在起始点载人)问题 3若建立 3 个乘车点，为使教师和工作人员尽量满意，至

4、少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客 47 人。问题 4；关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。各区的距离见附录表 1，各区人员分布见附录表 2。二、符号说明w：邻接矩阵Dv ： v 区域到v区域构成的距离矩阵ijijlij ：i 区到 j 区的距离Hi ：第 i 区乘客的满意度H ：总体乘客满意度的平均值lmax ：第 i 个区离本区最远区的距离lmin ：第 i 个区离本区最近区的距离Cn ：第 n 个乘车站点的车辆数mi ：第 i 个区的乘车人数三、问题假设1、假设教职工在去往乘车点途中不会发生意外2、假设校

5、车准时到达乘车点3、假设每辆校车的行驶速度是一定的4、假设校车不能重复经过各区5、乘车点只能建立在各区上，不能在区与区之间6、教职工的满意度与等车时间没有直接联系四、问题分析针对问题一，没有给出各个区的方位，是一个无向路线的问题。使各区人员到最近乘车点的距离最小，可以用 Floyd 算法先计算出各区之间的最短路径。在选择合适乘车点的问题上，用筛选矩阵的方法，每个区之间距离都要进行比较。进行多次循环找出各区到最近距离的乘车站点。针对问题二，教师与工作人员的最大满意度与等车时间没有直接关系，只与距离有关，乘车距离越近，教职工的满意度越高，所以要建立与距离有关的满 意度函数。在问题一的基础上，选择出

6、最高满意度的乘车点。建立平均满意度， 得到各区对乘车点的平均满意度。50针对问题三，根据题目可以算出最少的乘车辆，要设立三个乘车点有C3 种可能，利用问题二的模型计算出每种可能性的教职工人员满意度、总车辆数。然后让其与最小车辆数进行比较，筛选出较合适的车辆数，再结合教职工满意度，确定乘车点。针对问题四，可以在教职工每天上班时间，教职工乘车人数，等车时间，车辆型号大小等方面进行建议，提高效率，提高满意度。五、模型的建立与求解5.1、问题一的模型建立于求解5.1.1 、Floyd 的距离矩阵算法原理1ij 5050Floyd 算法：求任意两点之间的最短路径。首先根据题目给出的各区距离表，构造带权邻

7、接矩阵 w，作为距离矩阵的初值即 D0 = (d 0 ) = w 。带权邻接矩阵中的元素是由权构成的，此题中，权表示的到各区距离，每一行即表示vi 分别到v1,v2, ,vv 的距离，若没有该区到下一个区直接路径，将该权值可视为无穷值。距离矩阵可以理解为D = (d )vvijij vv，其中dv = min d v-1, d v-1 + d v-1ijijivvjd v 是表示v 到v 的只允许以v vv作为中间点的路径中最短路的长度。即是ijij1, 2,., vvij从vi 到vj 中间可插入任何顶点的路径中最短路的长度，因此， D 即是距离矩阵。ijij经过 matlab 的计算（程序

8、一）可得 D50 = (d 50 )5050的距离矩阵如图表 1（只列出了 1-15 个地区的距离矩阵）表 11-15 个地区的距离地区1234567891011121314151040045070091011401110128014801614176419042104164414542400085030051074071088010801214136415041704124410543450850060081010401010118013801560171018502050160414144700300600021044041058078096011101250145010048145910

9、510810210023020037057075090010401240845655611407401040440230032034054072087010101210815625711107101010410200320017037055070084010406454558128088011805803703401700200380530670870475285914801080138078057054037020001803304706704603401016141214156096075072055038018001502904902801601117641364171011109008

10、707005303301500140340130310121904150418501250104010108406704702901400200270450132104170420501450124012101040870670490340200047065014164412441604100484581564547546028013027047001901514541054141481465562545528534016031045065019005.1.2 、选取合适的乘车点1) 要建立 2 个乘车点，为使各区人员到最近乘车点的距离最小，根据距离矩阵，即每两个点都要进行比较，选取距离较小的

11、那个乘车点与下一站进行比较，依次循环，得出距离最短的两个点，经过 matlab 编程可得出（程序二）选择乘车站点在 18 和 31设lij 是 i 区到 j 区的距离，若li18 li31 ，则该地区 i 应在 18 号乘车点，否则，该地区 i 应该在 31 号乘车点即18 号乘车点的区有1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、24、25、26、27、47 31 号乘车点的区有22、23、28、29、30、31、32、33、34、35、36、37、38、39、40、41、42、43、44、45、46、48、49、50归属区域到

12、 18，31 乘车点的距离l总：244922)要建立 3 个乘车点，原理与建立 2 个乘车点的原理相似，在建立 2 个乘车点的循环下，再次循环，筛选出第三个乘车点。经计算、筛选得出乘车点在 152131若li15 li 21 &li31 ，则该地区 i 应在 15 号乘车点若li 21 li15 &li31 ，则该地区 i 应在 21 号乘车点若li31 a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j); path(i,j)=k;end a;endendendren=65 67 42 34 38 29 17 64 39 20 61 47 66 21 70 85 12 35 4

13、8 54 49 12 54 46 76 1694 18 29 75 10 86 70 56 65 26 80 90 47 40 57 40 69 67 20 18 68 72 76 62;程序二1、确定两站点： sl=inf;for b=1:nfor c=1:nfor d=1:nif a(b,d)Lsl=L;p1=b;p2=c;endendendsl,p1,p2 for i=1:nif a(i,p1)Lsl=L;p1=b;p2=c;p3=d;endend endendsl,p1,p2,p3 for i=1:nif a(i,p1)=a(i,p2)&a(i,p1)=a(i,p3) qulu(1,i

14、)=p1;end quluelseif a(i,p2)=a(i,p1)&a(i,p2)a(i,p3) qulu(1,i)=p2;else qulu(1,i)=p3; end程序三1、两站点q=sum(ren); sl=0; A=max(a);for c=1:nfor d=1:nfor e=1:nmm=a(c,e),a(d,e); l(e)=min(mm);lren(e)=(A(e)-l(e)/A(e)*ren(e); endL=sum(lren); if slLsl=L;p1=c;p2=d;endendendmanyidu=sl/q,p1,p2 for i=1:nif a(i,p1)=a(i,

15、p2) qulu(1,i)=p1;else qulu(1,i)=p2;end end qulu2、三站点q=sum(ren); sl=0; A=max(a); for b=1:nfor c=1:nfor d=1:nfor e=1:nmm=a(b,e),a(c,e),a(d,e); l(e)=min(mm);lren(e)=(A(e)-l(e)/A(e)*ren(e); endL=sum(lren); if slLsl=L;p1=b;p2=c;p3=d;endend endendmanyidu=sl/q,p1,p2,p3 for i=1:nif a(i,p1)=a(i,p2)&a(i,p1)=a

16、(i,p3) qulu(1,i)=p1;end quluelseif a(i,p2)=a(i,p1)&a(i,p2)a(i,p3) qulu(1,i)=p2;else qulu(1,i)=p3; end程序四q=sum(ren); sl=0; A=max(a); for b=1:nfor c=1:nfor d=1:nfor e=1:nmm=a(b,e),a(c,e),a(d,e); l(e)=min(mm);lren(e)=(A(e)-l(e)/A(e)*ren(e);end L=sum(lren); if slLsl=L;p1=b,p2=c,p3=d,manyidu=sl/q,for i=1:nif a(i,p1)=a(i,p2)&a(i,p1)=a(i,p3) qulu(1,i)=p1;elseif a(i,p2)=a(i,p1)&a(i,p2)a(i,p3) qulu(1,i)=p2;else qulu(1,i)=p3; endend p1renshu=0;p2renshu=0;p3renshu=0