基于大数据的公共自行车运营分析及调度模型

李明明

(吉林大学 大数据和网络管理中心, 长春130025)

0 引 言

中国是世界上人口和机动车数量最多的国家。 近年来, 随着居民收入水平和生活质量的不断提高,越来越多的家庭选择驾车出行。 据国家统计局可靠数据, 截止2017 年底我国机动车保有量已达21 743万辆, 驾车已经变成更多居民出行的首选交通方式[1-3]。 与此同时, 庞大的私家车数量给城市的发展带来了更多挑战, 交通拥堵和环境污染已成为迫切需要解决的问题。 而近年出现的公共自行车为解决该问题提供了有效途径。

公共自行车运营模式以其自身固定站点管理的方式, 很好地解决了乱停乱放和丢失问题, 减少了自行车的损坏率, 规范了操作秩序。 但公共自行车系统也有不可避免的缺点, 限制了进一步的发展[4-6], 其主要缺点是对于使用者租赁需求预测困难, 造成了公共自行车系统整体的资源浪费。 Contardo 等[7]分析了公共自行车动态平衡问题, 定义运输车辆将自行车从富裕站点运送至短缺站点的问题并建立数学模型。 吴满金等[8]研究了公共慢行系统调度过程中租赁点需求的动态特性及其模糊时间窗的约束, 以租赁点满意度最大化为目标建立了公共慢行系统调度模型,并用滚动时域算法对该模型进行求解, 动态获取调度计划。 何烨聪等[9]利用遗传算法建立公共自行车调度模型并进行检验, 结果表明遗传算法具有较高效率, 能有效求解自行车调度问题。利用数学工具可准确分析对象的本质特征, 并且可较为形象地分析和表述问题。 笔者以某市公共自行车运行系统为例, 通过大数据的统计方法分析公共自行车的运行特点, 进而采用蚁群算法( ACO: Ant Colony Optimization) 建模。 相比其他算法, 蚁群算法可更好地用于解决TSP( Traveling Salesman Problem)。

1 公共自行车使用频率分布特征

图1 为公共自行车不同站点使用频率。 由图1 可知, 不同的站点公共自行车使用频率相差较大, 最多的站点使用频率高达2 153 次, 而使用次数最少的站点仅有57 次。 公共自行车站点使用频率从侧面反应了站点规划的问题, 因此进行公共自行车站点规划时应在使用频数较多的站点补充自行车, 而使用频率较少的站点减少自行车供应。

图2 为不同类型公共自行车站点平均使用频率分布图。 由图2 可知, 公共自行车最大的作用是服务于居民出行和作为公共交通最后1 千米的补充。 公共自行车用于校园出行的频率较低, 同时休憩点公共自行车使用频率也较低。

图1 站点使用频率分布图Fig.1 Site usage frequency distribution

图2 不同类型站点平均使用频率Fig.2 Average usage frequency of different types of sites

图3 为一周内借还车数量分布图。 由图3 可知, 借还车数量在工作日内无明显变化, 而周末公共自行车使用次数相对较少。

地形、 降水等自然因素都会对公共自行车的出行造成很大的影响。 相关统计资料表明, 普通自行车上坡时可爬7% ～8% 的坡度, 但爬坡距离很短, 一般认为自行车通过大于2.5% 的坡时较为困难, 下坡时较为危险。

公共自行车的使用一般是在户外, 因此天气对于公共自行车出行有直接影响, 尤其是降水。 笔者将晴天与阴雨天气下公共自行车出行频率进行对比(见图4)。 由图4 可知, 晴天公共自行车出行的频率略大于阴雨天气。 其主要原因是由于公共自行车数据是在7 ～9 月份采集的, 此时天气较为炎热, 因此导致阴雨天气下公共自行车使用频率相对较低。 鉴于阴雨天气公共自行车骑行人数相对较少, 可安排此时检修公共自行车。

图3 不同工作日站点使用频率Fig.3 Frequency of use of different workday sites

图4 不同天气下公共自行车出行频率Fig.4 Frequency of public bicycle trips in different weather

2 公共自行车借还车时间分布特征

研究公共自行车的使用时间分布规律将对其系统的实际运营产生很大影响, 使运营公司更好地进行调度, 从而提高用户满意度, 使其更加便于人们出行。

图5 和图6 分别是借还车辆的时间分布曲线。 对比两条曲线不难发现具有很高的相似性。 这是由于公共自行车主要服务于短距离出行, 某市85% 的公共自行车出行时间都在30 min 以内。 同时, 时间分布有3 个明显的峰值, 即早高峰的8:00 ～9:00, 中午高峰的12:00 ～14:00 和晚高峰17:00 ～19:00, 其中晚高峰峰值最大并且持续时间最长。

图5 借车时间分布图Fig.5 Borrowing time map

3 公共自行车周转率特征分析

图6 还车时间分布图Fig.6 Return time map

周转率主要有两种: 站点周转率和行车周转率, 分别代表公共自行车租赁站点和行车的运行效率。站点周转率是指在每个单位时间内单独停车桩归放自行车的次数, 具体计算公式如下

目前该市一共有113 个站点, 停车桩总数为2 260 个, 综合前面总结的各类型停车站点借车次数的特征分析, 以及用户还车时间平均分布的相关数据, 可统计出该市的公共自行车系统在全天时间、 早晚高峰时间单位小时的站点周转率, 单位统一设定为次/(天·桩)。 如表1 所示, 公共自行车站点周转率仅为6.2 次/(天·桩)。

表1 公共自行车日周转率Tab.1 Public bicycle daily turnover rate 次/(天·桩)

4 公共自行车的调度原理

公共自行车辆的调度是按照一定的顺序, 通过不同租赁点, 在满足一定约束条件下, 将各个租赁点的公共自行车进行有效分配, 以达到预先目标并满足用户需求[10-12]。 公共自行车的统一调度主要为解决用户“无车可借, 无处可还” 的问题。 图7 为公共自行车调度原理图。

图7 公共自行车调度原理图Fig.7 Public bicycle scheduling schematic

调度问题根据约束条件和假设情况, 一般分为以下3 种调度方式。

1) 根据调度车辆数量分为单车辆调度和多车辆调度。 在公共自行车使用率较低或公共自行车站点较少的情况下, 采用单车辆调度, 即运营商只使用一辆调度车, 完成所有站点公共自行车调度。 单车辆调度最大的优点是调度成本低。

2) 公共自行车的运行效率分为静态调度和动态调度。 静态调度是指车辆调度过程中公共自行车租赁点的自行车数量不会发生改变; 而动态调度是指公共自行车单车处于用户使用状态, 系统处于运行中, 与之相对应的自行车调度人员根据租赁运行站点在桩车数量的变化优化调度策略, 以找到最优调度方案。

3) 根据调度车辆行驶路线分为封闭调度和开放调度。 封闭调度是指调度车辆完成公共自行车调度后返回租赁运行站点; 开放调度则不要求运行后的自行车一定返回综合调度中心。 笔者在分析该市的公共自行车运行状况时, 结合实际调度情况, 决定采用封闭调度。

5 基于蚁群算法的调度模型建立

5.1 蚁群算法模型

通过以上分析可知每天公共自行车需求的调度量, 而如何选择一条合适的自行车调度线路就成为首要考虑的问题。 为使各租赁站点都能得到足够的需求量, 必须优化调度自行车的策略, 让车辆的调度效率最高, 成本最低, 有效节约调度时间成本和物资成本。 用于解决公共自行车调度路径的算法目前有很多种, 如退火算法、 蚁群算法、 禁忌算法和遗传算法等, 笔者选择蚁群算法。 蚁群算法, 又称蚂蚁算法,该算法是一种寻找优化路径的机率型算法, 具有自组织, 并行, 正反馈及抗变换性等特点。

5.2 各站点距离及调度量计算

使用蚁群算法必要条件是已知公共自行车租赁点任意两点间距离。 可根据各站点经纬度建立相应坐标系(见表2)。 公共自行车调度有固定的调度起点与终点, 笔者以起点为点1 进行调度。

表2 各租赁点坐标距离Tab.2 Coordinate distance of each rental point

根据公共自行车出行记录, 使用枚举法得出公共自行车的调度量如表3 所示。

表3 公共自行车的调度量Tab.3 Scheduling volume of public bicycles

5.3 基于TSP 问题的基本蚁群算法

旅行推销员问题(TSP), 又称为货郎担问题, 是著名数学问题之一。 目的是在所有可选路径, 找出其长度为所有路径中的最短路径。

设bi(t)表示t时刻位于地点i的蚂蚁数目, 则全部蚂蚁数量点中蚂蚁信息量集合,C是两个城市连接的集合。

蚂蚁k(k=1,2,…,m)在 “觅食” 中, 根据走过路径信息激素量调整转移方向。 蚂蚁k的即时路径用Tk(k=1,2,…,m)表示。 算法执行过程中, 集合Tk会做相应的动态调整。pkij(k)是在时间点t蚂蚁k由i爬行到j的实时状态和转向概率, 即有

其中allowedk={C-tabuk}是蚂蚁k可以选择的地点;α表示信息素诱导因子,α越大, 越能体现蚂蚁们乐于走此路径;β是期望诱导因子,β值越大, 蚂蚁状态越接近贪婪规则;ηi,j(t)是诱导函数, 表达式为

其中di,j是i,j 两点之间的距离。 对于蚂蚁k, di,j值越小, ηi,j(t)越大, pki,j(k)也越大。

在t+n 时间段内, i、j 两个点之间所经过的路径上的信息量表示为

其中 ρ 表示挥发系数, (1-ρ)表示信息残留因子, ρ 的取值范围为[0,1]; Δ τij(t)为路径(i,j)上的信息素增量, 最初时, Δ τij(t)= 0; Δ τkij(t)为第k 只蚂蚁在同一循环中残留于路径(i,j)上的信息量; Q 为信息素强度, 算法的收敛速度依赖于它, Lk表示为第k 只蚂蚁在本次循环中所走路径总长度。

5.4 实例分析

笔者参考蚁群算法的计算步骤和整体流程, 构造一种静态的公共自行车调度算法。 公共自行车调度问题与TSP 问题的主要区别在于调度车容量约束和桩点供应量约束, 同时公共自行车调度具有设置固定的起终点。 笔者主要在这3 个方面进行改进。

5.4.1 模型假设

1) 调度车辆从起点出发时所载公共自行车为0, 返回终点时所载公共自行车也为0。

2) 任意租赁点的自行车调度量小于调度车辆的荷载, 保证每一租赁点调度一次。

3) 假设目前该市按照需求量执行调度, 并且可满足第2 d 的需求。

5.4.2 目标函数

此问题是单目标优化问题, 优化目标为在完成公共自行车调度的前提下, 调度车辆的总行驶里程最短

其中调度站点的集合S ={S0,S1,S2,…,S22}, S0为调度的起终点; A 为站点间的距离矩阵; d 为调度起点与各站点的距离; 调度车辆的调度路线T={S0,t1,t2,t3,…,S0}; L 为调度车辆按照调度线路行驶时所需行驶的长度; dS0,t1代表调度始终点S0到第1 个租赁点的距离逐个行驶至最后一个租赁点所需经过的距离, dtn,S0代表调度运输车从最后一个租赁点行驶到始终点所经过的距离。

5.4.3 收敛条件

1) 调度车辆从驶出公共自行车站开始调度时, 载荷为0。 若第1 个需调度租赁点的调度用车量为负数, 则不能满足该租赁点的调度需求, 所以一定保证第1 个租赁点公共自行车数为正数。 即

2) 当确定下一个调度站点时, 前一站点与后一站点调度量之和要小于被调度自行车的总量, 即确保当站点i 的调度需求Di＞0 时, 调度运输车能一次性将Di辆自行车运走, 此收敛条件可写为

3) 当租赁点的用车需求Di＜0 时, 此时要满足的条件是前i-1 个租赁点完成调度需求任务后, 调度运输车上自行车数量大于该点数量的绝对值, 即满足

4) 最后一个约束条件是最终将所有公共自行车调度完毕, 即调度车上不剩余公共自行车

5.5 模型求解

案例计算之前应该进行参数设定。 笔者按前面的蚁群算法求解方式, 给出算法各参数的初始对应值:m=12,α= 0.8,β= 4,Q= 100,ρ= 0.1, 极限迭代次数Nmax= 6 000,C= 15。 其计算结果如图8、图9 所示, 调度车辆行驶路径最短距离为1.5×104m。

图9 迭代次数图Fig.9 Iteration number map

图8 调度路线图Fig.8 Scheduling route map

6 结 语

公共自行车调度主要为解决用户无车可借及无处可还的问题, 公共自行车在调度时, 需要尽可能降低运营商的调度成本及减少调度所需时间并提高工作效率。 所以, 在公共自行车调度之前必须制定完成高效的调度方案, 即调度运输车的行驶线路和车载量等都需首先确定好。 笔者的研究基于满足各个租赁点需求量的静态调度, 以调度运输车辆的行驶距离最小化为目标, 通过改进蚁群算法蚁, 建立了一个调度运输车行驶路径最优化模型, 从而得到调度运输车在配送中的最优行驶路径。