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

一、最短路問(wèn)題(SPP)

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

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

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

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

二、label-setting算法

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

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

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

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

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

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

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

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

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

三、小結(jié)

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

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

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