我们在一种构造CVRP问题初始解的启发式方法续集(附matlab代码)这篇推文中使用节约(CW)算法构造容量受限的车辆路径问题(CVRP)初始解,然后在CW节约算法构造VRPTW初始解(附MATLAB代码)这篇推文讲解使用节约算法(CW)构造带时间窗的车辆路径(VRPTW)问题初始解。
我们先来回顾一下代码的思路:
Solomon测试算例的下载地址如下:https://www.sintef.no/projectweb/top/vrptw/solomon-benchmark/100-customers/
小编使用的是solomon算例中的rc208算例,在上述网址下载结束后,我们打开rc208测试算例,如下图所示。CAPACITY表示车辆最大装载量,第一列CUST NO.表示顾客编号,0表示配送中心,XCOORD.表示顾客的X坐标,YCOORD.表示顾客的Y坐标,DEMAND表示顾客的需求量,READY TIME表示顾客的左时间窗,DUE DATE表示顾客的右时间窗,SERVICE TIME表示车辆对每个顾客的服务时间。
但是小编在matlab里使用的rc208.txt文件是把前几行删掉,目的是方便matlab读取数据,小编处理后的rc208.txt文件如下所示。
接下来小编就带领各位感受一下构造初始解的结果。首先给出初始时配送中心和顾客的分布图:
在使用节约算法构造初始解后,效果如下所示:
各个车辆所经过顾客序号如下所示,其中0代表配送中心,一共用了11辆车,初始解中所有车辆所行驶的总距离为1074.63。
因为节约算法只是构造出问题的初始解,它只是基础,在构造完初始解后,一定还会用其他算法优化初始解,所以初始解的质量一般,各位不用担心。