基于组合优化算法下的校车发车时间问题研究

任建洵，王浩华



基于组合优化算法下的校车发车时间问题研究

任建洵，*王浩华

（海南大学信息学院数学系，海南，海口 570228）

以校车调度为研究对象，采用非线性动态组合优化的方法，以包含校车运营成本和学生出行成本在内的社会总成本为优化目标，考察最优校车发车时间间隔。以海南大学校车调度为研究对象，在考虑学生客流的变化规律时，将学校校车站点量化并采用驻站调查的方式，对其断面客流量包括上、下车人数、留站人数以及承载人数进行调查工作，获得运营时间内各时段内不同站点的客流量。依照客流规律建立了发车时间间隔的模型，通过分析最佳的校车发车时间间隔，进一步求得了全天客流高峰和全天客流低谷下的最优发车时间间隔，从而制定出新的发车方案。

校车调度；运营成本；学生效益；发车间隔；组合优化

校车优化调度是在研究学生流动规律之后，把大量的车辆组织在规定的线路上，按照客流的数量、方向、时间制定有节奏的、周而复始的行车计划。众多学者对校车的调动进行了研究，刘文[1]采用免疫算法和基本蚁群算法来搜索局部最优化模型，研究了某大学两个校区的校车安排的调度问题，并且建立了基于满意优化的数学模型，利用数学化语言对校车安排调度问题的影响因素、主要约束条件和求解目标等进行了描述和分析；马强等[2]通过对西北民族大学乘车情况进行调研分析建立一个合理的调度系统，该系统主要是针对校车调度手工方式落后、工作量大、统计结算复杂等问题而进行系统化、模型化，从而提高工作效率。姚俊等[3]从乘客候车满意度和公交公司运营成本的角度分析了公交车调度问题，建立了以乘客候车满意度为目标的公交线路发车频率优化模型，实现了模型的求解算法，并通过仿真算例进行了实证研究。本文以海南大学校车调度为考察对象，在确保学生和校车两者之间的利益最大化，确定各时段的合理发车时间间隔；遵循“先发车、先到达”调度的原则下，对海南大学校园内校车的调度问题进行了考察，假定始发站与终点站的发车时间间隔相同，并且线路上、下行单向客流基本均衡，司机规范操作不存在超车现象，从而将校车的调度问题转化为一个复杂的多目标非线性动态优化问题。

学生的广义出行成本概念是指将学生较关心的时间成本（包括步行到达校车站点的时间、等待时间和乘车时间等）和拥挤成本（与车辆内拥挤度或满载率有关）按一定系数折算成货币成本，从而得到总的出行成本。校车调度必须考虑学生的广义出行成本及企业的运营成本，鉴于此，本次对海南大学校车调度的优化是学生和校车利益的相互博弈结果。

1　校车发车时间基本模型的建立

为综合建立校车发车时间模型，本文将从校车实际运营成本、学生出行成本以及校车运营总成本三个方面进行评估。

1.1　校车运营成本

1.2　学生出行折算成本的量化

1) 等车成本

2) 乘车满意度

乘车成本为

学生出行折算成本=乘车成本+等候车成本

1.3　校车运营总成本

为方便计算，将校车运营成本，学生出行成本均折算成货币量纲，得到既体现了校车运营成本又体现了学生出行成本的总成本

显然上式含有两项，这两个目标是相互关联矛盾的。由于不同的决策者重视的角度不同，因此要对这两个目标分别赋予权重和得出最终的目标函数。设目标函数为(△)，总成本的加权平均值:

约束条件：

约束条件(6)表示运营时间内总发车次数（）不能超过现有设备条件下所能提供的最大发车车次（0max）；约束条件(7)表示发车间隔（△）应在规定的最大发车间隔△0max和最小发车间隔△0min之间，这是由校车管理单位规定的；约束条件(8)表示车辆平均满载率（）要小于最大满载率标准值（0max）[4-5]。

2　校车发车时间的模型求解

1) 化简约束条件，得最终约束条件

简化得到约束条件：

2) 简化目标函数

令

3　以海南大学校车为例的最佳发车时间实证研究

对于上文建立的校车发车时间模型，我们以海南大学校车调度为例，采用驻站调查的方式获得客流量，并依照客流规律建立了发车时间间隔的模型。通过分析最佳的校车发车时间间隔，进一步求得了全天客流高峰和全天客流低谷下的最优发车时间间隔，从而制定出新的发车方案。

3.1　平常时期学校内的客流量分布

以海大校车为对象来研究，可以将学校运营区间简化为五个站点，分别为海大南门—一号食堂（紫荆）—五号楼十字路口—北门路口—旅院食堂采用驻站调查的方式。对海大校车运营线路中上述五个站点的断面客流量包括上车人数、上下车后通过人数进行调查工作，并获得运营时间内各时段内不同站点的客流量（表1）。对原始数据汇总分析后绘制了各站点客流量随时间变化图表，可以看出各站点客流量随时间变化的规律[6]（图1）。

表1 各个站点各时间段上车人数、上下车后通过的人数的数据表

根据表1的数据，绘制出图1：

图1 不同时段各个站点的客流量

从图1可以分析得到：

1）旅游学院附近没有其他学院的生活区，乘车较少；

2）7:00和23:00左右，各个站的客流量都不太大，由于太早和太晚学生很少出来；

3）旅游学院学生宿舍楼离教学楼较近，且旅游学院大都在自己的教学楼上课，较少乘车；

乘车客流量大多数处于生活区。如三号楼—五号楼，和一号食堂客流量都不太低，充分说明了这个观点；

4）去旅游学院的大都是旅游学院学生，去五号教学楼大都是步行，不必绕北门一圈后来五号教学楼上课，少量学生是乘车东门外出；

5）三号教学楼中间时段客流量曲线较为平缓，不太有太大的变化，估计是因为处于中间路段，同时也不靠近生活区，客流量不是很大。

综合某个时间段各个站点的人数，得到各个时间段的总客流量，总客流量与时间间隔的关系图如图2所示。

图2 不同时段总客流量

从图2可以分析得到：图形呈现“两个高峰，一个低谷”的形态，分别在9:00-13:00、17:00-21:00和13:00-17:00这些时间段。

3.2　校车运营成本估算

故

3.3　学生出行折算成本估算

3.4　校车运营总成本估算

3.5　发车时间间隔对成本的影响分析

通过在各个站点统计的数据，可以得出发车时间间隔与校车运营成本，学生出行成本和总成本之间的关系图，如图3所示。

图3 发车时间间隔与校车运营成本、学生出行成本和总成本的关系图

从图3可以分析得到：

1）校车运营成本与发车时间间隔成反比，学生出行成本与发车时间间隔成正比。

2）选取最佳发车时间间隔，可使总成本最低（总成本=校车运营成本+学生出行成本）。

3.6　最佳发车时间间隔估算

根据以上情况，制定如下两个方案（表2）：

方案一：全天都是用2579 min作为发车时间间隔。

方案二：高峰阶段使用2243 min作为高峰发车时间间隔，低谷阶段使用3045 min作为低谷发车时间间隔。

表2 不同方案对应的校车运营成本，学生出行成本以及总成本

方案一、方案二的总成本变化不大，但从收益角度，选择方案二，带来的收益会更大，建议学校校车选择方案二作为校车运行方案，这样不仅能带来更多的经济收益，还能有较好的社会效益。

3.7 出行成本折算系数与最佳发车时间间隔的关系探究

当选定的出行成本折算系数不同时[7-8]，计算得到的发车间隔不同，图4描述了学生出行成本和发车间隔之间的关系。

图4 学生出行成本折算系数对最佳发车时间间隔的影响

从图4可以分析得到：

1）当学生把自己的时间都看得很重要时，出行成本折算系数，b1和b2都会变大；所引起社会效益的影响越显著最佳发车时间间隔更应该降低，方便学生出行。

（2）学生的出行成本折算系数越大时，最佳发车时间间隔降低，降低速度减慢；当最佳发车时间间隔降低到1~2 min时，基本上适合学生的时间观。

3.8 经济效益和社会效益的权重与最佳打车时间间隔的关系探究

若选定的经济效益和社会效益的权重不同时[9-11]，对应的发车间隔也是有较大的变化，数据表如图5所示。

图5 经济效益的重视程度对最佳发车时间间隔的影响

从图5可以分析得到：

1）alpha越大时，校车部门对经济效益更加看重，最佳发车时间间隔变大，可以减少运营成本。

2）alpha小于0.2时，最佳发车时间小于2 min，学生满意度很高，但是此时校车运营部门的成本较高，其经济效益不能令校车运营部门满意。

3）alpha大于0.8时，最佳发车时间间隔单位增量变大，最佳发车时间间隔超过5 min；明显是不能接受的，不利于校车部门可持续发展。

4　发车时间模型的总结与评价

本文在合理假设的前提下，构建学校校车发车时间间隔优化模型并给出相应算法，量化与发车时间间隔相关的，以学生为主的乘客广义出行成本，并统一量纲，方便模型构建；兼顾校车运营利益和学生利益将其共同纳入模型，并赋予相应的权值，既可以通过修正权值的相对大小来协调学校校车与学生的利益冲突，又可实现在乘客利益整体最优化情况下，确定发车间隔；针对不同的客流时段，采集实时数据作为模型的输入，可随时输出相应不同客流时段的发车时间间隔，实现较短周期内运营控制；通过等待时间和拥挤度(或满载率) 正确反应了发车时间间隔的服务水平。模型的构建与应用在理论上为校车的运营优化调度提供了一种有效的方法。

然而该模型涉及到的部分参数（如折算系数等）取值较难把握，而且直接影响输出结果的准确度，计算时要结合实际情况不断地进行经验调整，为此模型中部分参数在实际应用中的合理取值，有待进一步探讨；本文在建模过程中只考虑与发车时间间隔有关联的出行成本，即时间成本中的等待成本和拥挤成本，不包含其他与发车时间间隔无关或关系较小的出行成本（步行时间、乘车时间和票价等）[12]。另外该模型的构建属于静态模式，无法实现动态控制，这一部分内容有待以后研究。

另外，在实证研究时考虑的只是南门始发车，并未考虑东门始发车，如果结合东门始发车，那么所得的结论会更有说服力。在最后的模型中，假定了单次运行成本不变，这是与事实不符的，因为随着发车次数的增多，单次车的运营成本是减小的。进而可以对模型进行修正，已得到更好的结论。

[1] 刘文. 校车优化调度算法及模型研究[J]. 清华大学学报:自然科学版, 2013(2):247-251.

[2] 马强,肖俊生. 大学校车调度系统模型研究[J]. 科技风, 2012(19):11-12.

[3] 姚俊,吕智林,叶嫣. 基于满意度的公交车调度模型研究[J]. 交通信息与安全, 2009, 27(4):67-69.

[4] 孙文霞,宋倜, 乔国会. 公交调度中发车间隔控制研究[J]. 河北工业大学学报, 2007, 36(2):89-93.

[5] 徐甲. 基于随机运营时间的公交车辆调度研究[D]. 武汉:华中科技大学, 2016.

[6] 童刚．遗传算法在公交调度中的应用研究[J]．计算机工程,2005,31(13):29-31．

[7] 孙文霞,宋倜. 乔国会公交调度中发车间隔控制研究[J].河北工业大学学报,2007,36(2):89-93.

[8] 程功. 基于公交到站时间预测的公交调度模型研究[D]. 广州:华南理工大学, 2010.

[9] 马强,肖俊生. 大学校车调度系统模型研究[J].西北民族大学网络与信息管理中心,2012.

[10] 刘文. 校车优化调度算法及模型研究[J]. 清华大学学报:自然科学版, 2013(2):247-251.

[11] 金燕波. 校车路径优化问题研究[D].长春:吉林大学, 2006.

[12] 庄启智,郑新千. 大学校车调度优化问题分析及乘客满意度分析——以河海大学为例[J]. 城市地理, 2016(10):213-214.

RESEARCH ON SCHOOL BUS DEPARTURE TIME MODEL ON THE COMBINATORIAL OPTIMIZATION ALGORITHM

REN Jian-xun，*WANG Hao-hua

(College of Information Science and Technology, Hainan University, Haikou, Hainan 570228, China)

We use nonlinear dynamic combinatorial optimization methods in university school bus scheduling problem. Set up the total social cost of optimization goal which contain operating costs and student benefits, we investigate the best school bus departure time interval. In considering the variation of student passenger, we counting the numbers of people which on the bus and get off. Furthermore, we summarize the number of passenger in different station at each departure time interval. We also develop the model of departure time interval. Finally, we develop the new school bus program based on analyzing the best school bus departure time interval and further obtain the departure time interval of the day in peak and trough.

school bus scheduling；operating costs；student benefits；departure time interval；combinatorial optimization

1674-8085(2018)04-0011-06

TP301.6

A

10.3969/j.issn.1674-8085.2018.04.003

2018-03-21；

2018-07-05

海南省自然科学基金项目(117011)；海南省教育厅高校科研项目(Hnky2017-12)；海南大学青年基金项目(hdkyxj201719)；海南大学科研启动基金项目(KYQD(ZR)1735)

任建洵(1999-)，女，江苏兴化人,海南大学应用数学2017级本科生(E-mail:18861053782@163.com);

*王浩华(1981-)，男，湖北天门人，副教授，主要从事数学建模研究(E-mali:huazi8112@hainu.edu.cn).