基于POI 的出租車停靠位置選擇算法研究①

徐煥君 余 靖 苑 帥 張玉停

(燕山大學信息科學與工程學院 秦皇島066004)

0 引言

隨著互聯網技術的快速發展,傳統出租車行業面臨著網約車的競爭,其中一個重要原因就是出租車等待位置以及資源分配不合理而造成的打車難問題。如何合理選擇出租車停靠位置屬于城市交通設施建設的一個主要問題,也是城市規劃[1]的重要依據。

城市興趣點(point of interest,POI)數據涵蓋了廣泛的地理空間位置屬性,相關學者使用POI 為評價城市布局合理性提供了新的研究方法。文獻[2]基于地理信息系統(geographic information system,GIS)和POI 數據,研究了上海市的城市中心體系,與上海市現行城市總體規劃進行對比,并提出發展建議。文獻[3]基于POI 數據對蘇南4 個城市的生活便利度進行評價,為公共服務設施空間分布及其便利度評價提供了新的方法。文獻[4]基于住宅POI 數據,考慮城市公園綠地對周邊住宅價格的影響,構建了住宅市場特征價格模型并結合彈性與邊際價格分析,量化了公園綠地對住宅價格的影響。

基于POI 的出租車停靠位置是根據節點重要度來選擇的,用于判定網絡節點重要度的方法本質上源于圖論[5]。目前的研究均是僅以一種類型的場所作為研究對象,如公交站點、地鐵站點、鐵路站點等,而沒有綜合考慮多類型場所。判定重要節點的方法除了度數法[6]和介數法[7]之外,考慮到整個網絡的全局特性,又將貼近度中心性[8]、介數中心性[9]等也作為評價指標加入算法中。文獻[10]提出一種基于熵的復雜網絡節點重要性自適應判定方法,但采用的判定指標有一定的局限性。文獻[11]提出了一種基于生成樹數目的節點刪除法,但節點刪除可能會造成網絡不連通,從而使判定結果不準確。文獻[12]提出一種基于全網平均等效最短路徑數的網絡抗毀度評價模型,但沒有完全體現出網絡拓撲結構的差異性。網頁排名(PageRank)算法[13-14]不僅可以預測網絡流量、未來鏈路等,還可以識別重要節點,且其計算復雜度較低。此外,文獻[15,16]提出了融合節點自身重要度及連邊重要度的改進加權節點收縮法,主要用于判定供應鏈網絡節點間的重要度。文獻[17]利用A*算法,將復雜網絡理論與動態需求特征相結合,對公交站點進行重要度判定,解決了定制公交站點及路徑動態優化問題。文獻[13-17]主要是針對單一類型節點判定重要度,具有一定的局限性。

本文在綜合考慮節點在路網[18]中基本信息的前提下,建立了一種在不同模式下出租車按需分配呼叫模型,給出適用于無權節點和加權節點的重要度判定方法,并以POI 數據集為參考,對節點重要度進行排名,根據排名結果,依照杠桿原理和多邊形求“重心”方法,找出最適合的出租車停靠位置,并實現可視化。

1 系統模型

本節首先從城市道路網絡的結構特性出發,基于選取的POI 處產生的呼叫出租車次數的不同提出4 種模式。將城市中對于出租車需求量大的場所抽象為網絡中的節點,將不同POI 之間的運行線路抽象為節點間的連接邊,基于此得到城市道路拓撲網絡是一個復雜網絡。該網絡形成的拓撲圖是一個無向圖,數學表達式為G=(V,E) 是一個有序的二元組。其中V=(v1,v2,…,vm) 稱為點集,其元素稱為頂點或節點;E=(e1,e2,…,en) 稱為邊集,其元素稱為無向邊,簡稱邊。

圖G的鄰接矩陣A=[aij],其中,

1.1 呼叫模型

1.1.1 加權節點的權

(1)節點類型共有8 種,分別為車站a、住宅區b、學校(高校)c、醫院d、景區e、酒店f、餐館g 和購物廣場h。

(2)時間參數共有4 種,分別為早上mor、中午noon、下午aft 和晚上eve。

1.1.2 4 種出租車呼叫模式

模式1totalSame。不同節點處產生出租車呼叫次數相同,呼叫次數是一個有范圍的隨機數,隨機數的產生受時間參數控制。

模式2typeSame。相同類型的節點產生出租車呼叫次數相同,不同類型的節點之間產生的呼叫次數不考慮是否會相同。呼叫次數是一個有范圍的隨機數,隨機數的產生受時間參數控制。

模式3random。不同節點處產生出租車呼叫次數是隨機的,隨機數的產生受時間參數控制。

TotalSame、typeSame、random 模式隨機數選擇方案如表1 所示。

表1 totalSame、typeSame、random 模式隨機數選擇方案

模式4human。人工干涉節點處出租車呼叫次數,指定被選擇節點處的呼叫次數為一個較大的隨機數,其他節點處的呼叫次數的產生方式與total-Same 模式一致。

Human 模式隨機數選擇方案如表2 所示。

表2 human 模式隨機數選擇方案

1.2 相關定義

定義1 節點鄰域(neighborhood)與閉鄰域(closed neighborhood)。設無向圖G=＜V,E ＞,vi,vj∈V,若?et∈E,使得et=(vi,vj),則稱vi與vj是相鄰的,即aij=1。節點vi鄰域為δi={vj | vj∈V,aij=1,j=1,2,…,n}。節點vi閉鄰域為={vi} ∪δi。

1.2.1 節點加權系數

本文中節點的權值為節點處出租車的隨機呼叫次數,該指標的提出是考慮到判定節點重要度時除了拓撲圖本身結構屬性之外,還受到POI 即節點處權值大小的影響。在其他條件相同的前提下,節點處的權值越大,節點越重要,說明該指標的貢獻度越高。根據各POI 處對出租車的隨機呼叫次數,提出節點加權系數為不同節點處的出租車呼叫權重,也稱為節點貢獻度。

定義2局部加權系數(local weighting factor,LWF)。節點的局部加權系數為節點閉鄰域中的權值和,節點vi處的出租車呼叫次數為,節點vi鄰域的出租車呼叫次數為,則節點vi的局部加權系數可以定義為

為了簡化計算,縮小量值,將上述局部加權系數的值進行歸一化,使結果范圍在[0,1]之間。使用的歸一化方法如式(2)所示。

定義3全局加權系數(global weighting factor,GWF)。節點的全局加權系數為節點vi處的權值與整個網絡圖中所有節點的權值和之比,節點vi的全局加權系數為

1.2.2 局部重要度

定義4節點的度(degree)及其閉鄰域的度(degree of closed neighborhood,CND)。節點vi的度等于和vi相關聯的邊的條數,又稱關聯度,記作dG(vi)。節點vi閉鄰域的度為

式中,dG(δi) 為節點vi的鄰域集合中所有節點的度的累加和。

Sigmoid 函數也叫Logistic 函數,在信息科學中,由于其單增以及反函數單增等性質,Sigmoid 函數常被用作神經網絡的激活函數,將變量映射到0～1 之間。

為了將節點閉鄰域的度的值映射到0～1 之間,對原Sigmoid 函數進行一個變形。

其中x的取值范圍為[0,+∞),s(x) 的取值范圍為(0,1)。

定義5節點鄰域度密度(neighborhood degree density,NDD)。將節點vi鄰域集合中節點的度數之和與節點vi的度的比值定義為節點vi的鄰域度密度,代表著節點的鄰域關系。節點vi的鄰域度密度為

定義6基于度的點密度(dot density,DOTD)考慮了節點閉鄰域的度與節點鄰域集合的度密度之間的關系,其定義如式(8)所示。

定義7節點的局部集聚系數(agglomeration coefficient,AGGC)。節點vi的鄰居節點之間所存在的邊數與可能存在的最大邊數之比。節點vi的局部集聚系數為

該指標考慮了節點的鄰居節點之間的緊密程度。

1.2.3 全局重要度

定義8接近中心性(proximity centrality)。假設圖中共有m個節點,是節點vi到節點vj的距離(按經緯度計算),di是節點vi到網絡中所有節點的距離的平均值。節點vi的經緯度為節點vj的經緯度為,則兩點經緯度間的距離公式為

式中r為地球平均半徑,通常選擇常數值為6371 km。

節點vi的全局重要度(global importance)為

其中,di值的相對大小在某種程度上反映了節點vi在網絡中的相對重要性,di的值越小意味著節點vi更接近其他節點,越居于網絡中心,節點vi在全局網絡中越重要。

1.2.4 節點重要度

復雜網絡本質上的非同質拓撲結構,決定了網絡中每個節點的重要程度是不同的。節點在復雜網絡中的重要度首先取決于節點在網絡中的位置,如網絡中的“末梢節點”和“非末梢節點”的重要程度顯然是不一樣的;其次,節點在網絡中的重要度還取決于節點的連通能力,該節點連接的邊數越多,節點就越重要;除此之外,本文中提出的節點處的權值大小也影響著節點的重要程度。

定義9通用節點重要度(general node importance degree,GNID),稱

為節點vi是通用節點時的重要度。通用節點在本文里特指無權節點,即節點處無權值。

定義10專用節點重要度(dedicated node importance degree,DNID),稱

為節點vi是專用節點時的重要度。專用節點在本文里特指加權節點,即節點處有權值。

2 算法描述

復雜網絡中節點的重要度由節點在復雜網絡中的位置和在其鄰域中的度以及節點處的權值大小共同決定。

2.1 GNI 算法

本文通用節點重要度(general node importance,GNI)計算方法可以在常見的網絡圖中使用,節點處無權值,它考慮的是節點在網絡中的基本結構,綜合節點在局部區域和全局中的信息,設計算法過程如算法1 所示。

2.2 DNI 算法

本文專用節點重要度(dedicated node importance,DNI)計算方法是在DNI 算法的基礎上設計的,它除了綜合考慮節點在網絡中的基本結構信息外,還增加了節點加權系數(貢獻度)這一指標,更適用于本文的研究背景,算法過程如算法2 所示。

GNI 算法適用于節點處無權值的情況下求節點重要度。DNI 算法適用于節點處有權值的情況下求節點重要度。DNI 算法更適用于本文的研究背景,在POI 處對出租車有需求,即在節點處有權值的情況下判定節點重要度。

2.3 出租車停靠位置選擇算法

出租車停靠位置的選擇依據周圍節點的重要程度,在多個重要程度不同的節點之間的某個位置選擇出租車停靠點時,需要考慮到停靠位置到節點的距離及節點的重要程度兩個因素。本文類比多邊形獲取“重心”的方法,求得最佳的出租車停靠位置。

已知節點vi,其在平面坐標系中的坐標為(,),米勒坐標系中的坐標為。米勒坐標系下坐標轉化至平面坐標系下坐標公式為

得:

在平面直角坐標系下:

已知點o(xo,yo),其在平面坐標系中的坐標為(xo,yo),在米勒坐標系中的坐標為。平面坐標系下坐標轉化至米勒坐標系下坐標公式為

式中mill=2.3,最終結果留到小數點后7 位。出租車停靠位置選擇算法過程如算法3 所示。

3 實驗結果分析

3.1 數據集

本文選取的POI 為河北省秦皇島市北戴河區113 家對出租車有較大需求的8 類場所,分別為車站、住宅區、學校(高校)、醫院、景區、酒店、餐館和購物廣場,如圖1 和圖2 所示。這113 家場所的選取來自當前熱門APP 推薦并且根據真實的經緯度數據(北京大學開放數據平臺和高德地理信息集)與高德地圖實際行駛路線構成城市道路網。城市道路網是在城鎮管轄范圍內由節點和各種不同功能的干道和區域性道路組成的,是城市總體規劃布局的骨架。

圖1 POI 及出租車可行駛路線網絡圖

圖2 POI 按類型顯示及出租車可行駛路線網絡圖

選取北戴河區的POI 作為研究數據的原因:(1)北戴河區交通基礎設施建設還在發展中,沒有市中心發達,公交站點密度也比較小;(2)因為旅游等需求,人口流動量大;(3)堵車情況不嚴重,出租車市場發展潛力大。

3.2 實驗

為求得北戴河區最佳的出租車停靠位置,共進行2 組實驗。第1 組實驗根據定義8 和定義9 分別在4 種模式下以GNI 算法和DNI 算法求出圖中113個節點的重要度排名,通過比較兩種算法下的排名可以看到,在節點處有權值時會影響節點的重要度。第2 組實驗根據DNI 算法下的節點重要度排名,選出排名前5%的節點,依據出租車停靠位置選擇算法,求得最佳的出租車停靠位置。

下面的各個實驗是對于不同模式下DNI 算法與GNI 算法節點重要度變化量排名前5 結果對比。

3.2.1 節點重要度排名

(1) totalSame 模式

如圖3 所示,由實驗結果可知,當考慮節點處的權值時,會對最終節點重要度的排名結果產生明顯的影響,排名結果與權值大小無關。并且,若所有POI 處的呼叫次數為0 時,即節點處的權值大小為0時,DNI 算法的節點重要度排名與GNI 算法下的排名一致。

圖3 totalSame 模式

(2) typeSame 模式

如圖4 所示,該模式下,相同類型的節點處產生的呼叫次數相同。時間參數為mor 時,8 種類型節點的呼叫次數分別為5、3、7、7、0、4、1、0;時間參數為noon 時,8 種類型節點的呼叫次數分別為9、0、5、0、2、3、1、6;時間參數為aft時,8種類型節點的呼叫次數分別為6、9、16、7、15、9、4、5;時間參數為eve時,8 種類型節點的呼叫次數分別為12、3、2、6、1、4、5、1。由實驗結果可知,typeSame 模式下,節點重要度排名在DNI 算法下與GNI 算法下有明顯變化。

圖4 typeSame 模式

(3) random 模式

如圖5所示,該模式下,不同節點處產生的呼叫次數是在時間參數的控制下隨機生成的。由實驗結果可知,random 模式下,節點重要度排名結果在DNI 算法下與GNI 算法下有明顯變化。

圖5 random 模式

(4) human 模式

如圖6 所示,該模式下,人工選擇標號為50 的節點,此節點處產生一個較大的隨機數,而其余節點產生的隨機數方式與totalSame 模式一致。時間參數為mor 時,{50 號節點:58,其他節點:14};時間參數為noon 時,{50 號節點:37,其他節點:0};時間參數為aft 時,{50 號節點:45,其他節點:2};時間參數為eve 時,{50 號節點:50;其他節點:5}。

圖6 human 模式

由實驗結果可知,human 模式下,節點重要度排名在DNI 算法下與GNI 算法下有明顯變化。

3.2.2 出租車停靠位置選擇

本文節點重要度排名方法選取DNI 算法,以human 模式下,設定時間參數等于mor 時為例,生成出租車停靠位置并將其結果可視化。

根據出租車停靠位置選擇算法,排名前5%的節點的出租車停靠位置如圖7 所示(黑色粗加號)。從表3 及圖7 中可知,排名第2 的節點與排名第4的節點分別在其閉鄰域中找最合適的出租車停靠位置時,得到的結果一致。因為標號為56 的節點與標號為70 的節點互為閉鄰域的關系,在通過出租車停靠位置選擇算法計算時,是會出現結果一致的可能性的。而在該模式下,標號為50 的節點處隨機數為56,此時節點加權系數對50 號節點的重要度排名及最終的出租車停靠位置都有影響。

圖7 出租車停靠位置在網絡圖中的可視化

表3 human 模式下(時間參數為mor)出租車停靠位置選擇方案

本文以北戴河區113 個POI 進行實例分析,得出以下結論。

(1) POI 處的呼叫次數大小,即節點處隨機數的權值大小,會影響節點重要度的排名結果。

(2) 節點的權值與節點在圖中的基本屬性之間并無相關性,進一步說明單個指標具有不同側重點,而綜合指標更能從物理拓撲結構及呼叫次數屬性方面體現節點的重要性。

(3) 出租車停靠位置的選取與POI 處的重要性相關,停靠位置會更靠近較為重要的POI。

4 結論

本文選取北戴河區113 個POI,考慮了其實際地理位置信息與出租車行駛路線,提出了POI 處出租車呼叫的次數作為新指標,建立了一種具有不同模式的出租車按需分配呼叫模型。該模型更適合于判定加權節點的重要度,同時基于節點的重要度排名,給出了較好的出租車停靠位置。下一步的研究方向會將出租車的實際行駛距離以及行駛道路上需要經過的紅綠燈數等指標考慮進去,以得到更好的出租車停靠位置。