这篇内容本来是我分享在博客园上的技术博客，考虑到这些资料可能会对小黑盒平台上的游戏玩家们有帮助，这里决定抄送一份在小黑盒发布。
本文作者：多玩我的世界盒子
本文链接：https://www.cnblogs.com/BOXonline1396529/articles/18208092
版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。
2024 年 5 月我的实验课作业要求使用遗传算法解决任意的交通领域实践问题。我用 MATLAB 自己写了一个遗传算法求解器，对 CVRP 问题进行了求解，这里把代码分享给大家。
CVRP 问题，即包含容量限制的车辆路径优化问题（Capacity Vehicle Routing Problem），是物流和运输领域中的一个经典优化问题。其目标是确定一组车辆从一个配送中心出发，访问一系列客户节点并返回配送中心的 最优路径方案。该问题的目的是在满足所有客户需求和车辆运载能力限制的同时，最小化总行驶距离或总成本。该问题可以被认为是 TSP 问题的一种变体，即增加了车辆容量限制的 TSP 问题。TSP 问题也可以被理解为无容量限制的 VRP 问题，即一辆车走完全局最短路即可满足所有节点的需求。
我在写这个求解器的时候我尽量去做了很多的适配，比如让这个求解器能够适配尽可能多的 CVRP 问题，以及让代码注释尽可能详细，以便大家能够在我写的代码基础上自行开展学习等等。原本就想着等我把这个作业写完之后就把内容发到博客里面来的，但写完之后发现代码文件太多太长了，没有办法直接插入到博客里面来。博客园没有云存储，CSDN 又要充米恰金豆，所以只好上传到 Gitee 平台上了，项目地址是这个 通过遗传算法实现车辆路径优化问题求解：https://gitee.com/boxonline_1396529/ga-cvrp-opt
如果您还不知道如何从 Gitee 上面下载代码，请查看这篇文章：没有git，如何下载gitee代码？
https://www.cnblogs.com/boxonline1396529/p/18207930
示例代码及算例
算例生成
算例来自于 MATLAB 官网文章 CapacitatedVehicle Routing Problem（https://www.mathworks.com/help/matlab/math/quantum-capacitated-vehicle-routing.html），坐标点及各个顾客的需求量根据原文中的方法随机生成。算例可视化如下图所示，详情请参照原文。
Capacitated vehiclerouting is a combination of a knapsack problem and a traveling salespersonproblem. The problem is for a vehicle (or set of vehicles) to visit a group ofcustomers that are geographically distributed. The vehicle has a capacityconstraint, where the capacity refers to a quantity that the vehicle deliversto each customer. The problem has a central depot, and the vehicle must return tothe depot after each visit to a set of customers, or route. The problem is tovisit the customers at minimal cost, where the cost is the total length of theroute for visiting a group of customers.
The followingfigure shows four routes originating from a single point, the depot. Theseroutes do not represent a minimal solution, because nodes 2 and 3 (at least)should be visited in the opposite order. The route containing nodes 2 and 3 hasa self-intersection, which does not occur in an optimal tour.
下面的代码可以生成算例：
% CapacitatedVehicle Routing Problem
rng(1) %For reproducibility
numCustomers = 24; %Depot at [0 0] makes 25 locations
depot = [0 0]; %Depot at the origin
loc = [depot; randi([-50, 50],numCustomers,2)];
% Integers from -50 to 50, 24-by-2
demands = 100*randi([1, 25],numCustomers,1);
capacity = 6000;
算例可视化
同样是官网提供的代码，用下面的代码可以对算例进行可视化：
% Plot thelocations with demands overlaid
% figure;
scatter(loc(:,1),loc(:,2),'filled','SizeData',25);
text(loc(:,1),loc(:,2),["Depot"; num2str((1:numCustomers)')]);
title("Customer Locations and Demands");
hold off;
如下图所示：
算例可视化
算法使用顾客与仓库之间的 OD 矩阵，而不是真实坐标进行运算，保障了算法的兼容性和可拓展性。
取得 OD 矩阵，可以使用如下的代码：
% 生成 OD 矩阵
% OD_mat = squareform(pdist(loc));
% 鉴于一些人的电脑里可能没有统计与机器学习工具箱，pdist 函数有可能无法使用
% 下面的代码也可以获取原问题的 OD 矩阵
OD_mat = zeros(numCustomers, numCustomers);
for i = 1:numCustomers+1
for j = 1:numCustomers+1
OD_mat(i, j)= sqrt(sum((loc(i, :)- loc(j, :)).^2));
end
end
算法设计简述
基因编码设计： 基因编码设计参考了博客：用遗传算法解决VRP问题（https://blog.csdn.net/panbaoran913/article/details/128250015），其基本逻辑为：首先随机生成所有顾客节点编号的随机排列，再在其中插入数量相当于运载工具数量减去1 数量的0，即，设此时共有 辆车，则插入的 0 元素数量为 。每一段用0 分割的节点序列即代表一辆车的访问节点次序。
如：设此时存在基因编码方案 23 9 0 7 6 4 0 1 8 5，代表第一辆车访问节点的顺序是2、3、9，第二辆车访问的节点是 7、6、4，第三辆车访问的节点是 1、8、5。详情参见原文所述。
约束处理： 算法强调并实现了如下的模型约束：
• 每个客户节点必须被访问一次。
• 每辆车从配送中心出发并返回配送中心。
• 每辆车的总负载不能超过其最大载重量。
适应度函数取值： 取总路程倒数为适应度函数值。对于超出模型约束（车辆数量约束和总载重量限制约束）的个体，强制令其适应度函数值为0。
交叉和变异方法： 使用单点交叉和单点变异的方法。对于交叉、变异后产生不符合模型约束的非法个体的情形，不予交叉变异。 该策略通过在交叉、变异前提前对交叉编译产生的个体进行检验并根据检验结果进行判断来实现。
精英策略： 算法保存历次迭代中取得的最优适应度个体，并在未来次数迭代中使用该个体替换种群中适应度最低的个体，避免种群劣化。
对于代码里的详细的信息内容，请自行下载代码查看。
算法迭代过程
设置迭代次数为 1000 次，种群大小为 50000。由于交叉变异过程受到模型约束的限制，为了保障实际的交叉变异发生率，应当适当增加交叉变异概率。这里取得交叉变异概率分别为 Pc = 0.9，Pm = 0.09。
求解器的使用是很容易的。使用 help GA_CVRP_optimize 命令可以查看求解器的使用方法。这些代码注释我已经写得非常详细了。（真的很详细！）
>> help GA_CVRP_optimize
GA_CVRP_optimize 针对 CVRP 问题的遗传算法求解器
此 MATLAB 函数利用遗传算法优化解决 CVRP 问题，支持动态图实时显示迭代过程的全
局最优解搜索下降进度，会在命令行窗口输出提示信息。
[bestIndividual, minCost] = GA_CVRP_optimize( ...
OD_mat, numVehicles, demands, capacity, ...
popSize, maxIter, pc, pm)
[bestIndividual, minCost, iterPop, fitnessValues] ...
= GA_CVRP_optimize( ...
OD_mat, numVehicles, demands, capacity, ...
popSize, maxIter, pc, pm, ...
dynamic_plot ...
)
注意事项
1. 为了简化问题的建模，采用整型数据编码的形式。
2. 算法采用了精英策略，保存、记录和返回历代中的最精英个体及其适应度。
3. 交叉、变异过程采用了带约束的交叉编译过程，如果交叉变异产生的新的个体
无法满足模型约束的要求，交叉、变异将不会发生。
4. 无法确保找到全局最优解。
输入参数
OD_mat - 所有节点之间的 OD 矩阵。此处要求 OD 矩阵中的第一个节点是 CVRP
问题的配送中心节点，即 Depot 节点。
numVehicles - CVRP 问题中运载工具的数量
demands - CVRP 问题中各个顾客节点的需求量的一维向量
capacity - CVRP 问题中运载工具的容量限制
popSize - 遗传算法的种群大小
maxIter - 最大迭代次数限制
pc - 交叉概率
pm - 变异概率
dynamic_plot - 一个 Bool 值，表示是否弹窗并动态绘制模型求解的下降过程
输出参数
bestIndividual - 遗传算法迭代产生的最优精英个体
minCost - 遗传算法优化的结果，即 CVRP 问题中汽车最终行驶的总里程数
iterPop - 最终次迭代的种群
求解器支持在算法迭代过程中实时动态绘制下降过程，绘制效果如下图所示。
遗传算法中最小化路程的下降过程
输出结果
算法的输出结果如下图所示，图中使用不同的颜色标记了不同车辆的访问路径。取得极小化路径长度为 815.29。
遗传算法的优化结果
总结
代码是根据自己的理解写的，可能有诸多不成熟、不严谨的地方。如果您对于代码有任何的改进建议，欢迎您提交 Pull Request 和 Issue。您的建议对我来说很重要。