遗传算法在多车容量约束VRP问题中的应用与求解-编程实验室

遗传算法VRP问题：VRP，多车容量约束针对物流问题，根据实际情况，设置多车多容量，采用遗传算法分析求解，在matlab实现并画图，展示求解结果

前阵子帮做物流的表哥捋了捋他们的配送问题，本来十来个司机，仓库里几百个订单，既要让每辆车不超载，又要总里程最少，折腾了好几天才摸出点门道——这不就是带容量约束的车辆路径问题（CVRP）嘛？

说白了这问题就是：仓库有N辆货车，每辆能拉固定重量的货，外面有M个等着送货的点，怎么安排每辆车的送货路线，让所有货都送完，还能让总开车的路程最短？暴力枚举肯定不行，点一多就算不动，这时候遗传算法就派上用场了，不用搞太复杂的数学推导，跑两趟Matlab就能出结果。

先唠唠遗传算法解这个问题的大概思路

其实就是模拟生物进化那套逻辑：先随机生成一堆可行的路线方案（也就是种群里的个体），然后给每个方案打分（适应度），挑分数高的方案留下来，再互相杂交、变异，迭代个几十上百次，最后就能得到一个不错的解。

遗传算法VRP问题：VRP，多车容量约束针对物流问题，根据实际情况，设置多车多容量，采用遗传算法分析求解，在matlab实现并画图，展示求解结果

这里最关键的是得处理好「车辆不超载」这个约束，不然跑出来的路线看着挺顺，结果某辆车拉的货比额定载重还多，等于白搭。

直接上Matlab代码，边看边唠

我把代码拆成了小块，每块都讲清楚为啥这么写，不用怕看不懂。

先写个算路线总路程和总载重的辅助函数

这个函数是用来检查路线合不合格的，要是某辆车拉超了，直接给这个路线打个低分，直接淘汰。

function [total_dist, total_load] = calc_route_info(route, demand, dist_matrix, vehicle_cap) % 用0拆分每辆车的送货路线，0就是仓库的标记 sub_routes = split(string(route), 0); total_dist = 0; total_load = 0; for i = 1:length(sub_routes) sub = str2double(strsplit(sub_routes{i})); sub = sub(~isnan(sub)); % 去掉空的分段 if isempty(sub) continue; end % 先算这辆车的总送货量，超了直接给无穷大的距离 current_load = sum(demand(sub)); if current_load > vehicle_cap total_dist = inf; return; end total_load = total_load + current_load; % 计算路线距离：仓库→第一个送货点→中间点→最后一个送货点→仓库 path = [0, sub, 0]; for j = 1:length(path)-1 total_dist = total_dist + dist_matrix(path(j)+1, path(j+1)+1); end end end

唠两句：为啥用0当分隔符？因为这样能直接把每辆车的路线拆分开，不用费劲去数有几辆车。要是某段路线的总需求超了车的载重，直接返回无穷大，后面算适应度的时候就会把这个方案筛掉，简单粗暴还管用。

初始化种群的函数

就是随机生成一堆初始的送货路线方案，不用太严谨，只要大概符合要求就行，后面的惩罚机制会把不合格的筛掉。

function pop = init_pop(pop_size, num_customers, num_vehicles) pop = []; for i = 1:pop_size % 随机打乱所有送货点的顺序 cust_order = randperm(num_customers); % 随机插几个0，把路线分成num_vehicles段，对应每辆车 split_pos = sort(randperm(num_customers-1, num_vehicles-1)); route = []; prev = 0; for j = 1:num_vehicles if j <= length(split_pos) segment = cust_order(prev+1:split_pos(j)); else segment = cust_order(prev+1:end); end route = [route, segment, 0]; prev = split_pos(j); end pop = [pop; route]; end end

唠两句：一开始我还想着要严格按照载重来初始化，结果发现完全没必要，反正后面有惩罚机制，随便瞎生成就行，省事儿得很。

计算每个方案的适应度

我们想要总路程越短越好，所以适应度就设成总路程的倒数，总路程越短，分数越高。

function fitness = calc_fitness(pop, demand, dist_matrix, vehicle_cap) fitness = zeros(size(pop,1),1); for i = 1:size(pop,1) [total_dist, ~] = calc_route_info(pop(i,:), demand, dist_matrix, vehicle_cap); % 超载的方案给个极低的分数，几乎不会被选中 if total_dist == inf fitness(i) = 1e-6; else fitness(i) = 1 / total_dist; end end end

选择算子——锦标赛选择

比轮盘赌好用多了，不会轻易陷入局部最优，就是随机挑几个方案，选分数最高的留下来。

function new_pop = tournament_selection(pop, fitness, tour_size) new_pop = []; pop_size = size(pop,1); for i = 1:pop_size % 随机选tour_size个方案PK candidates = randperm(pop_size, tour_size); [~, best_idx] = max(fitness(candidates)); new_pop = [new_pop; pop(candidates(best_idx),:)]; end end

交叉和变异

交叉就是把两个不错的路线拼在一起，变异就是随机换两个送货点的位置，增加种群多样性，防止提前收敛到不好的解。

function [offspring1, offspring2] = crossover(parent1, parent2) len = length(parent1); cross_points = sort(randperm(len,2)); % 交换两个方案的中间片段 offspring1 = [parent1(1:cross_points(1)-1), parent2(cross_points(1):cross_points(2)), parent1(cross_points(2)+1:end)]; offspring2 = [parent2(1:cross_points(1)-1), parent1(cross_points(1):cross_points(2)), parent2(cross_points(2)+1:end)]; % 简单修复一下重复的送货点，保证每个点只送一次 offspring1 = repair_route(offspring1, len); offspring2 = repair_route(offspring2, len); end function route = repair_route(route, original_len) [~, idx] = unique(route, 'stable'); route = route(sort(idx)); % 补全到原来的长度，避免长度不对 if length(route) < original_len route = [route, zeros(1, original_len - length(route))]; else route = route(1:original_len); end end function route = mutate(route, pm) len = length(route); for i = 1:len if rand < pm % 随机交换两个位置的送货点 j = randi(len); temp = route(i); route(i) = route(j); route(j) = temp; end end route = repair_route(route, len); end

唠两句：这里的交叉和变异都是简化版的，要是想跑更大规模的问题，可以换成专门针对VRP的交叉算子，比如OX交叉，效果会更好，但对于十来个送货点的小问题，这么用完全够了。

主函数跑起来

把上面的函数都写好之后，直接跑主函数就行，我这里用了10个送货点，3辆货车，每辆载重20，送货点的需求都是1到5之间的随机数，坐标随便设在0-100的平面上。

%% 主函数 clear;clc;close all; % 定义问题参数 num_customers = 10; % 10个送货点 num_vehicles = 3; % 3辆货车 vehicle_cap = 20; % 每辆车最大载重20 % 随机生成送货点的位置和需求 customer_pos = rand(num_customers,2)*100; demand = randi([1,5], num_customers,1); % 计算两点之间的欧氏距离，包括仓库（0点） dist_matrix = zeros(num_customers+1, num_customers+1); for i = 1:num_customers+1 for j = 1:num_customers+1 if i == j dist_matrix(i,j) = 0; else p1 = i==1 ? [0,0] : customer_pos(i-1,:); p2 = j==1 ? [0,0] : customer_pos(j-1,:); dist_matrix(i,j) = norm(p1 - p2); end end end % 遗传算法参数 pop_size = 50; % 种群大小 gen_num = 100; % 迭代次数 tour_size = 3; % 锦标赛PK的人数 pm = 0.01; % 变异概率 % 初始化种群 pop = init_pop(pop_size, num_customers, num_vehicles); best_dist_history = zeros(gen_num,1); % 开始迭代 for gen = 1:gen_num fitness = calc_fitness(pop, demand, dist_matrix, vehicle_cap); % 记录每一代的最优解 [best_fit, best_idx] = max(fitness); best_route = pop(best_idx,:); [best_dist, ~] = calc_route_info(best_route, demand, dist_matrix, vehicle_cap); best_dist_history(gen) = best_dist; % 选择、交叉、变异 pop = tournament_selection(pop, fitness, tour_size); new_pop = []; for i = 1:2:pop_size if i+1 > pop_size new_pop = [new_pop; pop(i,:)]; break; end [o1, o2] = crossover(pop(i,:), pop(i+1,:)); new_pop = [new_pop; o1; o2]; end pop = new_pop(1:pop_size,:); for i = 1:pop_size pop(i,:) = mutate(pop(i,:), pm); end if mod(gen,10) ==0 fprintf('第%d代，最优总路程：%.2f\n', gen, best_dist); end end % 画迭代曲线 figure('Name','迭代曲线'); plot(best_dist_history,'LineWidth',1.5); xlabel('迭代次数');ylabel('总路程'); title('最优总路程随迭代次数变化'); grid on; % 画最优配送路线 figure('Name','最优配送路线'); plot(0,0,'ro','MarkerSize',10,'DisplayName','仓库');hold on; plot(customer_pos(:,1), customer_pos(:,2),'bo','MarkerSize',7,'DisplayName','送货点'); % 解析最优路线 sub_routes = split(string(best_route), 0); colors = ['r','g','b','m','c','y']; for i = 1:length(sub_routes) sub = str2double(strsplit(sub_routes{i})); sub = sub(~isnan(sub)); if isempty(sub) continue; end path = [0, sub, 0]; for j = 1:length(path)-1 p1 = path(j)==0 ? [0,0] : customer_pos(path(j),:); p2 = path(j+1)==0 ? [0,0] : customer_pos(path(j+1),:); plot([p1(1), p2(1)], [p1(2), p2(2)], [colors(mod(i,length(colors))+1)],'LineWidth',2); end end legend;