<meter id="nx1pr"><font id="nx1pr"><menuitem id="nx1pr"></menuitem></font></meter>

<listing id="nx1pr"><font id="nx1pr"></font></listing>
<menuitem id="nx1pr"><font id="nx1pr"></font></menuitem>

      <font id="nx1pr"></font>

      <var id="nx1pr"><var id="nx1pr"><delect id="nx1pr"></delect></var></var>
      <track id="nx1pr"></track>

      <video id="nx1pr"></video>
      <pre id="nx1pr"><menuitem id="nx1pr"><meter id="nx1pr"></meter></menuitem></pre>
        <pre id="nx1pr"></pre>
      CNTXJ.NET | 通信界-中國通信門戶 | 通信圈 | 通信家 | 下載吧 | 說吧 | 人物 | 前瞻 | 智慧(區塊鏈 | AI
       國際新聞 | 國內新聞 | 運營動態 | 市場動態 | 信息安全 | 通信電源 | 網絡融合 | 通信測試 | 通信終端 | 通信政策
       專網通信 | 交換技術 | 視頻通信 | 接入技術 | 無線通信 | 通信線纜 | 互聯網絡 | 數據通信 | 通信視界 | 通信前沿
       智能電網 | 虛擬現實 | 人工智能 | 自動化 | 光通信 | IT | 6G | 烽火 | FTTH | IPTV | NGN | 知本院 | 通信會展
      您現在的位置: 通信界 >> 工業自動化 >> 技術正文
       
      基于深度優先搜索的鐵路中轉路線規劃研究
      [ 通信界 | 郭怡然 | www.sdgj0817.com | 2023/7/23 18:30:06 ]
       

      摘要:目前,許多長距離鐵路出行沒有直達列車,或直達列車繞路,導致額外的時間和金錢花費。本文針對這一現象,將復雜的鐵路路線數據抽象成計算機方便處理的圖,使用帶有剪枝優化的深度優先搜索算法,對可能的乘車中轉方案進行遍歷,根據不同目標(如花費最少、耗時最短、到達時間最早等)挑選出不同中轉方案,供用戶出行參考。根據軟件設計的原則和方法,給出了使用實現該算法的系統的設計。

      關鍵詞:鐵路中轉方案;深度優先算法;剪枝優化;軟件系統設計

      一、引言

      隨著我國鐵路行業的飛速發展,鐵路出行已經成為很多人出行的首選。隨著高鐵、動車的車次越來越多,鐵路網變得愈加復雜。如何在錯綜復雜的鐵路線路中規劃出一條花費最少,或者到達時間最早,又或者是換乘次數最少的乘車方案愈發顯得重要。12306 官方網站提供的各種換乘方案無法讓用戶自己設定最早出發時間,最晚到達時間,以及最小換乘時間的限制,而且最多只能換乘一次,靈活性受限。提供的換乘方案又多又雜,用戶體驗不好。

      本文以開發一個能夠幫助用戶更加靈活地規劃乘車方案的系統為目標,彌補 12306 官網提供的服務的缺點,支持用戶自己定制各種條件,包括最早出發時間、最晚到達時間、最小換乘時間、最大換乘次數。為用戶規劃出行路線提供一定參考。

      二、算法設計

      算法主要分為兩部分,一部分是根據鐵路數據構建出圖,另一部分是在圖上進行搜索。

      (一)構建圖

      將每個站點抽象成點,兩個站點之間的鐵路線路抽象成邊。設計站點的數據結構如下,后期可以方便地進行屬性的添加。設計路線的數據結構如下,維護了始發站、終點站、始發時間、到達時間、座位類型(二等座/硬座)、價格、編號等信息。

      采用鄰接表數據結構存儲圖,即對于每個站點Station,存儲離開它的所有線路,圖的數據結構如圖1:

      為了方便剪枝和輸出最終方案,創建方案的數據結構如下,即維護花費、到達時間、總用時、與期望時間差異程度等各項評價參數:

      方法:betterInAllAspects和atLeastBetterInOneAspect,分別用于對其他方案進行剪枝和決定是否對當前方案剪枝。

      (二)圖的搜索

      常用的搜索算法主要有兩類,深度優先和廣度優先。廣度優先可以保證第一次搜索到站時可以保證在某方面最優,但空間復雜度較大。由于本系統是需要提供多個不同指標最優化的方案,因此廣度優先的這個性質并不能很好地被利用。同時考慮到圖的點數和邊數較多,因此選用空間復雜度較小的深度優先搜索算法來實現。

      算法核心流程:構建一個Traveler對象模擬各種乘車方案,具體來講,當traveler到達某個站點后,看一下在當前時間所有可以乘坐的車次,依次嘗試各個可以乘坐的車次,同時更新花費和到達時間,到達下一個車站后重復上述過程。當到達一個車站發現沒有任何一輛車次可以乘坐,則回退到上一個車站嘗試其他車次,具體實現如下:

      // 嘗試從當前站乘車

      for (Line line : graph.map.get(currentStation.id)) {

      if (!path.empty() && !path.peek().id.equals(line.id) &&

      (line.startTime.getTime() - currentDate.getTime()) <

      (long) minMinutesForSameStationTransfer * 60 * 1000)

      continue;

      if (line.startTime.compareTo(currentDate) < 0) continue; // 防止跨天

      // 更新換乘次數

      int newTransferTimes = transferTimes;

      if (!path.isEmpty() && 。╬ath.peek().id).equals(line.id)) newTransferTimes++;

      if (newTransferTimes > maxTransferTimes) continue;

      path.push(line);

      travel(line.endStation, line.endTime, currentCost + line.price, newTransferTimes);

      path.pop();

      }

      (三)剪枝優化

      為了縮短用戶查詢時間,需要對上述算法進行優化。通過之前定義的Scheme數據結構可以方便地對搜索過程進行剪枝。剪枝可以分為兩部分,一部分根據用戶的限制條件進行剪枝,例如當前時間已經超出用戶設置的可以接受的最晚到達時間,則沒有必要繼續擴展當前搜索子樹。另一種是通過和歷史經過該站點的方案進行比較,如果當前方案在所有方面均比歷史方案差,則沒有必要在此方案的基礎上繼續嘗試。

      (四)方案評價與復雜度分析

      曾考慮過效率更高的動態規劃算法,但為了更高的靈活性和可擴展性以及易實現性選用了搜索算法。搜索算法在最壞情況下時間復雜度將是指數級別。但由于乘車問題具有時間限制其復雜度遠遠低于指數。在最初測試時對于用戶查詢大概可以在幾分鐘內返回結果。這樣的表現顯然不盡如人意。于是采用“剪枝”對算法進行優化,優化之后,通過測試,平均可以在5s內可以返回查詢結果。

      三、系統設計

      本文所設計的系統是一個后端系統,為前端提供查詢服務接口,主要借助Spring平臺。

      系統分為四個模塊:數據獲取模塊、核心算法處理模塊、數據庫交互模塊、WEB模塊。各模塊之間的依賴關系如圖3。

      WEB模塊負責處理前端發送的請求,將請求傳遞給算法處理模塊,并將處理結果返回給前端。

      核心算法模塊在初始化時從數據庫中將鐵路路線信息加載進內存,接受請求,通過搜索,將結果返回給WEB模塊。

      數據庫交互模塊使用Mybatis框架,負責將數據庫數據映射成Java對象。

      數據獲取模塊使用并發優秀的WebMagic框架,負責訪問接口獲取鐵路信息,并將信息存入數據庫。同時使用Spring Task做定時任務框架,每日定時更新鐵路信息。

      同時系統采用分布式架構,各個服務之間使用Dubbo進行通信。整個系統的部署圖如圖4。

      四、結論

      基本實現了預期功能。

      五、解決方案持有的問題

      ①暫時無法提供跨天乘車方案,一是因為數據不充足,二是算法處理時間較長,無法在5s內返回用戶想要的方案。

      ②雖然在爬蟲系統方面采取種種措施保證數據完整性,但還會丟失0.2%的數據。難以在數據完整性和爬取速度方面達到平衡。

      ③由于采用將整條路線拆分成一段段的路徑類和求花費,使用這種方案計算出的價格和實際價格可能有0.5元或者1元的誤差。

      六、后續研究方向

      ①增加跨天乘車方案的功能。

      ②加強對數據獲取的控制,爭取達到更高的數據完整性和更快的獲取速度。

      作者單位:郭怡然 重慶市重慶郵電大學2019級軟件工程學院

      參  考  文  獻

      [1]林開欽,白羽,王倩,柴強. 一種改進的星間鏈路深度優先路由搜索算法[C]//第十二屆中國衛星導航年會論文集——S06 時間基準與精密授時.[出版者不詳],2021:98-101.DOI:10.26914/c.cnkihy.2021.002192.

      [2]https://redis.io/documentation [2021.10.2]

      [3]https://www.rabbitmq.com/getstarted.html [2021.10.3]

      [4]https://dubbo.apache.org/zh/docs/ [2021.10.5]

      [5]http://webmagic.io/docs/zh/ [2021.10.1]

       

      1作者:郭怡然 來源:中國新通信 編輯:顧北

       

      聲明:①凡本網注明“來源:通信界”的內容,版權均屬于通信界,未經允許禁止轉載、摘編,違者必究。經授權可轉載,須保持轉載文章、圖像、音視頻的完整性,并完整標注作者信息并注明“來源:通信界”。②凡本網注明“來源:XXX(非通信界)”的內容,均轉載自其它媒體,轉載目的在于傳遞更多行業信息,僅代表作者本人觀點,與本網無關。本網對文中陳述、觀點判斷保持中立,不對所包含內容的準確性、可靠性或完整性提供任何明示或暗示的保證。請讀者僅作參考,并請自行承擔全部責任。③如因內容涉及版權和其它問題,請自發布之日起30日內與本網聯系,我們將在第一時間刪除內容。 
      熱點動態
      普通新聞 中信科智聯亮相2023中國移動全球合作伙伴大會
      普通新聞 全球首個基于Data Channel的新通話商用網絡呼叫成功撥通
      普通新聞 中國聯通:以優質通信服務 助力“一帶一路”共建繁華
      普通新聞 楊杰:未來五年,智算規模復合增長率將超過50%
      普通新聞 長沙電信大樓火災調查報告發布:系未熄滅煙頭引燃,20余人被問責
      普通新聞 鄔賀銓:生態短板掣肘5G潛能發揮,AI有望成“破局之劍”
      普通新聞 工信部:加大對民營企業參與移動通信轉售等業務和服務創新的支持力
      普通新聞 摩爾線程亮相2023中國移動全球合作伙伴大會,全功能GPU加速云電腦體
      普通新聞 看齊微軟!谷歌表示將保護用戶免受人工智能版權訴訟
      普通新聞 聯想王傳東:AI能力已成為推動產業升級和生產力躍遷的利刃
      普通新聞 APUS李濤:中國的AI應用 只能生長在中國的大模型之上
      普通新聞 外媒:在電池競賽中,中國如何將世界遠遠甩在后面
      普通新聞 三星電子預計其盈利能力將再次下降
      普通新聞 報告稱華為5G專利全球第1 蘋果排名第12
      普通新聞 黨中央、國務院批準,工信部職責、機構、編制調整
      普通新聞 榮耀Magic Vs2系列正式發布,刷新橫向大內折手機輕薄紀錄
      普通新聞 GSMA首席技術官:全球連接數超15億,5G推動全行業數字化轉型
      普通新聞 北京聯通完成全球首個F5G-A“單纖百T”現網驗證,助力北京邁向萬兆
      普通新聞 中科曙光亮相2023中國移動全球合作伙伴大會
      普通新聞 最高補貼500萬元!哈爾濱市制定工業互聯網專項資金使用細則
      通信視界
      鄔賀銓:移動通信開啟5G-A新周期,云網融合/算
      普通對話 中興通訊徐子陽:強基慧智,共建數智熱帶雨
      普通對話 鄔賀銓:移動通信開啟5G-A新周期,云網融合
      普通對話 華為輪值董事長胡厚崑:我們正努力將5G-A帶
      普通對話 高通中國區董事長孟樸:5G與AI結合,助力提
      普通對話 雷軍發布小米年度演講:堅持做高端,擁抱大
      普通對話 聞庫:算網融合正值挑戰與機遇并存的關鍵階
      普通對話 工信部副部長張云明:我國算力總規模已居世
      普通對話 鄔賀銓:我國互聯網平臺企業發展的新一輪機
      普通對話 張志成:繼續加強海外知識產權保護工作 為助
      普通對話 吳春波:華為如何突破美國6次打壓的逆境?
      通信前瞻
      亨通光電實踐數字化工廠,“5G+光纖”助力新一
      普通對話 亨通光電實踐數字化工廠,“5G+光纖”助力新
      普通對話 中科院錢德沛:計算與網絡基礎設施的全面部
      普通對話 工信部趙志國:我國算力總規模居全球第二 保
      普通對話 鄔賀銓院士解讀ChatGPT等數字技術熱點
      普通對話 我國北方海區運用北斗三號短報文通信服務開
      普通對話 華為云Stack智能進化,三大舉措賦能政企深度
      普通對話 孟晚舟:“三大聚力”迎接數字化、智能化、
      普通對話 物聯網設備在智能工作場所技術中的作用
      普通對話 軟銀研發出以無人機探測災害被埋者手機信號
      普通對話 AI材料可自我學習并形成“肌肉記憶”
      普通對話 北斗三號衛星低能離子能譜儀載荷研制成功
      普通對話 為什么Wi-Fi6將成為未來物聯網的關鍵?
      普通對話 馬斯克出現在推特總部 收購應該沒有懸念了
      普通對話 臺積電澄清:未強迫員工休假或有任何無薪假
      普通對話 新一代載人運載火箭發動機研制獲重大突破
      推薦閱讀
      Copyright @ Cntxj.Net All Right Reserved 通信界 版權所有
      未經書面許可,禁止轉載、摘編、復制、鏡像
      亚洲超碰在线91,亚洲九九在线网站,亚洲精品欧美一级A片在线播放,亚洲精品4444