上海大学校车调度方案

上海大学校车调度方案

摘要

本文以上海大学为研究对象，制定出最优的校车调度方案。校车安排问题是一个多目标优化问题，本质是在保证服务质量的前提下尽可能节约成本。我们将问题分成四个部分：站点设置、路径选择、校车分配和量化满意度。

首先，我们将校车分为接送班车和校区班车，前者需接送教职工上下班，后者则用于校区之间的辗转。而前两个子问题仅适用于接送班车。

站点设置是图论中的最短路问题。我们将乘客的住址反映到直角坐标平面，考虑使得乘客到达站点的距离偏差最小（公平性）和所有乘客到达站点的总距离最小（便捷性），以此建立多目标优化模型。鉴于数据来源的局限性，我们以上海大学已有的站点作为模型结果。

对于路径选择问题，我们以总线路数最少、行驶总距离最短、载客量均衡和线路长度均衡四个因素建立目标函数，并运用Dijkstra思想设计出算法程序，得到最终的各校区接送校车的运营路线。随后，根据运营路线、校区之间的距离和上课时间安排，分别制定了接送班车和校区班车的时刻表。另外，出于节约运营成本的考虑，我们决定租用使用频率较低的接送班车，购买频率高的校区班车。而运营成本除了车辆的租赁和购买之外，还包括油费、维修费用以及司机薪酬。

至于乘客的满意度，考虑到它由等候时间和车内的拥挤程度决定，我们建立两个模型去刻画。一方面，等候时间的满意度函数S是分段函数，在一定时间段内是可以接受的，S=1，超过后满意度随时间下降至0，即不再等候校车。另一方面，拥挤程度的函数P与车内人数呈正比关系，车内人数越多，满意度越低。

我们的模型简单明了，删繁就简，在站点选择和最优路径选择时仅考虑一些关键因素。创新点则在于利用Dijkstra算法设计的程序能够依靠站点之间的距离直接确定最优路径，运行速度快且稳定。此外，满意度的量化让我们更清晰直观地改善调配方案。但由于数据来源的局限性和模型的简化，我们假定各个站点人数是固定的并且忽略了道路拥挤的可能性。不过，一旦有足够的数据用以拟合，我们仍可以通过模型进行校车的调配，而道路拥挤的状况下只需将时间适当提前。

关键字

多目标规划；最优路径；Dijkstra算法；满意度函数

1

目录

一、 引言............................................................................................................... 3 二、 模型假设....................................................................................................... 3 三、 符号说明....................................................................................................... 4 四、 站点选择....................................................................................................... 4

4.1 模型一：站点选取 ................................................................................ 4 4.2 模型求解 ................................................................................................ 6 五、 最优路径选择............................................................................................... 6

5.1 模型二：路径选择 ................................................................................ 6 5.2 算法设计 ................................................................................................ 8 5.3 求解结果 ................................................................................................ 8 5.4 结果分析 ................................................................................................ 9 六、 调配方案....................................................................................................... 9

6.1 时刻表 .................................................................................................... 9 6.2 运营成本 .............................................................................................. 10 七、 量化满意度................................................................................................. 10

6.1 模型三：等候时间 .............................................................................. 10 6.2 模型四：拥挤程度 .............................................................................. 11 八、 模型评价..................................................................................................... 13

7.1 优点 ...................................................................................................... 13 7.2 缺点 ...................................................................................................... 13 九、 结语............................................................................................................. 13

2

一、 引言

上海大学共有专职教师2824人[1]和包括研究生在内的30000余名学生，教学活动则分别位于宝山区（校本部）、闸北区（延长校区）和嘉定区(嘉定校区）。为了节省教职工的上下班时间和方便学生校区之间的转换，各个校区会两两对发不同时间班次的校车以及开往其他方向的车辆。

事实上，校车调度问题（School Bus Routing Problem SBRP）早在1969年由Newton和Thomas提出[2]，问题通常是要求确定哪些学生该由哪辆校车、按何顺序接送，并在满足车辆装载能力和送达时间等限制条件下，使得总费用最小。有效合理的调度方案，不仅能够改善学生学习、教职工工作的状况，更能降低学校运营成本，对于完善校区建设和创建节约型社会都具有重要意义。

而我们需要针对上海大学教职工和学生的人数分布和上课时间，以方便出行和保障利益为原则，设计出校车的站点设置、路线走向、运行时长、发车间隔等。

根据上海大学的实际情况而言，校车被分为接送教职工上下班的接送班车和辗转校区之间的班车，前者是有时间窗的开放式校车路径问题，需要合理设置站点和确定线路走向；后者是无时间窗的闭合式路径问题，依据学生的课程时间制定出校区班车的时刻表，使得校车资源得到最大程度的利用，降低运营成本和减缓交通状况。

而站点的设置由乘客的人口分布决定，在尽可能地减少站点的设置的同时，使乘客走到站点的距离最短和偏差最小，既提升了乘客的满意度，也保证了公平性。而路径的选择和调配方案是彼此制约的关系。在确定路径走向时，不仅需要满足乘客的需求，也要尽可能降低运营成本，如减少校车数量和路线数，即牵涉了实际的调配方案。而另一方面，校车的调度方案也取决于车辆的行驶路线。为此，我们将着重解决最优路径确定，继而制定调配方案，如发车数量和发车时间安排。

最后，我们根据模型计算运营成本，并量化乘客的满意度。其中，运营成本主要和发车数量、油费、车辆维修费用以及司机薪酬有关；满意度则与乘客的等候时间、车内拥挤程度和道路状况有关。

二、 模型假设

对于模型建立，我们提出以下假设:

假设校车在每一个站点的停靠时间相同，未开设的站点不予停靠。但一个站点只能有一辆车经过。

校区内部的停靠站点不作考虑，且上下车的时间忽略不计 根据《校车安全管理条例》，我们假定校车的行驶速度为60公里/时。而在行驶过程中，不会出现燃料耗尽以及轮胎报废等意外情况。 假设校车是同一型号，即最大载客数相等。

为简化模型和算法，我们假设每个站点的人数不得超过单辆车的最大载客数。 模型中所有的距离均为直线距离。 只考虑工作日的情况。

3

1. 2. 3. 4. 5. 6. 7.

三、 符号说明

表1符号说明

符号 ?? ?? ????,???? (??=1,…,??) ????,???? (??=1,…,??) ?? ??? ?2 ?3 ?4 ?? ?? ???? (??=1,…,??) ?? 乘客数 站点总数 第i乘客住址坐标 第j站点的坐标 定义 乘客走到站点所能承受的最远距离 总线路最少的函数 线路总长度最短的函数 线路人数偏差最小的函数 线路长度偏差最小的函数 关于等候时长的平均满意度 时段数 第i时段的满意度 校车的最大载客数 四、 站点选择

4.1 模型一：站点选取

就上海大学的实际情况而言，学生均居住在校区内部，需求是快捷方便地辗转于各校区之间上课。相比之下，教职工则需多考虑上下班接送问题，其中牵涉到开往其他区域的校车停靠点的选择和最优路径问题。因此，校车被分为接送班车和校区班车，其中前者因接送教职工需停靠校区外的站点，后者则不停靠。具体示意图如下：

4