[發明專利]網絡化運營條件下基于圖論的行程可達性計算和展示方法、計算機設備及存儲介質

在審

• 申請號: 202010151882.7
• 申請日: 2020-03-06
• 公開（公告）號: CN111368149A
• 公開（公告）日: 2020-07-03
• 發明（設計）人: 鄧波;劉杰;代平;楊峻峰
• 申請（專利權）人: 成都智元匯信息技術股份有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903;G06F16/953;G06Q10/04;G06Q50/26
• 代理公司: 成都金英專利代理事務所(普通合伙) 51218
• 代理人: 袁英

1.網絡化運營條件下基于圖論的行程可達性計算和展示方法，其特征在于，包括以下步驟：

S1：基于圖論建立線網靜態模型并存儲車站基本信息；

S2：接收OD信息進行動態行程可達性計算；

S3：通過跨終端平臺向外提供行程可達性查詢并展示。

2.根據權利要求1所述的網絡化運營條件下基于圖論的行程可達性計算和展示方法，其特征在于，以無向加權圖G表示所述線網靜態模型，并通過鄰接表的方式實現線網的存儲；

所述無向加權圖G＝(V,E,D)，所述G表示地鐵線網車站網絡；

所述V是圖G中所有站點的集合，v_i是圖中的節點，V＝{v_i|i＝1,2,3,...,n}；

所述E是表示圖G中所有邊的集合，

所述e_ij＝(v_i,v_j)，其中(v_i,v_j)為相鄰的兩個節點，對應真實線網中的兩個相鄰車站；

所述D表示線網中權值的集合，其中，d_ij為邊e_ij上的權值，即為車站v_i與v_j之間的距離；

所述鄰接表以表頭節點和邊表節點對圖G進行表示和存儲。

3.根據權利要求2所述的網絡化運營條件下基于圖論的行程可達性計算和展示方法，其特征在于，所述車站基本信息存儲于節點v_i中，所述車站基本信息包括車站名、車站類型、所屬線路以及在列車運行圖中對應的名稱；所述表頭結點存儲起點站ID，所述邊表節點包括有存儲鄰接車站ID、弧段所屬線路ID以及鄰接弧段權值的三個數據域。

4.根據權利要求1所述的網絡化運營條件下基于圖論的行程可達性計算和展示方法，其特征在于，所述步驟S2包括如下子步驟：

S21：生成路網基礎數據；所述基礎數據包括多條包含線網站點信息、站間走行時間以及運行圖對照信息的基礎信息，所述基礎信息存儲于數據庫，并通過鄰接矩陣表的方式導入線網靜態模型中；

S22：接收外部輸入的起點站點編號和終點站點編號獲取最短可行路徑集；

S23：對每一條可行路徑進行動態行程可達性計算；

S24：進行最優方案篩選和排序。

5.根據權利要求4所述的網絡化運營條件下基于圖論的行程可達性計算和展示方法，其特征在于，在圖的鄰接表表示方法中，一條基礎信息包含起點站、目的地站、走行時間以及路徑類型四個字段；其中，起點站和目的地站以車站AFC編號表示，走行時間為列車運行圖兩站間的開行時間，路徑類型包括普通類型和換乘類型。

6.根據權利要求4所述的網絡化運營條件下基于圖論的行程可達性計算和展示方法，其特征在于，采用Dijkstra算法尋找任意OD間的最短路徑，包括如下步驟：

S221：為每個節點v設置兩個標號：(l(v),p(v))；第一標號l(v)表示從起點到節點v的最小費用，第二標號p(v)為緊前節點，表示在當前最短路徑上節點v的前驅結點；

S222：基于深度優先搜索算法尋找最短路徑，所述最短路徑的搜索范圍至多為5個車站；

S223：基于K最短獲取可行路徑集。