如何分析CW节约算法构造VRPTW初始解

这篇文章将为大家详细讲解有关如何分析CW节约算法构造VRPTW初始解，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

VRPTW与CVRP的区别就是配送中心与顾客都有明确的时间窗的要求[ai,bi]，其中ai表示配送中心或顾客允许最早开始服务时间，bi表示配送中心或顾客允许最晚开始服务时间。代码里写的时间窗属于硬时间窗，即配送车量可以比最早开始服务时间早到，但是要一直等到最早开始服务时间才可以开始服务，而不允许比最晚开始服务时间晚到。

在CVRP的基础上，VRPTW的MATLAB代码只是加上判断是否时间窗约束的代码，看起来很简单的一句话，小编可是折腾了很长时间才把代码写出来。小编把代码的思路给大家梳理一下：

小编依然使用的是solomon算例中的c102算例，具体的数据在一种构造CVRP问题初始解的启发式方法续集（附matlab代码）这篇推文中已经给出。接下来小编就带领各位感受一下求解的结果。

首先放出初始时配送中心和顾客的分布图：

在使用节约算法构造初始解后，效果如下所示：

各个车辆所经过顾客序号如下所示，其中0代表配送中心，一共用了16辆车，初始解中所有车辆所行驶的总距离为1143.3，各位小伙伴看到这里发现这次求得的总距离居然与上次求得的总距离相等，说实话，小编也大吃一惊，不过咱们继续往下看。

这是所求得得VRPTW初始解：

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

看到这里小伙伴发现每辆车所服务的顾客明显与构造CVRP初始解有些相同，有些不同，这其实也好理解，因为有了时间窗的约束，有一些顾客必定要先服务，而有一些顾客必定要后服务。

16辆车每辆车所运输货物的载重量都没超过容量限制，即没超过200（正好等于200，是可以允许的）

下面是求解VRPTW时所得到的16辆车载货量：

下面是求解CVRP时所得到的16辆车载货量：

关于如何分析CW节约算法构造VRPTW初始解就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。