覃文杰

摘 要：隨著滴滴、Uber等打車軟件的興起，對于出租車供應(yīng)量的評估需求也越來越大。出租車的供應(yīng)量評估綜合是考慮不同地區(qū)的可用出租車數(shù)量和出租車需求，得到整體出租車供應(yīng)量的分布作為車輛調(diào)度的依據(jù)，達(dá)到提高服務(wù)質(zhì)量的目的。本文定義了出租車/乘客密度的計(jì)算公式以及供應(yīng)量的計(jì)算公式，并將它們應(yīng)用在上海市的路網(wǎng)數(shù)據(jù)和真實(shí)出租車軌跡數(shù)據(jù)集上，分別求得各個區(qū)域可用出租車的密度和乘客的密度，然后得出上海市整體的出租車供應(yīng)量情況。實(shí)驗(yàn)證明了該方法的有效性。

關(guān)鍵詞： 路網(wǎng)； 出租車； K近鄰查詢； 評估方法； 大數(shù)據(jù)

中圖分類號：TP931 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）07-0231-03

Abstract： The demand of taxi supply evaluation increases with the rapid development of location based services like Uber. For the purpose of increasing service quality， taxi supply evaluation should take the amount of taxi available and the needs of the passengers both into account， and calculate the distribution of taxi supply as the basis of vehicle scheduling. In this paper， the density formula of taxis/passengers and supply evaluation formula are proposed. We apply these formulas to the road networks of Shanghai and the real track of taxi datasets， and prove the effectiveness of our method by experiment.

Key words： road networks； taxi； k nearest neighbor query； evaluation； big data

1 引言

近年來滴滴、Uber等新興交通方式發(fā)展迅猛，在人們的日常生活中扮演著越來越重要的角色，如何調(diào)度路網(wǎng)上大量出租車則成為了影響整體服務(wù)質(zhì)量的一個關(guān)鍵點(diǎn)。要評估一個區(qū)域出租車的供應(yīng)量首先要考慮該區(qū)域內(nèi)空閑出租車的數(shù)量以及潛在乘客的數(shù)量，可用的方法包括基于歐式距離的K近鄰查詢或者基于路網(wǎng)距離的K近鄰查詢等，接著以此計(jì)算出出租車和乘客的密度，最終計(jì)算出出租車供應(yīng)量的區(qū)域分布。后文提供了使用K近鄰查詢結(jié)果計(jì)算出租車或乘客密度的公式，以及使用兩個密度計(jì)算出租車供應(yīng)量的公式，并通過實(shí)驗(yàn)驗(yàn)證了評估的效果。

2 供應(yīng)量評估方法

2.1 密度計(jì)算公式

密度反映的是移動目標(biāo)在查詢點(diǎn)周邊的分布情況，假設(shè)查詢點(diǎn)X在某一時刻kNN的查詢結(jié)果為[cj1，cj2，…，cjk]， 每一個查詢結(jié)果對應(yīng)路網(wǎng)距離的列表為[disj1，disj2，…，disjk]，那么定義查詢點(diǎn)在當(dāng)前時刻的密度為DK=k = k / 。

2.2 供應(yīng)量計(jì)算公式

假設(shè)查詢點(diǎn)X在當(dāng)前時刻周圍空閑出租車的密度為Dcar， 潛在乘客的密度為Dpassenger，那么定義查詢點(diǎn)X當(dāng)前時刻的出租車供應(yīng)量為F（k）=Dcar - Dpassenger = k×（ 1 / - 1 /）。其中disjk為第k輛可用出租車的距離，disik為第k個潛在乘客的距離。

2.3 實(shí)驗(yàn)

對于每一個不同的K值，我們都可以計(jì)算出一個不一樣的供應(yīng)量分布。我們可以根據(jù)實(shí)際的調(diào)度需求來調(diào)整K值的選擇，如選擇供應(yīng)量方差最大的K值以使得整體供應(yīng)量的差異最大。后文實(shí)驗(yàn)選擇K為275得到以下結(jié)果。

2.3.1 出租車密度

上圖為上海市晚高峰時段出租車的密度分布，可以看出上海市中心沿黃浦江區(qū)域的可用出租車分布較為密集，而其余區(qū)域可用出租車分布較少。

2.3.2 乘客密度

以乘客的需求為負(fù)值，計(jì)算得上海市晚高峰乘客密度分布如圖2。由圖可知，晚高峰時段上海市乘客需求最大的區(qū)域仍以市中心為主，但深顏色區(qū)域較之圖1要更大，因此乘客的區(qū)域分布更廣。

2.3.3 供應(yīng)量分布

根據(jù)我們2.2節(jié)的公式可以計(jì)算得出上海市晚高峰時段出租車的供應(yīng)量分布如圖3.可以明顯看出上海市中心區(qū)域顏色整體偏藍(lán)，屬于供不應(yīng)求區(qū)域，而外圍顏色鮮亮，屬于供過于求區(qū)域。此時可以考慮將周邊區(qū)域的出租車調(diào)往市中心區(qū)域以緩解整體的乘車壓力。

3 結(jié)論與展望

本文用K近鄰查詢結(jié)果定義了出租車和乘客的密度計(jì)算公式，以及出租車供應(yīng)量計(jì)算公式。并通過實(shí)驗(yàn)驗(yàn)證了該評估公式在上海市路網(wǎng)和出租車軌跡數(shù)據(jù)集上可以直觀地看出出租車供應(yīng)量的分布情況，從而為系統(tǒng)管理員調(diào)度出租車輛提供依據(jù)。待完善之處包括：1） 評估的效果根據(jù)檢查點(diǎn)在地圖上分布的疏密差別很大，如果檢查點(diǎn)數(shù)量較少，那么只能得到較為初略的評估結(jié)果，如果查詢點(diǎn)數(shù)量較大，則會帶來較大計(jì)算量，因此在查詢算法上可以據(jù)此做出相應(yīng)優(yōu)化以適應(yīng)大量查詢點(diǎn)同時查詢；2）依據(jù)不同的K值可以得到不同的評估結(jié)果，因此選擇一個合適的K值非常重要，后續(xù)可以根據(jù)不同的評估需求，比較不同K值得評估結(jié)果，以此選擇一個最優(yōu)的K值。

參考文獻(xiàn)：

[1] Papadias D， Zhang J， Mamoulis N， et al. Query processing in spatial network databases[C]//Proceedings of the 29th international conference on Very large data bases-Volume 29. VLDB Endowment， 2003： 802-813.

[2] Samet H， Sankaranarayanan J， Alborzi H. Scalable network distance browsing in spatial databases[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data. ACM， 2008： 43-54.

[3] Lee K C K， Lee W C， Zheng B. Fast object search on road networks[C]//Proceedings of the 12th International Conference on Extending Database Technology： Advances in Database Technology. ACM， 2009： 1018-1029.

[4] Huang W， Li G， Tan K L， et al. Efficient safe-region construction for moving top-k spatial keyword queries[C]//Proceedings of the 21st ACM international conference on Information and knowledge management. ACM， 2012： 932-941.

[5] Zhong R， Li G， Tan K L， et al. G-tree： An efficient index for knn search on road networks[C]//Proceedings of the 22nd ACM international conference on Information & Knowledge Management. ACM， 2013： 39-48.

[6] Zhong R， Li G， Tan K L， et al. G-tree： An efficient and scalable index for spatial search on road networks[J]. IEEE Transactions on Knowledge and Data Engineering， 2015， 27（8）： 2175-2189.

[7] Pfoser D， Jensen C S， Theodoridis Y. Novel approaches to the indexing of moving object trajectories[C]//VLDB. 2000： 395-406.

[8] ?altenis S， Jensen C S， Leutenegger S T， et al. Indexing the positions of continuously moving objects[M]. ACM， 2000.

[9] Jensen C S， Lin D， Ooi B C. Query and update efficient B+-tree based indexing of moving objects[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment， 2004： 768-779.

[10] Hu H， Xu J， Lee D L. A generic framework for monitoring continuous spatial queries over moving objects[C]//Proceedings of the 2005 ACM SIGMOD international conference on Management of data. ACM， 2005： 479-490.