• / 27
  • 下載費用:30 金幣  

一種基于出行需求分析的公交站點部署方法.pdf

摘要
申請專利號:

CN201511021260.8

申請日:

2015.12.30

公開號:

CN105427003A

公開日:

2016.03.23

當前法律狀態:

實審

有效性:

審中

法律詳情: 實質審查的生效IPC(主分類):G06Q 10/04申請日:20151230|||公開
IPC分類號: G06Q10/04(2012.01)I; G06F17/30 主分類號: G06Q10/04
申請人: 北京航空航天大學
發明人: 王海泉; 雷碩; 馬偉建; 石恒昆
地址: 100191北京市海淀區學院路37號
優先權:
專利代理機構: 北京科迪生專利代理有限責任公司11251 代理人: 成金玉; 孟卜娟
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201511021260.8

授權公告號:

|||

法律狀態公告日:

2016.05.11|||2016.03.23

法律狀態類型:

實質審查的生效|||公開

摘要

本發明涉及一種基于出行需求分析的公交站點部署方法,基于海量出租車數據針對北京市出行需求特征進行分析,通過軌跡數據得到了載客熱點區域,并通過GIS地圖數據提取得到了道路交通擁堵情況、道路類型、道路寬度和道路條數等數據作為部署站點的考慮因素,然后對站點部署位置優化目標進行了處理,進而采用貪心算法解決了站點部署問題。通過本發明得出的公交站點是智能公交線路設計的基礎,在這些公交站點之間安排出行路線,可以有效的降低乘客出行費用和道路資源消耗。

權利要求書

1.一種基于出行需求分析的公交站點部署方法,其特征在于實現步驟如下:
步驟一,通過DBSCAN算法對出租車的軌跡數據進行聚類分析,得到上下客的載客熱
點區域分布,該熱點區域的數據形式是一個帶有區域編號的離散的點集,也是步驟二的輸入;
步驟二,在步驟一得到的輸入的基礎上,通過格雷厄姆算法對離散的點集進行規整化,
再通過最小外包矩形算法對帶有區域編號的離散的點集的區域進行識別和劃分,得到矩形化
的熱點區域表示,輸出是一個矩形區域集合;
步驟三,基于步驟二中的矩形區域集合,對站點部署問題進行抽象和描述,即對站點部
署所考慮的因素進行歸納整理,合并為“道路寬度、道路條數、道路類型、交通瓶頸”四個參
考因素;然后將站點部署問題形式化為兩個約束條件和四個優化目標,兩個約束條件為限制
相鄰站點之間的距離在400m至600m之間且不能在沒有道路的地方布站;四個優化目標為
站點選址盡量選在雙行道上,避開交通瓶頸,選在道路寬度較寬且條數較多的位置;
步驟四,在步驟三的基礎上,通過線性加權和法將四個優化目標抽象為四個目標函
數,為每個目標函數分配權重,通過選擇價值函數計算出每一個區域單元的選擇價值
value,再將站點選取問題轉換為如下原則:多個區域單元格中選取一個格子單元的集合
Φ,使得Φ的所有格子的value值的和最大;Φ中格子需滿足如下條件:1)任意兩個格子
之間的間隔不得小于4個格子(100m*100m的格子單元);2)任意一個格子至少與其他一
個格子的間隔小于或等于6個格子(100m*100m的格子單元);3)格子的value不得等于β;
步驟五,在步驟四的基礎上,基于貪心算法選取公交站點。
2.根據權利要求1所述的基于出行需求分析的公交站點部署方法,其特征在于:所述
步驟一中的DBSCAN算法的流程如下:
(1)設置兩個參數,半徑距離ε和給定點在ε鄰域內成為核心對象的最小鄰域點數目
MinPts;
(2)首先,隨機選取點集中的一個起始點,稱為點p;
(3)遍歷點集并對點p的ε半徑內的點進行計數,即每遇到一個點與p的半徑距離小
于ε,計數器+1;
(4)依次遍歷一遍點集,直到所有點都被遍歷到;
(5)考察與點的半徑距離小于ε的點的個數是否大于閾值MinPts,若是的話,那么表
示該點p為核心對象,將p的ε鄰域內的點都歸為該簇內;若不是,那么則認為這個點p是
一個噪聲點,可以將其排除;
(6)依次對該簇內的其他點進行(2)-(5)的操作,不斷對簇進行擴展,直到所有點
都遍歷過,而該簇不再擴展的時候,該過程結束,得到帶有區域編號的離散的點集。
3.根據權利要求1所述的基于出行需求分析的公交站點部署方法,其特征在于:所述
步驟二中的格雷厄姆算法流程如下:
(1)選取點集P的個數為n,計數器為i,一個棧保存凸包的點集,計數器為k;
(2)選取點集中左邊最下邊的點P0;
(3)計算出每個點相對于P0的角度和距離;
(4)按照P0的角度和距離將點按升序排序;
(5)將P[n-1]和P[0]壓入棧中;
(6)判斷點集合是否為一條直線,若是的話跳轉至(6),否的話k--;
(7)P[k-1],P[k-2],P[i]是否滿足左轉,是的話將P[i]壓入棧中,否的話i--,k--;
(8)將棧中的點集輸出到文件,即所得到的規整化的點集。
4.根據權利要求1所述的基于出行需求分析的公交站點部署方法,其特征在于:所述
步驟二中最小外包矩形算法流程如下:
(1)準備帶有區域編號的離散的點集;
(2)將點集中所有點的坐標的X,Y的集合排序;
(3)選出最小X坐標即minX,最小Y坐標即minY,最大X坐標即maxX,最大Y坐標
即maxY;
(4)創建最小外包矩形的四個點,分別是P1(minX,minY),P2(minX,maxY),P3
(maxX,minY),P4(maxX,maxY);
(5)將矩形按照100m*100m的格子單元進行劃分,不足100m的按100m計算,最后
輸出一個矩形區域集合。
5.根據權利要求1所述的基于出行需求分析的公交站點部署方法,其特征在于:所述
步驟三中,將站點部署問題形式化具體方法為:
(5.1)綜合所考慮的站點部署因素,將站點部署因素簡化為四個參考因素:交通瓶頸、
道路類型、道路寬度、道路數量;
(5.2)根據步驟二中的區域識別,取每一個熱點區域的最小格子單元為站點部署的基本
單元,即District={P1,P2,P3,P4}={(Pi1,Pi2,Pi3,Pi4)|0≤i≤n},其中P1,P2,P3,P4分別表示最小外
包矩形的四個頂點,Pi1,Pi2,Pi3,Pi4分別為劃分之后的小區域單元的四個頂點,小區域單元面
積小于等于100m*100m,基于所得出的參考因素,確定每一個格子單元具有如下屬性:
a)交通瓶頸屬性bottleNeck
bottleNeck的取值范圍為{1,0},1表示該格子單元是交通瓶頸,0表示不是交通瓶頸,
默認交通瓶頸都在道路上,因此對于沒有道路的格子單元,都不會有交通瓶頸;
b)道路類型屬性roadType
roadType的取值范圍為{0,1,2},0表示該道路是雙行道,1表示該道路是單行道,2表
示沒有道路;
c)道路寬度屬性roadWidth
roadWidth的取值范圍是{0,3,5.5,13,20},0表示該格子單元沒有道路,其他表示該格子
單元的道路的寬度,如果一個格子有多條道路,那么取值為最寬的那一條;
d)道路數量屬性roadNumber
roadNumber的取值范圍是{0,1,2,3},0表示該格子單元沒有道路,1表示該格子單元有1
條道路,2表示該格子單元有2或3條道路,3表示該格子單元有4條道路;
這一步的輸出是一系列區域單元的集合,每一個單元表示為
(AreaID,P1,P2,P3,P4,bottleNeck,roadType,roadWidth,roadNumber),其中AreaID表示區域的
編號屬性,P1,P2,P3,P4分別表示區域的四個頂點,bottleNeck,roadType,roadWidth,roadNumber
分別表示交通瓶頸,道路類型,道路寬度和道路數量四個屬性,這一步的輸出是5.3的輸入;
(5.3)將站點部署問題抽象為兩個約束條件和四個優化目標如下:
(5.3.1)約束條件:
a)對于站點集合4≤dis(A,B)≤6,dis(A,B)表示A,B之間的距離,單位為
格子數;
b)A·roadType≠2;
(5.3.2)優化目標:
a)站點選址盡量選在道路類型為雙行道的道路上;
b)站點選址盡量避開交通瓶頸;
c站點選址盡量選在道路寬度較寬的位置;
d)站點選址盡量選在道路條數較多的位置
其中優化目標的優先級由從a)到d)由高到低;
最后得到兩個約束條件和四個優化目標。
6.根據權利要求1所述的基于出行需求分析的公交站點部署方法,其特征在于:所述
步驟四,站點選取問題轉換方法:用X表示一個格子單元,并用其ID作為其唯一的標識
符,那么X∈[1,2473],定義每一個格子單元具有五個屬性,區域編號屬性AreaID,交通瓶
頸屬性bottleNeck,道路數量屬性roadNumber,道路類型屬性roadType,道路寬度屬性
roadWidth,即R(X)=(AreaID,bottleNeck,roadNumber,roadType,roadWidth),
有四個優化目標分別抽象為四個目標函數如下:
f 1 ( x ) = 1 r o a d T y p e = 1 0.5 r o a d T y p e = 0 0 r o a d T y p e = 2 ]]>(式1)
f 2 ( x ) = 1 b o t t l e N e c k = 0 0 b o t t l e N e c k = 1 ]]>(式2)
f 3 ( x ) = 0 r o a d W i d t h = 0 0.25 r o a d W i d t h = 3 0.5 r o a d W i d t h = 5.5 0.75 r o a d W i d t h = 13 1 r o a d W i d t h = 20 ]]>(式3)
f 4 ( x ) = 0 r o a d N u m b e r = 0 0.33 r o a d N u m b e r = 1 0.66 r o a d N u m b e r = 2 1 r o a d N u m b e r = 3 ]]>(式4)
f1(x)表示道路類型的優化目標函數,f2(x)表示交通瓶頸的優化目標函數,f3(x)表示道
路寬度的優化目標函數,f4(x)表示道路數量的優化目標函數,roadType表示區域單元的道
路類型屬性,bottleNeck表示區域單元的交通瓶頸屬性,roadWidth表示區域單元的道路寬
度屬性,roadNumber表示區域單元的道路數量屬性;
考慮優化目標的優先級,且為了計算簡便,將f1(x),f2(x),f3(x),f4(x)的權值分別設為
α,β,θ和δ,且α>β>θ>δ,α+β+θ+δ=1.,每一個區域的選擇價值表示為:
y=F(x)=αf1(x)+βf2(x)+θf3(x)+δf4(x)(式5)
y和F(x)表示每一個區域的選擇價值函數,f1(x)表示道路類型的優化目標函數,f2(x)
表示交通瓶頸的優化目標函數,f3(x)表示道路寬度的優化目標函數,f4(x)表示道路數量的
優化目標函數,α,β,θ和δ分別表示f1(x)、f2(x)、f3(x)、f4(x)的選擇價值權重;
在此基礎之上,將每一個區域的站點選取問題轉化為:在多個區域單元格中選取一個格
子單元的集合Φ,使得集合Φ中的所有格子的選擇價值value值的和最大,Φ中格子需滿足
如下條件:
1)任意兩個格子之間的間隔不得小于4個格子;
2)任意一個格子至少與其他一個格子的間隔小于或等于6個格子;
3)格子的value不得等于β。
7.根據權利要求1所述的基于出行需求分析的公交站點部署方法,其特征在于:所述
步驟五,基于貪心算法對站點選取問題進行求解,設計的思路是首先保證站點的選取滿足約
束條件,在此前提之下,盡量保證每次選取的站點的value值較高;為了保證每一個站點都
被遍歷過,設置了一個see字段對每一個區域進行標記,凡是遍歷過的字段就標記see字段
為1,具體算法流程如下:
1)把區域集合List按照最小X坐標minX,最小Y坐標minY,最大X坐標maxX,最大
Y坐標maxY,選擇價值value依次升序排序;
2)修改每一個區域的X,Y坐標,并將其按照X升序,Y升序進行排列;
3)修改used(表示該區域已經被選擇)屬性為1,forbidden(表示該區域不能選擇)屬
性為0,value=0.3的屬性為1,allowed(表示該區域可以選擇)屬性為0,see(表示該區域
已經被遍歷過了)屬性為0;
4)修改cursor游標為0,指向List的第一個元素;
5)獲取區域,cursor+1;
6)修改區域的see屬性為1;
7)如果區域的used屬性為1,或者forbidden屬性為1或者allowed屬性為0,回到5),
否則跳至8);
8)添加區域至站點選擇集合中,設置區域的used屬性為1;
9)設置與該區域間隔小于4的區域的forbidden屬性為1;
10)設置與該區域間隔大于等于4且小于等于6的區域的allowed屬性為1;
11)如果cursor大于區域集合的個數,結束;否則跳至5);
最終得到公交站點選取結果。
8.根據權利要求1所述的基于出行需求分析的公交站點部署方法,其特征在于:所述
步驟一中的一個矩形區域的面積不超過100m*100m。

關 鍵 詞:
一種 基于 出行 需求 分析 公交 站點 部署 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:一種基于出行需求分析的公交站點部署方法.pdf
鏈接地址:http://www.rgyfuv.icu/p-6345769.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图