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