VRPTW合集 [CW节约算法,TS(硬约束版),TS(惩罚函数版),LNS四种方法对比(附MATLAB代码)]

01

方法回顾

VRPTW系列推文终于要告一段落了，最初小编写了一篇最基本的节约算法构造VRPTW初始解推文；然后在这个基础上，小编尝试用3种不同的策略在所构造的初始解的基础上，进一步优化解的质量。推文链接如下：

​​CW节约算法构造VRPTW初始解（附MATLAB代码）​​

​​大规模邻域搜索（LNS）求解带时间窗的车辆路径问题（VRPTW）（附MATLAB代码）​​

​​禁忌搜索算法求解带时间窗的车辆路径问题(上)​​

​​禁忌搜索算法求解带时间窗的车辆路径问题(下 附MATLAB代码)​​

​​禁忌搜索算法求解带时间窗的车辆路径问题(惩罚函数版 附MATLAB代码)​​

02

对TS惩罚函数版代码的修改

上一篇推文 ​​禁忌搜索算法求解带时间窗的车辆路径问题(惩罚函数版 附MATLAB代码)​​ 写完后，小编把代码在56个solomon算例进行测试，发现效果不佳，于是小编进行了小小的改动，构造初始解的方式不采用小编推文中说的CW法，而是采用论文里说的构造初始解的方法。

然后小编在调试的过程中发现，自适应调整惩罚权重的策略效果不好，于是稍微更改了一下自适应调整权重的策略：只在解违反约束时，使权重增加，不违反约束的时候，权重保持不变，即不像论文中写的那样不违反约束时，使权重减少。同时也将邻域结构也稍微改动了一下。最后把迭代次数设为500代。

1%% 当前解S的邻域，用[i,j,k,p,f+p]表示可行邻域，表示将顾客i从路径j移动到路径k的第p个位置,f+p表示该邻域解的成本函数+惩罚函数
 2%输入curr_vc                          当前解
 3%输入L                                仓库时间窗
 4%输入a,b                              顾客时间窗
 5%输入s                                对顾客的服务时间
 6%输入dist                             距离矩阵
 7%输入demands：表示由集配中心运送到顾客的配送量
 8%输入cap                              车辆负荷
 9%输入权重alpha,belta,lamda
10%输出NS
11function [NS] = neighborhood(curr_vc,cusnum,a,b,s,L,dist,demands,cap,alpha,belta,lamda)
12NS=[];
13NS_copy=[];
14NV=size(curr_vc,1);             %车辆数
15fcurr=costFuction(curr_vc,a,b,s,L,dist,demands,cap,alpha,belta);
16vc_copy=curr_vc;
17%思路是遍历所有顾客，将顾客从当前路径移除，然后依次插入到其他路径可行位置
18for i=1:cusnum
19    for j=1:NV
20        route=vc_copy{j};
21        pos=find(route==i,1,'first');       %顾客i在当前路径位置
22        %如果pos非空，则顾客i在路径j上
23        if ~isempty(pos)
24            break
25        end
26    end
27    for k=1:NV
28        vc_copy=curr_vc;
29        NS_copy=[];
30        if (k~=j)&&(~isempty(curr_vc{k}))
31            route=vc_copy{k};   %当前路径所经过的顾客
32            route_copy=route;
33            lr=length(route);   %当前路径所经过的顾客的数目，如果不考虑约束，就意味着有lr+1个插入位置
34            for p=1:lr+1
35                %先不考虑约束，将顾客i插入到路径k的任意可能插入位置
36                if p==1
37                    route=[i route_copy];
38                elseif p==lr+1
39                    route=[route_copy i];
40                else
41                    route=[route_copy(1:p-1) i route_copy(p:end)];
42                end
43                route_before=vc_copy{j};
44                route_before(route_before==i)=[];             %将顾客i从路径j中移除
45                vc_copy{j}=route_before;
46                route_k=vc_copy{k};
47                vc_copy{k}=route;
48                vc_c=deal_vehicles_customer(vc_copy);
49                f=costFuction(vc_c,a,b,s,L,dist,demands,cap,alpha,belta);
50                % 如果f>=fcurr，则给当前解加惩罚
51                if f>=fcurr
52                    c=travel_distance(vc_c,dist);
53                    ps=lamda*c*(cusnum*size(vc_c,1))^0.5;
54                    f=f+ps;
55                end
56                NS_copy=[NS_copy;i,j,k,p,f];
57                vc_copy{k}=route_k;
58            end
59        end
60        if ~isempty(NS_copy)
61            [minValue,minIndex]=min(NS_copy(:,5));           %从邻域中找出车辆总行驶距离最小的行序号
62            value=NS_copy(minIndex,:);                       %提取最小行序号的这一行数组
63            NS=[NS;value];
64        end
65    end
66    vc_copy=curr_vc;
67    nr=NV+1;        %如果新建一条路径，把该顾客插到新建路径中
68    route=i;
69    vc_copy{nr}=route;
70    vc_c=deal_vehicles_customer(vc_copy);
71    f=costFuction(vc_c,a,b,s,L,dist,demands,cap,alpha,belta);
72    % 如果f>=fcurr，则给当前解加惩罚
73    if f>=fcurr
74        c=travel_distance(vc_c,dist);
75        ps=lamda*c*(cusnum*size(vc_c,1))^0.5;
76        f=f+ps;
77    end
78    NS=[NS;i,j,nr,1,f];
79    vc_copy=curr_vc;  
80end
81end

03

算法对比

那这4种方法究竟求解质量怎么样，小编把这4种方法在56个solomon算例上测试了一遍，求解结果如下表所示。表格中NV代表所使用车辆数目，TD代表车辆行驶总距离，最后两列是目前国际上所获得的最优解。

Solomon算例中根据顾客分布情况分为3类：C类表示顾客分布比较集中，R类顾客分布比较随机，RC类既有集中分布的顾客，又有随机分布的顾客。同时每一种类型的顾客又分为两类：100系列的顾客表示时间窗比较窄，200系列的顾客表示时间窗比较宽。

04

总结

论文中一般都会将NV作为第一优化目标，TD作为第二优化目标。所以通过观察可以看出，LNS在求解时间窗窄和顾客分布集中的算例时能获得好的解，TS惩罚函数版在求解时间窗宽的算例上能获得好的解，当然目前的这四种方法都是最基础的方法，要想获得更高质量的解，还需小伙伴们设计更复杂的方法。

05

代码链接（后台回复“VRPTW”提取代码）

链接：​​https://pan.baidu.com/s/174x9Jg_azCOj4zPuozPS_Q​​

提取码：ichg

文件目录如下图所示

友情提示

代码的有效期只有7天，如需代码，请微信公众号后台联系小编，或者微博私信小编，微博ID：随心390。小编会第一时间回复您。

微信公众号：优化算法交流地

微博：随心390