基于用戶預約數據的公共自行車高峰期調度研究

靳文舟，葉欽海，郝小妮

(華南理工大學 土木與交通學院，廣東 廣州 510640)

基于用戶預約數據的公共自行車高峰期調度研究

靳文舟，葉欽海，郝小妮

(華南理工大學 土木與交通學院，廣東 廣州 510640)

圍繞公共自行車系統缺乏高峰期需求預測以及系統調度理念，引起調度滯后、用戶滿意度低等問題展開分析，探討公共自行車高峰期調度需求預測和系統平均滿意度量化的方法，研究公共自行車調度最優化路徑問題。在基于用戶預約數據的高峰期調度需求預測模型研究基礎上，考慮用戶滿意度，建立最小化調度綜合成本的優化調度模型，并采用改進的遺傳算法對模型進行求解。以廣州市某區域的公共自行車系統為研究對象，對模型進行實例驗證。研究結果表明：與常規調度方案相比，綜合成本降低了16.6%，系統平均用戶滿意度提升了28.7%。

交通運輸工程；公共自行車；需求預測；系統平均滿意度；優化調度；遺傳算法

0引言

交通領域中，自行車交通因其獨有的環保性以及便捷性，被認為是改善未來城市交通結構與緩解城市交通問題的良方。公共自行車作為公共交通的延伸，在國家明確提出“切實轉變過度依賴小汽車出行的交通發展模式”的大背景下，得到各大城市的青睞，但與此同時，運營中的調度問題也日漸突出。資料顯示，現狀運營方一般采用人工巡查或實時監控的方式對各服務點進行監測，當服務點的車樁比例臨近閾值時(小于0.2或大于0.8)，發出調度預警信息，提示管理員安排調度。整個過程各環節隨機性大，對用戶真實需求缺乏準確預判；調度多針對單個服務點，缺乏系統整體調度；調度路徑靠司機經驗臨時確定，無優化過程。這些現狀問題一定程度降低了調度效率，導致整個系統調度滯后，特別是在早晚高峰時段產生借還空白期，嚴重影響用戶的滿意度，不利于系統的良性發展。

目前，關于公共自行車調度的研究已成為交通領域的研究熱點之一。A. KALTENBRUNNER[1]等以自行車交通流為基礎，對任一自行車服務網點的自行車數量進行提取預測，為動態調度提供了依據；M.BENCHIMOL[2]、劉登濤[3]等以運輸費用最少為目標建立靜態調度模型；R A.RUSSELL[4]、胡列格[5]等在考慮所需運輸車輛數最少的基礎上建立有時間窗的調度模型；柳祖鵬等[6]將貨郎擔問題運用到公共自行車的動態調度問題中來，提供了一種優化站間調度思路；董紅召、吳滿金、秦茜等[7-9]以最大化公共自行車用戶的滿意度為目標建立調度模型，并采用滾動時域調度算法進行求解，實現了公共自行車系統的動態調度。上述文獻多根據用戶滿意度最大化或運輸成本最小化兩大目標建立動、靜態優化調度模型，并針對求解算法做了一定探索。

但是，現有文獻的研究多側重于調度過程的實施環節，而忽略了需求預測環節，且優化模型在量化系統平均用戶滿意度時，沒有考慮到各服務點間因需求差異從而對系統平均滿意度的權重影響也有所不同。因此，考慮調度過程的各環節，筆者嘗試探討基于用戶預約數據的高峰期調度需求預測，并建立最小化運輸成本、最大化用戶滿意度的調度模型，優化調度路徑，為有效解決高峰期公共自行車“借車難、還車難”問題提供參考。

1基于用戶預約數據的高峰期調度需求預測

1.1采集并處理預約數據

1.2讀取并處理歷史數據

首先系統讀取后臺歷史記錄數據，包括借車數據、還車數據以及對應的時間點，然后進行分類統計，區分工作日、周末以及節假日，剔除異常數據后，編成時間序列，最后綜合長期趨勢與季節變動等因素，運用SPSS中ARIMA模型對時間序列進行分析預測，得到下一個高峰期Δt時段內網點i的需求量預測值H(i，Δt)。

相比其他模型，ARIMA模型最明顯的特點是考慮了預測對象由于季節周期性等因素引起的數據序列非平穩現象，通過差分運算、模型定階等步驟使得預測值更精確。

1.3確定網點調度需求量

1) 整合預約數據值和根據歷史數據求得的預測值，確定不同網點各時間段的預測需求量。

O(i，Δt)=R(i，Δt)×α

(1)

(2)

式中：O(i，Δt)為Δt時段內網點i的公共自行車車輛預測需求量(負值表示車樁需求量)；α、β為未預約用戶預留系數，初值可取1.1～1.2，隨歷史數據累計修正。

在方案使用初期，R(i，Δt)

2) 結合網點公共自行車存量，確定最終調度需求量。

V(i，Δt)=O(i，Δt)-Pi

(3)

式中：V(i，Δt)為網點i在Δt時段的公共自行車車輛調度需求量(負值表示車樁需求量)；Pi為各時間段開始前網點i的公共自行車數量。

2公共自行車調度模型建立

2.1調度小區劃分

城市公共自行車系統服務網點布局廣、密度大，導致在運營過程中，面臨調度路徑復雜、隨機誤差大、時效性差等問題[10]。針對以上問題，筆者在充分分析各服務網點時空分布特性后，確立了兩層分區調度方法，將高峰期借還特性相近且距離不大的服務網點劃分為一個小區，每個小區的服務網點個數根據小區整體調度需求靈活設置，但一般不應大于6個。不同層面的調度策略有所差異，小區層面：建立以小區總體需求為基準的小區間軟時間窗調度模型，最終確定調度方案；小區內部：根據小區內服務網點的位置和路徑，采用最短路模型確定調度固定路線。筆者的研究重點是小區層面的調度。

2.2虛擬小區設置

由于調度模型是針對調度小區建立的，且受運輸車輛的容量限制，難免會出現一個調度小區的調度需求量大于運輸車輛的最大容量，為了解決這一困惑，筆者采取設置虛擬小區的方法，并假定虛擬小區的坐標信息與原小區的坐標信息一致，虛擬小區的調度需求量由原小區的調度需求量平均分配。

2.3服務滿意度量化

公共自行車系統的運營效益，與服務質量有直接關系，而由調度服務時間決定的用戶滿意度是衡量服務質量的重要因素之一。用戶的滿意度一般通過借還車過程中的時間消耗值來量化，若在期望時間內完成借還車，則用戶滿意度最大，服務效果最好；若介于期望時間與可接受時間內完成，則用戶滿意度隨著消耗時間的增加而降低；其它情況下，滿意度為0，即用戶不可接受，如圖1。

圖1用戶滿意度與時間的關系Fig.1Relationship between user satisfaction and time

假設運輸車輛到達服務網點i的時刻為ti，則該服務網點的用戶平均滿意度Si(ti)表示如下：

(4)

筆者重點考慮的是高峰期公共自行車系統的調度問題，用戶對時間要求都比較高，但由于各服務點間需求存在一定差異，導致不同服務點對系統的平均滿意度影響程度不一樣，需求大的，其權重影響大，反之亦成立。因此，考慮到各服務點需求差異，系統的平均用戶滿意度則為：

(5)

2.4參數說明

N：調度小區編號{0，1，2，…，n}，其中0表示中心車場；M：虛擬小區編號{n+1，n+2，…，n+m}；K：運輸車輛{1，2，…，p}；

i，j∈N∪M；k∈K；

i∈N∪M;k∈K；

dij：小區i到小區j的實際距離；qi：小區i的調度需求量，調入為正，調出為負；Q：運輸車輛的最大載運量；Rqijk：運輸車輛k從服務網點i到服務網點j車上載運量：

(6)

li：小區i可接受的最晚服務時間；ei：小區i可接受的最早服務時間；Li：小區i的期望最晚服務時間；Ei：小區i的期望最早服務時間；ti：運輸車輛到達小區i的時間；tij：運輸車輛從小區i到小區j的行駛時間；tui：運輸車輛在小區i的裝卸時間；P：權重系數，P1+P2+P3=1，具體數值根據系統測算需求而定；C0：單位運輸車輛的固定成本；C1：運輸車輛單位里程的成本費用；C2：滿意度與成本換算系數，取值大小與系統平均滿意度相關，同時受城市居民平均工資水平、公共自行車系統發展狀況等多因素影響。

2.5調度模型建立

綜上分析，考慮運營固定成本、行駛成本以及用戶滿意度，建立綜合成本最小化的優化調度模型如下：

(7)

s.t.

(8)

(9)

0≤Rqijk-qj≤Q

(10)

(11)

tj=ti+tui+tij

(12)

(13)

目標函數式(7)第1部分為固定成本，C0的取值與人工費用、車輛折舊費用以及其它固定費用等有關；第2部分為行駛成本，其值與單位油耗、實際行駛距離等有關；第3部分為系統總體滿意度；約束條件式(8)表示運輸車輛必須從中心車場出發并開始服務；式(9)表示完成調度任務后，運輸車輛必須從最后一個服務點回到中心車場；式(10)表示運輸車輛服務任一小區時，其原有載運量與該小區調度需求量之和不小于0且不大于運輸車輛的最大載運量；式(11)表示任一調度小區至多由1輛運輸車服務；式(12)表示到達下一服務網點的時刻由上一服務網點的開始服務時刻、服務時長以及兩點間的行程時間決定；式(13)表示運輸車輛服務完某一調度小區后，必須從該小區離開。

2.6算法設計

筆者將采用改進的遺傳算法對調度模型進行求解。在調度優化問題上，遺傳算法相對于其它算法，具有高效、實用性強、魯棒性強等特點，其良好的全局搜索能力，可以快速地將解空間中的全體解搜索出，而不會陷入局部最優解的快速下降陷阱，并且它可以利用內在的并行性，方便進行分布式計算，加快了求解速度[11]。

針對文中的調度模型，算法設計步驟如下[12-14]：

Step1染色體編碼

遺傳算法在進行搜索前，需選擇適當的編碼策略，將解數據表示成基因串結構數據。適合文中調度模型的編碼方式是實數編碼，將需要進行調度的小區用1、2、…、n、n+1、…、n+m表示，求得的解根據運輸車輛最大載運量等約束條件分配給不同的車輛。

Step2生成初始種群

系統隨機產生一系列初始串結構數據作為初始種群。初始種群的數目一般根據經驗得到，一般情況下種群數量越大，生成的解效果越好，但同時也會降低求解速度，其取值通常在20～100之間，本次研究中，算例調度區域相對較小，我們確定初始種群數目為30。

Step3計算適應度值

適應度函數是用來判斷群體中個體優劣程度的指標，其值越大，證明該個體相對更優。根據本文調度模型的特性，選取以下函數計算個體的適應度值。

(14)

式中:f(xi)為某個體(調度方案)的目標函數值，f(x)min為種群中所有個體(調度方案)目標函數的最小值。

Step4選擇算子

筆者采用最經典的選擇方法——輪盤賭算法，該算法選擇個體的概率與其適應度值有關，假設種群個體數量為N，則個體i被選中的概率為：

(15)

Step5交叉操作

從種群中隨機選取兩個個體，通過兩個染色體的交換組合，把父串的優秀特征遺傳給子串，從而得到新的優秀個體。本文假設交叉概率Pc為0.85，采用順序交叉法對個體進行交叉操作。

Step6變異操作

變異操作是為了保持種群的多樣性，本文假設變異概率Pm為0.005，采用2-Opt算法對個體進行變異操作。

Step7終止運算

若進化代數大于預設的遺傳代數，或算法在連續進化一定代數后，個體的適應度值沒有明顯改進，則終止運算。

3實例分析

3.1前期準備

筆者選取了廣州市某區域的公共自行車系統作為調度研究區域。區域內包含中心車場1個，各類站點共27個，其中公建類11個，公交站點類6個，交通樞紐類2個，住宅類7個，休閑類1個，涵蓋類別相對全面。

根據各服務網點坐標、高峰期借還數據進行聚類分析，將研究區域分成10個小區，其中1、5、6小區以公建類為主，2、3、9小區為住宅類，4以交通樞紐類為主，7、8為公交站點類，10為休閑類，各小區的基本信息、各時段的需求預約量以及根據歷史數據求得的各時段需求預測值分別如表1、表2、表3。

整合表2與表3，可以確定需要在不同的時間段，對10個調度小區，共147輛公共自行車進行調度服務，具體如表4。

表1不同調度小區基本信息Table 1Basic information of different service areas

表2不同調度小區各時間段的預約量Table 2Reservations of different service areas in each time section

表3不同調度小區各時間段的預測值Table 3Prediction values of different service areas in each time section

表4不同調度小區各時間段的調度需求量Table 4Scheduling demand of different service areas in each time section

3.2結果分析

分別使用人工經驗方法和文中的優化算法對上述案例進行求解，結果如表5、表6。對比結果顯示，優化后調度方案的綜合成本為42.57元，比優化前調度方案的綜合成本節約了8.45元，即綜合成本降低了16.6%。此外，從表6可以發現，優化后，運輸車輛到達各服務小區開始服務的時刻均在用戶可接受的時間段內，其中小區1、2、5、6處在用戶期望服務的時間段內；換算成滿意度后，除小區8和10外，其它小區的用戶滿意度均在0.5以上，且小區1、2、5、6的滿意度值達到1，系統平均滿意度值由優化前的0.620 5提升到優化后的0.798 5，提升幅度為28.7%，用戶總體較為滿意。

由于本算例選取的研究區域面積不到0.5 km2，是廣州市某片區總規劃用地面積的1/13，因此測算結果中綜合成本的絕對數值較小，倘若將此優化調度模型應用至片區乃至全市整個公共自行車系統，其優化效果將更明顯。

表5優化前后調度方案的對比分析Table 5Contrastive analysis of dispatching schemes before and after optimization

表6優化后運輸車到達各服務點的實際時間Table 6Actual service time which the transport vehicles use to arrive at each service point after optimization

4結語

在城市公共自行車“借車難、還車難”問題愈發突出的大背景下，筆者針對現狀城市公共自行車調度對系統性考慮不足、路徑未經優化等問題，以及高峰期對用戶實際需求缺乏預判使得調度滯后、用戶整體滿意度低的情況，提出基于用戶預約數據的高峰期公共自行車需求預測方法，利用互聯網平臺以及后臺歷史記錄數據，提前預測用戶實際需求，然后在量化平均用戶滿意度的基礎上，建立最小化運輸成本、最大化用戶滿意度的公共自行車調度模型，并采用遺傳算法進行求解。算例結果表明：該算法可以有效地減少系統綜合成本，提升用戶滿意度，對城市公共自行車優化調度具有一定的指導作用。

準確預測用戶需求以便更有針對性的制定調度計劃，可以改善用戶體驗，提升用戶滿意度。考慮天氣、空氣質量等影響用戶選擇自行車出行的指標，可以使需求預測模型更貼近實際，是下一步研究的方向之一。

[1] KALTENBRUNNER A，MEZA R，GRIVOLLA J.Urban cycles and mobility patterns：exploring and predicting trends in a bicycle-based public transport system[J].PervasiveandMobileComputing，2010，6(4)：455-466.

[2] BENCHIMOL M，BENCHIMOL P，CHAPPERT B，et al.Balancing the stations of a self-service“Bike Hire”system[J].RAIRO-OperationsResearch，2011，45(1)：37-61.

[3] 劉登濤，方文道，章堅民，郭明澤.公共自行車交通系統調度算法[J].計算機系統應用，2011，20(9)：112-116.

LIU Dengtao，FANG Wendao，ZHANG Jianmin，GUO Mingze.Scheduling algorithm for public bicycle system[J].ComputerSystems&Applications，2011，20(9)：112-116.

[4] RUSSELL R A.Hybrid Heuristics for the vehicle routing problem with time windows[J].Transportation Science，1995，29(2)：156-166.

[5] 胡列格，夏云，王佳，等.城市公共自行車高峰期需求不均衡的調度優化研究[J].鐵道科學與工程學報，2015 (2)：441-448.

HU Liege，XIA Yun，WANG Jia，et al.Scheduling optimization research on demand imbalance of urban public bicycles during peak period[J].JournalofRailwayScienceandEngineering，2015(2)：441-448.

[6] 柳祖鵬，丁衛東，程逸旻.公共自行車系統站點間調度優化研究[J].城市公共交通，2011(1)：39-42.

LIU Zupeng，DING Weidong，CHENG Yimin.Research of optimal scheduling between stations for public bicycle system[J].UrbanPublicTransport，2011(1)：39-42.

[7] 董紅召，趙敬洋，郭海峰，等.公共慢行系統的動態調度建模與滾動時域調度算法研究[J].公路工程，2009，34(6)：68-71.

DONG Hongzhao，ZHAO Jingyang，GUO Haifeng，et al.Research on the dynamic model and rolling horizon scheduling algorithm for public-use bicycle vehicle scheduling problem[J].HighwayEngineering，2009，34(6)：68-71.

[8] 吳滿金，董紅召，劉東旭，等.公共自行車多目標動態調度建模與算法研究[J].機電工程，2015，32(7)：1006-1010.

WU Manjin，DONG Hongzhao，LIU Dongxu，et al.Research on the dynamic model with multi-objective and algorithm for public rebalance problem[J].JournalofMechanical&ElectricalEngineering， 2015，32(7)：1006-1010.

[9] 秦茜.公共自行車租賃系統調度問題研究[D].北京：北京交通大學，2013.

QIN Xi.TheResearchonRepositioninginaBbike-sharingSystem[D].Beijing：Beijing Jiaotong University，2013.

[10] CHEMLA D，MEUNIER F，CALVO R W.Bike sharing system solving the static rebalancing problem[J].DiscreteOptimization，2013，10(2)：120-146.

[11] GASPERO L D，RENDL A，URLI T.Constraint based approaches for balancing bike sharing systems[J].SpringerBerlinHeidelberg，2013，8124：758-773.

[12] 史彩霞.公共自行車系統運行數據時空分析及智能調度系統的研究[D].杭州：浙江工業大學，2012.

SHI Caixia.AnalysisonRunningDataandResearchintheIntelligentVehicleSchedulingforPublicBicycleSystem[D].Hangzhou：Zhejiang University of Technology，2012.

[13] 李錦霞.公共自行車調度優化研究[D].長沙：長沙理工大學，2013.

LIN Jinxia.TheSchedulingOptimizationStudyofUrbanPublicBicycle[D].Changsha：Changsha University of Science & Technology，2013.

[14] 管娜娜.公共自行車調度路徑優化問題研究[D].成都：西南交通大學，2015.

GUAN Nana.ResearchonPublicBicycleRoutingandSchedulingOptimization[D].Chengdu：Southwest Jiaotong University，2015.

(責任編輯：朱漢容)

Scheduling of Public Bicycle during Peak Period Based on the Customer Reservation Data

JIN Wenzhou，YE Qinhai，HAO Xiaoni

(School of Civil Engineering and Transportation，South China University of Technology，Guangzhou 510640，Guangdong，P.R.China)

The issues of scheduling delay and low customer satisfaction caused by the lack of demand forecast during peak period and the concept of systematic scheduling in the public bicycle system were analyzed.The quantization method of scheduling demand forecast and system average satisfaction of the public bicycle during peak period was discussed; the optimal routing of the public bicycle scheduling was also analyzed.According to the analysis on the scheduling demand forecast model based on the customer reservation data during peak period，the optimal scheduling model to minimize the comprehensive scheduling costs with considering the customer satisfaction level was established，and then an improved Genetic Algorithm was adopted to solve the proposed model.Finally，a case study of the public bicycle system at certain area in Guangzhou was cited to verify the proposed model.Research results show that，compared with the conventional scheduling plan，the comprehensive cost of the proposed model is reduced by 16.6% and the system average customer satisfaction is improved by 28.7%.

traffic and transportation engineering; public bicycle; demand forecast; system average satisfaction; optimal scheduling; genetic algorithm

U492.2+2

A

1674-0696(2017)10-091-06

2016-07-25；

2016-08-29

國家自然科學基金項目(61473122)；中央高校基本科研業務費專項資金項目(2015ZM124)

靳文舟(1960—)，男，吉林四平人，教授，博士，主要從事交通運輸規劃與管理研究。E-mail：ctwzhjin@scut.edu.cn。

10.3969/j.issn.1674-0696.2017.10.15