校车安排问题数学建模.doc

《校车安排问题数学建模.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、题目：校车安排问题摘要本文针对高校新校区校车运行的安排问题，通过合理的抽象假设，建立了校车安排方案的优化模型。从乘车点的距离最小，满意度最大又可节省运行成本等方面考虑，依据题目中所给条件分别建模求解。在问题解决过程中使用了Warshall-Floyd算法，分析、建模、求解过程中利用MATLAB编写相应程序并对数据进行分析处理，最终得出结论如下：问题1：仅考虑到每个区按距离车站的远近选择车站n=2时，乘车点：18、31距离：24492n=3时，乘车点：15、21、31距离：19660问题2：综合考虑距离及教师总体满意度n=2时，乘车点：19、32满意度：77.77%n=3时

2、，乘车点：15、21、32满意度：82.60%问题3：为使教师及工作人员尽量满意，至少需要安排54辆校车区15：安排17辆校车区21：安排19辆校车区32：安排18辆校车问题4：综合考虑距离模型，满意度模型，运营成本以及现实中的各种因素，给出校车安排的一些建议：在校车安排时应综合考虑教师的满意度和增加校车与乘车点的成本问题，在条件允许的范围内尽量增加乘车点以提高总体满意度。关键词：Warshall-Floyd算法总体满意度距离矩阵MATLAB1、问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安

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

4、最多载客47人。（4）问题4；关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。2、模型的假设及符号分析2.1模型的假设（1）50个区域看做50个点，附录A中标注距离的点间可以直接连通，而未标注的点则不能，必需通过其他点间接到达。（2）假设所有乘车点设立在各小区（点）上，乘车站点不设立在路上。（3）假设教师和工作人员的满意度只与距离有关，而忽略其他因素对其满意度的影响。（4）校车只在各个点上载人，行驶途中不载人。（5）假设所有人员均乘车。（6）假设任意时刻任意站点均有车，不考虑教师及工作人员的等车时间。2.2符号说明A：各点间距离的邻

5、接矩阵；B：各点间的最短距离矩阵；：顶点到顶点的最短距离；：图中点到点最短路径的权；：图中点的权，表示点（即i区）的人数；：各个点到乘车点的总距离；：最短总距离;ρ:乘客个体的满意度；Λ：所有乘客的总体满意度；d：某点走到乘车点的距离；D：任意两点最短距离的最大值；R：教师及工作人员走到乘车点的平均距离。1、模型的建立与求解3.1计算各区（点）之间的最短路3.1.1数据分析及处理用附录A中的各区之间距离建立对应各点距离的邻接矩阵A，即A=其中表示点i到点j的距离，当=inf，表示点i和点j不直接相通。3.1.2用Warshall-Floyd算法计算任意两点间的最短路设i为

6、图G中的顶点。令是顶点到顶点的最短距离，是顶点到顶点的权。对于任何一个顶点，顶点到顶点j的最短路经过顶点或者不经过顶点。比较与+的值。若+，则令+，保持是当前搜索的顶点到顶点的最短距离。重复这一过程，最后当搜索完所有顶点时，顶点到顶点的最短距离。这一算法的具体实现由MATLAB编程实现，具体程序见附录D。将邻接矩阵A作为Warshall-Floyd算法的输入矩阵，程序输出各点间的最短距离矩阵B（结果见附录B）以及取最短距离时部分点间的走法（结果见附录C）。3.2建立n个乘车点使各区人员到最近乘车点的距离最小的数学模型3.2.1模型的建立为图中点到点最短路径的权，表示从点到

7、点的最短距离；为图中点的权，表示点（即i区）的人数，由于不考虑人数对乘车点的影响，取=1，i，j∈（1,50）。问题1的模型为=1时的特殊情况：Minf==3.2.2模型的求解任取n个互异点，为乘车点，则从各点到乘车点的总路程为：=则取50个点的组合做，，分别计算，取得使取最小值的，点即为所求乘车点。即：=min（）其中∈{1,2,…,50},且互不相等取n=2,3，计算结果，算法的MATLAB实现减附录D.由程序计算得：n=2时，求得乘车点应在区域18和31，且=24492n=3时，求得乘车点应在区域15、21和31，且=1