数学建模解决乘车点安排问题.doc

摘要本文就目前大学各区域与新校区之间校车乘车点的安排及教师和工作人员的满意程度展开研究，通过合理的抽象和假设，将乘车点的安排问题转化为无向图的多源最短距离的搜索问题，并通过一定的实地调查，将教师员工的满意度问题与校车运营成本结合起来，并在计算过程中运用exel,matlab等一系列计算机软件，得到了一些较为实际和精确的结果。1、 问题一：不考虑各点的人数，仅考虑各点到乘车点的总距离最短。当乘车点n=3时，选择的乘车点是15,21,31三个点，最短总距离为19660；当乘车点n=4时，选择的乘车点是11,18,22,32四个点，最短总距离为16961；2、 问题二：考虑到各点的人数，使将人数计算在内的总体距离最短（此时认为总体距离最短就是最满意）当乘车点n=3时，选择的乘车点是16,23,32三个点，满意度为0.7811；当乘车点n=4时，选择的乘车点是2,15,23,32四个点，满意度为0.8170；3. 问题三：为使教员和工作人员达到相对满意的的程度，又要求车辆最少，综合考虑到总体满意度和个体最小满意度。得到三个点为x,x,x;安排车辆数为y.4. 问题四：经过一定的实际情况调查，考虑到车辆运行成本和车辆满座率，乘车时间等实际问题，量化给出较为优化的解决方案。关键词：搜索算法，最短距离矩阵，总体满意度，个人满意度，实际方案。1、问题重述：某学校建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。现有如下问题请你设计解决。假设老校区的教师和工作人员分布在50个区，各区的距离见表1。各区人员分布见表2。问题1：如要建立n个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪 个点。建立一般模型，并给出n=3,4时的结果。 问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪n个点。建立一般模型，并给出n=3,4时的结果。 问题3 若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客45人（假定车只在起始站点载人）。问题4；关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。2、 问题分析2.1研究意义 就我校而言，就建有理学院新校区，各专业学院及教员小区与新校区之间就要靠校车解决。同时学校车辆有限，考虑到交通状况也不可能每个点都有车辆到达，如何安排车辆和乘车点使教员和工作人员满意，同时又能节约成本使资源得到最大的运用就是一个十分实际而有意义的问题。2.2研究现状 目前大多数校车乘车点和车辆安排都是在经验下做出的，没有做到量化处理，使方案达到最优化。2.3存在问题满意度的具体定义，乘车点和车辆怎样安排才能使教员和工作人员达到相对满意的程度，同时怎样在保证相对满意的条件下使车辆的运营成本最小，就牵扯到运营成本的具体量化，最后提出一套量化解决方案。2.4解决方法首先这50个区域可以简化成由50个点组成的无向图，题设中给出的点点之间的距离就是无向图中的边的权值，题目一可简化为无向图中其他点到选出点的最短距离问题，可以用floyd算法算出所有点之间的最短距离，再用穷举比较的方法计算各点到选出点的最短距离和的最小值。问题二可建立关于人数的满意度函数，在问题一的基础上算出最大满意度的方案。问题三则要考虑到校车的运营成本问题，综合总体满意度和个人满意度，给出一个教员相对满意且用车最少的方案，问题四则要结合一些实际问题考虑，如人的高峰时间、校车的满座率、校车的运行线路后才能给出一个较为实际和完备的方案。3. 模型假设(1) 未给出距离的两个区可以由其他区间接到达。(2) 乘车点只设在某几个区域内不能选择50个点以外的点作为乘车点。(3) 所有的教员都乘车，且都会去离自己最近的乘车点乘车。(4) 教员的满意度与离乘车点的距离有关，距离越远满意度越低，距离越近满意度越高。(5) 作为乘车点的区域的人到乘车点的距离为0。(6) 乘车点的选取数目不超过50。4. 符号约定p:区域个数。n:乘车点的个数.X:题设给出的个点之间的稀疏矩阵。Z:个点之间的最短距离矩阵。：题设给出的i,j点原始距离。：i,j两个点之间通过这五十个区域中的节点相连得到的最短距离：i,j点之间的最短距离。:五十个点到选出的乘车点的距离之和。:第i个点的人数。：第i个点距乘车点的最短距离。：第i个点距离他最远点的距离。M:教员的总体满意度。：第i个区的区域满意度。5. 模型的建立和求解5.1最短距离矩阵的计算floyd算法对有权无向图 来说计算点与点之间的最短距离的方法有基于动态规划的floyd算法和dijkstra算法，其中的floyd算法具有速度快，且能方便记录路径的特点，所以我们选用floyd算法。(1)在稀疏矩阵G中表示第i个区域到第j个区域之间的距离；(2)用矩阵R来记录插入点的信息，其中表示第i个区域到达第j个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距离，如果的距离变小，则=k，并把最短距离记录在矩阵D中。算法完成后则R中包含了最短通路的信息，中包含了最短路径的信息。5.1.1数据分析题设已经给出了一定的点之间的距离列表，由matlab求出个点之间距离的稀疏矩阵X.其中没有给出距离的点置为无穷大inf X= 再由floyd算法，进行迭代计算。对任意两点，若存在，使，则更新。3. 直到所有点的距离不再更新停止计算,则得到最短路距离矩阵 （i,j=1,2,.50) Matlab的代码将在附录一中给出，下图是由matlab生成的最 小距离矩阵的示意图，其中颜色越深表示距离越短。 5.2使各区到乘车点的距离最小 5.2.1模型建立为使个区人员到乘车点的距离最小，我们考虑个区人员到乘车点的总距离应该最小。 首先考虑仅设立一个乘车点的情况.设选出的乘车点是p1,则最短总距离则为最短距离矩阵中其他点到选出点的距离之和 在考虑设立两个乘车点的情况。当n=2时，我们就要考虑到一个乘车点的选择问题，第i点到底是选择p1作为乘车点，还是选择p2作为乘车点呢？应该是在这两种方案中选出距离较短的点作为i点的乘车点。 则选取的两个点应使目标函数 最小。下面我们考虑乘车点数为n的情况，当乘车点为n时的情况其实与乘车点为二是的情况没有什么区别，区别在与对乘车点的选择上需要比较更多的情况。 乘车点的选择应使目标函数最小。5.2.2模型求解具体的matlab程序将在附录二中给出由程序计算得当n=3时 选择的乘车点应为15,21,31三个点，最短总距离为19660。且到15乘车点的区域有5,6,7,8,9,10,11,12,13,14,15,16,17,18,25,26,27；到21乘车点的区域有1,2,3,4,19,20,21,22,23,24,44,45,46,47,48,49；到31乘车的区域有28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,50.当n=4时 选择的乘车点应为11,18,22,32四个点，最短总距离为16961。且到11乘车点的区域有9,10,11,12,13,14,26,27；到18乘车点的区域有3,4,5,6,7,8,15,16,17,18,19，20,24,25；到22乘车点的区域有1,2,21,22,23,43,44,45,46,47,48,49；到32乘车点的区域有29,30,31,32,33,34,35,36,37,38,39,40,41,42,50.5.3乘车点的设置使各区人员满意度最大的模型5.3.1模型建立首先靠考虑到在该种情况下满意度的定义是什么，很明显在问题二的情况下啊，乘客满意的情况是到乘车点的距离越短越好，当乘车点就是该点的时候满意度就为最大，如果将满意度定为一的话，那么此时的满意度即为1,；如果乘车点世道该点最远的点时，此时乘客的满意度应为最小，即为0，由此我们可以建立满意度方程： 该方程认为满意度与距离之间是简单的线性关系。由于问题二中每个点都有不同的人数存在，即无向图的每个点都有了一定的权重，我们不可能使每个区域的满意度都达到最大，所以在计算最终的满意程度时要将人数的因素加权进入方程： M即为模型二的目标函数。5.3.2模型求解 相关的matlab程序将在附录三中给出.当n=3时，选择的点为16,23,32.满意度为0.7811.其中选择16为乘车点的区域有3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,25,26,27；选择23为乘车点的区域有1,2,20,21,22,23,24,28,29,30,42,43,44,45,46,47,48,49；选择32为乘车点的区域有13,31,32,33,34,35,36,37,38,39,40,41,50.当n=4时，选择的点为2,15,23,32.满意度为0.8107.其中选择2为乘车点的区域有1,2,3,4,5,20,21,47；选择15为乘车点的8,9,10,11,12,13,14,15,16,17,18,26,27；选择23为乘车点的区域有19,22,23,24,25,28,29,30,41,42,43,44,45,46,48,49；选择32为乘车点的区域有31,32,33,34,35,36，37，38，39，40,41,50.点数越来越多的情况等会考虑。5.4建立三个乘车点时，使教员相对满意且用车最少的模型5.4.1模型建立如果我们以考虑教员的满意程度为主，则乘车点一定与模型二的选择一样，且车辆数也不一定是最少的。所以在该模型中应该建立两个目标函数，一个是教员的满意程度，另一个则是车辆的数量。由于有很大的机会不等于零，对于每个点整数辆的车装不满的人，是再安排一辆车去接这几个人，还是让这几个人自己去不那么近的乘车点降低以下满意度呢？下面就这两种不同的方案建立模型。（1） 剩余人再派车接。在模型二的基础上，设到各个乘车点的总人数为（第k乘车点的人数）则每个乘车点的车辆数为 则总的车辆数为 使ZC最小的乘车点即为所需要的状态。（2） 剩余的人到离自己相对近的乘车点乘车，牺牲一定的满意程度。 任是在模型二的基础上，选择乘车点。每个乘车点仅安排能满载的车辆数，设为，则满足 每个点剩下的人数为： 再考虑这些剩下的人应该怎样办？我们的解决方法是，再运用模型二，不过这次只有这三个乘车点和每个乘车点剩下的人再做一次乘车点优化，使这些人到三个乘车点的某个点的距离最短即使目标函数 最小，其中为二次优化中各乘车点剩下的人的满意度函数。5.4.2模型求解由matlab得出以下结果 车辆数满意度选择乘车点方案1570.781118,23,32方案2560.768216,23,32（23）有结果可以看出，当选择较小的车辆数的时候，满意度会有所降低，选择较大的满意度的时候，车辆数会有所增加。5.5建议和意经过一定的实践考察我们得出教员和工作人员出行的时间如图所示 一般来说教员的出行几种在上午上课，下午上课以及傍晚放学这三个时段，是有高峰的出行，而且有出行集中，不能迟到的特点，由此并结合问题一，二，三提出以下建议：1.在资金和人员允许的情况下适当的增加乘车点的数量，这样可以有效的提高教员的满意度。2.安排一辆或者两辆速度较快的巡游车在各个乘车点和新校区之间巡游及时带走没有赶上车的教员。3.改善教学课表，使教员能够分时段上车，让一部分的车辆能够循环使用，不用一起派出大量的车在较短的时间里将教员送到新校区。4.建议购买不同大小的车，使各个站点的老师正好乘坐，即不留一个老师也不遗漏一个空位。5.对教员提出要求，要求教员在一定的乘车时间内乘车，避免因为某些人迟到而导致的等人，空载的情况。6.某型的分析与评价6.1优点1、本文的基础采用floyd算法，由于有成熟的算法，使得带权邻接矩阵的得出十分流畅，算法效率很高。2、采用分布计算方法，使得乘车点事先确定后的最值求出，再使乘车点的可能性取遍所有可能，较容易用程序循环实现。3、将人的心理满意度函数化，较贴切的反映了人的心理，具有较强的现实性。4、模型建立的合理性，模型的建立是在对给的数据进行充分的挖掘的基础上，通过数据之间的关系提炼出各个区域之间的关系并建立起模型。5、模型的建立是按照问题的解决的思路进行的，分析和发现很有规律，然后对规律进行评价，最后建模。6.2缺点1、 把人的满意度随距离成正比，对模型的求解带来一定的误差2、 程序耗时长，时间复杂度太大。3、 考虑问题的全面性还不够。7模型的推广本例的延伸对于解决各种交通问题，物流问题，计算机网络问题等问题。8. 参考文献【1】高等数学问题的matlab求解【2】数学模型 姜启元 谢金星9. 附录 各点距离分布图区域号区域号距离(m)1240013450243002212302471403460045210419310562305720067320683407817071816089200815285910180101115010151601112140111413012132001334400141519014261901516170151725016171401618130172724018192041825180192014019241752021180202419021223002123270214735022441602245270224818023242402329210233029023441502425170242813026271402634320272819028292602931190303124030421303043210313223031362603150210323319032351403236240333421035371603639180364019037381353839130394131040411404050190425020043442604345210454624046482804849200 各点人员分布区域人数区域人数16526162672794342281843429295383075629311071732868643370939345610203565116136261247378013663890142139471570404016854157171242401835436919484467205445202149461822124768235448722446497625765062附录一 clear;clc;n=50;a=zeros(n);a(1,2)=400;a(1,3)=450;a(2,4)=300;a(2,21)=230;a(2,47)=140;a(3,4)=600;a(4,5)=210;a(4,19)=310;a(5,6)=230;a(5,7)=200;a(6,7)=320;a(6,8)=340;a(7,8)=170;a(7,18)=160;a(8,9)=200;a(8,15)=285;a(9,10)=180;a(10,11)=150;a(10,15)=160;a(11,12)=140;a(11,14)=130;a(12,13)=200;a(13,34)=400;a(14,15)=190;a(14,26)=190;a(15,16)=170;a(15,17)=250;a(16,17)=140;a(16,18)=130;a(17,27)=240;a(18,19)=204;a(18,25)=180;a(19,20)=140;a(19,24)=175;a(20,21)=180;a(20,24)=190;a(21,22)=300;a(21,23)=270;a(21,47)=350;a(22,44)=160;a(22,45)=270;a(22,48)=180;a(23,24)=240;a(23,29)=210;a(23,30)=290;a(23,44)=150;a(24,28)=130;a(24,25)=170;a(26,27)=140;a(26,34)=320;a(27,28)=190;a(28,29)=260;a(29,31)=190;a(30,31)=240;a(30,42)=130;a(30,43)=210;a(31,32)=230;a(31,36)=260;a(31,50)=210;a(32,33)=190;a(32,35)=140;a(32,36)=240;a(35,37)=160;a(36,39)=180;a(36,40)=190;a(37,38)=135;a(38,39)=130;a(39,41)=310;a(40,41)=140;a(40,50)=190;a(42,50)=200;a(43,44)=260;a(43,45)=210;a(33,34)=210;a(45,46)=240;a(46,48)=280;a(48,49)=200;a=a+a;M=max(max(a)*n2;a=a+(a=0)-eye(n)*M;path=zeros(n);for k=1:nfor i=1:nfor j=1:nif a(i,j)a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendenda; q=sum(ren);sl=0;A=max