如何分析CW節(jié)約算法構(gòu)造VRPTW初始解

這篇文章將為大家詳細(xì)講解有關(guān)如何分析CW節(jié)約算法構(gòu)造VRPTW初始解，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

VRPTW與CVRP的區(qū)別就是配送中心與顧客都有明確的時(shí)間窗的要求[ai,bi]，其中ai表示配送中心或顧客允許最早開始服務(wù)時(shí)間，bi表示配送中心或顧客允許最晚開始服務(wù)時(shí)間。代碼里寫的時(shí)間窗屬于硬時(shí)間窗，即配送車量可以比最早開始服務(wù)時(shí)間早到，但是要一直等到最早開始服務(wù)時(shí)間才可以開始服務(wù)，而不允許比最晚開始服務(wù)時(shí)間晚到。

在CVRP的基礎(chǔ)上，VRPTW的MATLAB代碼只是加上判斷是否時(shí)間窗約束的代碼，看起來很簡單的一句話，小編可是折騰了很長時(shí)間才把代碼寫出來。小編把代碼的思路給大家梳理一下：

小編依然使用的是solomon算例中的c102算例，具體的數(shù)據(jù)在一種構(gòu)造CVRP問題初始解的啟發(fā)式方法續(xù)集（附matlab代碼）這篇推文中已經(jīng)給出。接下來小編就帶領(lǐng)各位感受一下求解的結(jié)果。

首先放出初始時(shí)配送中心和顧客的分布圖：

在使用節(jié)約算法構(gòu)造初始解后，效果如下所示：

各個(gè)車輛所經(jīng)過顧客序號(hào)如下所示，其中0代表配送中心，一共用了16輛車，初始解中所有車輛所行駛的總距離為1143.3，各位小伙伴看到這里發(fā)現(xiàn)這次求得的總距離居然與上次求得的總距離相等，說實(shí)話，小編也大吃一驚，不過咱們繼續(xù)往下看。

這是所求得得VRPTW初始解：

這是上一篇推文所求得的CVRP的初始解：

看到這里小伙伴發(fā)現(xiàn)每輛車所服務(wù)的顧客明顯與構(gòu)造CVRP初始解有些相同，有些不同，這其實(shí)也好理解，因?yàn)橛辛藭r(shí)間窗的約束，有一些顧客必定要先服務(wù)，而有一些顧客必定要后服務(wù)。

16輛車每輛車所運(yùn)輸貨物的載重量都沒超過容量限制，即沒超過200（正好等于200，是可以允許的）

下面是求解VRPTW時(shí)所得到的16輛車載貨量：

下面是求解CVRP時(shí)所得到的16輛車載貨量：

關(guān)于如何分析CW節(jié)約算法構(gòu)造VRPTW初始解就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。