2023年数学建模解决乘车点安排问题.pdf

《2023年数学建模解决乘车点安排问题.pdf》由会员分享，可在线阅读，更多相关《2023年数学建模解决乘车点安排问题.pdf（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、实用标准 文档大全 摘要 本文就目前大学各区域与新校区之间校车乘车点的安排及教师和工作人员的满意程度展开研究，通过合理的抽象和假设，将乘车点的安排问题转化为无向图的多源最短距离的搜索问题，并通过一定的实地调查，将教师员工的满意度问题与校车运营成本结合起来，并在计算过程中运用 exel,matlab等一系列计算机软件，得到了一些较为实际和精确的结果。1、问题一：不考虑各点的人数，仅考虑各点到乘车点的总距离最短。当乘车点 n=3 时，选择的乘车点是 15,21,31 三个点，最短总距离为 19660；当乘车点 n=4 时，选择的乘车点是 11,18,22,32四个点，最短总距离为 16961；2、

2、问题二：考虑到各点的人数，使将人数计算在的总体距离最短（此时认为总体距离最短就是最满意）当乘车点 n=3 时，选择的乘车点是 16,23,32 三个点，满意度为 0.7811；当乘车点 n=4 时，选择的乘车点是 2,15,23,32四个点，满意度为 0.8170；3.问题三：为使教员和工作人员达到相对满意的的程度，又要求车辆最少，综合考虑到总体满意度和个体最小满意度。得到三个点为x,x,x;安排车辆数为 y.4.问题四：经过一定的实际情况调查，考虑到车辆运行成本和车辆满座率，乘车时间等实际问题，量化给出较为优化的解决方案。关键词：搜索算法，最短距离矩阵，总体满意度，个人满意度，实际方案。1、

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

4、问题 3 若建立 3 个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客 45 人（假定车只在起始站点载人）。问题 4；关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。2、问题分析 2.1 研究意义 就我校而言，就建有理学院新校区，各专业学院及教员小区与新校区之间就要靠校车解决。同时学校车辆有限，考虑到交通状况也不可能每个点都有车辆到达，如何安排车辆和乘车点使教员和工作人员满意，同时又能节约成本使资源得到最大的运用就是一个十分实际而有意义的问题。2.2 研究现状 2 目前大多数校车乘车点和车辆安排都

5、是在经验下做出的，没有做到量化处理，使方案达到最优化。2.3 存在问题 满意度的具体定义，乘车点和车辆怎样安排才能使教员和工作人员达到相对满意的程度，同时怎样在保证相对满意的条件下使车辆的运营成本最小，就牵扯到运营成本的具体量化，最后提出一套量化解决方案。2.4 解决方法 首先这 50 个区域可以简化成由 50 个点组成的无向图，题设中给出的点点之间的距离就是无向图中的边的权值，题目一可简化为无向图中其他点到选出点的最短距离问题，可以用 floyd 算法算出所有点之间的最短距离，再用穷举比较的方法计算各点到选出点的最短距离和的最小值。问题二可建立关于人数的满意度函数，在问题一的基础上算出最大满

6、意度的方案。问题三则要考虑到校车的运营成本问题，综合总体满意度和个人满意度，给出一个教员相对满意且用车最少的方案，问题四则要结合一些实际问题考虑，如人的高峰时间、校车的满座率、校车的运行线路后才能给出一个较为实际和完备的方案。3.模型假设(1)未给出距离的两个区可以由其他区间接到达。(2)乘车点只设在某几个区域不能选择 50 个点以外的点作为乘车点。(3)所有的教员都乘车，且都会去离自己最近的乘车点乘车。(4)教员的满意度与离乘车点的距离有关，距离越远满意度越低，距离越近满意度越高。(5)作为乘车点的区域的人到乘车点的距离为 0。(6)乘车点的选取数目不超过 50。4.符号约定 p:区域个数。

7、n:乘车点的个数.X:题设给出的个点之间的稀疏矩阵。Z:个点之间的最短距离矩阵。jix,：题设给出的 i,j 点原始距离。pjiz,：i,j 两个点之间通过p3,2,1这五十个区域中的节点相连得到的最短距离 jiz,：i,j 点之间的最短距离。S:五十个点到选出的乘车点的距离之和。iZP:第 i 个点的人数。iZD：第 i 个点距乘车点的最短距离。iZY：第 i 个点距离他最远点的距离。M:教员的总体满意度。3 im：第 i 个区的区域满意度。5.模型的建立和求解 5.1 最短距离矩阵的计算floyd算法 对有权无向图 来说计算点与点之间的最短距离的方法有基于动态规划的floyd 算法和 di

8、jkstra 算法，其中的 floyd 算法具有速度快，且能方便记录路径的特点，所以我们选用 floyd 算法。(1)在稀疏矩阵G中ijG表示第i个区域到第j个区域之间的距离；(2)用矩阵R来记录插入点的信息，其中ijR表示第i个区域到达第j个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距离，min(,)ijijikkjGG GG，如果ijG的距离变小，则ijR=k，并把最短距离记录在矩阵D中。算法完成后则R中包含了最短通路的信息，ijD中包含了最短路径的信息。5.1.1数据分析 题设已经给出了一定的点之间的距离列表，由 matlab 求出个点之间距离的稀疏矩阵X.其

9、中没有给出距离的点置为无穷大 inf X=50,502,501,5050,21,250,12,11,1xxxxxxxx 再由 floyd 算法，进行迭代计算。对任意两点(,)i j，若存在z，使1,1,pjpppijizzz，则更新pjijizz,。3.直到所有点的距离不再更新停止计算,则得到最短路距离矩阵 jiz,（i,j=1,2,.50)Matlab 的代码将在附录一中给出，下图是由matlab生成的最 小距离矩阵的示意图，其中颜色越深表示距离越短。4 5.2 使各区到乘车点的距离最小 5.2.1模型建立 为使个区人员到乘车点的距离最小，我们考虑个区人员到乘车点的总距离应该最小。首先考虑仅

10、设立一个乘车点的情况.设选出的乘车点是p1,则最短总距离则为最短距离矩阵中其他点到选出点的距离之和 501,1)1(piipiZD 在考虑设立两个乘车点的情况。当 n=2时，我们就要考虑到一个乘车点的选择问题，第 i 点到底是选择 p1 作为乘车点，还是选择 p2 作为乘车点呢？应该是在这两种方案中选出距离较短的点作为 i 点的乘车点。),min(21pipiiZDZDZD 则选取的两个点应使目标函数 5 501iiZD 最小。下面我们考虑乘车点数为n 的情况，当乘车点为n 时的情况其实与乘车点为二是的情况没有什么区别，区别在与对乘车点的选择上需要比较更多的情况。),min(321npipip

11、ipiiZDZDZDZDZD 乘车点的选择应使目标函数最小。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 时 选择的

12、乘车点应为 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模型建立 首先靠考虑到在该种情况下满意度的定义是什么，很明显在问

13、题二的情况下啊，乘客满意的情况是到乘车点的距离越短越好，当乘车点就是该点的时候满意度就为最大，如果将满意度定为一的话，那么此时的满意度即为 1,；如果乘车点世道该点最远的点时，此时乘客的满意度应为最小，即为 0，由此我们可以建立满意度方程：6 iiiZYZDm 1 该方程认为满意度与距离之间是简单的线性关系。由于问题二中每个点都有不同的人数存在，即无向图的每个点都有了一定的权重，我们不可能使每个区域的满意度都达到最大，所以在计算最终的满意程度时要将人数的因素加权进入方程：iiiZPZPmM M即为模型二的目标函数。5.3.2 模型求解 相关的matlab 程序将在附录三中给出.当 n=3时，选

14、择的点为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,

15、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 模型建立 如果我们以考虑教员的满意程度为主，则乘车点一定与模型二的选择一样，且车辆数也不一定是最少的。所以在该模型中应该建立两个目标函数，一个是教员的满意程度，另一个则是车辆的数量。由于45modiZP有很大的机会不等于

16、零，对于每个点整数辆的车装不满的人，是再安排一辆车去接这几个人，还是让这几 7 个人自己去不那么近的乘车点降低以下满意度呢？下面就这两种不同的方案建立模型。（1）剩余人再派车接。在模型二的基础上，设到各个乘车点的总人数为kCP（第 k 乘车点的人数）则每个乘车点的车辆数kC为 145modkkCPC 则总的车辆数为 )min(1nkkCPZC 使 ZC最小的乘车点即为所需要的状态。（2）剩余的人到离自己相对近的乘车点乘车，牺牲一定的满意程度。任是在模型二的基础上，选择乘车点。每个乘车点仅安排能满载的车辆数，设为kMZ，则满足 45ikCPMZ 每个点剩下的人数kSZ为：45modkkCPSZ

17、再考虑这些剩下的人应该怎样办？我们的解决方法是，再运用模型二，不过这次只有这三个乘车点和每个乘车点剩下的人再做一次乘车点优化，使这些人到三个乘车点的某个点的距离最短即使目标函数 kkkSZmSZM 8 最小，其中km为二次优化中各乘车点剩下的人的满意度函数。5.4.2 模型求解 由 matlab 得出以下结果 车辆数 满意度 选择乘车点 方案 1 57 0.7811 18,23,32 方案 2 56 0.7682 16,23,32（23）有结果可以看出，当选择较小的车辆数的时候，满意度会有所降低，选择较大的满意度的时候，车辆数会有所增加。5.5 建议和意 经过一定的实践考察我们得出教员和工作人

18、员出行的时间如图所示 一般来说教员的出行几种在上午上课，下午上课以及傍晚放学这三个时段，是有高峰的出行，而且有出行集中，不能迟到的特点，由此并结合问题一，二，三提出以下建议：1.在资金和人员允许的情况下适当的增加乘车点的数量，这样可以有效的提高教员的满意度。2.安排一辆或者两辆速度较快的巡游车在各个乘车点和新校区之间巡游及时带走没有赶上车的教员。3.改善教学课表，使教员能够分时段上车，让一部分的车辆能够循环使用，不用一起派出大量的车在较短的时间里将教员送到新校区。4.建议购买不同大小的车，使各个站点的老师正好乘坐，即不留一个老师也不遗漏一个空位。9 5.对教员提出要求，要求教员在一定的乘车时间

19、乘车，避免因为某些人迟到而导致的等人，空载的情况。6.某型的分析与评价 6.1 优点 1、本文的基础采用 floyd算法，由于有成熟的算法，使得带权邻接矩阵的得出十分流畅，算法效率很高。2、采用分布计算方法，使得乘车点事先确定后的最值求出，再使乘车点的可能性取遍所有可能，较容易用程序循环实现。3、将人的心理满意度函数化，较贴切的反映了人的心理，具有较强的现实性。4、模型建立的合理性，模型的建立是在对给的数据进行充分的挖掘的基础上，通过数据之间的关系提炼出各个区域之间的关系并建立起模型。5、模型的建立是按照问题的解决的思路进行的，分析和发现很有规律，然后对规律进行评价，最后建模。6.2 缺点 1

20、、把人的满意度随距离成正比，对模型的求解带来一定的误差 2、程序耗时长，时间复杂度太大。3、考虑问题的全面性还不够。7模型的推广 本例的延伸对于解决各种交通问题，物流问题，计算机网络问题等问题。8.参考文献【1】高等数学问题的 matlab 求解【2】数学模型 姜启元 谢金星 9.附录 各点距离分布图 区域号 区域号 距离(m)1 2 400 10 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

21、 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 11 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 1

22、50 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 12 32 33 190 32 35 140 32 36 240 33 34 210 35 37 160 36 39 180 36 40 190 37 38 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 28

23、0 48 49 200 各点人员分布 区域 人数 区域 人数 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 13 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、 24 46 49 76 25 76 50 62 附录一 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;

25、a(12,13)=200;a(13,34)=400;a(14,15)=190;a(14,26)=190;a(15,16)=170;a(15,17)=250;14 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)=21

26、0;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)=;a(38,39)=130;a(

27、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:n for i=1:n for j=1:n if a(i,j)a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;end end end end a;q=sum(ren);sl=

28、0;15 A=max(a);for b=1:n for c=1:n for d=1:n for e=1:n for f=1:n mm=a(b,f),a(c,f),a(d,f),a(e,f);l(f)=min(mm);lren(e)=(A(e)-l(e)/A(e)*ren(e);end L=sum(lren);if slL sl=L;p1=b;p2=c;p3=d;p4=e;end end end end;q=sum(ren);sl=0;A=max(a);for b=1:n for c=1:n for d=1:n for e=1:n for f=1:n mm=a(b,f),a(c,f),a(d,f

29、),a(e,f);l(f)=min(mm);lren(f)=(A(f)-l(f)/A(f)*ren(f);end L=sum(lren);if slL 16 sl=L;p1=b;p2=c;p3=d;p4=e;end end end end;manyidu=sl/q,p1,p2,p3,p4 p1renshu=0;p2renshu=0;p3renshu=0;p4renshu=0;for i=1:n if qulu(1,i)=p1 p1renshu=p1renshu+ren(1,i);elseif qulu(1,i)=p2 p2renshu=p2renshu+ren(1,i);elseif qulu(1,i)=p3 p3renshu=p3renshu+ren(1,i);else p4renshu=p4renshu+ren(1,i)end end p1renshu,p2renshu,p3renshu,p4renshu ch1=p1renshu/45,ch2=p2renshu/45,ch3=p3renshu/45,ch4=p4renshu/45 che=ceil(ch1)+ceil(ch2)+ceil(ch3)+ceil(ch4)manyidu=sl/q,p1,p2,p3,p4 17