干貨 | VRPTW子問題ESPPRC的介紹及其求解算法的C++代碼

wake up

各位小伙伴大家好，相信大家已經(jīng)看過前面Column Generation求解VRPTW的線性松弛模型的過程詳解了。

子問題的目標(biāo)是找到一條reduced cost最小的合法路徑，然后加入到Linear Master Problem中。其實(shí)，子問題被稱為Elementary Shortest Path Problem with Resource Constraints （ESPPRC）也是一個(gè)著名的NP-Hard問題，今天我們就來詳細(xì)介紹一下。

01 ESPPRC

考慮圖1.1中描述的網(wǎng)絡(luò)。除了每條邊的成本c_ij之外，還存在經(jīng)過邊（i，j）的所消耗的資源t_ij，比如時(shí)間。我們的目標(biāo)是找到從開始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的最短路徑，每個(gè)節(jié)點(diǎn)只能訪問一次，同時(shí)使得資源消耗滿足可用的資源約束，比如全程不能超過多少時(shí)間[1]。

當(dāng)然上面描述問題只是ESPPRC中的一個(gè)例子，實(shí)際的資源約束可能有很多種，比如在VRPTW的子問題中[2]：

起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)一樣，每個(gè)節(jié)點(diǎn)有固定的時(shí)間窗和固定的需求，車輛不能超過容量約束的要求等等。

ESPPRC vs SPPRC

SPPRC和ESPPRC一樣，只不過SPPRC去掉了elementary的約束，允許最短路中一個(gè)節(jié)點(diǎn)被訪問多次。

02 應(yīng)用

我們知道，ESPPRC可以應(yīng)用在Column Generation中的算法框架中的。那么具體是怎么應(yīng)用的呢？

我們知道，在Column Generation中，子問題每次迭代就是找一條reduced cost最小的路徑，然后加入到Master Problem中。但是對(duì)于ESPPRC來說，每次的cost一樣的，那不每次都求出同一條路徑嗎？？？

不！在Column Generation中，其子問題ESPPRC中邊的cost是會(huì)隨著Linear Master Problem的對(duì)偶變量值的改變而改變的。還記得reduced cost是怎么計(jì)算的嗎？

其中，式子(22)可以表達(dá)成式子(23)。(23)是什么意思呢？b_ijk意思是邊ij是否在路徑k中。

那么，在每一次迭代中，我們就可以利用Linear Master Problem的對(duì)偶變量，來更新ESPPRC中每條邊的cost，最終求得的路徑cost就是Column Generation中的reduced cost。

03?常見的算法

ESPPRC的建模如下[4]：

求解SPPRC和ESPPRC常見的算法主要有以下幾種[3]：

• Dynamic programming and labeling algorithms

• Lagrangean relaxation

• Constraint programming(建模)

• Heuristics

  
  

04?Pulse Algo

這一節(jié)介紹一個(gè)ESPPRC的精確算法Pulse Algorithm[5]，算法的偽代碼如下：

其中：

r：表示到達(dá)當(dāng)前節(jié)點(diǎn)時(shí)的cost；

q：表示到達(dá)當(dāng)前節(jié)點(diǎn)時(shí)的裝載量；

t：表示到達(dá)當(dāng)前節(jié)點(diǎn)所需的總時(shí)間，早到需要等待，不能晚到。

大體的思想是通過bound算法確定到達(dá)每個(gè)節(jié)點(diǎn)的最低cost，然后pulse進(jìn)行路徑搜索，而之前bound求出來的最低cost就可以在pulse搜索的過程中起到定界的作用，去掉一些不好的路徑。

bound的算法如下：

每個(gè)節(jié)點(diǎn)的最低cost（相當(dāng)于一個(gè)lower bound）是怎么算出來的呢？簡單來說是通過限定每個(gè)節(jié)點(diǎn)最晚到達(dá)時(shí)間。

在每個(gè)節(jié)點(diǎn)都給定最晚到達(dá)時(shí)間t，然后計(jì)算在這個(gè)最晚到達(dá)時(shí)間下，每個(gè)到達(dá)每個(gè)節(jié)點(diǎn)的最低cost。

然后讓t遞減，直到t減少到臨界值。最終得到的是每個(gè)節(jié)點(diǎn)關(guān)于各個(gè)最晚到達(dá)時(shí)間的最低cost矩陣。

最后來看看pulse算法：

pulse是找路的過程，在該過程中：

isFeasible檢查到達(dá)節(jié)點(diǎn)時(shí)路徑是否滿足各種資源約束。

checkBounds檢查在當(dāng)前到達(dá)時(shí)間下，到達(dá)節(jié)點(diǎn)的cost是否小于等于之前bound算法求出來的那個(gè)最晚時(shí)間下的最低cost，如果不是就丟棄該支路徑。

rollback進(jìn)行如下檢查：

在每一個(gè)節(jié)點(diǎn)（開始節(jié)點(diǎn)除外），比如上圖中節(jié)點(diǎn)j，如果實(shí)線路徑的cost < 虛線路徑的cost。那么砍掉實(shí)線的路徑（已經(jīng)有人的cost比你更低，你可以卷鋪蓋走人了），這就相當(dāng)于一個(gè)回滾的操作，回滾到節(jié)點(diǎn)i的狀態(tài)，然后直接走虛線路徑。

以上就是整個(gè)pulse算法。這里只是起到一個(gè)拋磚引玉的過程。可能講的不是很詳細(xì)，詳細(xì)的過程請(qǐng)大家去閱讀文獻(xiàn)。

05 算法代碼

關(guān)于整個(gè)pulse算法偽代碼和講解已經(jīng)夠詳細(xì)了，這里給出一個(gè)C++的實(shí)現(xiàn)代碼，是我遠(yuǎn)房的一個(gè)學(xué)長的學(xué)姐的男朋友寫的（真話）。關(guān)于編譯運(yùn)行上面也說明得夠詳細(xì)了。

代碼下載請(qǐng)移步留言區(qū)。

【如對(duì)代碼有疑問，可聯(lián)系小編，可以提供有償輔導(dǎo)服務(wù)】

References

[1]?Desrosiers J , Marco E. Lübbecke. A Primer in Column Generation. Column Generation, G. Desaulniers, J. Desrosiers, and M.M. Solomon (Eds.), Springer, 2005.

[2]?Feillet D . A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR: A Quarterly Journal of Operations Research, 2010, 8(4):407-424.

[3]?Irnich S . Shortest Path Problems with Resource Constraints. Column Generation, G. Desaulniers, J. Desrosiers, and M.M. Solomon (Eds.), Springer, 2005.

[4]?Feillet D , Dejax P , Gendreau M , et al. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, 2004, 44(3):216-229.

[5]?Leonardo Lozano, Daniel Duque, Andrés L. Medaglia (2016) An Exact Algorithm for the Elementary Shortest Path Problem with?Resource Constraints. Transportation Science 50(1):348-357.

END