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

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

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

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

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

共享單車調(diào)度；需求預測；用戶激勵；馬爾可夫決策；深度強化學習

0 引言

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

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

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

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

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

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

1 相關工作

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

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

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

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

2 基本設定

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

2.1　問題場景

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

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

2.2　符號定義

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

表1　符號定義

2.3　共享單車平臺設定

2.4　用戶設定

2.5　問題描述

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

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

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

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

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

3.1　任務生成算法

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

算法1 基于LSTM的任務生成算法。

else：

3.2　預算分配算法

3.2.1馬爾可夫決策過程

3.2.2基于DDPG的預算分配算法

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

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

算法2 基于DDPG的預算分配算法。

if ：

輸出每個時間段的預算分配策略.

3.3　任務分配算法

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

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

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

4 實驗與結(jié)果分析

4.1　實驗設定

本文實驗數(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)并不明顯，所以實驗中僅使用工作日AM 7：00到PM 8：00的用戶使用數(shù)據(jù)。

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

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

表2　實驗參數(shù)

4.2　對比算法

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

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

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

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

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

4.3　實驗結(jié)果分析

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

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

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

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

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

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

5 結(jié)語

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

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

[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)濟視角下城市共享單車發(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)濟”在中國的發(fā)展現(xiàn)狀和模式的研究——以共享單車為例［J］. 當代經(jīng)濟， 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］. 軟件學報， 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］. 軟件學報， 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］. 計算機研究與發(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] 杜圣東，李天瑞，楊燕，等. 一種基于序列到序列時空注意力學習的交通流預測模型［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] 余顯，李振宇，孫勝，等. 基于深度強化學習的自適應虛擬機整合方法［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] 盧海峰，顧春華，羅飛，等. 基于深度強化學習的移動邊緣計算任務卸載研究［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。

教育部人文社會科學研究項目（19YJC790111）；教育部哲學社會科學研究后期資助項目（18JHQ060）。

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