[發(fā)明專利]一種基于重優(yōu)化技術(shù)的物流網(wǎng)絡(luò)高效K最短路徑算法

在審

• 申請(qǐng)?zhí)枺?/td>: 202010003810.8
• 申請(qǐng)日: 2020-01-03
• 公開(kāi)（公告）號(hào): CN111210065A
• 公開(kāi)（公告）日: 2020-05-29
• 發(fā)明（設(shè)計(jì)）人: 陳碧宇;陳小威;林興強(qiáng)
• 申請(qǐng)（專利權(quán)）人: 武漢大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/08;G06F17/18
• 代理公司: 武漢科皓知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42222
• 代理人: 魯力

本發(fā)明提供一種基于重優(yōu)化技術(shù)的物流網(wǎng)絡(luò)高效K最短路徑算法，用于快速生成K條無(wú)環(huán)的最短路徑，主要用于諸如交通網(wǎng)絡(luò)、物流網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等網(wǎng)絡(luò)優(yōu)化中高效地查找K條最短路徑。本發(fā)明將偏離路徑計(jì)算過(guò)程表達(dá)為在一個(gè)每次還原一個(gè)節(jié)點(diǎn)和一條邊的動(dòng)態(tài)網(wǎng)絡(luò)中進(jìn)行最短路徑搜索。本發(fā)明采用Life Long A*重優(yōu)化技術(shù)，通過(guò)重新利用上一次最短路徑搜索生成的最短路徑樹(shù)，對(duì)最短路徑樹(shù)進(jìn)行局部更新，本發(fā)明能夠高效地計(jì)算偏離路徑。本發(fā)明能夠獲得同其他偏離路徑算法一致的結(jié)果，同時(shí)運(yùn)算性能也優(yōu)于現(xiàn)有其他偏離路徑算法。

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)優(yōu)化中的K最短路徑計(jì)算技術(shù)領(lǐng)域，具體涉及一種基于重優(yōu)化技術(shù)的物流網(wǎng)絡(luò)高效K最短路徑算法。

背景技術(shù)

K最短路徑問(wèn)題，即在起點(diǎn)和終點(diǎn)之間查找第一條最短路徑、第二條最短路徑，…，直到第K條最短路徑，其在交通運(yùn)輸、通信網(wǎng)絡(luò)、物流等領(lǐng)域都有著廣泛的應(yīng)用。作為最短路徑問(wèn)題的擴(kuò)展，K最短路徑問(wèn)題一直是交通、物流、運(yùn)籌學(xué)等領(lǐng)域的研究重點(diǎn)，文獻(xiàn)中有大量的學(xué)者提出了解決算法，其中大部分算法是基于Yen(1971)提出的偏離路徑概念。隨著近年來(lái)交通、物流等網(wǎng)絡(luò)規(guī)模逐步擴(kuò)大，傳統(tǒng)基于偏離路徑概念的K最短路徑算法計(jì)算效率變得越來(lái)越低下，已無(wú)法滿足大規(guī)模網(wǎng)絡(luò)實(shí)時(shí)計(jì)算的要求。

針對(duì)以上問(wèn)題，國(guó)內(nèi)外學(xué)者提出了大量的改進(jìn)算法。Martins和Pascoal提出一種逆向計(jì)算偏離路徑的高效算法，在他的算法中構(gòu)建并更新一顆以目的地為根節(jié)點(diǎn)的最短路徑樹(shù)，以便能夠利用先前的搜索結(jié)果。該算法性能優(yōu)于原始的Yen’s算法，然而依然需要更新整個(gè)最短路徑樹(shù)，效率低下。Vanhove和Fack(2012)提出了一種準(zhǔn)確算法，該算法通過(guò)后向一對(duì)多的Dijkstra算法預(yù)計(jì)算所有節(jié)點(diǎn)到目的地的最短路徑，在計(jì)算偏離路徑時(shí)，通過(guò)判斷組合的偏離路徑是否有環(huán)來(lái)決定是否利用預(yù)計(jì)算的結(jié)果，然而大部分情況下預(yù)計(jì)算的結(jié)果無(wú)法利用。這些改進(jìn)的算法在計(jì)算效率上較原始Yen’s算法都所提升，然而，這些算法在計(jì)算偏離路徑集嚴(yán)重依賴最短路徑的計(jì)算效率，仍然存在較大的計(jì)算負(fù)擔(dān)，尤其是當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，依然存在計(jì)算效率低的問(wèn)題。

發(fā)明內(nèi)容

本發(fā)明提出一種基于重優(yōu)化技術(shù)的K最短路徑算法，用于高效地在大規(guī)模網(wǎng)絡(luò)中準(zhǔn)確查找K條最短路徑。本發(fā)明采用從終點(diǎn)到起點(diǎn)的逆向方式計(jì)算偏離路徑，構(gòu)建以終點(diǎn)為根的最短路徑樹(shù)。在每次計(jì)算偏移路徑時(shí)，還原一個(gè)節(jié)點(diǎn)和一條邊，利用Life Long A*重優(yōu)化技術(shù)，通過(guò)重用上一步偏移路徑搜索的最短路徑樹(shù)結(jié)果，高效地獲得計(jì)算偏移路徑。本發(fā)明能夠獲得與其他K最短路徑算法一致的最優(yōu)解，能夠大大提升大規(guī)模網(wǎng)絡(luò)中K條最短路徑計(jì)算的效率。

本發(fā)明具體包括以下步驟：

一種基于重優(yōu)化技術(shù)的物流網(wǎng)絡(luò)高效K最短路徑算法，包括以下步驟：

步驟1、輸入物流網(wǎng)絡(luò)數(shù)據(jù)以及當(dāng)前物流參數(shù)，所述物流網(wǎng)絡(luò)數(shù)據(jù)給定區(qū)域所有的路段，并將路段進(jìn)行抽象化，具體是：采集給定區(qū)域內(nèi)所有物流網(wǎng)絡(luò)數(shù)據(jù)，并將該區(qū)域內(nèi)物流網(wǎng)絡(luò)數(shù)據(jù)中所有路段抽象成有向邊a(n_u,n_v)，每條邊有兩個(gè)端節(jié)點(diǎn)n_u,n_v，以及一個(gè)權(quán)重值t(n_u,n_v)(如：行程時(shí)間、距離、運(yùn)輸時(shí)間、中轉(zhuǎn)次數(shù)、物流車輛數(shù))，每個(gè)節(jié)點(diǎn)n_u包含若干列前繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)，分別用PRED(n_u)和SUCC(n_u)表示，當(dāng)前物流參數(shù)包括起點(diǎn)o、目的地d、路徑數(shù)K；

步驟2、根據(jù)當(dāng)前輸入物流參數(shù)，調(diào)用物流網(wǎng)絡(luò)數(shù)據(jù)，得到當(dāng)前輸入物流參數(shù)所在區(qū)域的物流路段數(shù)據(jù)，并針對(duì)物流路段數(shù)據(jù)執(zhí)行如下步驟：

步驟2.1，初始化，包括以下子步驟，

S101,調(diào)用Dijkstra算法計(jì)算從起點(diǎn)o和目的地d的第一條最短路徑標(biāo)號(hào)p¹；