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
81end03
算法对比
那这4种方法究竟求解质量怎么样，小编把这4种方法在56个solomon算例上测试了一遍，求解结果如下表所示。表格中NV代表所使用车辆数目，TD代表车辆行驶总距离，最后两列是目前国际上所获得的最优解。
Solomon算例中根据顾客分布情况分为3类：C类表示顾客分布比较集中，R类顾客分布比较随机，RC类既有集中分布的顾客，又有随机分布的顾客。同时每一种类型的顾客又分为两类：100系列的顾客表示时间窗比较窄，200系列的顾客表示时间窗比较宽。
04
总结
论文中一般都会将NV作为第一优化目标，TD作为第二优化目标。所以通过观察可以看出，LNS在求解时间窗窄和顾客分布集中的算例时能获得好的解，TS惩罚函数版在求解时间窗宽的算例上能获得好的解，当然目前的这四种方法都是最基础的方法，要想获得更高质量的解，还需小伙伴们设计更复杂的方法。