技術(shù)分析：最短路問題中的label-setting算法

2021-01-09 16:14

時間過得真快!轉(zhuǎn)眼間一年又過去了,我記得上一次寫推文還是在去年。前段時間一直在做Label Setting相關(guān)的研究,今天趁著有空了,趕緊來聊一下吧～

一、最短路問題(SPP)

最短路問題(Shortest Path Problems)相信學(xué)過運(yùn)籌學(xué)的小伙子們都不陌生了,就是給定一個網(wǎng)絡(luò),網(wǎng)絡(luò)的邊上有權(quán)重,找一條從給定起點(diǎn)到給定終點(diǎn)的路徑使路徑上的邊權(quán)重總和最小。其實(shí)從廣義上來說,他是一個非常大的分類。在近幾十年的研究中,涌現(xiàn)了很多最短路問題的變種。

最簡單的就是下面這種,不帶任何約束的,只要路是想通的,就隨便你怎么走,反正最后是cost最低就好了。

稍微難一點(diǎn)的就是在上面的基礎(chǔ)上,加上資源約束,變成了帶資源約束的最短路問題。也就是說,不僅要cost最低,還得滿足一些奇奇怪怪的約束。比如下面的這種。定點(diǎn)上面[]表示的是時間窗,邊上面()第一個元素表示經(jīng)過這條邊所需要時間,第二個元素表示經(jīng)過這條邊所需要花費(fèi)的成本。一般來說成本和時間是正相關(guān)的,但是也有例外,比如車輛下坡的時候成本是很低。

第三種常見的,就是在上面的基礎(chǔ)上再加一個約束,即限定每個點(diǎn)只能被經(jīng)過一次,變成了Elemental Shortest Path Problems。這個問題可以變成很多利用column generation求解車輛路徑問題的子問題。

二、label-setting算法

對于最簡單的最短路問題,比較流行的算法就是Floyd算法和Dijkstra算法,這個相信大家學(xué)過運(yùn)籌學(xué)都懂的啦。Dijkstra算法跟貪心有點(diǎn)像,而Floyd算法跟動態(tài)規(guī)劃又有點(diǎn)像,這兩個都是精確算法哦。

而對于帶資源約束的最短路問題,目前比較流行的精確算法有modeling(構(gòu)建arc-flow或者什么模型,調(diào)用solver進(jìn)行求解)、label-setting、label-currenting以及前些年提出來的pulse算法。

而labeling算法其實(shí)就是動態(tài)規(guī)劃,算法從起始點(diǎn)開始,不斷往后進(jìn)行擴(kuò)展,用label記錄當(dāng)前的資源使用情況以及累計的cost,進(jìn)行新擴(kuò)展時通過當(dāng)前l(fā)abel,判斷下一個可達(dá)點(diǎn)是否滿足擴(kuò)展的條件,滿足資源約束時才前往到下一個節(jié)點(diǎn)。如圖中畫虛線的就是資源不滿足的情況

通常來說,在寫labeling算法時,為了加快算法的運(yùn)行速度,都需要加上dominance規(guī)則,即把一些潛在的比較差的label給干掉,避免它繼續(xù)往下擴(kuò)展浪費(fèi)時間。注意,我上面用了潛在,因?yàn)槿绻耆_定一個label比另一個label差的話,得一直擴(kuò)展到終點(diǎn)。而dominance rule能通過一些判斷,把擴(kuò)展到中間的一些沒有潛力的label給干掉。

接下來講講dominance rules,通常來說,對于到達(dá)了同一個點(diǎn)的兩個Label 和, 我們假定表示從出發(fā)擴(kuò)展到終點(diǎn)的所有子路徑集合,而表示一條完整路徑的cost,能把干掉,需要滿足以下兩個條件:

對于第一個條件的判斷是非常容易的,通過記錄已訪問的點(diǎn),即可得出未訪問的點(diǎn)集合,假設(shè)未訪問的點(diǎn)集合,如果,那么久等同于能擴(kuò)展的路徑數(shù)≥。當(dāng)然你結(jié)合當(dāng)前點(diǎn)的到達(dá)時間+時間窗(如果有的話),也能進(jìn)行這個判斷,并且后面這種方式可能會快點(diǎn),大家可以在課后想想。

但是第二個條件比較復(fù)雜一點(diǎn),因?yàn)橐杜e中所有的子路徑,這個枚舉量隨著節(jié)點(diǎn)數(shù)的增加,將是非常大的。因此我們往往在label中記錄一些資源的消耗情況,從而通過這些情況推導(dǎo)出第二個條件。比如,路徑的cost為整條路徑的距離時(記為),在滿足第一個條件的基礎(chǔ)上,只需要即可。這是很容易想明白的,因?yàn)?我們有

當(dāng)然使用距離作為cost這個是比較容易證明的,其他情況的話,可能會比較復(fù)雜一點(diǎn)。

所有的dominance rules都是以這兩條為基礎(chǔ)的,也就是說dominance rules生效的前提是得滿足上面那兩個條件,不然你把不該dominance的label給干掉了,很可能就得不出最優(yōu)解了。總的來說,labeling算法的實(shí)現(xiàn)還是比較簡單的,前提是你要把dominance rules推好,把extension condition和extension function都寫好。

三、小結(jié)

其實(shí)labeling算法是解決最短路問題一種比較有效的方法,現(xiàn)在很多branch and price的文獻(xiàn)中都是用的labeling,其實(shí)這個東西難點(diǎn)就在于如何推導(dǎo)dominance rules加快算法的速度。并且對于大多數(shù)dominance rules都需要給出嚴(yán)格的證明。

還有雙向labeling,就是同時前向和后向進(jìn)行擴(kuò)展,然后對兩個前后向的標(biāo)簽進(jìn)行拼接。通過限制擴(kuò)展迭代的條件,對整個branch and price算法進(jìn)行加速。這個,以后有時間我再介紹啦!

最后,關(guān)于最短路問題,公眾號之前已經(jīng)做過系列更專業(yè)的教程了,大家可以去翻翻歷史消息。