✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，matlab项目合作可私信。
🍎个人主页：Matlab科研工作室
🍊个人信条：格物致知。
更多Matlab仿真内容点击👇
⛄ 内容介绍
LNS算法是一种启发式算法，用于解决组合优化问题，其基本思想是在每一步中随机选择一个子问题，然后对其进行求解，并将得到的解用于更新全局最优解，不断迭代直到满足终止条件。LNS算法通常用于解决NP难问题，如TSP、VRP等。
VRP问题是指在有限数量的车辆和客户需求点之间建立最优的路径规划方案，使得总路程或总成本最小，同时满足车辆容量限制等约束条件。而LNS算法是一种启发式算法，用于解决组合优化问题，其基本思想是在每一步中随机选择一个子问题，然后对其进行求解，并将得到的解用于更新全局最优解，不断迭代直到满足终止条件。
下面是基于LNS算法求解带容量的车辆路径规划问题的大致步骤：
- 随机生成初始解。可以使用贪心算法等方法生成初步解。
- 进行大邻域搜索。将初始解分为多个子问题，然后对每个子问题进行局部搜索，得到一个局部最优解。
- 更新全局最优解。将每个子问题的局部最优解与当前全局最优解进行比较，如果局部最优解更优，则更新全局最优解。
- 根据终止条件判断是否结束。如果未满足终止条件，则回到步骤2继续搜索。
- 输出最优解。最终得到的全局最优解即为所求的最优解。
需要注意的是，在大邻域搜索过程中，需要根据问题特点和约束条件设计合适的局部搜索算法。例如，对于带容量的VRP问题，可以使用贪心算法、禁忌搜索等方法进行局部搜索。
⛄ 部分代码
function routes=parallel_savings_init(model)
D=model.d;
d=model.r;
C=model.c(1);
L=0;
minimize_K=false;
C_EPS=1e-1;
N=size(D,1);
ignore_negative_savings=true;
routes=cell(numel(2:N),1);
route_costs=cell(numel(routes),1);
for i=1:numel(routes)
routes{i}=i+1;
end
if C
route_demands=d(2:end);
else
route_demands=zeros(N,1);
end
if L>0.1
for i=1:numel(routes)
route_costs{i}=D(1,i+1)+D(i+1,1);
end
end
saving=clarke_wright_savings_function(model);
endnode_to_route=[1,1:N-1];
for p=1:size(saving,1)
% best_saving=saving(p,1);
i=saving(p,3);
j=saving(p,4);
if ignore_negative_savings
cw_saving = D(i,1)+D(1,j)-D(i,j);
if cw_saving<0
break
end
end
left_route = endnode_to_route(i);
right_route = endnode_to_route(j);
if isnan(left_route) || isnan(right_route) || left_route==right_route
continue
end
% if isempty(left_route) || isempty(right_route) || left_route==right_route
% continue
% end
if C
merged_demand = route_demands(left_route)+route_demands(right_route);
if merged_demand-C_EPS > C
continue
end
end
% if L>0.1
% merged_cost = route_costs[left_route]-D[0,i]+\route_costs[right_route]-D[0,j]+\D[i,j]
% end
if C
route_demands(left_route) = merged_demand;
end
% if L>0.1
% route_costs(left_route) = merged_cost;
% end
if routes{left_route}(1)==i
routes{left_route}=flip(routes{left_route});
end
if routes{right_route}(end)==j
routes{right_route}=flip(routes{right_route});
end
if numel(routes{left_route})>1
endnode_to_route( routes{left_route}(end) ) = nan;
end
if numel(routes{right_route})>1
endnode_to_route( routes{right_route}(1) ) = nan;
end
endnode_to_route( routes{right_route}(end) ) = left_route;
routes{left_route}=[routes{left_route},routes{right_route}];
routes{right_route} = nan;
end
end
⛄ 运行结果
⛄ 参考文献
[1] 王仁民.改进变邻域搜索算法在动态车辆路径问题中的研究[D].广西师范学院[2023-06-10].DOI:CNKI:CDMD:2.1013.315439.
