基于用戶(hù)激勵(lì)的共享單車(chē)調(diào)度策略

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

基于用戶(hù)激勵(lì)的共享單車(chē)調(diào)度策略

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

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

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

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

0 引言

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 基本設(shè)定

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

2.1　問(wèn)題場(chǎng)景

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

圖1　用戶(hù)激勵(lì)下共享單車(chē)調(diào)度工作示意圖

2.2　符號(hào)定義

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

表1　符號(hào)定義

2.3　共享單車(chē)平臺(tái)設(shè)定

2.4　用戶(hù)設(shè)定

2.5　問(wèn)題描述

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

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

3 用戶(hù)激勵(lì)下的共享單車(chē)調(diào)度策略

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

圖2　用戶(hù)激勵(lì)下的共享單車(chē)調(diào)度策略

3.1　任務(wù)生成算法

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

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

else：

3.2　預(yù)算分配算法

3.2.1馬爾可夫決策過(guò)程

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

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

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

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

if ：

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

3.3　任務(wù)分配算法

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

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

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

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

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

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

圖3　工作日與周末的用戶(hù)需求

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

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

4.2　對(duì)比算法

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

本文研究中假設(shè)用戶(hù)需要真實(shí)報(bào)告自身信息，在實(shí)際情況中，用戶(hù)可能會(huì)謊報(bào)自己的目的地、成本等信息以獲得更多的收益，因此后續(xù)將進(jìn)一步設(shè)計(jì)防策略的共享單車(chē)調(diào)度機(jī)制，防止用戶(hù)的策略性行為，以保證用戶(hù)能夠真實(shí)地向平臺(tái)上報(bào)相關(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ì)視角下城市共享單車(chē)發(fā)展對(duì)策研究［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ì)”在中國(guó)的發(fā)展現(xiàn)狀和模式的研究——以共享單車(chē)為例［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] 吳垚，曾菊儒，彭輝，等. 群智感知激勵(lì)機(jī)制研究綜述［J］. 軟件學(xué)報(bào)， 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í)空眾包數(shù)據(jù)管理技術(shù)研究綜述［J］. 軟件學(xué)報(bào)， 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ī)模拼車(chē)算法研究進(jìn)展［J］. 計(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] 杜圣東，李天瑞，楊燕，等. 一種基于序列到序列時(shí)空注意力學(xué)習(xí)的交通流預(yù)測(cè)模型［J］. 計(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ì)算機(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í)的移動(dòng)邊緣計(jì)算任務(wù)卸載研究［J］. 計(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。

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

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