考虑移步需求的无桩型共享单车动态调度研究

李兴华，张昕源，成 诚，杨 超，王 洧

(同济大学道路与交通工程教育部重点实验室，上海201804)

0 引 言

随着互联网技术的快速发展，无桩型共享单车技术应运而生，自行车租赁不再受取车、还车地点限制，为用户提供更加便捷、快速的出行体验.为减少无桩共享单车在使用后车辆停放位置分散、与出行需求不匹配等现象，需要经常进行单车运力调度，动态调整车辆供给位置和数量，保障共享单车系统服务水平，提高企业经济效益[1].

既有研究中，Contardo[2]通过构建时空网络模型，实现方格网络下共享单车的动态调度.Zhang[3]将共享单车动态调度问题解析为混合整数规划问题，采用启发式算法进行求解.Warrington[4]在考虑用户需求随机的情况下，使用两阶段随机近似方法求解动态调度问题.Caggiani[5]和Regue[6]提出基于阈值的响应式共享单车动态调度算法，以提高调度效率.Julius[7]和Angelopoulos[8]提出基于用户激励的方法，通过给予用户经济奖励，鼓励用户将车辆骑行到预设区域，实现柔性调度.Shui[9]以用户需求损失、调度成本和尾气排放为控制目标，提出共享单车的动态调度新思路.

既有调度算法多数是建立在出行者仅在出发点使用共享单车的假设上.若起点无单车供给，用户需步行至行程中单车富余的位置，选择共享单车出行.本文将此类产生的共享单车出行需求定义为移步需求.移步需求能反映共享单车投放位置和数量的合理性，当单车位置分布与用户需求分布匹配程度高时，移步需求较少，用户步行寻车花费的时间少，共享单车使用率高，服务水平也相应提升.

为提高共享单车动态调度的有效性，本文建立考虑移步需求的共享单车动态调度模型.考虑用户的选择行为，采用双层规划模型.上层模型以最小化用户需求损失为目标，优化共享单车运力调度方案；下层模型体现调度方案下用户的出行选择行为，以辅助调度方案决策；并采用基于多主体仿真的启发式算法求解.研究成果为共享单车的动态调度提供经验借鉴.

1 数学模型

1.1 问题描述

考虑一个交通网络G ≡(N,E)，其中，N为区域集合，E为网络中有向弧集合，E⊆N×N，仅当两区域相邻时，有(i,j)∈E.将分别定义为时间段t内网络调度前、后的闲置单车数量及用户出行需求.问题描述如图1 所示，目的在于找到一种调度策略，使得调度后闲置单车数量尽量满足需求Dt，最小化用户需求损失.

1.2 符号说明

模型相关参数及符号含义如表1所示.

1.3 模型假设

为降低建模难度，保障实用性，共享单车动态调度双层规划模型进行如下假设：

(1)只有一家共享单车运营商，且运营单车数量不变.

(2)用户在其所在区域内寻找单车，在时间段结束时决定是放弃使用共享单车出行还是移步相邻区域寻找可用单车.

(3) 用户寻车意愿仅与步行至终点的时间有关.

(4)任意时间段内，用户和调度均了解其所在小区闲置共享单车的位置信息，与单车交互的顺序为：车辆放置、区域内需求/移步需求、空置车辆抓取.

1.4 数学模型

建立双层规划模型：上层以用户损失需求最小为原则，构建共享单车动态调度方案生成模型；下层以用户出行时间最短为目标，体现移步需求用户的出行行为.

表1 参数及符号定义表Table 1 Definition of parameters

上层规划模型为

约束条件为

下层规划模型为

约束条件为

上层规划模型目标函数：式(1)为共享单车用户需求损失最少.约束条件：式(2)～式(4)说明调度车辆路径的连通性和起始点要求，式(5)～式(7)保证区域单车数量守恒，式(8)～式(10)规定调度车辆在抓取、放置及运行过程中投放区、调度车辆的容量限制，式(11)表示各区域单车到达的数量与历史的出行无关，仅与已经发生且未完成的需求有关，式(12)和式(13)是决策变量的规范性约束.

下层规划模型目标函数：式(14)体现用户在前往目的地过程中的出行链行为，通过获取各用户的出行链构成，确定共享单车用户数量.式(15)～式(20)为约束条件.式(15)为当一个用户步行到一个新的区域时(不是目的地)面临的3种相斥情况：(a)找到闲置单车，骑行至目的；(b)无闲置单车，步行至下一个区域寻找单车；(c)无闲置单车，使用其他交通方式到达目的地.式(16)为用户愿意继续步行寻找单车的概率，令κ(·) 函数为负指数函数.式(17)为用户在新区域中找到单车的概率，用户与用户之间为竞争关系，每一位用户找到单车的概率是相同的，与同一时间进入该区域的用户总数成反比，与该区域当时可用的单车数量成正比.式(18)和式(19)为用户出行的起、终点.式(20)为决策变量的取值范围.

2 求解算法

针对双层规划模型的特征及下层模型中出行者的动态选择特征，本文采用基于多主体仿真、动态规划及遗传算法的启发式算法.

2.1 仿真系统

仿真系统流程如图2所示，从第一个时间段开始循环直到调度窗口结束.在各时段起始，更新各区域的空置车辆供给及用户出行需求Dit，其中，用户出行需求等于该区域自身的出行需求加上其他区域步行至该区域的移步需求.

单车资源调度过程中，抓取单车数量不超过区域内空置单车数量，放置单车数量不超过携带的单车数量，且在任意时刻携带的单车数量不超过车辆的富余装载能力.在任意时段结束时，结算各区域内剩余车辆及需求满足情况，有如下3种情况.

(1) 若区域i在本时段内满足区域内所有需求，令

(2)若区域i没有满足任何需求，令

未能成功使用共享单车的出行者，根据其距离目的地的步行时间，决定是否再次寻车.若出行者选择步行寻车，则朝着目的地方向出发，根据出行者的步行速度，确定下一时间段出行者所在区域，将该用户的用车需求加载至新的区域中，此需求即为移步需求.同时记录下不愿移步寻车的用户，记为用户需求损失.

图2 仿真系统流程图Fig.2 Flowchart of simulator system

(3)若该区域在时段内满足部分需求，即

第3种情况，通过轮盘赌算法确定使用单车的用户，将需求满足的用户归至情况1，需求未满足的用户归至情况2.开始下一轮循环.

2.2 启发式算法

模型求解思路如下：

Step 1初始化遗传算法.

Step 2利用动态规划算法生成车队调度方案，以此生成种群初始解集.

Step 3将调度方案输入仿真系统，以用户需求损失的倒数作为个体适应度，运用轮盘赌算法进行遗传操作.

Step 4确定出行链中是否产生变异(如果确定产生变异则随机确定一个变异位置和对应可选择的基因)，采用动态规划生成变异位置后的车辆调度计划，保持变异位置前调度计划不变.

Step 5终止条件判断.迭代计数器达到最大迭代次数时停止计算，输出最优解.

动态规划流程如下.

(1)获得初始数据.

在没有调度情况下运行仿真系统，得到，作为后续制定决策的依据.

(2)决定放置或者抓取.

根据调度车辆当前装载的单车数量决定下一个动作是抓取或者放置，如果单车数量达到装载阈值的1/2，则调度车辆下一步计划为放置，否则为抓取.

(3)决定在何地进行放置或者抓取.

进行调度车辆的距离修正：若调度车辆在下一时刻执行抓取行为，则以提供最多闲置单车的区域作为抓取目标；若下一时刻执行放置行为，则选择单车需求最大的区域投放车辆.

(4)决定放置或者抓取多少车辆.

若为抓取行为，则抓取数量为该区域从当前至调度结束的的平均值，即；若为放置行为，则投放所有携带的单车.

(5)更新各区域的单车数量.

如图3 所示，对进行更新，其中，内层数值表示调度前闲置单车数量，外层数值表示调度后闲置单车数量.如果为抓取，则后续所有减去；如果为放置，则依次与相加.若为负，则减去等量的bitb；否则不变，直到归零.移动至下一个决策时间，即，其中，i为调度车辆当前所在区域编号，j为Step 2中选择区域编号.

(6)补充后续调度链.

返回Step 1 开始循环，直到调度窗口结束，得到完整的调度序列，输入仿真系统进行评价.

图3 更新区域内调度前共享单车可用数量Fig.3 Update number of available bikes beforerepositioning

3 案例分析

3.1 输入参数说明

基于2016年9月上海市杨浦、虹口区无桩共享单车数据，设计共享单车动态调度案例.选取工作日出行需求，按照骑行距离小于300 m或者大于6 km，骑行时间小于2 min或者大于2 h的标准剔除无效数据，需求及骑行特征的基本情况如图4所示.

图4 仿真数据概况Fig.4 Overview of simulator input-data

3.2 案例验证

在数据分析的基础上，标定案例中交通需求的时空分布随机性，作为特征参数输入仿真模型.遗传算法预设参数如表2所示，实现调度方案的生成和优化.

表2 模型主要参数取值Table 2 Value of main parameters

在不同调度车队规模下，对是否考虑移步需求进行对比，使用相同的启发式算法求解.结果表明，算法均表现出良好的收敛性能.不同场景下最优调度方案对应的需求损失值如表3所示.本文的调度策略有效减少共享单车潜在用户需求损失值，不同调度车队下用户使用量提升18.07% ～19.89%；随着调度车队数量的增加，出行需求及移步需求损失量逐步减少，结果与实际运行相符.

表3 案例结果Table 3 Results of case

对比考虑移步需求前后调度方案产生的效益，调度车队规模设置为5 辆时，共享单车需求的损失情况如图5所示.大部分小区中共享单车出行损失量均有所下降，局部区域用户损失过大的现象得到缓解.

图5 区域累计用户需求损失Fig.5 Accumulated user demand loss

将调度车队规模设置为5辆，分析不同移步意愿下模型生成的调度方案效益，结果如图6 所示，用户增加量为相比不考虑移步需求带来的额外用户需求满足量.随着用户寻车意愿的增强，考虑移步需求的调度方案能提供更好的服务质量.

4 结 论

本文针对现有调度方法未考虑出行过程中移步需求，用户需求分布与共享单车供给产生偏差的缺陷，提出以用户出行选择行为为下层，以调度车辆路径规划为上层的双层建模方法，并设计了相应的启发式求解算法.

图6 移步意愿设定对模型的影响Fig.6 Influence of shiftingdemand setting

仿真结果显示，在采用相同算法的情况下，额外考虑用户移步需求的调度方案能有效减少出行需求损失量，提升出行服务品质.未来，将进一步验证模型的普适性和可靠性，提出更加高效地求解算法.