摘要：近年來(lái)，很多人將共享單車(chē)作為短途代步工具，這些單車(chē)會(huì )階段性地聚集在人流密集的交通樞紐，共享單車(chē)立體車(chē)庫可將這些車(chē)輛收容，減少擁堵，但現階段的共享單車(chē)立體車(chē)庫車(chē)輛出入庫速度較慢，調度不當的話(huà)會(huì )造成用戶(hù)等待時(shí)間過(guò)長(cháng)?，F有的調度算法主要是為小型車(chē)立體車(chē)庫設計，不適合共享單車(chē)立體車(chē)庫。共享單車(chē)立體車(chē)庫的調度算法需要能夠識別車(chē)輛類(lèi)型，預測下一時(shí)段不同類(lèi)型車(chē)輛的出入庫情況，在空閑階段調整車(chē)輛存放位置，保證車(chē)輛能夠快速入庫、快速出庫。本文基于深度學(xué)習技術(shù)實(shí)現共享單車(chē)識別模型、共享單車(chē)出入庫預測模型，并基于該預測模型設計結果，結合調度論體系實(shí)現一種共享單車(chē)立體車(chē)庫調度策略。通過(guò)實(shí)驗驗證，本文提出的調度算法有效地避免了調度不當問(wèn)題，減少了用戶(hù)等待時(shí)間。

關(guān)鍵詞：共享單車(chē)立體車(chē)庫；識別；預測；調度

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　背景

近年來(lái)共享單車(chē)種類(lèi)和數量越來(lái)越多，由于租借容易，使用方便，容易找到，很多人將其作為短途代步工具。但隨著(zhù)人流流動(dòng)，這些共享單車(chē)會(huì )階段性地聚集在人流密集的交通樞紐，如地鐵站、公交站，最終導致大量道路面積被占用，嚴重時(shí)會(huì )妨礙車(chē)輛行人通行，造成交通擁堵。

共享單車(chē)立體車(chē)庫可將這些共享單車(chē)收容，減少車(chē)輛占用道路面積。本文所述的共享單車(chē)立體車(chē)庫為具有如下特征的立體車(chē)庫：立體車(chē)庫只有一個(gè)通行口；自行車(chē)出庫/入庫操作是串行的，即一輛車(chē)出庫/入庫之后才能出庫/入庫第二輛；每一個(gè)車(chē)位只能存放一輛自行車(chē)；同一車(chē)位上車(chē)輛的出庫時(shí)間和入庫時(shí)間相等；立體車(chē)庫中，不同車(chē)位上的車(chē)輛出庫時(shí)間不同；立體車(chē)庫的容量大。

由于共享單車(chē)立體車(chē)庫容量大、存放的車(chē)輛類(lèi)型不單一、立體車(chē)庫中距離通行口遠的車(chē)位出庫/入庫時(shí)間很長(cháng)，所以當調度不當時(shí)，會(huì )導致共享單車(chē)出庫/入庫時(shí)間過(guò)長(cháng)，致使用戶(hù)長(cháng)時(shí)間等待。因此，如何合理地進(jìn)行立體車(chē)庫內的車(chē)位調度就成為亟待解決的問(wèn)題。

2　相關(guān)工作

目前，現有的立體車(chē)庫調度算法大多是為小型車(chē)立體車(chē)庫設計的，主要算法包括基于隊列的調度算法、基于窮搜的調度算法、遺傳算法和蟻群算法^{[1、4、5、8]}。

這些調度算法并不能直接應用于共享單車(chē)立體車(chē)庫的調度。和小汽車(chē)立體車(chē)庫不同，共享單車(chē)立體車(chē)庫中存放的車(chē)輛屬于多個(gè)類(lèi)別，出庫時(shí)只需出庫同一類(lèi)型車(chē)輛中的任意一輛即可。共享單車(chē)的存取會(huì )受到早晚上下班高峰、天氣、節假日等因素的影響，具有規律性，調度算法需要根據歷史信息預測下一時(shí)刻的車(chē)輛出入庫情況，根據預測結果調整立體車(chē)庫中共享單車(chē)存放位置。因為用戶(hù)存入共享單車(chē)時(shí)輸入的車(chē)輛類(lèi)型很有可能和實(shí)際入庫的車(chē)輛類(lèi)型不一致，所以，在收集歷史信息時(shí)，算法要能夠根據車(chē)輛入庫時(shí)立體車(chē)庫拍攝的圖片主動(dòng)識別車(chē)輛類(lèi)型。

綜上所述，必須為共享單車(chē)立體車(chē)庫設計專(zhuān)門(mén)的車(chē)輛出入庫調度算法。該算法需要能夠識別車(chē)輛類(lèi)型，預測下一時(shí)段車(chē)輛的出入庫情況，在空閑階段調整車(chē)輛存放位置，保證車(chē)輛快速出庫/入庫，縮短用戶(hù)等待時(shí)間。本文闡述的算法可以滿(mǎn)足以上需求。

3　算法描述

本文提出的調度算法由三部分組成：調度策略、共享單車(chē)出入庫預測、共享單車(chē)識別。其中，調度策略需要依賴(lài)共享單車(chē)出入庫預測部分提供的預測信息，后者又需要依賴(lài)共享單車(chē)識別部分提供的識別信息。

3.1　調度策略描述

建立數組T，T的大小為共享單車(chē)立體車(chē)庫中車(chē)位的數量n。為車(chē)位編號，按照每個(gè)車(chē)位上車(chē)輛出庫時(shí)間，由小到大對車(chē)位進(jìn)行排序，然后將數組T的下標按順序[0,1,…,n-1]分配給排好序的車(chē)位，0號車(chē)位上車(chē)輛出庫時(shí)間最短，(n-1)號車(chē)位上車(chē)輛出庫時(shí)間最長(cháng)。T[i]表示第i號車(chē)位的狀態(tài)，若i號車(chē)位上有共享單車(chē)，則T[i]的值為該共享單車(chē)的類(lèi)型，即T[i]=共享單車(chē)類(lèi)型；若i號車(chē)位上無(wú)車(chē)，則T[i]的值為0，即T[i]=0。

共享單車(chē)立體車(chē)庫有三種狀態(tài)：出庫、入庫、空閑。

當出庫時(shí)，設出庫車(chē)輛類(lèi)型為type_i，遍歷數組T，找到第一個(gè)值為type_i的元素T[m]，將車(chē)位m上的自行車(chē)出庫，并設置T[m]=0。

當入庫時(shí)，設入庫車(chē)輛類(lèi)型為type_j，遍歷數組T，找到第一個(gè)值為0的元素T[m]，將自行車(chē)入庫到m號車(chē)位，并設置T[m]=type_j。

當空閑時(shí)，調整立體車(chē)庫中自行車(chē)的位置。使用共享單車(chē)出入庫預測模塊預測下一時(shí)刻每種類(lèi)型車(chē)輛的出入庫情況bicycle_ini和bicycle_outi。bicycle_ini表示第i種類(lèi)型共享單車(chē)的入庫量，bicycle_outi表示第i種類(lèi)型共享單車(chē)的出庫量。將立體車(chē)庫中的車(chē)位分成兩部分：0到(r-1)號車(chē)位為首部，r到(n-1)號車(chē)位為尾部。設r的粗略值為r_e，r_e的計算公式如下：

設為b_r _in為需要調整的0到(r_e-1)號車(chē)位中，應當處于空閑的車(chē)位的個(gè)數，其計算公式為：

設為b_r_outi為需要調整的0到(r_e-1)號車(chē)位中，應當存放的每種共享單車(chē)的個(gè)數，其計算公式為：

 設r的實(shí)際值為rreal，rreal的計算公式為：

 檢索T[0,…,r_real-1],若空閑車(chē)位小于b_r_in，則檢索T[0,…,r_real-1]中的每種共享單車(chē)的車(chē)輛個(gè)數，找到個(gè)數大于對應的b_r_outi的共享單車(chē)類(lèi)型，將下標最大的元素對應的車(chē)輛放入T[r_real,…,n -1]中第一個(gè)檢索到的空閑車(chē)位。然后檢索T[0,…, r_real-1]中的每種共享單車(chē)的車(chē)輛個(gè)數，找到個(gè)數小于對應的b_r_outi的共享單車(chē)類(lèi)型，從T[r_real,…,n -1]中找到第一個(gè)該類(lèi)型的共享單車(chē)放到T[0,…, r_real-1]中下標最大的空閑車(chē)位中。

3.2　共享單車(chē)出入庫預測描述

共享單車(chē)出入庫預測使用深度學(xué)習技術(shù)，一種共享單車(chē)類(lèi)型建立一個(gè)預測模型，設共享單車(chē)類(lèi)型為m，則需要m個(gè)共享單車(chē)出入庫預測模型，所有預測模型采用同一種網(wǎng)絡(luò )結構[2]，具體結構如圖1所示。

 圖1 共享單車(chē)出入庫預測模型網(wǎng)絡(luò )結構

3.3　共享單車(chē)識別描述

共享單車(chē)識別使用深度學(xué)習技術(shù)，由兩個(gè)模型（自行車(chē)檢測模型和自行車(chē)識別模型）組成，采用級聯(lián)方式[3]。自行車(chē)檢測模型Bicycle_Detect_Net（BDN）用來(lái)檢測圖像中的自行車(chē)，輸出自行車(chē)在圖像中的坐標。自行車(chē)識別模型 Bicycle_Recognize_Net（BRN）用來(lái)識別輸入的自行車(chē)屬于哪種共享單車(chē)。整體流程為：輸入圖片到BDN中，根據輸出坐標截取圖片中對應的車(chē)輛，然后將截取出的圖像輸入到BRN中，識別出自行車(chē)所屬的共享單車(chē)類(lèi)型，如圖2所示。

圖2 共享單車(chē)識別描述

4　算法實(shí)現

4.1　共享單車(chē)識別

4.1.1　訓練樣本的制作

拍攝各個(gè)種類(lèi)的共享單車(chē)的視頻，拍攝的視頻需要滿(mǎn)足：包含共享單車(chē)各個(gè)角度、不同遠近、無(wú)干擾物品的僅包含共享單車(chē)的圖片。將視頻按幀拆分成圖片，并剔除相似度高的、有遮擋的或有噪聲的圖片，要求篩選后的每類(lèi)共享單車(chē)的圖片數量在2000以上^[6]。之后使用標注工具，標注篩選后的圖片，標注需要滿(mǎn)足標注框緊貼圖片中共享單車(chē)的邊緣。將標注后的圖片按照9:1的比例分為訓練集和驗證集。

4.1.2　模型的訓練

自行車(chē)檢測模型和自行車(chē)識別模型分開(kāi)訓練。首先訓練自行車(chē)檢測模型，然后訓練自行車(chē)識別模型。當增加一個(gè)新類(lèi)型的共享單車(chē)時(shí)，自行車(chē)檢測模型不需要重新訓練，自行車(chē)識別模型需要重新訓練。

4.1.3　模型的使用

輸入圖片到自行車(chē)檢測模型，得到自行車(chē)在圖片中的坐標，截取出自行車(chē)所在的那部分圖像，縮放并填充截圖，得到一個(gè)正方形圖，將該正方形圖輸入到自行車(chē)識別模型，最后輸出共享單車(chē)的類(lèi)型。

4.2　共享單車(chē)出入庫預測

4.2.1　訓練樣本的制作

訓練樣本需要從共享單車(chē)立體車(chē)庫和網(wǎng)絡(luò )實(shí)時(shí)收集數據，需要收集的數據主要包括車(chē)輛出/入庫時(shí)間、車(chē)輛類(lèi)型、車(chē)輛位置、天氣信息（陰晴雨雪、溫度、濕度、風(fēng)速、風(fēng)向）、PM2.5、是否節假日、周邊事故個(gè)數、周邊擁堵程度等^[7]。其中，車(chē)輛類(lèi)型由共享單車(chē)識別模塊檢測識別得到。以十分鐘為一個(gè)單位時(shí)間段，其中t0表示00:00-00:10，t1表示00:10-00:20，以此類(lèi)推。將上述信息按照單位時(shí)間段進(jìn)行統計。每條樣本數據包括（tx、時(shí)間距離、陰晴雨雪、溫度、濕度、風(fēng)速、風(fēng)向、PM2.5、是否節假日、……），tx表示第x個(gè)時(shí)間段，時(shí)間距離表示當前日期距離數據采集日期的天數。每條樣本對應的標簽為車(chē)輛類(lèi)型1的出庫數量、車(chē)輛類(lèi)型1的入庫數量、車(chē)輛類(lèi)型2的出庫數量、車(chē)輛類(lèi)型2的入庫數量……車(chē)輛類(lèi)型k的出庫數量、車(chē)輛類(lèi)型k的入庫數量。

4.2.2　模型的結構

預測模型的隱藏層由8層組成，每層都采用全連接網(wǎng)絡(luò )，激活函數都采用ReLU，每層包含的神經(jīng)元個(gè)數分別為：512、512、256、256、128、128、64、64。輸出層的神經(jīng)元個(gè)數為2k，k為共享單車(chē)類(lèi)型總數。

4.2.3　模型的訓練

模型訓練時(shí)，訓練集不做特殊要求，校驗集有特殊要求，校驗集需要選用距離當前時(shí)刻較近的樣本，即時(shí)間距離值較小的樣本。訓練頻率為每3天一次。每次訓練時(shí)，訓練樣本需要重新制作，需要添加最近3天的共享單車(chē)立體車(chē)庫出入庫信息、天氣信息、交通信息等，訓練樣本中的“時(shí)間距離”也需要重新計算，校驗集也要重新選擇。

4.2.4　模型的使用

輸入當前時(shí)刻的（tx、時(shí)間距離、陰晴雨雪、溫度、濕度、風(fēng)速、風(fēng)向、PM2.5、是否節假日等）到預測模型中，獲得模型輸出的每種共享單車(chē)出入庫預測情況，包括車(chē)輛類(lèi)型1的出庫數量、車(chē)輛類(lèi)型1的入庫數量……車(chē)輛類(lèi)型k的出庫數量、車(chē)輛類(lèi)型k的入庫數量。

4.3　調度策略

調度策略包含三部分：出庫策略、入庫策略和空閑時(shí)的調整策略。

4.3.1　出庫

若系統發(fā)出出庫指令，出庫車(chē)輛的類(lèi)型為type_k，則從前到后檢索數組T，找到值為type_k的元素的下標，出庫對應下標的車(chē)位上的自行車(chē)，同時(shí)該元素的值設置為0。

4.3.2　入庫

若系統發(fā)出入庫指令，入庫車(chē)輛的類(lèi)型為type_g，則從前到后檢索數組T，找到值為0的元素的下標，將自行車(chē)入庫到對應下標的車(chē)位上，同時(shí)該元素的值設置為type_g。

4.3.3　調整

當共享單車(chē)立體車(chē)庫進(jìn)入空閑階段時(shí)，調用共享單車(chē)出入庫預測部分，獲得每種共享單車(chē)的出入庫數量。由公式1，2，3，4計算得到rreal、b_r_in、 b_r_outi。具體調整過(guò)程如偽代碼所示：

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

if 空閑車(chē)位數 < b_r_in:

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

 if T[0,…,r_real-1]中i種類(lèi)型車(chē)輛總數 > b_r_outi:

將T[0,…,r_real-1]中i種類(lèi)型車(chē)輛下標最大的元素對應的車(chē)輛放入T[r_real,…,n -1]中第一個(gè)檢索到的空閑車(chē)位。

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

 if T[0,…,r_real-1]中類(lèi)型i的車(chē)輛個(gè)數 ＜b_ r_outi:

從T[r_real,…,n -1]中找到第一個(gè)該類(lèi)型的共享單車(chē)放到T[0,…,r_real-1]中下標最大的空閑車(chē)位中。

5　實(shí)驗

以層高5層，每層10個(gè)車(chē)位的共享單車(chē)立體車(chē)庫進(jìn)行測試。測試結果如表1所示。

表1 D表示日期（天）, S表示出入庫等待時(shí)間（秒）, A表示算法

通過(guò)表1可以發(fā)現，隨著(zhù)時(shí)間的推移，使用貪心算法的調度，車(chē)輛出入庫平均等待時(shí)間在變長(cháng)，最終穩定在70s左右，最長(cháng)等待時(shí)間達100s以上；使用本文算法的調度，平均等待時(shí)間是穩定的，最大等待時(shí)間也是穩定的，并且遠遠小于使用貪心算法的調度。

6　結論

本文提出的算法能夠識別共享單車(chē)車(chē)輛類(lèi)型；預測下一時(shí)段不同類(lèi)型車(chē)輛的出入庫情況，并且預測模型每3天更新一次，做到根據近期車(chē)輛出入庫規律及時(shí)調節；在空閑階段調整車(chē)輛存放位置，保證車(chē)輛能夠快速入庫、快速出庫，縮短用戶(hù)等待時(shí)間。

7　未來(lái)工作

本文提出的算法在共享單車(chē)立體車(chē)庫調整車(chē)輛位置階段，對r_e的選值比較固定，不夠靈活，這部分有改進(jìn)的空間。在共享單車(chē)識別部分，每增加一種車(chē)輛類(lèi)型，就需要人工標注新類(lèi)型的車(chē)輛，制作訓練樣本，然后重新訓練自行車(chē)識別模型，這部分也有改進(jìn)的空間。

參考文獻：

[1] 王相峰, 劉勝永, 李曉寧, 等. 一種應用于堆垛式立體車(chē)庫AC-TSP算法的研究[J]. 廣西科技大學(xué)學(xué)報, 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]刁瑞興, 徐海峰. 自動(dòng)化立體車(chē)庫調度策略淺析[J]. 科技資訊, 2017 (14) : 68 - 69.

[5]萬(wàn)方. 基于蟻群算法的自動(dòng)化立體車(chē)庫監控軟件的優(yōu)化設計[J]. 網(wǎng)絡(luò )安全技術(shù)與應用, 2017 (2) : 64 - 65.

[6] 彭博, 臧笛. 基于深度學(xué)習的車(chē)標識別方法研究[J]. 計算機科學(xué), 2015, 42 (4) : 268 - 273.

[7] 譚娟, 王勝春. 基于深度學(xué)習的交通擁堵預測模型研究[J]. 計算機應用研究, 2015, 32 (10) : 2951 - 2954.

[8] 宋揚, 田野, 蘇瑞聰. 公交立體車(chē)庫調度算法的研究與實(shí)現[J]. 技術(shù)縱橫, 2018，(299) : 118 - 122.

作者簡(jiǎn)介：

宋　揚（1990-），男，吉林長(cháng)春人，碩士，現任首鋼自動(dòng)化信息技術(shù)有限公司智慧城市創(chuàng )新中心大數據人工智能研發(fā)室副主任，主要研究方向為高性能計算。

田　野（1990-），男，遼寧海城人，研究生，現就職于百度在線(xiàn)網(wǎng)絡(luò )技術(shù)（北京）有限公司智能云業(yè)務(wù)運營(yíng)部，主要研究方向為計算機科學(xué)。

陳　星（1987-），男，河北遵化人，碩士，現任首鋼自動(dòng)化信息技術(shù)有限公司智慧城市創(chuàng )新中心大數據人工智能研發(fā)室算法架構師，主要研究方向為計算機視覺(jué)。

蘇睿聰（1991-），男，吉林長(cháng)春人，碩士，現任首鋼自動(dòng)化信息技術(shù)有限公司智慧城市創(chuàng )新中心大數據人工智能研發(fā)室算法架構師，主要研究方向為計算機科學(xué)。

摘自《自動(dòng)化博覽》2018年12月刊