摘要：近年来，很多人将共享单车作为短途代步工具，这些单车会阶段性地聚集在人流密集的交通枢纽，共享单车立体车库可将这些车辆收容，减少拥堵，但现阶段的共享单车立体车库车辆出入库速度较慢，调度不当的话会造成用户等待时间过长。现有的调度算法主要是为小型车立体车库设计，不适合共享单车立体车库。共享单车立体车库的调度算法需要能够识别车辆类型，预测下一时段不同类型车辆的出入库情况，在空闲阶段调整车辆存放位置，保证车辆能够快速入库、快速出库。本文基于深度学习技术实现共享单车识别模型、共享单车出入库预测模型，并基于该预测模型设计结果，结合调度论体系实现一种共享单车立体车库调度策略。通过实验验证，本文提出的调度算法有效地避免了调度不当问题，减少了用户等待时间。

关键词：共享单车立体车库；识别；预测；调度

Abstract: In recent years, many people use shared bicycles as a short-distance transportation tool, and these bicycles will be gathered in traffic hubs with dense traffics periodically. Stereo Garage for Shared Bicycle (SGSB) can accommodate these bicycles and reduce congestion. However, the speed of entering and leaving the SGSB is slow, therefore, it will be time-consuming of improper dispatch. Basically, the existing scheduling algorithms are mainly designed for Stereo Garage for Car, which is not suitable for SGSB. The scheduling algorithm of SGSB needs to identify the type of bicycles, predict the number of in-out bicycles at the next period, adjust the storage location of bicycles at the idle stage, and ensure that bicycles can enter and leave the garage quickly. Based on deep learning, this paper implements a recognition model and a loading and unloading prediction model of shared bicycles.Besides, a scheduling strategy of SGSB based on the prediction model and the dispatching theory system is also proposed. Experimental results show that the proposed scheduling algorithm avoids the problem of improper scheduling effectively and reduces the waiting time of users.

Key words: Stereo garage for shared bicycle; Recognition; Prediction; Scheduling

1　背景

近年来共享单车种类和数量越来越多，由于租借容易，使用方便，容易找到，很多人将其作为短途代步工具。但随着人流流动，这些共享单车会阶段性地聚集在人流密集的交通枢纽，如地铁站、公交站，最终导致大量道路面积被占用，严重时会妨碍车辆行人通行，造成交通拥堵。

共享单车立体车库可将这些共享单车收容，减少车辆占用道路面积。本文所述的共享单车立体车库为具有如下特征的立体车库：立体车库只有一个通行口；自行车出库/入库操作是串行的，即一辆车出库/入库之后才能出库/入库第二辆；每一个车位只能存放一辆自行车；同一车位上车辆的出库时间和入库时间相等；立体车库中，不同车位上的车辆出库时间不同；立体车库的容量大。

由于共享单车立体车库容量大、存放的车辆类型不单一、立体车库中距离通行口远的车位出库/入库时间很长，所以当调度不当时，会导致共享单车出库/入库时间过长，致使用户长时间等待。因此，如何合理地进行立体车库内的车位调度就成为亟待解决的问题。

2　相关工作

目前，现有的立体车库调度算法大多是为小型车立体车库设计的，主要算法包括基于队列的调度算法、基于穷搜的调度算法、遗传算法和蚁群算法^{[1、4、5、8]}。

这些调度算法并不能直接应用于共享单车立体车库的调度。和小汽车立体车库不同，共享单车立体车库中存放的车辆属于多个类别，出库时只需出库同一类型车辆中的任意一辆即可。共享单车的存取会受到早晚上下班高峰、天气、节假日等因素的影响，具有规律性，调度算法需要根据历史信息预测下一时刻的车辆出入库情况，根据预测结果调整立体车库中共享单车存放位置。因为用户存入共享单车时输入的车辆类型很有可能和实际入库的车辆类型不一致，所以，在收集历史信息时，算法要能够根据车辆入库时立体车库拍摄的图片主动识别车辆类型。

综上所述，必须为共享单车立体车库设计专门的车辆出入库调度算法。该算法需要能够识别车辆类型，预测下一时段车辆的出入库情况，在空闲阶段调整车辆存放位置，保证车辆快速出库/入库，缩短用户等待时间。本文阐述的算法可以满足以上需求。

3　算法描述

本文提出的调度算法由三部分组成：调度策略、共享单车出入库预测、共享单车识别。其中，调度策略需要依赖共享单车出入库预测部分提供的预测信息，后者又需要依赖共享单车识别部分提供的识别信息。

3.1　调度策略描述

建立数组T，T的大小为共享单车立体车库中车位的数量n。为车位编号，按照每个车位上车辆出库时间，由小到大对车位进行排序，然后将数组T的下标按顺序[0,1,…,n-1]分配给排好序的车位，0号车位上车辆出库时间最短，(n-1)号车位上车辆出库时间最长。T[i]表示第i号车位的状态，若i号车位上有共享单车，则T[i]的值为该共享单车的类型，即T[i]=共享单车类型；若i号车位上无车，则T[i]的值为0，即T[i]=0。

共享单车立体车库有三种状态：出库、入库、空闲。

当出库时，设出库车辆类型为type_i，遍历数组T，找到第一个值为type_i的元素T[m]，将车位m上的自行车出库，并设置T[m]=0。

当入库时，设入库车辆类型为type_j，遍历数组T，找到第一个值为0的元素T[m]，将自行车入库到m号车位，并设置T[m]=type_j。

当空闲时，调整立体车库中自行车的位置。使用共享单车出入库预测模块预测下一时刻每种类型车辆的出入库情况bicycle_ini和bicycle_outi。bicycle_ini表示第i种类型共享单车的入库量，bicycle_outi表示第i种类型共享单车的出库量。将立体车库中的车位分成两部分：0到(r-1)号车位为首部，r到(n-1)号车位为尾部。设r的粗略值为r_e，r_e的计算公式如下：

设为b_r _in为需要调整的0到(r_e-1)号车位中，应当处于空闲的车位的个数，其计算公式为：

设为b_r_outi为需要调整的0到(r_e-1)号车位中，应当存放的每种共享单车的个数，其计算公式为：

 设r的实际值为rreal，rreal的计算公式为：

 检索T[0,…,r_real-1],若空闲车位小于b_r_in，则检索T[0,…,r_real-1]中的每种共享单车的车辆个数，找到个数大于对应的b_r_outi的共享单车类型，将下标最大的元素对应的车辆放入T[r_real,…,n -1]中第一个检索到的空闲车位。然后检索T[0,…, r_real-1]中的每种共享单车的车辆个数，找到个数小于对应的b_r_outi的共享单车类型，从T[r_real,…,n -1]中找到第一个该类型的共享单车放到T[0,…, r_real-1]中下标最大的空闲车位中。

3.2　共享单车出入库预测描述

共享单车出入库预测使用深度学习技术，一种共享单车类型建立一个预测模型，设共享单车类型为m，则需要m个共享单车出入库预测模型，所有预测模型采用同一种网络结构[2]，具体结构如图1所示。

 图1 共享单车出入库预测模型网络结构

3.3　共享单车识别描述

共享单车识别使用深度学习技术，由两个模型（自行车检测模型和自行车识别模型）组成，采用级联方式[3]。自行车检测模型Bicycle_Detect_Net（BDN）用来检测图像中的自行车，输出自行车在图像中的坐标。自行车识别模型 Bicycle_Recognize_Net（BRN）用来识别输入的自行车属于哪种共享单车。整体流程为：输入图片到BDN中，根据输出坐标截取图片中对应的车辆，然后将截取出的图像输入到BRN中，识别出自行车所属的共享单车类型，如图2所示。

图2 共享单车识别描述

4　算法实现

4.1　共享单车识别

4.1.1　训练样本的制作

拍摄各个种类的共享单车的视频，拍摄的视频需要满足：包含共享单车各个角度、不同远近、无干扰物品的仅包含共享单车的图片。将视频按帧拆分成图片，并剔除相似度高的、有遮挡的或有噪声的图片，要求筛选后的每类共享单车的图片数量在2000以上^[6]。之后使用标注工具，标注筛选后的图片，标注需要满足标注框紧贴图片中共享单车的边缘。将标注后的图片按照9:1的比例分为训练集和验证集。

4.1.2　模型的训练

自行车检测模型和自行车识别模型分开训练。首先训练自行车检测模型，然后训练自行车识别模型。当增加一个新类型的共享单车时，自行车检测模型不需要重新训练，自行车识别模型需要重新训练。

4.1.3　模型的使用

输入图片到自行车检测模型，得到自行车在图片中的坐标，截取出自行车所在的那部分图像，缩放并填充截图，得到一个正方形图，将该正方形图输入到自行车识别模型，最后输出共享单车的类型。

4.2　共享单车出入库预测

4.2.1　训练样本的制作

训练样本需要从共享单车立体车库和网络实时收集数据，需要收集的数据主要包括车辆出/入库时间、车辆类型、车辆位置、天气信息（阴晴雨雪、温度、湿度、风速、风向）、PM2.5、是否节假日、周边事故个数、周边拥堵程度等^[7]。其中，车辆类型由共享单车识别模块检测识别得到。以十分钟为一个单位时间段，其中t0表示00:00-00:10，t1表示00:10-00:20，以此类推。将上述信息按照单位时间段进行统计。每条样本数据包括（tx、时间距离、阴晴雨雪、温度、湿度、风速、风向、PM2.5、是否节假日、……），tx表示第x个时间段，时间距离表示当前日期距离数据采集日期的天数。每条样本对应的标签为车辆类型1的出库数量、车辆类型1的入库数量、车辆类型2的出库数量、车辆类型2的入库数量……车辆类型k的出库数量、车辆类型k的入库数量。

4.2.2　模型的结构

预测模型的隐藏层由8层组成，每层都采用全连接网络，激活函数都采用ReLU，每层包含的神经元个数分别为：512、512、256、256、128、128、64、64。输出层的神经元个数为2k，k为共享单车类型总数。

4.2.3　模型的训练

模型训练时，训练集不做特殊要求，校验集有特殊要求，校验集需要选用距离当前时刻较近的样本，即时间距离值较小的样本。训练频率为每3天一次。每次训练时，训练样本需要重新制作，需要添加最近3天的共享单车立体车库出入库信息、天气信息、交通信息等，训练样本中的“时间距离”也需要重新计算，校验集也要重新选择。

4.2.4　模型的使用

输入当前时刻的（tx、时间距离、阴晴雨雪、温度、湿度、风速、风向、PM2.5、是否节假日等）到预测模型中，获得模型输出的每种共享单车出入库预测情况，包括车辆类型1的出库数量、车辆类型1的入库数量……车辆类型k的出库数量、车辆类型k的入库数量。

4.3　调度策略

调度策略包含三部分：出库策略、入库策略和空闲时的调整策略。

4.3.1　出库

若系统发出出库指令，出库车辆的类型为type_k，则从前到后检索数组T，找到值为type_k的元素的下标，出库对应下标的车位上的自行车，同时该元素的值设置为0。

4.3.2　入库

若系统发出入库指令，入库车辆的类型为type_g，则从前到后检索数组T，找到值为0的元素的下标，将自行车入库到对应下标的车位上，同时该元素的值设置为type_g。

4.3.3　调整

当共享单车立体车库进入空闲阶段时，调用共享单车出入库预测部分，获得每种共享单车的出入库数量。由公式1，2，3，4计算得到rreal、b_r_in、 b_r_outi。具体调整过程如伪代码所示：

while (未收到入库指令 && 未收到出库指令)：

if 空闲车位数 < b_r_in:

for i in [1,2,…,k]:

 if T[0,…,r_real-1]中i种类型车辆总数 > b_r_outi:

将T[0,…,r_real-1]中i种类型车辆下标最大的元素对应的车辆放入T[r_real,…,n -1]中第一个检索到的空闲车位。

for i in [1,2,…,k]:

 if T[0,…,r_real-1]中类型i的车辆个数 ＜b_ r_outi:

从T[r_real,…,n -1]中找到第一个该类型的共享单车放到T[0,…,r_real-1]中下标最大的空闲车位中。

5　实验

以层高5层，每层10个车位的共享单车立体车库进行测试。测试结果如表1所示。

表1 D表示日期（天）, S表示出入库等待时间（秒）, A表示算法

通过表1可以发现，随着时间的推移，使用贪心算法的调度，车辆出入库平均等待时间在变长，最终稳定在70s左右，最长等待时间达100s以上；使用本文算法的调度，平均等待时间是稳定的，最大等待时间也是稳定的，并且远远小于使用贪心算法的调度。

6　结论

本文提出的算法能够识别共享单车车辆类型；预测下一时段不同类型车辆的出入库情况，并且预测模型每3天更新一次，做到根据近期车辆出入库规律及时调节；在空闲阶段调整车辆存放位置，保证车辆能够快速入库、快速出库，缩短用户等待时间。

7　未来工作

本文提出的算法在共享单车立体车库调整车辆位置阶段，对r_e的选值比较固定，不够灵活，这部分有改进的空间。在共享单车识别部分，每增加一种车辆类型，就需要人工标注新类型的车辆，制作训练样本，然后重新训练自行车识别模型，这部分也有改进的空间。

参考文献：

[1] 王相峰, 刘胜永, 李晓宁, 等. 一种应用于堆垛式立体车库AC-TSP算法的研究[J]. 广西科技大学学报, 2015 (2) : 53 - 59.

[2] LeCun Y, Yann L, Yoshua B, Geoffrey H. Deep Learning[J]. Nature. 2015, 521 (7553) : 436 - 444.

[3] Kaipeng Zhang, Zhanpeng Zhang, Zhifeng Li, Senior Member, and Yu Qiao. Joint Face Detection and Alignment using Multi-task Cascaded Convolutional Networks[C]. ECCV. 2016.

[4]刁瑞兴, 徐海峰. 自动化立体车库调度策略浅析[J]. 科技资讯, 2017 (14) : 68 - 69.

[5]万方. 基于蚁群算法的自动化立体车库监控软件的优化设计[J]. 网络安全技术与应用, 2017 (2) : 64 - 65.

[6] 彭博, 臧笛. 基于深度学习的车标识别方法研究[J]. 计算机科学, 2015, 42 (4) : 268 - 273.

[7] 谭娟, 王胜春. 基于深度学习的交通拥堵预测模型研究[J]. 计算机应用研究, 2015, 32 (10) : 2951 - 2954.

[8] 宋扬, 田野, 苏瑞聪. 公交立体车库调度算法的研究与实现[J]. 技术纵横, 2018，(299) : 118 - 122.

作者简介：

宋　扬（1990-），男，吉林长春人，硕士，现任首钢自动化信息技术有限公司智慧城市创新中心大数据人工智能研发室副主任，主要研究方向为高性能计算。

田　野（1990-），男，辽宁海城人，研究生，现就职于百度在线网络技术（北京）有限公司智能云业务运营部，主要研究方向为计算机科学。

陈　星（1987-），男，河北遵化人，硕士，现任首钢自动化信息技术有限公司智慧城市创新中心大数据人工智能研发室算法架构师，主要研究方向为计算机视觉。

苏睿聪（1991-），男，吉林长春人，硕士，现任首钢自动化信息技术有限公司智慧城市创新中心大数据人工智能研发室算法架构师，主要研究方向为计算机科学。

摘自《自动化博览》2018年12月刊