校车安排问题

《校车安排问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、校车安排问题的研究摘要本文主要对现实中学校安排校车接送教职工，对于满足不同的情况下校车站点建在哪些区域进行了分析研究，并建立了数学模型和求解方法。问题一中，首先根据floyd算法计算出每个区域到达其他区域的最短路径矩阵，然后根据穷举法利用计算机进行求解。得知当n=2时，在区域18和31处建立乘车点，最短距离和为24492.当n=3时，在区域15、21和31处建立乘车点，最短距离和为19660.问题二中，为了考虑教师和工作人员的满意度、各区域的乘车人数。本文把满意度理解为随距离而递减的一种关系，并定义最

2、简单的关系式.同时为了考各虑区域的人数，本文把各区域的人数乘以满意度来作为问题一中最短路径矩阵的权值。然后同样根据穷举法利用计算机进行求解。得知当n=2时，在区域16和32建立乘车点，最大满意度为12.1945.当n=3时，在区域16、27和32处建立乘车点，最大满意度为14.1716.问题三中，为了使教师的满意度最高，同时使所需要的车辆数目最少。这本是一个多目标最优化问题，为简化问题，本文定义为新的目标函数。这样的最大值就是题目所要求的结果。同样按照穷举法求解得知当在区域16、27和32处建立乘车点

3、，最大满意度为14.1716。其中在区域16乘车点乘车的人数为609，需要车辆数14；在区域27乘车点乘车的人数为982，需要车辆数21.在区域32乘车点乘车的人数为911，需要车辆数20.一共需要车辆数为55.关键词：最短路径；floyd算法；穷举法；满意度；简化问题一.问题的重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。现有如下问题请你设计解决。

4、假设老校区的教师和工作人员分布在50个区，各区的距离见附件表1。各区人员分布见附件表2。问题1：如要建立个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。问题3：若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。问题4：关于校车安排问题，你还有什么好的建议

5、和考虑。可以提高乘车人员的满意度，又可节省运行成本。二．问题分析对于问题一的求解，要建立乘车点的位置，使各区人员到乘车点的距离和最小。本文首先必须计算出各区域之间的最短距离，然后可以考虑穷举法利用计算机搜索出建立乘车点的最佳位置。对于问题二的求解，首先可以根据距离来定义一个满意度函数，把问题一中的最短路径矩阵转化成满意度矩阵。然后考虑区域人数因素，对满意度矩阵进行权值处理，然后可以按照问题一中的穷举法求出建立乘车点的最佳位置。对于问题三，为了使教师和工作人员的满意度最大，而安排的车辆最少，这是一个多目

6、标最优化问题。在问题二的基础上，可以同时考虑满意度和车辆数进行最优化求解。三．符号说明n站点个数G各区域间距离的邻接矩阵表示第i个区域最短路径矩阵考虑满意度和各区域人数后的权值矩阵表示最短路径矩阵中第i个区域到第j个区域的最短距离第i个区域的人员数满意度系数第i个区域人员的到第j个乘车点乘车的满意度四．模型假设：1.不考虑教职工在站点的等待时间；2.不考虑各个站点之间路面的情况；3.不考虑各区域的面积大小。五．模型的建立与求解5.1问题一的模型建立与求解根据题意，为了建立n个乘车点，使各区域人员到最近

7、乘车点的距离总和最小。首先本文根据floyd最短路径算法[5]求出每个区域到其他各区域的最短路径。其中floyd算法的过程如下:1.在邻接矩阵G中表示第i个区域到第j个区域之间的距离；2.用矩阵R来记录插入点的信息，其中表示第i个区域到达第j个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距离，，如果的距离变小，则=k，并把最短距离记录在矩阵D中。算法完成后则R中包含了最短通路的信息，中包含了最短路径的信息。在得到了包含最短路径信息的矩阵后，本文采用了穷举法找出了建立n个乘车点

8、的最优解，穷举法的过程如下:在总区域中任选n个区域(n=2,3)，计算V中每个区域到的最短距离的总和。在这些最短距离的总和中，最小的那个距离总和就是本题的最优方案。本文用计算机对n=2和n=3的情况进行了求解，具体的求解结果如下1.当n=2时，应该在第18和第31区域建立乘车点，最短路径和为24492.其中到第18区域乘车点的乘车的区域有:.到第31区域乘车点乘车的区域有:2.当n=3时，应该在第15，21和31区域建立乘车点，最短路径和为19960.其