干貨 | VRPTW子問題ESPPRC的介紹及其求解算法的C++代碼
wake up
各位小伙伴大家好，相信大家已經(jīng)看過前面Column Generation求解VRPTW的線性松弛模型的過程詳解了。
子問題的目標是找到一條reduced cost最小的合法路徑，然后加入到Linear Master Problem中。其實，子問題被稱為Elementary Shortest Path Problem with Resource Constraints （ESPPRC）也是一個著名的NP-Hard問題，今天我們就來詳細介紹一下。
01 ESPPRC
考慮圖1.1中描述的網(wǎng)絡。除了每條邊的成本c_ij之外，還存在經(jīng)過邊（i，j）的所消耗的資源t_ij，比如時間。我們的目標是找到從開始節(jié)點到結束節(jié)點的最短路徑，每個節(jié)點只能訪問一次，同時使得資源消耗滿足可用的資源約束，比如全程不能超過多少時間[1]。
當然上面描述問題只是ESPPRC中的一個例子，實際的資源約束可能有很多種，比如在VRPTW的子問題中[2]：
起始節(jié)點和結束節(jié)點一樣，每個節(jié)點有固定的時間窗和固定的需求，車輛不能超過容量約束的要求等等。
ESPPRC vs SPPRC
SPPRC和ESPPRC一樣，只不過SPPRC去掉了elementary的約束，允許最短路中一個節(jié)點被訪問多次。
02 應用
我們知道，ESPPRC可以應用在Column Generation中的算法框架中的。那么具體是怎么應用的呢？
我們知道，在Column Generation中，子問題每次迭代就是找一條reduced cost最小的路徑，然后加入到Master Problem中。但是對于ESPPRC來說，每次的cost一樣的，那不每次都求出同一條路徑嗎？？？
不！在Column Generation中，其子問題ESPPRC中邊的cost是會隨著Linear Master Problem的對偶變量值的改變而改變的。還記得reduced cost是怎么計算的嗎？
其中，式子(22)可以表達成式子(23)。(23)是什么意思呢？b_ijk意思是邊ij是否在路徑k中。
那么，在每一次迭代中，我們就可以利用Linear Master Problem的對偶變量，來更新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é)介紹一個ESPPRC的精確算法Pulse Algorithm[5]，算法的偽代碼如下：
其中：
r：表示到達當前節(jié)點時的cost；
q：表示到達當前節(jié)點時的裝載量；
t：表示到達當前節(jié)點所需的總時間，早到需要等待，不能晚到。
大體的思想是通過bound算法確定到達每個節(jié)點的最低cost，然后pulse進行路徑搜索，而之前bound求出來的最低cost就可以在pulse搜索的過程中起到定界的作用，去掉一些不好的路徑。
bound的算法如下：
每個節(jié)點的最低cost（相當于一個lower bound）是怎么算出來的呢？簡單來說是通過限定每個節(jié)點最晚到達時間。
在每個節(jié)點都給定最晚到達時間t，然后計算在這個最晚到達時間下，每個到達每個節(jié)點的最低cost。
然后讓t遞減，直到t減少到臨界值。最終得到的是每個節(jié)點關于各個最晚到達時間的最低cost矩陣。
最后來看看pulse算法：
pulse是找路的過程，在該過程中：
isFeasible檢查到達節(jié)點時路徑是否滿足各種資源約束。
checkBounds檢查在當前到達時間下，到達節(jié)點的cost是否小于等于之前bound算法求出來的那個最晚時間下的最低cost，如果不是就丟棄該支路徑。
rollback進行如下檢查：
在每一個節(jié)點（開始節(jié)點除外），比如上圖中節(jié)點j，如果實線路徑的cost < 虛線路徑的cost。那么砍掉實線的路徑（已經(jīng)有人的cost比你更低，你可以卷鋪蓋走人了），這就相當于一個回滾的操作，回滾到節(jié)點i的狀態(tài)，然后直接走虛線路徑。
以上就是整個pulse算法。這里只是起到一個拋磚引玉的過程?？赡苤v的不是很詳細，詳細的過程請大家去閱讀文獻。
05 算法代碼
關于整個pulse算法偽代碼和講解已經(jīng)夠詳細了，這里給出一個C++的實現(xiàn)代碼，是我遠房的一個學長的學姐的男朋友寫的（真話）。關于編譯運行上面也說明得夠詳細了。
代碼下載請移步留言區(qū)。
【如對代碼有疑問，可聯(lián)系小編，可以提供有償輔導服務】
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