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

在審

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

1.一種裝卸次數受限的快速復合運輸路徑規劃方法，用于在指定最大裝卸次數約束條件下，輸出頂點之間的最短路徑，其特征在于，包括：

步驟S1，對路網中所有頂點執行Kirby-Potts擴展，生成各自對應的元組(v,c,i,l,n)，該元組包含的元素有反向指向其對應的原始頂點運v、運輸方式c、出入方向i、從起點到當前頂點的路徑長度l以及從起點到當前頂點經過的裝卸次數n；

步驟S2，選定最大裝卸次數n_max，選定起點v_src和終點v_dst，基于起點v_src的Kirby-Potts擴展，構建方向為出即i＝OUT的初始元組序列Q；

步驟S3，判斷所述初始元組序列Q是否為空；

步驟S4，當步驟S3判斷為是時，表示起點到終點不存在可達路徑，結束規劃；

步驟S5，當步驟S3判斷為否時，從所述初始元組序列Q中選擇具有最小l值的元組p(v,c,i,l,n)，標記該元組；

步驟S6，判斷標記的元組p(v,c,i,l,n)中i的方向；

步驟S7，當步驟S6判斷為IN時，選取從IN能夠轉換為OUT的元組，標記該元組為p2；

步驟S8，判斷元組p2中的運輸方式與所述標記的元組中的運輸方式是否相同；

步驟S9，當步驟S8判斷為否時，則記臨時路徑成本為c_tmp＝p(l)+c_tx，c_tx為換乘成本，并增加一次裝卸次數n_tmp＝p(n)+1；

步驟S10，當步驟S8判斷為是時，表示進入頂點和離開頂點的運輸方式相同，則路徑成本和裝卸次數不變；

步驟S11，判斷裝卸次數n_tmpn_max；

步驟S12，當步驟S11判斷為是時，p2元組不變；

步驟S13，當判斷為否時，判斷c_tmpp2(l)，如果判斷為否，則p2的路徑成本無變化，如果判斷為是則更新p2(l)＝c_tmp，把更新后的p2放入序列Q中然后進入步驟S16；

步驟S14，當步驟S6判斷為OUT時，選擇能夠從OUT轉換為IN、運輸方式一致并且未被標記的元組，記為p2，則有p2(c)＝p(c)；

步驟S15，計算此時的臨時轉化路徑成本c_tmp＝p(l)+w(p(v),p2(v))，其中w為頂點之間邊的路徑成本，并判斷c_tmpp2(l)，當判斷為是時，將p2放入序列Q中然后進入步驟S16；

步驟S16，判斷p2(v)＝v_dst，即當前頂點是否為終點；

步驟S17，當步驟S16判斷為是時，表示起點v_src和終點v_dst的最短路徑存在，計算總換乘次數以及總路徑成本；否則重復執行步驟S5至步驟S17直至結束。

2.一種計算機可讀的存儲介質，用于存儲計算機程序，其特征在于，所述計算機程序被配置成執行時實現權利要求1中所述的一種裝卸次數受限的快速復合運輸路徑規劃方法。