✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，matlab项目合作可私信。
🍎个人主页：Matlab科研工作室
🍊个人信条：格物致知。
更多Matlab仿真内容点击👇
⛄ 内容介绍
在这篇文章中，我们详细介绍2E-VRP问题，这个问题是传统的有容量限制的VRP问题的扩展。在这个问题中，货物是从一个中心仓库运往不同的客户点，并且货物在中介仓库进行整合，这些仓库被称为卫星。本文介绍了一组多端起始的启发式算法，这种算法将仓库与卫星之间的运输和卫星与客户之间的运输分离处理，并且通过调整连接两层运输系统的卫星负载，迭代地解决这两个路线规划子问题。基本上所有的启发式算法的常规解决方案都是先找到一个初始解，然后通过分类进行局部搜索；如果新获得的解是可行的，那么继续进行局部搜索，否则将进行可行性搜索过程。如果可行性解搜索成功，将对这个新的可行解进行局部搜索。本文提出了不同的分类策略和可行性解搜索规则。我们在文章中呈现了对多达50个客户和5个卫星的大范围数据集的计算结果，并且与以往文献中相关的结果进行了比较，说明了本文提出的在性能和准确性上都优于之前的方案。
1.1 First Clustering.
基于距离的贪婪法则将每个客户分配给一个卫星，完成初始解计算。
- 将每个客户按照需求递减的顺序排序
- 将每个客户分配到相应的卫星，按照距离最近的原则
- 如果将某个客户分配给卫星时，意味着需要额外增加一辆车辆，则需要检查整个车辆容量是否被违反。如果是的话，这个分配解不可行，客户应当被分配到第二个最近的卫星，直到找到一个可行解。
1.2 GACVRP
采用遗传算法解决Ns+1个CVRP问题。
- 初始化，随机选择一些个体选择最初的种群。
- 评估，通过某种方法来评估个体的适应度（生存能力）。路线越短越好。
- 选择，类似于自然选择，优良的基因，生存能力强的被选择下来的概率要大。采用 最佳个体保存与赌轮相结合 的选择策略。其具体操作为：将每代群体中的N个个体按适应度由小到达排列，排在首位的个体性能最好，将它直接复制到下一代。下一代群体的令N-1个体需要根据上一代群体的N个个体的适应度采用赌轮选择。
- 交叉，产生后代，基因交叉。
- 变异，后代的基因可能会变异，变异在生物进化中起了很大作用。
选择、交叉、变异是产生新种群的步骤，新种群再进行评估，直至找到一个近似最优解。
1.3 Clustering Improvement
基于FC的解，每次改变一个客户-卫星分配关系。
1.4. Perturbation
鉴于目前最好的解，根据规则（考虑重组花费）对客户-卫星分配关系进行扰乱。
如果新的解不是可行解，使用可行解搜索算法获得新的可行解。
如果新的解是可行解，执行CI阶段。
⛄ 部分代码
fprintf('total Cost = %0.2f\n', totalcost);
fprintf('----------------layer1-------------------\n');
for i = 1:size(layer1,1)
fprintf('Cost(%0.1f),Weight(%0.1f),Cust(%d) ',layer1{i,1},layer1{i,2},layer1{i,3});
fprintf('%d ',layer1{i,4});
fprintf('\n');
end
fprintf('\n----------------layer2-------------------\n');
Cost = 0;
for i = 1:size(layer2,1)
output = layer2{i,1};
for j = 1:size(output,1)
Cost = Cost + output{j,1};
Vehicles = size(output,1);
end
fprintf('Cost=%0.2f Vehicles=%d\n', Cost, Vehicles);
for j = 1:size(output,1)
fprintf('Cost(%0.1f),Weight(%0.1f),Cust(%d) ',output{j,1},output{j,2},output{j,3});
fprintf('%d ',output{j,4});
fprintf('\n');
end
Cost = 0;
fprintf('\n');
end
end
⛄ 运行结果
⛄ 参考文献
[1] Crainic T , Tadei R , Mancini S , et al. Heuristics for the two-echelon vehicle routing problem: A multi-start approach[J]. 2011.
