一、问题建模（以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)]);四、扩展方法对比
| 方法 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 遗传算法 | 全局搜索能力强 | 收敛速度较慢 | 大规模复杂问题 |
| 粒子群 | 收敛速度快 | 易陷入局部最优 | 中小规模问题 |
| 模拟退火 | 适合离散优化 | 参数敏感 | 时间窗约束问题 |
| 蚁群算法 | 正反馈机制高效 | 需要精细参数调优 | 动态路径规划 |
参考代码 基于Matlab解决VRP路径优化问题www.youwenfan.com/contentcsp/97656.html
五、注意事项
- 数据预处理客户坐标需包含仓库节点（通常作为索引0） 需构建完整的距离矩阵（含仓库与客户间距离）
- 性能优化使用
parfor实现并行计算 采用稀疏矩阵存储大规模距离数据 - 结果验证对比CPLEX精确解（适用于小规模问题） 使用Solomon测试集进行基准测试
