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

一、最短路問題(SPP)

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

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

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

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

二、label-setting算法

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

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

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

通常來說,在寫labeling算法時,為了加快算法的運行速度,都需要加上dominance規(guī)則,即把一些潛在的比較差的label給干掉,避免它繼續(xù)往下擴展浪費時間。注意,我上面用了潛在,因為如果要完全確定一個label比另一個label差的話,得一直擴展到終點。而dominance rule能通過一些判斷,把擴展到中間的一些沒有潛力的label給干掉。

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

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

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

當然使用距離作為cost這個是比較容易證明的,其他情況的話,可能會比較復雜一點。

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

三、小結(jié)

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

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

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