共享单车需求预测及调度优化

刘恒孜， 贺玉龙， 宋太龙， 许 鹏

(北京工业大学, 北京市交通工程重点实验室， 北京 100124)

在共享经济的发展下，共享单车出现在了城市的大街小巷，绿色、低碳和健康的自行车出行方式正在被居民普遍接受。共享单车系统能够有效解决用户短途出行问题，是城市交通系统中的重要组成部分。准确的共享单车需求预测以及合理的调度研究可以为共享单车运营部门和交通管理部门提供有效的参考，从而提高共享单车系统的运行效率。

由于竞争激烈，全球大多数共享单车公司似乎都在亏损经营。不断增加的收入加上持续的亏损表明，共享单车公司迫切需要改进运营。大多数调度优化和供需平衡都依赖于对未来需求的准确预测[1]。关于共享单车的需求预测，曹旦旦等[2]和高巍等[3]采用长短期记忆神经网络模型对纽约市共享单车每小时需求量进行预测。Fournier等[4]建立了一个估计自行车季节性需求的正弦模型。Gao等[5]提出了一种基于模糊c均值的遗传算法和反向传播网络相结合的混合方法，来预测共享单车需求。共享单车需求受时空状态、骑行人心理生理状态、气候环境条件等因素影响，是随机的、不确定的。共享单车系统存在不确定性，获得的信息通常也是不完整的，因此可以被建模为一个灰色系统，进而用灰色预测理论来研究共享单车需求。Xiao等[6]在传统GM(1,1)模型的基础上，通过季节性累加得到新的序列，提出了一种季节性GM(1,1)模型。从预测结果上来看，传统GM(1,1)模型的残差序列具有较强的波动性，而Markov链适用于具有随机波动性的数据序列[7]。马尔可夫模型是一种无后效性的时间序列模型，采用马尔可夫模型修正残差可以提高残差序列的随机灵活性，进而使预测结果更加科学合理[8]。

共享单车调度优化研究是共享单车系统优化的重要组成部分，中外学者在静态调度[9]、动态调度[10]、调度路径[11-13]、调度时间[14]和调度成本[15]等方面做了大量的研究。Kadri等[16]用分支定界算法研究了再平衡车辆路径问题，找出用户等待总时间最小的最优调度方案。胡郁葱等[17]用双层规划模型来解决投放区域虚拟站点的选址及规模问题。Du等[18]针对车辆路径问题建立一个模糊二层规划模型，并设计了4种基于模糊仿真的启发式算法。Hemmati等[19]研究了一个混合整数二层规划公式，寻求博弈双方利润最大化。Yue等[20]提出了一个混合整数二层规划建模框架以及最优供应链设计和运营的求解算法。共享单车调度涉及到各个部门的组织规划，是一个NP(nondeterminism polynomial)难问题，双层规划模型考虑了决策过程中不同决策者的作用与表现，可以在不同层次上为决策者提供决策，是解决多层结构决策问题的最佳数学规划方法之一[21]。

现提出一种基于Markov模型修正残差的季节性灰色Markov模型来预测共享单车的需求，选取纽约市17个站点来验证模型的预测精度。然后基于预测得到的需求值，建立双层规划模型，上层目标为运营商的调度成本，下层目标为调度中心的调度时间，用GUROBI求解器求解。最后根据双层规划模型结果来制定调度优化方案，在最大化满足用户需求的同时，使调度成本和调度时间最少。

1 季节性灰色Markov模型

共享单车的骑行数据通常具有复杂的非线性、随机性和波动性等特征，并且呈现出季节性的特点。季节性GM(1,1)[SGM(1,1)]模型可以结合数据的周期性特征有效弱化数据的波动性，从而提高预测精度。

1.1 SGM(1,1)模型

对于原始非负序列

x(0)=(x(0)(1),x(0)(2),…,x(0)(n))

(1)

取q为一个循环，采用循环截断累加生成算子(CTAGO)得到新的序列[6]为

y(0)=(y(0)(1),y(0)(2),…,y(0)(r)),

r=1,2,…,n-q+1

(2)

∀k=1,2,…,n-q+1

(3)

y(0)的1-AGO序列为

y(1)=(y(1)(1),y(1)(2),…,y(1)(n))

(4)

计算式(4)可得

(5)

将通过季节性累加得到的式(2)代入传统的GM(1,1)模型，则SGM(1,1)模型的基本形式可定义为

y(0)(k)+az(1)(k)=b

(6)

式(6)中：a表示发展系数；背景值z(1)(k)(k=2,3,…，n)可用均值生成序列表示，z(1)(k)=0.5y(1)(k)+0.5y(1)(k-1)；b表示灰作用量。

令

(7)

同样，由最小二乘法求解p=(a,b)Τ=(BΤB)-1BΤY。

参照GM(1,1)模型[22]解白化微分方程得到SGM(1,1)模型的时间响应序列为

k=1,2,…,r

(8)

将式(8)进行一次累减得

k=1,2,…,r

(9)

式(9)的还原值为

(10)

1.2 Markov模型修正预测残差

马尔可夫链是一种无后效性的时间序列模型，SGM(1,1)模型预测的残差序列有正有负具有较强的随机性，采用马尔可夫链修正残差可以提高残差序列的随机灵活性，进而使预测结果更加科学合理，具体步骤[23]如下。

(1)由初步预测结果得到残差序列，即

ε(0)=(ε(0)(1),ε(0)(2),…,ε(0)(n))

(11)

将残差序列划分为s个状态，记作E={E1,E2,…,Es}，确定序列中每个元素所在的状态。

(2)计算状态转移概率矩阵，即

(12)

i,j=1,2，…,s

(13)

(3)修正残差序列。根据新信息优先原理，以残差序列中待修正元素的前s个元素的状态为原始状态，依据其离待修正元素的远近分别转移1,2,…,s步，在转移步数所对应的转移矩阵中，取原始状态所对应的行向量组成新的概率矩阵。对新的概率矩阵的列向量求和，得到待修正元素在每个状态区间的概率矩阵p=[p1,p2,…,ps]，通过加权平均得到修正的残差值

(14)

(4)优化预测结果，得到最终预测值

(15)

1.3 模型步骤

Step 1确定原始序列x(0)，以q为周期，对原始序列进行季节性累加得到CTAGO序列y(0)(r),r=1,2,…,n-q+1。

Step 2对序列y(0)(r)进行一阶累加，求解参数a、b。

Step 3将参数代入SGM(1,1)模型求解得到时间响应序列，累减还原计算出初步预测值。

2 双层规划模型

中国对双层规划的研究始于20世纪80年代，最早开展双层规划研究的是东南大学的盛昭翰教授[21]。双层规划模型可以在不同层面上做出决策，为了满足共享单车用户的需求，同时使运营商的调度成本和调度中心的调度时间最低，引入双层规划模型来进行调度优化。

假设运营商下面设有多个调度部门，不同的调度部门负责不同区域的车辆调度；假设调度中心的车辆足够；假设在开始调度前每个站点都处于空站状态；假设在调度过程中没有车辆驶入各站点。

根据以上假设，建立以运营商为上层，调度部门为下层的双层规划模型。其中上层运营商的决策变量是确定调度中心选址方案x=(x1,x2, …,xJ),使总的调度成本尽可能小。下层调度部门的决策变量为yij，将在上层调度中心选址方案x=(x1,x2, …,xJ)给定的前提下，确定各个调度中心的调度方案，使得调度时间尽可能小。

因此上层规划为

(16)

(17)

(18)

(19)

约束条件式(17)表示不超过运营商给出的预算成本；式(18)表示调度中心的个数不超过给定的上限个数P；式(19)表示建立调度中心才能提供车辆。

下层调度部门的决策变量为yij，在上层调度中心选址方案x=(x1,x2, …,xJ)给定的前提下，确定如何从调度中心调度车辆到各个站点才能使整个区域的调度时间最小，从而提高调度中心的效率。因此下层调度部门的规划为

(20)

(21)

(22)

yij-xj≤0,i=1,2,…,I,

j=1,2,…,J

(23)

yij,xj∈{0,1},i=1,2,…,I,

j=1, 2,…,J

(24)

式中：f()表示调度时间的目标函数;tij表示第j个调度中心到达第i个站点所需的时间；Sj表示第j个调度中心的最大供应能力；yij、xj都是0-1变量。

目标函数式(20)是使调度中心总的调度时间最小；约束条件式(21)表示只有一个调度中心为第i个站点调度车辆；约束条件式(22)表示调度中心j能配送的车辆数不超过它本身的供给能力；约束条件式(23)表示第j个调度中心为第i个站点调度车辆的前提是在第j个地点建立调度中心。

3 实例分析

3.1 数据来源

研究所采用的共享单车骑行数据来自美国纽约市Citi Bike共享单车的网站。选取纽约市17个共享单车站点作为研究对象，部分站点之间的距离如表1所示。

表1 部分站点之间的距离

3.2 误差指标

平均绝对百分比误差(mean absolute percentage error，MAPE)是一个非常有用的评价指标，它不仅能够很直观地看出模型对于整体数据样本的相对误差的数量，还可以对整体数据误差做出估计。MAPE计算公式为

(25)

MAPE值越小表明模型的精度越高，即MAPE值低于10%则认为模型的精度高[24]，MAPE值的范围11%～20%表示精度较高，为21%～50%表示精度一般，大于或等于51%表示精度差。

3.3 预测结果

研究选取美国纽约市Citi Bike共享单车2019年6月10—28日周一到周五的骑行数据作为原始数据，用季节性灰色Markov模型来预测，利用Matlab R2020b计算出各个站点的需求预测值，同时验证模型的精度。17个站点在2019年6月24—28日的共享单车需求预测值如表2所示。

表2的结果表明：在17个站点里，有10个站点的MAPE平均值低于10%，预测精度高；有6个站点的MAPE平均值在11%～20%这个范围，预测精度较高；有1个站点的MAPE平均值在21%～50%这个范围，预测精度一般。站点14的预测精度一般可能是由于季节性灰色Markov模型中q取值的影响，由于研究预测的是周一至周五的需求量，所以原模型的q=5，而站点14的原始数据周期性和波动性更强，当q=4时，计算得到该站点的MAPE平均值为5.52%。17个站点的MAPE平均值为10.68%，所以该模型本身的预测效果是好的，可以用于共享单车需求预测。将季节性灰色Markov模型的预测结果与传统GM(1,1)模型和SGM(1,1)模型做比较，由于站点较多，选取站点1～4的预测结果比较如图1所示，预测误差比较如图2所示。

表2 季节性灰色Markov模型预测结果

图1 原始数据和3种模型预测结果比较Fig.1 Comparison of the original data and the prediction results of the three models

图2 3种模型预测结果的误差比较Fig.2 Error comparison of prediction results of three models

从图1和图2可以看出：季节性灰色 Markov 模型的预测结果具有波动性且更加接近原始数据，其预测误差在较低水平范围内波动，整体的预测效果要优于传统GM(1,1)模型和SGM(1,1)模型。

GUROBI是新一代大规模数学规划优化器，可以求解很多线性和非线性的问题。利用GUROBI求解器求解双层规划模型，得到各个站点和调度区域分布如图3所示。

图3 共享单车站点和调度区域分布图Fig.3 Distribution map of shared bicycle stations and scheduling areas

从图3可以看出，双层规划模型得出的最优解将17个站点划分为3个区域，分别设置调度中心，可以最大化满足用户需求的同时，使调度成本和调度时间最优。2019年6月24日3个区域的最优调度路径和最差调度路径的行驶时间和调度成本比较如表3所示。

从表3可以看出3个区域的最优调度路径相比最差调度路径分别节省了23.05%、45.8%和35.19%的行驶时间，节省了23.15%、46.45%和34.93%的调度成本。表3所得行驶时间和调度成本具有比较意义，实际的行驶时间和调度成本会根据具体情况有所变化。如果站点增加，行驶时间和调度成本的优化效果会更加明显。

表3 各区域调度路径的行驶时间和调度成本比较

3个区域的最优调度路径和最差调度路径比较如图4所示。

图4 各区域调度路径比较Fig.4 Comparison of scheduling routes in various regions

从图4可以看出，最优调度路径的路线清晰顺畅且没有线路交叉，最差调度路径的路线错综复杂且没有规律性。在共享单车调度过程中，应尽量避免过多的线路交叉，以节省调度时间和调度成本。

4 结论

通过对美国纽约市17个Citi Bike共享单车站点的算例分析，得出以下结论。

(1) 对于具有周期性波动特征的共享单车需求预测，SGM(1,1)模型比GM(1,1)模型有更好的适应性。通过Markov模型修正之后的SGM(1,1)模型的精度有了一定的提高，季节性灰色Markov模型的预测效果要明显优于传统GM(1,1)模型和SGM(1,1)模型，预测结果科学合理，可用于实际问题的计算。

(2) 双层规划模型考虑了决策过程中运营商和调度部门的作用与表现，在调度成本和调度时间上为决策者提供决策。利用双层规划模型制定的调度优化方案能确定调度中心数量、位置，调度范围和调度路径，可以在满足用户需求的同时使调度成本和调度时间最优。

基于Markov模型修正残差的季节性灰色Markov模型的共享单车需求预测，以及在此基础上根据双层规划模型结果提出的调度优化方案，可以为共享单车运营部门和交通管理部门提供有效的参考，从而提高共享单车系统的运行效率。