基于校车数量的无混载校车路线问题模型优化实现

高 巍，陈泽颖，李大舟

(沈阳化工大学 计算机科学与技术学院， 辽宁 沈阳 110142)

随着中国义务教育水平的不断提高，为中小学生提供合理的校车服务成为对学校和教育部门的新要求.对地方教育局而言，正确规划校车路线并尽可能降低校车运营成本是一个难题[1].校车路径问题主要是为一个校车车队规划路线，使校车沿路线将学生送至学校或放学时送回乘车站点，并使特定的目标达到最优.校车不仅可以很大程度上提高道路利用率，而且还能节省大量的能源.相对于其他的出行行为，上下学出行行为在时间上和空间上都具有一定的确定性，这在一定程度上不仅影响人们的日常活动，而且还对城市交通有着不可忽视的影响[2].

文献[3-6]表明通过校车路径优化能够显著减少校车数量或校车行驶距离，从而降低校车运营成本.文献[3]分析纽约市路径问题的各个方面，包括在曼哈顿区建立路线，并提供一种解决方案，方案的校车数量远远少于目前使用的校车数量.文献[4]开发了一个解决方案程序，分别考虑每个目标并搜索一组有效的解决方案，而不是单一的最优解决方案.文献[5]以车辆数为优化目标，设计了一个“后启发”算法进行求解，求解过程中对不同车型的校车进行分配，并不考虑不同车型的固定成本和可变成本的差异.孟凡超等[6]利用禁忌搜索进行求解，主要采用插入法和交换法获取邻域解.以上算法仅考虑了车辆容量约束，优化目标是最小化车辆行驶距离，主要利用已有求解VRP(vehicle routing problem)的算法框架，通过引入需求拆分算子进行求解.

本文侧重于校车的最少运营数问题，对校车问题进行定义和描述，将问题分为极限情况和一般情况，针对不同情况设计了SBLS(school bus limit situation)算法和SBGS(school bus general situation)算法，并在沈阳市某校进行实验验证，达到了运营成本降低的预期效果.

1 上下学时校车的最少运营数量问题

1.1 问题定义

校车无混载指的是一辆校车只为一所学校服务，一辆校车只负责一个学校学生的上下学接送[7].将一所学校全部乘校车的学生作为一个优化的目标，对校车乘降站、校车行驶路径、校车数量和每辆校车负责接送哪些学生进行优化.由于高额的运营费用以及不同于公交客运的运营模式，因此减少校车的数量即从源头上降低了校车的运营成本.若只考虑成本而无限减少校车数量将会造成行程路径的增加和时间的延长，导致学生可能上学迟到、家长满意度下降等问题.解决该问题就是在确保学生正常上下学的基础上，将运营成本降到最低.

1.2 问题描述

具体分为两种情况描述上下学校车的最少运营数量问题，即极限情况和一般情况.

极限情况：U学校只有1辆校车，要完成送S个学生上学.该情况下校车的数量最少，校车的利用率最高，空载率最低，校车公司收益最大，但是每个学生的到校时间最晚，最早上车的学生乘车时间最长.

该问题可以抽象为在m个乘降站中选择某一个特定的乘降站作为起点，将学校作为终点，选择一条能够遍历所有乘降站的最短的校车行驶路线.考虑到该情况下路线具有双向性，该情况下上学的最优路线也是放学送学生回家的最优路线.因此时这个问题就是一个单源点的顶点遍历最短路径问题，可以采用本文提出的SBLS算法求解.解题时将其源点和终点互换，避免m个乘降站作为源节点时的m个方案之间的比较，使得运算时间降低m倍.

一般情况：U学校有n辆校车，接送S个学生放学上学，此时n

该问题首先需要在m个乘降站中选择n个乘降站作为n辆校车的起始出发点.考虑到每个乘降站都有可能成为校车的出发点，这使得计算复杂度增加m!/((m-n)!n!).该情况下路线仍然具有双向性，上学时的最优解也是放学时的最优解，可以将上学问题转化为放学问题，将学校作为起点，将m个乘降站中的n个乘降站作为终点.

此时该问题可以抽象为：每辆校车都有一个最远的行驶距离，保证最后下车学生能够在给定时间内按时到家；每辆校车最多载学生30人；第1辆校车选择运送某个学生时，该校车的座位数量和剩余行驶距离都会减少，第1辆校车要在保证运载人数和最远的行驶距离都不超标的条件下，尽可能的多挑选学生乘坐该校车.此时问题就变成了一个0-1的背包问题[8]，下面采用SBGS算法来解决该问题.

第1辆校车采用SBGS算法挑选完其运载的学生之后，第2辆校车从剩余的没被第一辆校车选走的学生中再次采用SBGS算法挑选第2辆校车要运载的学生.以此类推，直到第n辆校车挑选完最后一个学生为止.此时n就是所需的最少的校车数量.

通过SBGS算法可以有效地确定出每辆校车应该运送的学生是谁，再根据这些学生到达的乘降站，采用SBLS算法获得该校车遍历这些乘降站的最短行驶路径.

上学时校车的最少运营数量问题是放学校车最少运营数的等价反问题，其采用放学校车最少运营数给出的求解方法.

2 算法设计

2.1 SBLS算法

SBLS算法用来确定地图上学校为起点某个乘降站为终点的最短路径，并且该路径必经过特定的其他顶点.

SBLS算法解决的问题是基于图论的，但是并不是图论中的经典问题.乘降站和学校都被视为一个图G的顶点V，连接乘降站和学校道路被看成是该图G的边E.每条边无方向但是有权重W，权重W就是该路径的长度.该图G上任意两个顶点V有边E，地理因素决定所有顶点V都是相邻顶点，例如：所有的乘降站之间、学校和乘降站之间在地理上都会有一条可以行使的路线，即地理上任何两个地点之间都会有至少一条道路连通[9].

综上，图G可以看成是一个无向有权重全连通图，SBLS算法就是在图G中找到一条以学校为起点，能够遍历所有其他顶点的最短路径.

SBLS算法解决的问题就是一个单源点的遍历最短路径问题，求得从学校途经指定的所有乘降站的一条最短的遍历路径.

2.2 SBGS算法

U学校需要n辆校车完成学生放学后送学生回家的任务.第一辆校车C1要在U学校的m个乘降站选择e1个乘降站作为校车C1负责到达的乘降站.校车C1一旦选择了m个乘降站中的e1个乘降站，则选择的e1个乘降站分别是：P1，P2，P3，…，Pi，…，Pe1-1，Pe1.

校车C1创造的总的运营价值(下车人数)V1=S1+S2+S3+…+Si+…+Se1-1+Se1.

校车C1消耗的总的运营成本(行驶距离)G1=D1+D2+D3+…+Di+…+De1-1+De1.

校车C1要在m个乘降站选择e1个乘降站使校车C1创造的总的运营价值V1尽可能的大.V1越大表示校车C1装载的学生人数越多，即充分利用了每辆校车，但是V1一般要≤20人或者≤30人.

同时，校车C1要在m个乘降站选择e1个乘降站，使消耗的总的运营成本G1≤L.L是一辆校车的一次行驶最大距离，规定校车一次行驶最大距离L是为了保证家距离学校很远的学生也能够在放学后的1 h内到家.L的具体设定取决于实际情况，由家长和学校共同商讨确定.

问题简化：1个学校，n辆校车，m个乘降站.

校车C1要在m个乘降站选择e1个乘降站，使校车C1消耗的总的运营成本G1≤L，同时创造的总的运营价值V1尽可能的大.

校车C2要在m-e1个乘降站选择e2个乘降站，使校车C2消耗的总的运营成本G2≤L，同时创造的总的运营价值V2尽可能的大.

校车C3要在m-e1-e2个乘降站选择e3个乘降站，使校车C3消耗的总的运营成本G3≤L，同时创造的总的运营价值V3尽可能的大.

以此类推，校车Ci要在m-e1-e2-e3-…-ei-1个乘降站选择ei个乘降站，使校车Ci消耗的总的运营成本Gi≤L，同时创造的总的运营价值Vi尽可能的大.

以此类推，校车Cn要在m-e1-e2-e3-…-en-1个乘降站选择en个乘降站，使校车Cn消耗的总的运营成本Gn≤L，同时创造的总的运营价值Vn尽可能的大.

该问题本质上属于0-1背包问题，可以采用动态规划的方法求解.

3 实 验

3.1 实验数据

实验选取沈阳市某校 U为例，学生数据为该学校周边范围内就读于该校的学生信息.所获得的数据信息见表1.信息包括10个属性:学生的ID(5位数字)、学校名称(本实验以U 校为例)、年级、班级、性别、上学出行方式、放学出行方式，上学离家时间、乘校车意愿、家庭住址.其中乘校车意愿中 0 表示不愿意乘坐校车，1 表示愿意乘坐校车，后续数据对其统计筛选.

表1 U校学生信息表Table 1 Student information of U school

3.2 实验结果分析

3.2.1 SBLS算法

如图1所示，假设学校U是图G的顶点a，4个乘降站分别是图G的4个顶点b、c、d、e.图G是全连通图，5个顶点之间都有连通的路径，原因是地理上任意两个点之间都有道路的连通.

每条路径都有权重，例如连接顶点a和顶点b之间的边Eab的权值可以通过使用SBLS算法获得，即SBLS中每条边的权值都是通过最短路径算法计算出来的，表示两个顶点之间的最短路径的长度.校车从顶点a出发，遍历4个顶点b、c、d、e.

如图2所示，全连通图G中有5个顶点，因此图G中有10条边.抽象图G中边的几何长度不表示权重，每条边的权重可以通过前面的SBLS算法求出，结果如表2所示，例如边Eba的权重为1.1 km.

图2 U学校和4个乘降站在图G中抽象位置关系Fig.2 Abstract positional relationship in figure G of U school and 4 boarding and landing stations

表2 全连通图G中每条边的权重Table 2 Weights of each edge in the fully connected graph G km

图G中以顶点a为源点，遍历顶点b、c、d、e的路径共有(5-1)!=24条(见图3).

SBLS算法基于Branch Bounding思想以广度优先的方式搜索图3中的树，找到最优路径所在的分支，即权重之和最小的分支[10].在实现SBLS的过程中可以引入堆栈存储的方式来增加SBLS的运行效率.把搜索过程看作是对一棵树的遍历，那么剪枝就是将树中不能得到最优解的结点剪掉[11].

SBLS算法从G的源点a和空队列开始.结点a被扩展之后，其子结点b、c、d、e被依次插入队列当中；然后取出队头元素，进行下一步扩展，保证每一次扩展时，源点a到当前节点的和都是最小.具体的解空间图如图3所示.

SBLS算法过程：SBLS算法先从源节点a开始扩展，4个子结点b、c、d、e被插入到队列当中，如表3所示.

表3 SBLS算法的活节点队列Table 3 Live node queue of SBLS algorithm

取出结点a-b，它有3个子树.因为Ecb=1 km Eea=9.5 km，所以结点a-b的子树b-e没有得到优化，该子树被删除.结点a-b沿边Ecb和Edb扩展到顶点c和d时，将他们加入优先队列，如表4所示.

表4 SBLS算法的活节点队列Table 4 Live node queue of SBLS algorithm

取出头结点a-c，它有3个子树.因为Ecb=1 kmEea=9.5 km，所以结点a-c的子树c-e没有得到优化，该子树被删除.结点a-c沿边Ecb和Edc扩展到顶点b和d时，将他们加入优先队列，如表5所示

表5 SBLS算法的活节点队列Table 5 Live node queue of SBLS algorithm

重复上面操作直到队列为空.

3.2.2 SBGS算法

下面以校车C1为例，给出校车C1在m个乘降站里选择e1个乘降站的具体计算方法.

V1(Pi,G1)=

(1)

(2)

Pi表示C1可选的乘降站为Pi，…，Pe1-1，Pe1;G1表示校车C1消耗的总的运营成本(行驶距离);V1(Pi,G1)表示乘降站为Pi、运营成本为G1时校车C1创造的总的运营价值(下车人数).

以学校U为例，学校U有7名学生乘坐校车C1回家，该7名学生的乘降站位置选择方法如前文所述，共有7个乘降站，如图4所示.7个乘降站的地理位置、运营价值、运营成本见表6.

图4 U学校和7个乘降站的位置Fig.4 Location of U school and 7 boarding and landing stations

表6 7个乘降站的地理位置、运营价值和运营成本Table 6 Geographical location,operational value and operating costs of the seven boarding and landing stations

每个乘降站有1名学生下车，因此校车C1途经每个乘降站的运营价值都是1.校车C1为了到达某个乘降站Pi而行驶的距离Di取决于校车C1的前一个途经的乘降站Pi-1.因此,校车C1到达乘降站Pi的运营成本(行驶距离)Di是一个动态变量，取决于出发点，如表7所示.

表7 不同起始点的7个乘降站的动态运营成本Table 7 Dynamic operating costs of 7 boarding and landing stations with different starting points

校车C1沿着不同顺序到达7个乘降站时，所消耗运营成本将会发生动态变化.到达同一个乘降站也会随着起始点的不同而产生不同的成本.表8给出了7种顺序得到的全部成本.

表8 校车C1搜索7次的每一次运营成本Table 8 Each operating cost of the school bus C1 search 7 times

通过上述SBGS算法,可以得出校车C1到达哪些乘降站，这些乘降站的数量是e1，以及到达上述e1个乘降站的顺序.然后再次使用SBGS算法在剩余的m-e1个乘降站中选择出e2个乘降站作为校车C2的到达目的地，同时也获得最短行驶路径下的到达上述e2个乘降站的顺序.

依次反复使用SBGS算法，直到所有的乘降站都被选择完毕，则此时所需的校车数量、每辆校车负责的乘降站集合、每辆校车到达各自负责的多个乘降站的最短路径都可以被依次求出.

4 总 结

针对无混载校车路径规划问题，查询部分中小学校的上下学时间、学生的家庭住址和学校地址，充分调研沈阳市交通情况，综合考虑校车运营方式和盈利方法，对实际的校车运营问题进行分析，把经典的校车路径规划问题拆分为校车最短路径与最少运营数.重点关注校车数量，提出了SBLS算法和SBGS算法.实验结果表明：运用算法后的行车距离更短，校车数量减少，达到了降低运营成本的预期效果.

采用图论的方法，推导了不同情况下校车数量与校车路径之间的计算关系，阐述了不同运营方式所产生的行驶距离不同的情况.对校车数量问题设定两种情况，不同情况给出不同的算法.极限情况作为一般情况的支撑，一般情况的SBGS算法加上极限情况SBLS算法为无混载校车路径问题、校车运营数量问题提供了解决方案.

文中在构建校车路线优化模型时没有考虑城市交通的情况.事实上，由于校车运营时间集中在早晚的城市交通高峰期，不可避免地出现交通拥堵现象，导致校车到达不及时. 在这种情况下，一些学校调整了学校的上下学时间，在设计校车路线时做到基于学校上下学时间调整校车调度方案[12].后续将会在本研究的基础上，考虑学校时间窗的调整，服务于错峰上学背景下的校车路径问题；考虑实时交通情况，做出基于实时城市交通的校车路径规划；结合两种情况的有混载校车路径规划，进一步完善校车路径问题在生活实际中的运用.