[發明專利]一種裝卸次數受限的快速復合運輸路徑規劃方法

在審

• 申請號: 202210673769.4
• 申請日: 2022-06-15
• 公開（公告）號: CN115187158A
• 公開（公告）日: 2022-10-14
• 發明（設計）人: 盧文聯;陳發君
• 申請（專利權）人: 復旦大學
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06Q10/04
• 代理公司: 上海德昭知識產權代理有限公司 31204
• 代理人: 陳龍梅

本發明提供一種裝卸次數受限的快速復合運輸路徑規劃方法，用于在指定最大裝卸次數約束條件下，輸出頂點之間的最短路徑。該方法在Lewis算法的基礎上，增加了對裝卸次數的限制，在裝卸次數受限條件下實現了快速復合運輸路徑規劃算法。相較于現有算法，本發明的快速復合運輸路徑規劃方法不僅解決了復合運輸中最短路徑的求解問題，還在不引入額外的計算復雜性的情況下，從裝卸次數的角度出發，靈活實現裝卸次數受限的快速復合運輸路徑規劃，降低復合運輸的成本，為復合運輸提供便利，具有較高的適用性。

技術領域

本發明屬于路徑規劃領域，具體涉及一種裝卸次數受限的快速復合運輸路徑規劃方法。

背景技術

復合運輸路徑規劃中，存在兩種以上運輸方式，不同運輸方式之間切換需要進行裝卸操作，比如公路和鐵路運輸之間銜接，需要在火車站點進行裝卸操作。目前，一般做法是把裝卸操作折算為路徑規劃成本，如果目標是求最短路徑，那么折算為路徑長度，如果目標是求最快路徑，那么折算為時間，然后使用擴展Dijkstra算法進行路徑規劃。然而，在實際作業中，裝卸開銷并不好度量，會受很多因素的影響，用戶提出得需求更多情況時希望限定裝卸次數。

Dijkstra算法[1]是求解網絡中兩個頂點之間最短路徑的算法，在不考慮特殊數據結構的情況下計算復雜性是O(n²)，使用堆結構優化排序計算復雜性提高到O(m+nlog(n))。Dijkstra算法本身不能求解復合運輸中的路徑規劃問題，其主要利用了邊的長度屬性，在網絡拓撲結構中累加計算，選取達到頂點的最小值作為最短路徑長度，所以Dijkstra算法中每個標記的頂點只能有一個從起點出發的最短路徑值。

因為Dijkstra算法限定每個標記頂點只存儲了一個最優最短路徑值，然而，在復合運輸網絡中，途徑不同的運輸方式，經過不同數量的裝卸過程后，到達同一個位置的最短路徑值并不相同，所以Dijkstra算法本身不能用于求解裝卸次數受限的復合運輸路徑規劃問題。

Kirby-Potts擴展[2]把路網中每個頂點按到達或離開的運輸方式不同擴展為多個虛擬頂點，由于每個虛擬頂點只允許有一種到達或離開運輸方式，所以使用Dijkstra算法求解時，在虛擬頂點標記的最短路徑就是使用該運輸方式到達此節點的最短路徑，不能是其他運輸方式。Kirby-Potts擴展示意如圖6所示，為了抽象描述，把不同運輸方式用不同的顏色來標注，比如鐵路運輸使用紅色(圖6中粗線段)，公路運輸使用黑色(圖6中虛線段)等等，所以Kirby-Potts擴展后的復合運輸網絡也稱為著色網絡。

Kirby-Potts擴展網絡雖然能夠使用Dijkstra算法求解，但是頂點數量增加了M倍，所以計算復雜性增加了M²，基于Kirby-Potts的復合運輸路徑規劃算法計算復雜性為O(M²n²)。

Rhyd Lewis[3]在分析Kirby-Potts擴展的基礎上，提出以空間換時間的策略，算法在標記節點是還是以原始節點為基礎，同時對所有虛擬節點進行計算，所以Lewis算法沒有增加Dijkstra算法的計算復雜性，但是需要更多的存儲空間，如圖7所示。

雖然Lewis算法相比Kirby-Potts擴展算法提高了計算效率，能夠求解復合運輸網絡路徑規劃問題，但是Lewis算法依然只是把裝卸開銷折算為一種代價與路徑長度相加，計算從起點到終點的最短路徑，并沒有從裝卸次數的角度進行算法設計。

參考文獻：

[1]E.W.Dijkstra,“A note on two problems in connexion with graphs,”Numer.Math.,vol.1,no.1,pp.269–271,Dec.1959,doi:10.1007/BF01386390.