干貨 | 求解VRPTW松弛模型的Column Generation算法的JAVA代碼分享

前言

經(jīng)過(guò)小編的不斷努力和修正，Column Generation + ESPPRC+ pulse algorithm的內(nèi)容終于寫(xiě)完了。此過(guò)程真是充滿曲折啊，希望大家看完多多支持一下。

運(yùn)行說(shuō)明

關(guān)于這部分的代碼，我們提供兩個(gè)版本。

第一個(gè)版本來(lái)自GitHub，是一個(gè)叫Seminar的國(guó)外大神寫(xiě)的。

他的子問(wèn)題采用上一篇推文介紹的模型，找一條reduced cost最短的路徑，運(yùn)行只需要更改下面文件中算例文件的路徑即可。

運(yùn)行的中間結(jié)果如下：

- Iteration：迭代次數(shù)

- SbTime：子問(wèn)題求解時(shí)間(s)

- nPaths：Master Problem中的總路徑

- MP lb：Master Problem的線性松弛最優(yōu)解，這里由于建模方式的原因，該最優(yōu)解把服務(wù)時(shí)間也算在路徑距離上的，最終減去9000即可得到路徑距離。

- SB lb：子問(wèn)題的線性松弛最優(yōu)解。

- SB int：子問(wèn)題的整數(shù)最優(yōu)解。

關(guān)于子問(wèn)題的最大求解時(shí)間限制(s)，可以在下面文件中設(shè)置：

第二個(gè)版本是小編寫(xiě)的：

運(yùn)行參數(shù)說(shuō)明：

-in：算例文件路徑；

-out：結(jié)果文件輸出。

比如：

【-in input\Solomon\100_customer\C101.TXT -out output\】

參數(shù)設(shè)置請(qǐng)找到以下主運(yùn)行文件：

右鍵找到運(yùn)行設(shè)置里面進(jìn)行配置。（默認(rèn)情況下輸入上面的參數(shù)能直接運(yùn)行）

中間結(jié)果：

- Iteration：迭代次數(shù)

- SbTime：子問(wèn)題求解時(shí)間(s)

- nPaths：MasterProblem中的總路徑

- MP lb：Master Problem的線性松弛最優(yōu)解。

- SB lb：子問(wèn)題的最優(yōu)解。

關(guān)于第一個(gè)版本，其子問(wèn)題建模方式還是依賴主問(wèn)題的對(duì)偶變量的，如下：

其中t_ij就是每條邊本來(lái)的cost，pi就是Master Problem的對(duì)偶變量。每一次迭代就是這樣更新子問(wèn)題的cost，重新建模求解的。

關(guān)于小編的版本：

每次迭代的時(shí)候會(huì)更新ESPPRC問(wèn)題中的cost，然后運(yùn)行pulse算法重新求解。

其他的話結(jié)構(gòu)和注釋都寫(xiě)得非常清晰了，大家肯定能看懂的。

由于是精確算法，子問(wèn)題時(shí)間沒(méi)有保障的，有時(shí)候很快能跑完，有時(shí)候一天都跑不完。和算例有很大關(guān)系的。

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

【有償輔導(dǎo)純屬個(gè)人行為，與團(tuán)隊(duì)無(wú)關(guān)】

代碼獲取

代碼獲取請(qǐng)關(guān)注我們的公眾號(hào)，在公眾號(hào)后臺(tái)回復(fù)【cgvrptw】不包括【】即可獲取。

覺(jué)得不錯(cuò)的同學(xué)請(qǐng)?jiān)贕itHub上加個(gè)星，謝謝！

END