[發明專利]基于位序的多式聯運有效路徑搜索方法

在審

• 申請號: 202211534930.6
• 申請日: 2022-11-30
• 公開（公告）號: CN116090940A
• 公開（公告）日: 2023-05-09
• 發明（設計）人: 周博見;李世豪;陳婧煦;董瀟瀟;陳曉偉;張永
• 申請（專利權）人: 東南大學
• 主分類號: G06Q10/0835
• 分類號: G06Q10/0835;G06Q10/047
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 陳月菊

本發明公開了一種基于位序的多式聯運有效路徑搜索方法，包括如下步驟：S1、采集各運輸方式下的多式聯運路網數據；S2、初始化多式聯運網絡S3：確定搜索的基準面；S4：采用坐標變換的方式確定節點與基準面的相對位置；S5：基于位序確定定向搜索節點的順序；S6：建立多式聯運所有節點的轉運時間集；S7：輸入多式聯運路段時間成本；S8：基于位序進行搜索多式聯運有效路徑；S9：建立時間成本最小的多式聯運的有效路徑集；S10：終止本次起訖點的搜索，重新選取另一對起訖點，重復以上搜索過程。本發明能夠有效保證在費用確定、時間不確定的情況下，不重復、不遺漏地選擇出時間成本最低轉運次數滿足要求的多式聯運有效路徑。

技術領域

本發明屬于多式聯運技術領域，更具體地說，涉及一種基于位序的多式聯運有效路徑搜索方法。

背景技術

多式聯運指由兩種及其以上的交通工具相互銜接、轉運而共同完成的運輸過程，也可以稱為復合運輸。多式聯運正成為國家間運輸業務活動的主要組織形式和未來物流的主要發展趨勢，也是我國物流行業發展的主要研究方向。在為不同的用戶提供路網的最優路徑時，系統所需要提供的不僅是一條最優出行路徑，而應是一個有效路徑集，在一個有效路徑集上導行，可以有效地避免由于單一路徑誘導可能產生的“過激反應”從而避免在路網中產生新的擁堵，同時在實際的配流過程中，例如隨機用戶均衡模型配流時也需要以有效路徑為基礎進行。目前針對城市交通道路的有效路徑的定義是指它所包含的所有路段都使得乘客距離初始點的最小費用越來越大，同時距離終訖點的最小費用越來越小。

目前，網絡路徑搜索方法大多是針對城市交通道路網絡，針對復合型網絡的研究較少。目前的城市道路網絡路徑搜索方法運用在多式聯運網絡時，不能有效反應多式聯運路徑類型改變(例如鐵路轉公路、公路轉水路等等)，同時忽略了轉運次數過高導致運輸時間的浪費以及運輸安全性下降的特點，也不能反應多式聯運網絡一定程度上允許路段不完全距離初始點的最小費用越來越大，距離終訖點的最小費用越來越小的特點。

發明內容

有鑒于此，本發明提供了一種基于位序的多式聯運有效路徑搜索方法，用于解決多式聯運網絡的有效路徑搜索問題。本方法首先針對多式聯運路網的特殊性提出多式聯運有效路徑的定義，然后針對多式聯運有效路徑設計出基于位序的搜索算法，該方法解決了常規城市道路網路徑搜索算法不適用多式聯運道路網的問題，且搜索過程基于節點位序，有效避免了搜索過程的重復，大大節省了搜索時間，非常適合求解多式聯運路網的有效路徑搜索問題。

為了解決上述技術問題至少之一，根據本發明的一方面，提供了一種基于位序的多式聯運有效路徑搜索方法，包括如下步驟：

S1、采集各運輸方式下的多式聯運路網數據，根據多式聯運路網數據建立各運輸方式下運輸網絡中各節點及各路段的連通信息，根據連通信息連接不同運輸方式的運輸網絡，得到多式聯運網絡；

S2、初始化多式聯運網絡；輸入起始節點集和終訖節點集，路網中所有節點的坐標信息，以及建立每個節點的相鄰節點集；

S3：確定搜索的基準面；

S4：采用坐標變換的方式確定節點與基準面的相對位置；

S5：基于位序確定定向搜索節點的順序，包括確定容忍系數、創建同位序節點集以及在對同位序節點集中的節點按照排列組合原理羅列后按照位序對所有節點排序；

S6：建立多式聯運所有節點的轉運時間集；

S7：輸入多式聯運路段時間成本；

S8：基于位序進行搜索多式聯運有效路徑，包括初始化、檢查搜索節點判斷相鄰節點集的搜索情況、判斷轉運次數是否超過最大允許轉運次數、判斷是否完成搜索并在完成搜索后進行下一節點的搜索；

S9：建立時間成本最小的多式聯運的有效路徑集；