石兵，黃茜子，宋兆翔，徐建橋

基于用戶激勵的共享單車調(diào)度策略

石兵1，黃茜子1，宋兆翔1，徐建橋2*

（1.武漢理工大學(xué) 計算機(jī)與人工智能學(xué)院，武漢 430070； 2.海軍工程大學(xué) 信息安全系，武漢 430033）（?通信作者電子郵箱 xujianqiao321@163.com）

針對共享單車的調(diào)度問題，在考慮預(yù)算限制、用戶最大步行距離限制、用戶時空需求以及共享單車分布動態(tài)變化的情況下，提出一種用戶激勵下的共享單車調(diào)度策略，以達(dá)到提高共享單車平臺長期用戶服務(wù)率的目的。該調(diào)度策略包含任務(wù)生成算法、預(yù)算分配算法和任務(wù)分配算法。在任務(wù)生成算法中，使用長短期記憶（LSTM）網(wǎng)絡(luò)預(yù)測用戶未來的單車需求量；在預(yù)算分配算法中，采用深度策略梯度（DDPG）算法來設(shè)計預(yù)算分配策略；任務(wù)分配完預(yù)算后，需要將任務(wù)分配給用戶執(zhí)行，因此在任務(wù)分配算法中使用貪心匹配策略來進(jìn)行任務(wù)分配?；谀Π輪诬嚨臄?shù)據(jù)集進(jìn)行實(shí)驗(yàn)，并把所提策略分別與無預(yù)算限制的調(diào)度策略（即平臺不受預(yù)算限制，可以使用任意金錢激勵用戶將車騎行至目標(biāo)區(qū)域）、貪心的調(diào)度策略、卡車拖運(yùn)下的調(diào)度策略以及未進(jìn)行調(diào)度的情況進(jìn)行對比。實(shí)驗(yàn)結(jié)果表明，與貪心調(diào)度策略和卡車托運(yùn)下的調(diào)度策略相比，用戶激勵下的共享單車調(diào)度策略能有效提高共享單車系統(tǒng)中的用戶服務(wù)率。

共享單車調(diào)度；需求預(yù)測；用戶激勵；馬爾可夫決策；深度強(qiáng)化學(xué)習(xí)

0 引言

共享單車系統(tǒng)（Bike?Sharing System）作為共享經(jīng)濟(jì)中交通出行領(lǐng)域的一個典型例子，在世界各地發(fā)展迅速。共享單車已廣泛應(yīng)用于國內(nèi)外各主要城市的短途通行，有效解決了“最后一公里”的問題，給國內(nèi)外都帶來了很大的經(jīng)濟(jì)效益［1-3］。

由于用戶在時間以及空間上的需求不對稱，導(dǎo)致共享單車平臺在運(yùn)行一段時間后，共享單車的分布不能很好地滿足用戶的需求：有些區(qū)域的共享單車大量積壓，甚至影響路面交通；而有些區(qū)域的共享單車數(shù)量卻很少，導(dǎo)致用戶的需求無法得到滿足。然而，增加共享單車的數(shù)量并不能有效解決上述問題，這不僅會導(dǎo)致許多共享單車空閑，造成資源浪費(fèi)，還會導(dǎo)致道路堵塞，對環(huán)境帶來更大的影響。因此如何有效地對共享單車進(jìn)行調(diào)度來提高共享單車平臺的長期用戶服務(wù)率是平臺需要解決的關(guān)鍵性問題。共享單車調(diào)度問題主要面臨著兩個挑戰(zhàn)：首先，共享單車平臺對于共享單車的調(diào)度具有一定的預(yù)算限制，需要合理地分配預(yù)算資源來使平臺的長期用戶服務(wù)率最大化；其次，用戶的時空需求也在不斷地發(fā)生變化，各個區(qū)域的共享單車供應(yīng)量也會隨著用戶的騎行而不斷發(fā)生變化。因此需要在預(yù)算限制下，對共享單車進(jìn)行調(diào)度以滿足不斷變化的用戶需求，提高平臺的長期用戶服務(wù)率。

傳統(tǒng)的共享單車調(diào)度方法是由平臺的工作人員通過卡車進(jìn)行拖運(yùn)調(diào)度［4］。然而，在實(shí)際情況下，共享單車通常無規(guī)律地分布在不同區(qū)域，這給卡車托運(yùn)帶來不便。共享單車的調(diào)度區(qū)域之間的距離通常不遠(yuǎn)，滿足一般的步行距離［5］，所以平臺可以通過一定的金錢激勵，鼓勵騎行的用戶在滿足自身目的地的前提下適當(dāng)繞行將單車歸還到目標(biāo)區(qū)域，再步行回目的地。本文將對此問題進(jìn)行研究，設(shè)計用戶激勵下的共享單車調(diào)度策略，從而最大化平臺的長期用戶服務(wù)率。

具體地說，本文將在預(yù)算限制、用戶步行距離限制和用戶需求變化情況下，設(shè)計激勵用戶參與的共享單車調(diào)度策略，最大化平臺的長期用戶服務(wù)率。本文主要工作如下：

1）在對共享單車的調(diào)度問題進(jìn)行數(shù)學(xué)描述后，設(shè)計了高效的激勵用戶參與的共享單車調(diào)度策略，該策略包含任務(wù)生成算法、預(yù)算分配算法和任務(wù)分配算法。首先通過基于長短期記憶（Long Short?Term Memory，LSTM）的任務(wù)生成算法預(yù)測用戶在每個時間段各個區(qū)域的單車需求量；再通過預(yù)算分配算法為每個時間段的調(diào)度任務(wù)分配預(yù)算，該過程是一個序貫決策過程，可以建模為馬爾可夫決策過程（Markov Decision Process， MDP），在每個時間段為每個任務(wù)分配預(yù)算的動作空間是連續(xù)的，因此使用適合解決高維連續(xù)動作空間的深度確定性策略梯度（Deep Deterministic Policy Gradient， DDPG）算法來分配預(yù)算；最后通過基于貪心策略的任務(wù)分配算法合理地將任務(wù)分配給用戶。

2）在摩拜單車數(shù)據(jù)集上對本文的調(diào)度策略進(jìn)行實(shí)驗(yàn)評估，發(fā)現(xiàn)任務(wù)生成算法對用戶未來的單車需求量預(yù)測與真實(shí)值較為吻合。在不同預(yù)算和不同初始單車供應(yīng)量的條件下，將本文調(diào)度策略與貪心調(diào)度算法、無預(yù)算限制的調(diào)度算法、卡車拖運(yùn)的調(diào)度算法進(jìn)行了兩組對比實(shí)驗(yàn)，結(jié)果表明本文提出的用戶激勵下的單車調(diào)度策略能取得除無預(yù)算限制外最好的表現(xiàn)，對共享單車的調(diào)度問題有現(xiàn)實(shí)的指導(dǎo)意義。

1 相關(guān)工作

在用戶激勵下的共享單車調(diào)度策略中，給予用戶一定的金錢獎勵以激勵用戶去執(zhí)行調(diào)度任務(wù)，這本質(zhì)上是一種眾包管理技術(shù)。對于這種時空眾包問題，學(xué)術(shù)上也取得了一些成果。吳垚等［6］講解了群智感知激勵機(jī)制相關(guān)的工作；童詠昕等［7］對時空眾包在數(shù)據(jù)管理中的應(yīng)用問題進(jìn)行了綜述，同時他們還在文獻(xiàn)［8］中發(fā)現(xiàn)貪心算法在時空眾包類任務(wù)中可以取得較好的效果；徐毅等［9］研究了共享出行中的路線規(guī)劃問題，同樣適用于本文的單車調(diào)度問題。

時空眾包問題中關(guān)于共享單車調(diào)度問題的研究也取得了一些成果。Aeschbach等［10］比較早地提出了在沒有工人操作卡車或共享單車拖車的情況下，讓用戶參與到共享單車的調(diào)度中，提出了四種不同的控制策略，并通過在一個基于倫敦巴克萊共享單車租賃的真實(shí)系統(tǒng)模型上的廣泛模擬評估了其有效性。Fricker等［11］提出了同質(zhì)共享單車的隨機(jī)模型，研究了用戶選擇的隨機(jī)性對滿站或空站共享單車數(shù)量的影響。他們在研究中表明，簡單的激勵措施，如建議用戶將共享單車返還到兩個站點(diǎn)中負(fù)荷最小的站點(diǎn)，可以指數(shù)性地改善基于卡車調(diào)度的方法。Caggiani等［12］將零車時間和滿站時間作為關(guān)鍵性能指標(biāo)，用來反映站內(nèi)車輛短缺的持續(xù)時間和停車位無法使用的持續(xù)時間，并依次提出了一個優(yōu)化模型，使共享單車系統(tǒng)能夠在有限的預(yù)算下最大限度地提高平臺的長期用戶服務(wù)率。Tong等［13］考慮到時空眾包問題中任務(wù)和工作者都是動態(tài)的，提出了一種強(qiáng)化學(xué)習(xí)的方法解決時空眾包中的任務(wù)分配問題。Li等［14］考慮到眾包任務(wù)與工人的差異性，提出了一種基于強(qiáng)化學(xué)習(xí)的數(shù)據(jù)標(biāo)簽框架，使用強(qiáng)化學(xué)習(xí)方法對任務(wù)分配和任務(wù)選擇進(jìn)行建模，提高了眾包任務(wù)的收益。Cheng等［15］在時空眾包問題中考慮眾包工作者競爭之間的公平性，提出了一種基于預(yù)測的匹配方案，解決了眾包競爭中的易勝問題。Yang等［16］在拼車出行場景下，提出了一種強(qiáng)化學(xué)習(xí)方法解決司機(jī)與乘客的匹配半徑優(yōu)化問題。Zhao等［17］提出了一個兩階段的數(shù)據(jù)驅(qū)動框架，通過預(yù)測未來的時空眾包任務(wù)并進(jìn)行匹配，從而提高匹配的任務(wù)數(shù)量。

在關(guān)于用戶參與下共享單車調(diào)度的具體問題研究中，Ban等［18］提出了一套仿真系統(tǒng)，以測試用戶參與下的共享單車調(diào)度策略中不同用戶參數(shù)對用戶服務(wù)率的影響，如激勵給用戶的價錢、用戶的參與率和額外最大步行距離等。Li等［19］為緩解騎行高峰期的供需矛盾，通過對逆峰騎行者進(jìn)行獎勵以及對平臺和政府進(jìn)行雙向激勵的方式建立了相關(guān)分析模型。Reiss等［20］通過分析慕尼黑共享單車的定位數(shù)據(jù)，考慮同時使用基于價格折扣的用戶調(diào)度策略與人工調(diào)度策略，以在調(diào)度過程中減少碳排放量和平臺運(yùn)營成本。Huang等［21］提出了一種借助已在共享單車平臺注冊的志愿者來對共享單車進(jìn)行調(diào)度的方法，并且利用稀疏網(wǎng)絡(luò)來指導(dǎo)志愿者的調(diào)度運(yùn)動。Pan等［22］為用戶起始區(qū)域的周圍區(qū)域定價，給予一定的金錢激勵用戶去其他區(qū)域騎共享單車，并提出了一種新的深度強(qiáng)化學(xué)習(xí)框架來激勵用戶重新平衡這些系統(tǒng)。他們雖然考慮了整個系統(tǒng)的長期收益，但只考慮了用戶在取車時的調(diào)度策略，并沒有考慮到用戶還車時的調(diào)度策略以及用戶最大步行距離的限制。Duan等［23］擴(kuò)展了Pan等［22］的深度強(qiáng)化學(xué)習(xí)框架來促進(jìn)用戶激勵，并以自適應(yīng)的方式來將起始地和目的地激勵措施結(jié)合。他們雖然考慮到了用戶在還車時的調(diào)度策略，但只是將共享單車歸還到相鄰的區(qū)域，并沒有考慮到用戶最大步行距離的限制。

針對現(xiàn)有工作存在的一些局限，本文主要研究在一定預(yù)算限制、用戶最大步行距離限制、用戶時空需求動態(tài)變化以及共享單車分布動態(tài)變化的情況下，為用戶生成調(diào)度任務(wù)并對調(diào)度任務(wù)進(jìn)行預(yù)算分配，最后將調(diào)度任務(wù)合理地分配給用戶以實(shí)現(xiàn)對共享單車的調(diào)度，從而提高平臺的長期用戶服務(wù)率。

2 基本設(shè)定

本章介紹了用戶激勵下的共享單車調(diào)度問題，并給出了該問題的相關(guān)設(shè)定和相關(guān)符號的定義。

2.1　問題場景

激勵用戶參與的共享單車調(diào)度問題主要是指共享單車平臺將調(diào)度任務(wù)眾包給用戶，給予用戶一定的金錢激勵，激勵用戶將共享單車歸還到合適的區(qū)域，從而達(dá)到對共享單車進(jìn)行調(diào)度的目的，工作示意圖如圖1所示。其中：虛線表示用戶不執(zhí)行調(diào)度任務(wù)的路線；實(shí)線表示用戶執(zhí)行調(diào)度任務(wù)的路線，通過給予用戶一定金錢激勵用戶將單車歸還到調(diào)度任務(wù)所在區(qū)域，完成任務(wù)后用戶再步行到自身目的地。

圖1　用戶激勵下共享單車調(diào)度工作示意圖

2.2　符號定義

本文主要數(shù)學(xué)符號如表1所示。

表1　符號定義

2.3　共享單車平臺設(shè)定

2.4　用戶設(shè)定

2.5　問題描述

對于調(diào)度任務(wù)的眾包，在用戶的時空需求不斷發(fā)生變化時，各個區(qū)域中共享單車的數(shù)量只受用戶騎行的影響，則有：

調(diào)度策略的目標(biāo)是最大化平臺的長期用戶服務(wù)率，即最小化未騎到車的用戶數(shù)，表示為：

3 用戶激勵下的共享單車調(diào)度策略

在用戶激勵下的共享單車調(diào)度策略中，共享單車平臺通過合理地預(yù)測共享單車的用戶需求量從而為用戶生成調(diào)度任務(wù)，然后在有限的預(yù)算下合理地為每個任務(wù)分配預(yù)算，最后將調(diào)度任務(wù)分配給用戶。因此用戶激勵下的共享單車調(diào)度策略主要分為三個部分：任務(wù)生成算法、預(yù)算分配算法以及任務(wù)分配算法，如圖3所示。

圖2　用戶激勵下的共享單車調(diào)度策略

3.1　任務(wù)生成算法

任務(wù)生成算法基于用戶歷史使用數(shù)據(jù)對各個區(qū)域的用戶需求進(jìn)行預(yù)測，再與各個區(qū)域現(xiàn)有的單車數(shù)量比較分析，進(jìn)而求得缺車需求，即生成調(diào)度任務(wù)。

算法1 基于LSTM的任務(wù)生成算法。

else：

3.2　預(yù)算分配算法

3.2.1馬爾可夫決策過程

3.2.2基于DDPG的預(yù)算分配算法

DDPG算法［29］是谷歌DeepMind團(tuán)隊(duì)提出的一種以確定性策略梯度（Deterministic Policy Gradient，DPG）算法［30］為基礎(chǔ)的深度確定性策略梯度算法，可以很好地解決高維狀態(tài)空間以及連續(xù)的動作空間的問題?，F(xiàn)有研究中也有許多研究使用DDPG算法解決實(shí)際問題［31-32］，并且能取得比較好的效果，因此本文基于DDPG算法來實(shí)現(xiàn)用戶激勵下的共享單車調(diào)度策略中的預(yù)算分配算法。

對于策略和價值網(wǎng)絡(luò)的權(quán)重參數(shù)更新如下：

算法2 基于DDPG的預(yù)算分配算法。

if ：

輸出每個時間段的預(yù)算分配策略.

3.3　任務(wù)分配算法

在單個時間段內(nèi)，當(dāng)調(diào)度任務(wù)生成并對其分配預(yù)算后，需要將調(diào)度任務(wù)分配給當(dāng)前時間段可執(zhí)行的用戶。任務(wù)分配算法需要在一定的預(yù)算限制和用戶的最大步行距離限制下，使用戶與調(diào)度任務(wù)盡可能多地匹配。

傳統(tǒng)的二部圖匹配中難以附加預(yù)算限制的約束條件，所以在匹配過程中可能為了保證完備匹配的結(jié)果選擇更遠(yuǎn)的調(diào)度任務(wù)從而造成成本增加，導(dǎo)致在預(yù)算限制下，本可以執(zhí)行調(diào)度任務(wù)的用戶因完備匹配的結(jié)果而無法執(zhí)行調(diào)度任務(wù)，所以二部圖匹配并不適用于有預(yù)算限制的任務(wù)分配算法。而貪心匹配策略能保證在預(yù)算限制下的局部最優(yōu)的匹配，即在預(yù)算限制下，使執(zhí)行調(diào)度任務(wù)的用戶數(shù)最大化。因?yàn)榛谪澬钠ヅ洳呗缘娜蝿?wù)分配算法中，依據(jù)貪心策略找到最小預(yù)算的用戶?任務(wù)匹配對，直至預(yù)算耗盡。因此，本文的任務(wù)分配算法適合基于貪心匹配策略來執(zhí)行調(diào)度任務(wù)的分配，基于貪心匹配策略的任務(wù)分配算法的偽碼如算法3所示。

算法3 基于貪心匹配策略的任務(wù)分配算法。

4 實(shí)驗(yàn)與結(jié)果分析

4.1　實(shí)驗(yàn)設(shè)定

本文實(shí)驗(yàn)數(shù)據(jù)采用摩拜單車數(shù)據(jù)集（數(shù)據(jù)集來源為https：//www.heywhale.com/mw/dataset/5eb6787e366f4d002d77c331/file）。每個數(shù)據(jù)包含以下信息：訂單ID、單車ID、用戶ID、用戶騎行起始時間、結(jié)束時間和用戶起始位置、結(jié)束位置（由經(jīng)度和緯度指定）等。數(shù)據(jù)集包含一個月的用戶使用數(shù)據(jù)，工作日和周末的用戶需求曲線呈現(xiàn)不同的特征。根據(jù)圖3可知，工作日的用戶需求數(shù)據(jù)在一天內(nèi)會呈現(xiàn)雙峰，具有一定的規(guī)律性，同時在時間上不平衡的用戶需求與本文的研究背景相似，而周末的用戶需求對于上述規(guī)律的呈現(xiàn)并不明顯，所以實(shí)驗(yàn)中僅使用工作日AM 7：00到PM 8：00的用戶使用數(shù)據(jù)。

圖3　工作日與周末的用戶需求

圖4　區(qū)域劃分及編號

表2　實(shí)驗(yàn)參數(shù)

4.2　對比算法

本文將用戶激勵下的共享單車調(diào)度策略與無預(yù)算限制下的調(diào)度、貪心策略調(diào)度、卡車拖運(yùn)下的共享單車調(diào)度策略以及未進(jìn)行調(diào)度的情況對比。

1）無預(yù)算限制下的調(diào)度策略：無預(yù)算限制下的調(diào)度策略是指在預(yù)算分配算法中平臺不受預(yù)算限制，可以使用任意金錢對調(diào)度任務(wù)進(jìn)行預(yù)算分配，任務(wù)生成算法以及任務(wù)分配算法與本文的方法保持一致。由于擁有無限預(yù)算激勵用戶完成調(diào)度任務(wù)，此算法性能是最好的。

2）貪心策略調(diào)度：Tong等［8］在研究中表明貪心策略對時空眾包問題能夠取得很好的效果，因此本文使用貪心策略調(diào)度與本文用戶激勵下的共享單車調(diào)度策略進(jìn)行對比。貪心策略調(diào)度是指將本文用戶激勵下的共享單車調(diào)度策略中的預(yù)算分配算法改為基于貪心策略的預(yù)算分配，任務(wù)生成算法以及任務(wù)分配算法與本文的方法保持一致。

3）卡車拖運(yùn)下的共享單車調(diào)度策略：對于卡車調(diào)度共享單車，平臺在每個時間段決策卡車前往哪個區(qū)域進(jìn)行調(diào)度以及在該區(qū)域裝載或卸載的共享單車數(shù)量，來提高平臺的長期用戶服務(wù)率。該過程同樣是一個序貫決策過程，因此可以建模為MDP，并且卡車拖運(yùn)的調(diào)度策略只涉及對卡車的調(diào)度算法，不用生成與分配調(diào)度任務(wù)。與用戶激勵下的調(diào)度策略不同，卡車的調(diào)度算法并不需要將缺車需求眾包給用戶，只需要合理的調(diào)度卡車，以提高單車長期利用率。

4）未進(jìn)行調(diào)度：即平臺不執(zhí)行任何調(diào)度操作。

4.3　實(shí)驗(yàn)結(jié)果分析

圖5為根據(jù)某區(qū)域內(nèi)用戶的歷史需求信息預(yù)測該區(qū)域內(nèi)的未來用戶需求信息的訓(xùn)練結(jié)果，虛線左側(cè)為訓(xùn)練數(shù)據(jù)，右側(cè)為預(yù)測數(shù)據(jù)。由圖5可知，基于LSTM模型可以很好地擬合一個區(qū)域內(nèi)共享單車用戶需求的周期性變化，得到接近真實(shí)用戶需求的預(yù)測結(jié)果，為后續(xù)的用戶執(zhí)行調(diào)度任務(wù)提供較為準(zhǔn)確的用戶需求數(shù)據(jù)支撐。

圖5　LSTM預(yù)測的用戶需求數(shù)據(jù)

接著從不同的預(yù)算限制和不同的單車初始供應(yīng)量兩個方面進(jìn)行對比實(shí)驗(yàn)。圖6顯示了當(dāng)各個區(qū)域的初始共享單車供應(yīng)量設(shè)定為5，時間周期設(shè)置為78個時間段時，在不同預(yù)算下，未騎到車的用戶數(shù)變化情況。隨著預(yù)算不斷增加，共享單車平臺未騎到車的用戶數(shù)會隨之減少，這是因?yàn)楫?dāng)預(yù)算增加時，可激勵更多的用戶去執(zhí)行調(diào)度任務(wù)。從圖6中可以看到，用戶激勵下的共享單車調(diào)度策略始終能取得最好的性能。當(dāng)預(yù)算較少時，用戶激勵下的共享單車調(diào)度策略、卡車拖運(yùn)下的共享單車調(diào)度策略以及貪心預(yù)算分配的共享單車調(diào)度策略相較于其他預(yù)算取得的效果較為接近，這是因?yàn)轭A(yù)算較少時，沒有足夠的預(yù)算去合理分配給各個時間段，而當(dāng)預(yù)算增加時，用戶激勵下的共享單車調(diào)度策略能夠合理的將預(yù)算分配給各個時間段，使平臺的長期用戶服務(wù)率更高。總而言之，本文用戶激勵下的共享單車調(diào)度策略在不同的預(yù)算限制下，相較于其他調(diào)度策略都能取得最好的效果。

圖6　不同預(yù)算限制下未騎到車的用戶數(shù)

圖7顯示了當(dāng)共享單車平臺的預(yù)算限制設(shè)定為1 000，時間周期設(shè)置為78時，在不同單車初始供應(yīng)量下，未騎到車的用戶數(shù)變化情況。從圖7可以看出，所有調(diào)度策略的未騎到車的用戶數(shù)都會隨區(qū)域內(nèi)共享單車的初始供應(yīng)量的增加而減少。這是因?yàn)楫?dāng)區(qū)域內(nèi)共享單車的供應(yīng)量增加時，平臺的缺車需求便會降低，未騎到車的用戶數(shù)也會減少。同時，由圖7可知，除了無預(yù)算限制的調(diào)度策略之外，本文用戶激勵下的共享單車調(diào)度策略在提高平臺的用戶服務(wù)數(shù)方面都能取得最好的效果。而對于無預(yù)算限制的調(diào)度策略，即使在沒有預(yù)算限制限制的情況下，未騎到車的用戶數(shù)仍然不能降為0，這表明不是所有的調(diào)度任務(wù)都會被用戶執(zhí)行，這是因?yàn)檎{(diào)度任務(wù)的個數(shù)可能會大于可執(zhí)行調(diào)度任務(wù)的用戶數(shù)，且用戶有最大步行距離的限制，即使給用戶很多的金錢激勵，用戶也不愿去執(zhí)行調(diào)度任務(wù)。

圖7　不同共享單車初始供應(yīng)量情況下未騎到車的用戶數(shù)

5 結(jié)語

本文研究了用戶激勵下的共享單車調(diào)度策略，在有限預(yù)算以及最大步行距離的限制下制定合理的調(diào)度策略以最大化平臺長期的用戶服務(wù)率。本文將用戶激勵下的共享單車調(diào)度策略分為三個步驟完成，即任務(wù)生成算法、預(yù)算分配算法和任務(wù)分配算法。對于任務(wù)生成算法，基于LSTM模型對用戶未來需求進(jìn)行預(yù)測，預(yù)測結(jié)果接近真實(shí)用戶對需求，為后續(xù)的調(diào)度策略算法提供了較為準(zhǔn)確的數(shù)據(jù)支撐；對于預(yù)算分配算法，由于其問題特性可以將其建模為馬爾可夫決策過程，因此基于深度強(qiáng)化學(xué)習(xí)算法DDPG來解決；對于任務(wù)分配算法，由于預(yù)算的限制使得二部圖匹配的性能比貪心策略差，因此基于貪心匹配策略來執(zhí)行調(diào)度任務(wù)的分配。使用摩拜單車的真實(shí)數(shù)據(jù)集分別在不同預(yù)算和不同初始單車供應(yīng)量的條件下進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文用戶激勵下的共享單車調(diào)度策略的性能均僅次于無預(yù)算限制的調(diào)度策略。這說明本文用戶激勵下的共享單車調(diào)度策略具有現(xiàn)實(shí)意義，特別是在共享單車使用量峰值較大的地區(qū)，能夠有效提高平臺長期的用戶服務(wù)率。

本文研究中假設(shè)用戶需要真實(shí)報告自身信息，在實(shí)際情況中，用戶可能會謊報自己的目的地、成本等信息以獲得更多的收益，因此后續(xù)將進(jìn)一步設(shè)計防策略的共享單車調(diào)度機(jī)制，防止用戶的策略性行為，以保證用戶能夠真實(shí)地向平臺上報相關(guān)信息。

[1] DEMAIO P. Bike?sharing： history， impacts， models of provision， and future［J］. Journal of Public Transportation， 2009， 12（4）： 41-56.

[2] 李琨浩. 基于共享經(jīng)濟(jì)視角下城市共享單車發(fā)展對策研究［J］. 城市， 2017（3）： 66-69.（LI K H. Research on the development countermeasures of city shared bicycles from the perspective of sharing economy［J］. City， 2017（3）： 66-69.）

[3] 王怡蘇.“共享經(jīng)濟(jì)”在中國的發(fā)展現(xiàn)狀和模式的研究——以共享單車為例［J］. 當(dāng)代經(jīng)濟(jì)， 2017（17）： 140-141.（WANG Y S. Research on development status and model of “sharing economy” in China ― taking shared bicycle as an example［J］. Contemporary Economics， 2017（17）： 140-141.）

[4] PFROMMER J， WARRINGTON J， SCHILDBACH G， et al. Dynamic vehicle redistribution and online price incentives in shared mobility systems［J］. IEEE Transactions on Intelligent Transportation Systems， 2014， 15（4）： 1567-1578.

[5] SHAHEEN S A， GUZMAN S， ZHANG H. Bikesharing in Europe， the Americas， and Asia： past， present， and future［J］. Transportation Research Record， 2010， 2143（1）： 159-167.

[6] 吳垚，曾菊儒，彭輝，等. 群智感知激勵機(jī)制研究綜述［J］. 軟件學(xué)報， 2016， 27（8）： 2025-2047.（WU Y， ZENG J R， PENG H， et al. Survey on incentive mechanisms for crowd sensing［J］. Journal of Software， 2016， 27（8）：2025-2047.）

[7] 童詠昕，袁野，成雨蓉，等. 時空眾包數(shù)據(jù)管理技術(shù)研究綜述［J］. 軟件學(xué)報， 2017， 28（1）： 35-58.（TONG Y X， YUAN Y， CHENG Y R， et al. Survey on spatiotemporal crowdsourced data management techniques［J］. Journal of Software， 2017， 28（1）： 35-58.）

[8] TONG Y X， SHE J Y， DING B L， et al. Online minimum matching in real?time spatial data： experiments and analysis［J］. Proceedings of the VLDB Endowment， 2016， 9（12）： 1053-1064.

[9] 徐毅，童詠昕，李未. 大規(guī)模拼車算法研究進(jìn)展［J］. 計算機(jī)研究與發(fā)展， 2020， 57（1）： 32-52.（XU Y， TONG Y X， LI W. Recent progress in large?scale ridesharing algorithms［J］. Journal of Computer Research and Development， 2020， 57（1）： 32-52.）

[10] AESCHBACH P， ZHANG X J， GEORGHIOU A， et al. Balancing bike sharing systems through customer cooperation ― a case study on London’s Barclays Cycle Hire［C］// Proceeding of the 54th IEEE Conference on Decision and Control. Piscataway： IEEE， 2015： 4722-4727.

[11] FRICKER C， GAST N. Incentives and redistribution in homogeneous bike?sharing systems with stations of finite capacity［J］. EURO Journal on Transportation and Logistics， 2016， 5（3）： 261-291.

[12] CAGGIANI L， CAMPOREALE R， MARINELLI M， et al. User satisfaction based model for resource allocation in bike?sharing systems［J］. Transport Policy， 2019， 80： 117-126.

[13] TONG Y X， ZENG Y X， DING B L， et al. Two?sided online micro?task assignment in spatial crowdsourcing［J］. IEEE Transactions on Knowledge and Data Engineering， 2021， 33（5）： 2295-2309.

[14] LI K Y， LI G L， WANG Y， et al. CrowdRL： an end?to?end reinforcement learning framework for data labelling［C］// Proceeding of the IEEE 37th International Conference on Data Engineering. Piscataway： IEEE， 2021： 289-300.

[15] CHENG H， WED S Y， ZHANG L Y， et al. Engaging drivers in ride hailing via competition： a case study with arena［C］// Proceeding of the 22nd IEEE International Conference on Mobile Data Management. Piscataway： IEEE， 2021： 19-28.

[16] YANG H， QIN X R， KE J T， et al. Optimizing matching time interval and matching radius in on?demand ride?sourcing markets［J］. Transportation Research Part B： Methodological， 2020， 131： 84-105.

[17] ZHAO Y， ZHENG K， CUI Y， et al. Predictive task assignment in spatial crowdsourcing： a data?driven approach［C］// Proceeding of the IEEE 36th International Conference on Data Engineering. Piscataway： IEEE， 2020： 13-24.

[18] BAN S， HYUN K H. Designing a user participation?based bike rebalancing service［J］. Sustainability， 2019， 11（8）： No.2396.

[19] LI L F， SHAN M Y. Bidirectional incentive model for bicycle redistribution of a bicycle sharing system during rush hour［J］. Sustainability， 2016， 8（12）： No.1299.

[20] REISS S， BOGENBERGER K. A relocation strategy for Munich’s bike sharing system： combining an operator?based and a user?based scheme［J］. Transportation Research Procedia， 2017， 22： 105-114.

[21] HUANG J J. CHOU M C， TEO C P. Bike?repositioning using volunteers： crowd sourcing with choice restriction［C］// Proceeding of the 35th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2021： 11844-11852.

[22] PAN L， CAI Q P， FANG Z X， et al. A deep reinforcement learning framework for rebalancing dockless bike sharing systems［C］// Proceeding of the 33rd AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2019： 1393-1400.

[23] DUAN Y B， WU J. Optimizing rebalance scheme for dock?less bike sharing systems with adaptive user incentive［C］// Proceeding of the 20th IEEE International Conference on Mobile Data Management. Piscataway： IEEE， 2019： 176-181.

[24] SINGLA A， SANTONI M， BARTóK G， et al. Incentivizing users for balancing bike sharing systems［C］// Proceeding of the 29th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2015： 723-729.

[25] SUTSKEVER I， VINYALS O， LE Q V. Sequence to sequence learning with neural networks［C］// Proceeding of the 27th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2014： 3104-3112.

[26] DONG C J， XIONG Z H， SHAO C F， et al. A spatial?temporal? based state space approach for freeway network traffic flow modelling and prediction［J］. Transportmetrica A： Transport Science， 2015， 11（7）： 547-560.

[27] YAO H X， TANG X F， WEI H， et al. Revisiting spatial?temporal similarity： a deep learning framework for traffic prediction［C］// Proceeding of the 33rd AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2019： 5668-5675.

[28] 杜圣東，李天瑞，楊燕，等. 一種基于序列到序列時空注意力學(xué)習(xí)的交通流預(yù)測模型［J］. 計算機(jī)研究與發(fā)展， 2020， 57（8）： 1715-1728.（DU S D， LI T R， YANG Y， et al. A sequence?to? sequence spatial?temporal attention learning model for urban traffic flow prediction［J］. Journal of Computer Research and Development， 2020， 57（8）： 1715-1728.）

[29] LILLICRAP T P， HUNT J J， PRITZEL A， et al. Continuous control with deep reinforcement learning［EB/OL］.（2019-07-05）［2021-09-23］.https：//arxiv.org/pdf/1509.02971.pdf.

[30] SILVER D， LEVER G， HEESS N， et al. Deterministic policy gradient algorithms［C］// Proceeding of the 31st International Conference on Machine Learning. New York： JMLR.org， 2014： 387-395.

[31] 余顯，李振宇，孫勝，等. 基于深度強(qiáng)化學(xué)習(xí)的自適應(yīng)虛擬機(jī)整合方法［J］. 計算機(jī)研究與發(fā)展， 2021， 58（12）： 2783-2797.（YU X， LI Z Y， SUN S， et al. Adaptive virtual machine consolidation method based on deep reinforcement learning［J］. Journal of Computer Research and Development， 2021， 58（12）： 2783-2797.）

[32] 盧海峰，顧春華，羅飛，等. 基于深度強(qiáng)化學(xué)習(xí)的移動邊緣計算任務(wù)卸載研究［J］. 計算機(jī)研究與發(fā)展， 2020， 57（7）： 1539-1554.（LU H F， GU C H， LUO F， et al. Research on task offloading based on deep reinforcement learning in mobile edge computing［J］. Journal of Computer Research and Development， 2020， 57（7）： 1539-1554.）

User incentive based bike?sharing dispatching strategy

SHI Bing1， HUANG Xizi1， SONG Zhaoxiang1， XU Jianqiao2*

（1，，430070，；2，，430033，）

To address the dispatching problem of bike?sharing， considering the budget constraints， user maximum walking distance restrictions， user temporal and spatial demands and dynamic changes in the distribution of shared bicycles， a bike?sharing dispatching strategy with user incentives was proposed to improve the long?term user service rate of the bike?sharing platform. The dispatching strategy consists of a task generation algorithm， a budget allocation algorithm and a task allocation algorithm. In the task generation algorithm， the Long Short?Term Memory （LSTM） network was used to predict the future bike demand of users； in the budget allocation algorithm， the Deep Deterministic Policy Gradient （DDPG） algorithm was used to design a budget allocation strategy； after the budget was allocated to the tasks， the tasks needed to be allocated to the user for execution， so a greedy matching strategy was used for task allocation. Experiments were carried out on the Mobike dataset to compare the proposed strategy with the dispatching strategy with unlimited budget （that is， the platform is not limited by budget and can use any money to encourage users to ride to the target area）， the greedy dispatching strategy， the dispatching strategy with truck hauling， and the situation without dispatching. Experimental results show that the proposed dispatching strategy with user incentive can effectively improve the service rate in the bike?sharing system compared to the greedy dispatching strategy and dispatching strategy with truck hauling.

bike?sharing dispatching; demand prediction; user incentive; Markov decision; deep reinforcement learning

This work is partially supported by Humanity and Social Science Research Foundation of Ministry of Education of China （19YJC790111）， Philosophy and Social Science Post?Foundation of Ministry of Education （18JHQ060）.

SHI Bing， born in 1982， Ph. D.， professor. His research interests include artificial intelligence， multi?agent systems.

HUANG Xizi， born in 1997， M. S. candidate. Her research interests include artificial intelligence， multi?agent systems.

SONG Zhaoxiang， born in 1997， M. S. candidate. His research interests include artificial intelligence， multi?agent systems.

XU Jianqiao， born in 1979， M. S.， lecturer. His research interests include network and information security， artificial intelligence.

TP181

A

1001-9081（2022）11-3395-09

10.11772/j.issn.1001-9081.2021122109

2021?12?15；

2022?01?18；

2022?01?24。

教育部人文社會科學(xué)研究項(xiàng)目（19YJC790111）；教育部哲學(xué)社會科學(xué)研究后期資助項(xiàng)目（18JHQ060）。

石兵（1982—），男，江蘇泰興人，教授，博士，CCF會員，主要研究方向：人工智能、多智能體系統(tǒng)；黃茜子（1997—），女，湖北咸寧人，碩士研究生，主要研究方向?yàn)椋喝斯ぶ悄?、多智能體系統(tǒng)；宋兆翔（1997—），男，湖北孝感人，碩士研究生，主要研究方向：人工智能、多智能體系統(tǒng)；徐建橋（1979—），男，湖北武漢人，講師，碩士，主要研究方向：網(wǎng)絡(luò)與信息安全、人工智能。