基于两阶段调度策略下的公共自行车调度模型与优化方法

成先镜，吕亚楠,翁小勇，孙泽新，陈小勇

（遵义师范学院a.黔北信息技术研究院；b.数学学院贵州遵义563006）

随着经济全球化、区域一体化的快速发展，环境污染、能源浪费、汽车尾气排放等给城市发展带来一系列问题，“绿色出行”理念越来越深入人心。2005年以来我国陆续推出的公共自行车租赁系统正是出于节约道路资源、减少环境污染、缓解“市民出行难”、打造“绿色城市”的目的而提出的一种低碳交通方式[1]。公共自行车在给城市居民出行提供方便的同时，也出现了用户借车难、还车难以及自行车租赁公司调度运营成本高等问题，严重制约了公共自行车的发展。针对公共自行车发展过程中存在的问题，建立合理、动态的调度系统显得尤为重要。

关于调度模型的研究，国内外专家提出了许多不同目标下的调度模型[2,3]。刘登涛[4]以运输成本最少为目标建立了公共自行车交通调度系统模型；董红召[5]以最大化租赁点满意度为目标建立了公共慢行系统调度模型；贺竹磬[6]提出了具有时间窗约束与成本最小的车辆路径混合整数非线性调度模型；秦茜[7]提出了以运输成本最小和用户满意度最大为目标的调度模型；张建国[8]将调度时间分为平峰和高峰，建立了租赁点满意度最大化和调度成本最小化的调度模型；Raviv[9]以调度路径长度和用户满意度为目标，提出了基于时间、基于调度序列和基于弧的MIP模型；Chemla[10]提出了以实现最优平衡为目标的调度模型；Benchimol[11]将平衡作为最主要的约束，提出了以总的调度路径长度为目标的调度模型；Vogel[12]以获取站点的最优填充水平为目标，提出了一个扩展的动态服务网络设计模型下的MIP模型。但这些研究都未针对用户借车难、还车难为主要目标设计调度模型，而利用预测机制能快速准确地对租赁点的需求进行预测，能解决借车难和还车难的问题；此外，降低调度成本也是设计调度模型需要考虑的目标之一。

1 两阶段调度策略

当前公共自行车调度系统采用的是贪心策略，即先从距离调度中心最近的租赁点开始进行调度，逐步到最远的租赁点，调度完毕后返回调度中心。一旦公共自行车系统中的租赁点提出调度请求，调度人员就必须对其进行调度，而在调度系统中存在一些地理位置较偏远或需要运入/运出自行车数量较少的租赁点，调度系统在为这些租赁点进行调度时便增加了调度的成本。这种调度策略缺乏全局考虑，仅仅是局部最优解。因此，本文提出了两阶段调度策略，将调度过程分为两个阶段来进行：

（1）根据租赁点装/卸载自行车数量的大小、地理位置的远近等对租赁点赋予不同的权重，在首次筛选租赁点时将权重大的租赁点优先进行调度，满足相应的约束条件，得到可行的租赁点序列和调度路线。

（2）将权重小的租赁点与已选租赁点的距离进行比较。若它们之间的距离、时间和成本都是在可接受的范围内，将此租赁点添加进调度序列，对初始路线进行适当调整，反之，排除此租赁点，继续比较下一租赁点，直到租赁点比较完毕。

两阶段调度策略重点考虑第一个阶段，第二个阶段在全局基础上进行局部优化。以各租赁点装/卸载自行车的数量作为赋予权重的主要依据，在第二阶段进行租赁点的距离比较时，根据调度人员的经验和统计数据可知，权重小的租赁点与距离最近权重大的租赁点间的距离在1km以内是调度成本可以接受的，由此将各租赁点的对比距离设为1km。

2 调度模型

解决用户借车难、还车难以及降低租赁公司的调度成本是本研究的主要目的。调度系统的目标包括用户满意度、调度成本和弹性的时间窗。由于调度的过程是动态的，租赁点自行车的需求量会随着时间而发生变化，需要将调度时间分为一系列离散的时间段。时间连续、租赁点状态离散的特性符合连续时间的马尔科夫链的生成过程，从而能精确地进行调度预测量的计算。通过对用户无法租车和无法还车设置惩罚值进行用户满意度的计算[13]。

2.1 惩罚值的计算

采用马尔科夫链的生灭过程[14]对租赁点的自行车需求量作出预测，生灭过程的变化情况分为三种情形：

图1 表示租赁点变化的连续时间的马尔科夫链

租赁点的状态有三种即已空、已满和正常。当租赁点状态为已空或已满时，用户无法进行正常的借还操作，对此设置惩罚值。将惩罚值分为两类：

（1）将租赁点状态为已空即租赁点可借自行车数为零、用户不能借车称为用户无法借车的惩罚值。

（2）将租赁点状态为已满即租赁点空位数为零、用户不能还车称为用户无法还车的惩罚值。

租赁点的惩罚值为用户无法借车的惩罚值与用户无法还车的惩罚值之和。

2.2 调度时间的确定

调度时间分为三部分：

（1）车辆行驶时间；

（2）车辆沿途遇红灯延迟的时间；

（3）车辆起停时间及装/卸自行车时间。

2.3 时间满意度计算

在调度系统中，租赁点对调度车辆的到达有时间要求。因此，本文利用满意优化理论[15,16]对时间进行限制。传统的车辆调度将硬性时间窗作为调度车辆的时间约束，在实际应用中，硬性时间窗不能很好地反映出用户的满意程度，用户倾向于在某个特定的时间段或在其他时间段接受服务，不同时间段的服务会造成满意度的变化。设FAi为租赁点i接受车辆到达的开始时间，为租赁点i接受车辆到达的最晚时间，为租赁点接受i车辆到达的期望时间，如图2所示。

图2 租赁点i时间满意度

调度时间和时间满意度之和为：

N0：包含起始点的租赁点集合

Ci：租赁点i的锁桩数即容量

kv：调度车辆的最大载重量

T：调度周期

tij：租赁点i到的调度时间

Sit：在时刻租赁点i的可借自行车数

yijv：时刻，调度车辆v从租赁点i到装载的自行车数

模型目标函数为：

其中，time与f分别为调度时间和时间满意度。

3 邻域搜索算法

在两阶段调度策略的第二个阶段，随着租赁点的增加，程序运行时间也会增加。在实际调度过程中，要求快速计算调度路径，缩短程序运行时间。由变邻域[17,18]思想，本文提出了一个缩短程序计算时间的方法，称之为邻域搜索算法，步骤如下：

（1）从起点开始搜索附近小于1km的租赁点；

（2）若存在这样的租赁点，则找出目标值最小的一条路径，将最后的租赁点作为起点进行搜索；若不存在这样的租赁点，则添加最近的租赁点，将此作为起点继续进行下一次搜索。

（3）如果起点刚好为调度序列终点时，则结束搜索，否则，回到步骤（2）继续进行搜索。

图3 邻域搜索算法

该算法是在租赁点1km范围内搜索出租赁点，计算出目标值最小的一条路径，而不是通过排列组合的方式得到所有路径，再求出目标值最小的一条路径。通过这样的思想和方法，即可减少程序运行的时间。

4 实验

在此实验中，作者选取了温州市鹿城区20天公共自行车的调度数据。设调度租赁点的惩罚值和调度时间是相对固定的，对比采用和未采用两阶段调度模型和邻域搜索算法的时间满意度、目标值和程序运行时间。

设调度时间段为早上6到11点，车辆在每个租赁点的停车时间为5min，每辆自行车的装/卸时间为1min，车速为30km/h，并假设调度车辆的容量足够大。通过实验数据发现时间满意度的值为1时符合实验的要求，因此，分别设每1、5、10、15min调度一次，即分别取值为1，1/5，1/10，1/15。选取10个租赁点进行调度，如图4所示。

图4 租赁点数为10的数据分析

表1 租赁点为10的运行时间(s)

由图4可知，在对10个租赁点进行调度时，采用两阶段调度策略的时间满意度低，即用户满意度高，基于邻域搜索算法下的两阶段调度策略的时间满意度要略低于两阶段调度策略的时间满意度，即基于邻域搜索算法下的两阶段调度策略用户满意度最高。此外，其目标值也低于两阶段调度策略下的目标值。

由表1可知，未采用两阶段调度策略的运行时间长，采用两阶段调度策略的运行时间显著少于未采用两阶段调度策略的运行时间，基于邻域搜索算法下的两阶段调度策略的运行时间最短。

图5 租赁点数为20的数据分析

表2 租赁点为20的程序运行时间(s)

由图5可知，随着租赁点的增加，时间满意度的数值随着增加，采用两阶段调度策略的用户满意度高越来越明显，而采用基于邻域搜索算法下的两阶段调度策略得到的时间满意度更低，目标值更小。由表2可知两阶段调度策略下的程序运行时间显著缩短，而采用基于邻域搜索算法下的两阶段调度策略的运行时间最短，能在较短的时间内做出处理，满足在实际运行中的要求。

由表2可知，采用不同调度策略的运行时间差别较大：两阶段调度策略下的运行时间明显少于未采用两阶段策略下的运行时间，而基于邻域搜索算法下的两阶段调度策略时间最短。

图6 租赁点数为30的数据分析

表3 租赁点为30的运行时间(s)

由图6可知，在30个调度租赁点下得到的基于邻域搜索算法下的两阶段调度策略的时间满意度值低于未采用邻域搜索算法和两阶段调度策略的时间满意度值，即采用基于邻域搜索算法下的两阶段调度策略的用户满意度高。

由表3可知，在30个调度租赁点下未采用两阶段调度策略和邻域搜索算法的运行时间较长，不能在较短的时间内作出调度。基于邻域搜索算法下的两阶段调度策略将程序运行时间控制在0.1s内，能快速得到调度路线，更符合在实际运营过程中的调度需求。

实验采用10、20和30个租赁点对比分析了未采用两阶段调度策略、采用未基于邻域搜索算法下的两阶段调度策略和采用基于邻域搜索算法下的两阶段策略的时间满意度（即用户满意度）、目标值和程序运行时间，得到以下结论：

（1）两阶段调度得到的时间满意度更低，即用户满意度更高。

（2）随着租赁点数的增加，程序运行时间也会增加。由实验可知，基于邻域搜索算法下的两阶段调度策略能够快速进行调度，能更好地满足实际的需求。

（3）未采用两阶段调度策略的目标值较大，采用两阶段调度策略的目标值较低，而基于邻域搜索算法下的两阶段调度策略得到的目标值最低。

（4）采用基于邻域搜索算法下的两阶段调度策略计算时间最短，时间满意度最低即用户满意度高，得到的路线更优，在实际应用中具有更高的效率，实用性较强。

5 结语

本文针对公共自行车调度系统提出了两阶段调度模型。在第一阶段增加了动态调度过程中模糊时间窗的概念，在初次调度时筛选租赁点得到初始路径；在第二阶段通过衡量成本和距离将满足条件的租赁点添加进调度序列。通过实验发现该模型在实际运行中具有较高的效率。然而，在实验中也发现随着调度租赁点的增加，程序运行时间较长。针对此问题，提出了邻域搜索算法，明显地缩短了运行时间。在动态调度过程中还存在很多复杂的问题，如用户出行规律、两阶段模型中筛选租赁点的准则、早晚高峰期自行车数量、精确的预测机制等，将是下一步的研究工作。

[1]龚迪嘉,朱忠东.城市公共自行车交通系统实施机制[J].城市交通,2008,6(6):27-32.

[2]成先镜,王正伟,冉杰,等.公共自行车调度模型研究[J].遵义师范学院学报,2016,4(18):94-100.

[3]吕亚楠,吴有富,杨正云.一种改进的TOPSIS算法及其在贵阳市水质评价中的应用研究[J].遵义师范学院学报,2016,18(1):91-94.

[4]刘登涛,方文道,章坚民,等.公共自行车交通系统调度算法[J].计算机系统应用,2011,20(9):112-115.

[5]董红召,赵敬洋,郭海锋,等.公共慢行系统的动态调度建模与滚动时域调度算法研究[J].公路工程,2009,34(6):68-75.

[6]贺竹磬,孙林岩.动态交通下车辆路径选择模型及算法[J].交通运输工程学院学报,2007,7(1):112-115.

[7]秦茜.公共自行车租赁系统调度问题研究[D].北京:北京交通大学,2013.

[8]张建国,吴婷,蒋阳升.基于蚁群算法的公共自行车系统调度算法研究[J].西华大学学报,2014,33(3):70-76.

[9]Raviv T,Tzur M,Forma I A.Static Repositioning in a Bike-Sharing System:Models and Solution Approaches[J].EURO J Transp Logist,2013,11(2):187-229.

[10]Chemla D,Meunier F,Calvo R W.Bike sharing systems:Solving the static rebalancing problem[J].Discrete Optimization,2013,10(2):120-146.

[11]Benchimol M,Benchimol P,Chappert B,et al.Balancing The Stations of a Self-Service Bike Hire System[J].RAIRO-Operations Research,2011,45(1):37-61.

[12]Vogel P,Bruno A,Saavedra N,Mattfeld D C.A Hybrid Metaheuristic to Solve the Resource Allocation Problem in Bike Sharing Systems[C].Hybrid Metaheuristics,Lecture Notes in Computer Science 8457,2014.16-29.

[13]成先镜.公共自行车两阶段调度策略与模型及求解方法研究[D].南京:南京师范大学,2015.

[14]王梓坤,杨向群.生灭过程与马尔可夫链[M].北京:科学出版社,2005.

[15]张建勇,郭耀煌,李军.基于顾客满意度的多目标模糊车辆优化调度问题研究[J].铁道学报,2003,25(2):15-17.

[16]Bent R,Pascal V H.A Two-Stage Hybrid Local Search for the Vehicle Routing Problem With Time Windows[J].Transportation Science,2004,38(4):515-530.

[17]董红宇,黄敏,王兴伟,等.变邻域搜索算法综述[J].控制工程,2009,7(16):1-13.

[18]Mladenovi′cN,HansenP.Variable Neighborhood Search[J].European Journal of Operational Research,2001,130(3):449-467.