基于MATLAB解决车辆路径问题（VRP）-程序员充电站

一、问题建模（以CVRP为例）

目标函数：最小化总行驶距离

约束条件：

每辆车从仓库出发并返回
单个车辆载重量不超过容量限制
每个客户仅被访问一次

数学模型：

二、遗传算法实现（核心代码）

1. 参数设置

% 基础参数depot=[0,0];% 仓库坐标customers=[10,5;15,8;5,12;20,15;8,18;12,3;18,7;3,10];% 客户坐标demands=[15;20;18;25;22;10;16;12];% 客户需求vehicle_capacity=50;% 车辆容量num_vehicles=3;% 车辆数pop_size=50;% 种群大小max_gen=200;% 最大迭代pc=0.85;% 交叉概率pm=0.1;% 变异概率

2. 关键函数实现

(1) 适应度函数（含惩罚项）

functionfitness=calc_fitness(route,dist_matrix,demands,capacity)total_dist=0;current_load=0;current_pos=1;% 仓库索引fori=1:length(route)cust=route(i);load=demands(cust);% 距离计算total_dist=total_dist+dist_matrix(current_pos,cust+1);current_pos=cust+1;% 容量检查current_load=current_load+load;ifcurrent_load>capacity penalty=1000*(current_load-capacity);% 惩罚项total_dist=total_dist+penalty;endend% 返回仓库total_dist=total_dist+dist_matrix(current_pos,1);fitness=1/total_dist;% 适应度与距离成反比end

(2) 顺序交叉（OX）操作

functionoffspring=ox_crossover(parent1,parent2)n=length(parent1);cut1=randi([1,n-1]);cut2=randi([cut1+1,n]);% 复制中间段offspring=zeros(1,n);offspring(cut1:cut2)=parent1(cut1:cut2);% 填充剩余基因ptr=cut2+1;fori=1:nifptr>n ptr=1;endif~ismember(parent2(i),offspring)offspring(ptr)=parent2(i);ptr=ptr+1;endendend

(3) 变异操作（交换+逆转变异）

functionmutated=mutate(route,mutation_rate)ifrand<mutation_rate% 交换变异idx=randperm(length(route),2);route(idx)=route(fliplr(idx));% 逆转变异sub=route(2:end-1);sub=fliplr(sub);route(2:end-1)=sub;endmutated=route;end

三、完整算法流程

%% 初始化种群population=zeros(pop_size,n_customers);fori=1:pop_sizepopulation(i,:)=randperm(n_customers);end%% 主循环best_fitness=inf;forgen=1:max_gen% 计算适应度fitness=arrayfun(@(i)calc_fitness(population(i,:),dist_matrix,demands,vehicle_capacity),1:pop_size);% 更新最优解[min_fit,idx]=min(fitness);ifmin_fit<best_fitness best_fitness=min_fit;best_route=population(idx,:);end% 选择（锦标赛选择）parents=tournament_selection(population,fitness);% 交叉（OX交叉）offspring=cell(pop_size/2,2);fori=1:2:pop_size parents_sel=parents(randperm(size(parents,1),2),:);child1=ox_crossover(parents_sel(1,:),parents_sel(2,:));child2=ox_crossover(parents_sel(2,:),parents_sel(1,:));offspring{i}=child1;offspring{i+1}=child2;end% 变异fori=1:pop_size offspring{i}=mutate(offspring{i},pm);end% 更新种群population=cell2mat(offspring);end%% 结果可视化plot_route(best_route,depot,customers);disp(['最优路径总距离: ',num2str(1/best_fitness)]);

四、扩展方法对比

方法	优点	缺点	适用场景
遗传算法	全局搜索能力强	收敛速度较慢	大规模复杂问题
粒子群	收敛速度快	易陷入局部最优	中小规模问题
模拟退火	适合离散优化	参数敏感	时间窗约束问题
蚁群算法	正反馈机制高效	需要精细参数调优	动态路径规划