[發明專利]一種基于車載GPS數據的公交路線運營時段劃分方法

有效

• 申請號: 201510032960.0
• 申請日: 2015-01-22
• 公開（公告）號: CN104573972B
• 公開（公告）日: 2017-09-29
• 發明（設計）人: 別一鳴;程紹武;張亞平;劉瑩
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/30
• 代理公司: 哈爾濱市松花江專利商標事務所23109
• 代理人: 王大為

1.一種基于車載GPS數據的公交路線運營時段劃分方法，其特征在于：所述一種基于車載GPS數據的公交路線運營時段劃分方法是通過如下步驟實現的：

步驟一、提取公交線路運營時段劃分指標：設一條公交線路每天從始發站發出M趟公交車，第1趟編號為1，以此類推最后一趟編號為M，該線路有N個運營時段，第n個運營時段的車頭時距是H_n，1≤n≤N，設屬于第n個運營時段、編號為m_n的公交車連續J天的平均線路停靠時間為D(m_n)，1≤m_n≤M，它的計算方法如公式(1)所示；

D(mn)=HminHnJΣj=1JΣi=1Idij(mn)---(1)]]>

公式(1)中I表示公交線路的停靠站點數量，J表示天數，d_ij(m_n)表示第m_n趟公交車第j天在第i個站點的停靠時間，H_min表示N個運營時段的發車間隔最小值；

d_ij(m_n)的計算方法如公式(2)所示，

dij(mn)=|Tija(mn)-Tijb(mn)|---(2)]]>

公式(2)中表示第j天第m_n趟公交車到達第i個站點的時刻，表示第j天第m_n趟公交車駛離第i個站點的時刻；

的獲取方式為：公交車載GPS可以記錄公交車在每個位置的時刻、速度以及該位置的經緯度，將GPS數據中的經緯度信息與站點i的經緯度信息進行匹配，可以獲得第j天第m_n趟公交車到達站點i、駛離站點i的時刻

設屬于第n個運營時段、編號為m_n的公交車連續J天的平均線路站間行程時間為E(m_n)，1≤m_n≤M，它的計算方法如公式(3)所示；

E(mn)=1JΣj=1JΣi=1I-1eij(mn)---(3)]]>

公式(3)中e_ij(m_n)表示第m_n趟公交車第j天在第i、i+1個站點之間的行程時間；

步驟二、初始劃分公交線路運營時段：

步驟二(一)、給矩陣賦初始值：定義矩陣Φ存放公交車編號，即Φ＝[1,2,…,m,…,M]；定義矩陣D、E分別存放每趟公交車的平均線路停靠時間、平均線路站間行程時間，即D＝[D(1),D(2),…D(m),…D(M)]，E＝[E(1),E(2),…E(m),…E(M)]，矩陣C存放初始劃分結果，C(1,1)＝Φ(1)；矩陣C每行代表一類，每行的元素代表劃入這一類的各趟公交車編號；

步驟二(二)、給變量k、j、m均賦予初始值1；

步驟二(三)、判斷第m趟與第m+1趟公交車的平均線路停靠時間、平均線路站間行程時間的差值絕對值是否都小于閾值，即：|D(m)-D(m+1)|<ΔD_max并且|E(m)-E(m+1)|<ΔE_max；如果是，則進入步驟二(四)，否則進入步驟二(五)；ΔD_max是劃入同一個時段的各趟公交車平均線路停靠時間差值絕對值的最大值，ΔE_max是劃入同一個時段的各趟公交車平均線路站間行程時間差值絕對值的最大值；

ΔD_max＝r·c·T_ob(4)

公式(4)中r表示調節系數，取值0.85；c表示每輛公交車能夠承載的最大乘客數量；T_ob表示每位乘客在站點的平均上車時間，取值2.4秒/人；

ΔE_max＝max{0,H_min-r·c·T_ob}(5)

公式(5)中H_min表示N個運營時段的發車間隔最小值；

步驟二(四)、j的值加1，并且C(k,j)＝Φ(m+1)，m的值加1；進入步驟二(六)；

步驟二(五)、k的值加1，j等于1，C(k,j)＝Φ(m+1)，進入步驟二(六)；

步驟二(六)、判斷m是否等于M，如果是則進入步驟二(七)，否則返回步驟二(三)；

步驟二(七)、公交線路運營時段的初始劃分結束；

步驟三、拆分初始劃分形成的公交線路運營時段：當第m+1趟公交車與所在的第k類已有的其他趟公交車的劃分指標差異要大于閾值時，通過如下步驟解決：

步驟三(一)、給k賦予初始值1；

步驟三(二)、判斷第k類的標記P是否等于1，如果是則進入步驟三(三)，否則進入步驟三(四)；P用來標記第k類是否已經進行過拆分，如果等于1則代表進行過拆分，否則代表未進行過拆分；

步驟三(三)、將k的值加1，判斷此時k是否大于K，如果大于則進入步驟三(十七)，否則轉至步驟三(二)，K為劃分所形成的時段數，也是矩陣C的行數；

步驟三(四)、判斷矩陣C第k行的元素個數L(C(k,:))是否小于等于2，如果是則將第k類的標記P設置為1，并轉至步驟三(三)；否則進入步驟三(五)；

步驟三(五)、計算矩陣C第k行任意兩個元素的平均線路停靠時間、平均線路站間行程時間的差值絕對值；

步驟三(六)、判斷所有差值絕對值是否都小于閾值ΔD_max、ΔE_max，如果是則將第k類的標記P設置為1，并轉至步驟三(三)；否則進入步驟三(七)；

步驟三(七)、將矩陣C第k行最小、最大數值記為k_min、k_max；

步驟三(八)、計算矩陣C第k行每兩個相鄰元素的劃分指標的歐式距離；

步驟三(九)、以歐式距離最小值對應的兩個元素組成臨時集合；

步驟三(十)、臨時集合中各個元素編號的最小值記為u_min，最大值記為u_max；

步驟三(十一)、判斷是否u_min>k_min并且u_max<k_max，如果是則進入子模塊I，子模塊I結束后進入步驟三(十四)；否則進入步驟三(十二)；

步驟三(十二)、判斷是否u_min>k_min并且u_max＝k_max，如果是則進入子模塊II，子模塊II結束后進入步驟三(十四)；否則進入步驟三(十三)；

步驟三(十三)、此時u_min＝k_min并且u_max<k_max，進入子模塊III，子模塊III結束后進入步驟三(十四)；

步驟三(十四)、判斷第k類是否還有元素可以納入臨時集合，如果是則返回步驟三(十一)，否則進入步驟三(十五)；

步驟三(十五)、將臨時集合標記P設置為1；并確定其類別編號；

步驟三(十六)、判斷每一類的標記P是否都等于1，如果是則進入步驟三(十七)，否則返回步驟三(一)；

步驟三(十七)、公交線路運營時段的拆分流程結束；

步驟四、合并公交線路運營時段：

步驟四(一)、對于任意不相鄰的兩類，計算兩類各個元素所對應平均線路停靠時間、平均線路站間行程時間的差值絕對值，并存入矩陣；

步驟四(二)、判斷每個矩陣里的差值絕對值是否都小于等于ΔD_max或ΔE_max，刪除不滿足要求的矩陣；

步驟四(三)、判斷剩余的矩陣數量是否為0，如果是進入步驟四(六)，否則進入步驟四(四)；

步驟四(四)、對于每個矩陣涉及的兩類，計算兩類合并情況下各個元素至類中心的歐式距離平均值，以類x、類k為例，在兩類合并情況下歐式距離平均值Eu(k,x)的計算方法如公式(7)所示；

Eu(k,x)=Σi=1Ne(D(i)-D‾(x,k))2+(E(i)-E‾(x,k))2Ne---(7)]]>

N_e＝L(C(x,:))+L(C(k,:))(8)

D‾(x,k)=Σi=1NeD(i)Ne---(9)]]>

E‾(x,k)=Σi=1NeE(i)Ne---(10)]]>

公式(7)、(8)、(9)、(10)中N_e表示類k、類x的元素數量之和，表示類k、類x合并后的聚類中心，取各個元素平均線路停靠時間、平均線路站間行程時間的平均值，L(C(x,:))表示矩陣C第x行的元素個數；

步驟四(五)、對比每個矩陣涉及的兩類合并情況下的歐式距離平均值，將歐式距離平均值最小值對應的兩類合并，轉至步驟四(一)；

步驟四(六)、公交運營時段劃分結束。