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

在審

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

本發明公開了網絡化運營條件下基于圖論的行程可達性計算和展示方法，包括步驟：S1：基于圖論建立線網靜態模型并存儲車站基本信息；S2：接收OD信息進行動態行程可達性計算；S3：通過跨終端平臺向外提供行程可達性查詢并展示；本方案通過圖論建立城市軌道交通車站站點簡化模型，以Dijkstra算法尋找任意OD間的最短路徑，并根據深度優先搜索算法搜索線網中存在的有效路徑集，同時實現與列車運行圖相關聯的地鐵行程計算，并完成電腦端及企業微信端行程計算查詢程序的開發，可方便乘客對行程進行估計，提高通行效率。

技術領域

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

背景技術

線網規模日趨龐大，目前我國地鐵已經進入網絡化運營階段。與運行圖相結合精細化計算行程的可達情況，為乘客做好出行引導是提升網絡化運營服務水平的有效手段。而隨著線網的不斷發展，地鐵運營里程不斷攀升，至2020年年底，成都地鐵將建成515公里線網，車站數量將突破300座，運營規模跨入國內第一方陣。

和全國絕大多數地鐵一樣，成都地鐵同樣缺少一個完善的體系來誘導乘客晚間出行。運營相關部門向公眾告知末班車的運行方式，一般是通過廣播或在車站出入口張貼本站首末班車時刻表的方式。隨著路網規模的擴大，兩站之間的可選換乘路徑增多，乘客的平均換乘次數也逐漸增多，理論上有效的出行路徑隨之增多。

由于各線路的運營長度不同，雖然車站提前通過站內廣播等方式告知了乘客換乘線路末班車的開行情況，但當行程換乘次數超過2次以后，乘客很難在出行前就得知是否可以在途徑的各個換乘站實現換乘。同時在低峰期，一些理論上的最短行程不一定就是最快到達的方案，隨著客運服務質量要求的不斷提高，車站末班車服務壓力也日趨增大，傳統的方式已經無法應對。基于上述幾個方面的情況，為乘客提供準確可靠的出行誘導信息勢在必行。

發明內容

本發明的目的在于，針對現有技術的不足，提出網絡化運營條件下基于圖論的行程可達性計算和展示方法。本方案基于圖論的相關理論，在此基礎上建立了線網站點簡化模型，以Dijkstra算法和深度優先搜索算法求解OD可行路徑，并通過分段求解的方式計算出了各可行方案的實際可達性情況，最后通過開源框架制作了多平臺、終端的在線行程查詢程序。

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

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

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

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

進一步的，以無向加權圖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進行表示和存儲。