基于Matlab遗传算法(GA)编写的通用性可读性强的带时间窗车辆路径问题(VRPTW)求解程...

Matlab带时间窗的车辆路径问题 VRPTWGA编写通用性可读性较好附带时间窗车辆载重同时取配货等现实约束条件最近帮朋友调他的快递配送优化代码才发现原来天天见的“顺路送件”背后藏着这么多绕不开的约束——比如快递车不能装超了、每个小区必须在早上8点到10点之间到晚了人家取不了早了没人在。这不就是经典的VRPTW带时间窗的车辆路径问题吗Matlab带时间窗的车辆路径问题 VRPTWGA编写通用性可读性较好附带时间窗车辆载重同时取配货等现实约束条件一开始朋友用的是瞎排的路线不仅多跑了几十公里还经常超时被客户吐槽。我给他改了个基于遗传算法的Matlab版本通用性拉满还把时间窗、载重限制、配货要求这些现实约束都嵌进去了跑起来既能看迭代曲线又能直接出可视化路线用起来贼顺手。先唠明白啥是VRPTW说白了就是你有若干辆快递车从仓库出发要给一堆客户送货每个客户只能在指定的时间段里接收货物每辆车有最大载货量最后还要回到仓库目标是让总行驶里程最少或者总耗时最少。比普通的VRP多了时间窗这个硬约束也是实际配送里最常见的场景。咱们直接上代码边写边唠第一步先把基础数据和参数整明白首先得定义我们的客户和车辆信息我这里用模拟数据1个仓库10个客户把所有参数都存在一个数组里不用分开存好几个变量可读性拉满clear;clc;close all %% 1. 初始化基础业务参数 % 客户/仓库数据每一行依次是 [x坐标, y坐标, 最早到达时间, 最晚到达时间, 服务时长, 货物重量] % 时间全部转成分钟避免时分换算踩坑比如8点就是8*60480分钟 customer_info [ 0, 0, 0, 0, 0, 0; % 第1行是仓库不用送货 23, 45, 480, 600, 15, 200; % 客户18点到10点到服务15分钟带200kg货 35, 12, 540, 660, 10, 150; 18, 67, 420, 540, 20, 300; 56, 34, 600, 720, 8, 120; 72, 21, 480, 600, 12, 250; 41, 55, 540, 660, 15, 180; 29, 78, 450, 570, 10, 220; 63, 89, 600, 720, 20, 300; 52, 31, 480, 600, 12, 170; 11, 62, 540, 660, 15, 210; ]; % 车辆配置3辆车每车最多拉1000kg每公里耗时按1分钟算简化成本计算 vehicle_cnt 3; max_load 1000; time_per_km 1; depot 1; % 仓库在数组里的索引 customer_cnt size(customer_info,1)-1; % 去掉仓库总共10个客户这里踩过最蠢的坑就是没统一时间单位一开始用小时算后来加等待时间的时候直接乱套了全转成分钟之后就清爽多了。第二步遗传算法的核心适配度函数遗传算法好不好用全看你怎么定义“好坏”。我们的适配度函数要同时满足三个约束每辆车的总载货量不超过上限每个客户都在指定时间窗内到达早了就等晚了直接判无效总行驶里程尽可能短我这里用了硬约束的写法只要有一个条件不满足直接给这个路线打满分无穷大相当于直接扔进垃圾桶比加惩罚项省心一百倍——之前朋友用惩罚项的时候调惩罚系数调了一下午要么非法路线混进来要么全给毙了。function [fitness, total_dist] calc_fitness(chromosome, customer_info, vehicle_cnt, max_load, depot) % 把染色体拆成每辆车的配送顺序染色体是一串随机的客户编号按位置分成vehicle_cnt段 split_pos sort(randperm(length(chromosome)-1, vehicle_cnt-1)); routes mat2cell(chromosome, 1, [split_pos(1), diff(split_pos), length(chromosome)-sum(split_pos)]); total_dist 0; is_valid true; for v 1:vehicle_cnt current_route routes{v}; if isempty(current_route) continue; end current_time 0; % 从仓库出发的时间是0 current_load 0; last_pos depot; for c 1:length(current_route) cust_idx current_route(c); % 注意客户在数组里的索引是cust_idx1因为第1行是仓库 cust customer_info(cust_idx1,:); % 计算行驶到当前客户的时间 dist norm(customer_info(last_pos,1:2) - customer_info(cust_idx1,1:2)); drive_time dist * time_per_km; arrive_time current_time drive_time; % 检查时间窗晚了直接无效 if arrive_time cust(4) is_valid false; fitness inf; return; end % 早了就等到最早时间 if arrive_time cust(3) current_time cust(3); else current_time arrive_time; end % 加上服务时长 current_time current_time cust(5); % 检查载货量 current_load current_load cust(6); if current_load max_load is_valid false; fitness inf; return; end total_dist total_dist dist; last_pos cust_idx1; end % 送完这批客户回仓库 back_dist norm(customer_info(last_pos,1:2) - customer_info(depot,1:2)); total_dist total_dist back_dist; end if ~is_valid fitness inf; else fitness total_dist; end end第三步种群迭代和进化逻辑遗传算法的流程就是初始化随机种群→计算每个个体的适配度→选择优秀个体→交叉变异→重复迭代直到收敛。我这里用了锦标赛选择比轮盘赌更不容易早熟新手改起来也简单%% 3. 遗传算法超参数设置 pop_size 50; % 种群数量客户越多可以调大一点 gen_max 100; % 迭代次数 cross_prob 0.8; % 交叉概率 mutate_prob 0.1; % 变异概率 % 初始化种群每个染色体都是一串随机的客户编号1~10 pop zeros(pop_size, customer_cnt); for i 1:pop_size pop(i,:) randperm(customer_cnt); end % 记录每一代的最优结果 best_cost_record zeros(1, gen_max); %% 4. 开始迭代进化 for gen 1:gen_max % 计算所有个体的适配度 fitness_list zeros(pop_size,1); for i 1:pop_size [fitness_list(i), ~] calc_fitness(pop(i,:), customer_info, vehicle_cnt, max_load, depot); end % 记录当前代最优解 [current_best_fit, best_idx] min(fitness_list); best_cost_record(gen) current_best_fit; best_chromosome pop(best_idx,:); % 锦标赛选择每次随机挑两个个体选适配度好的留下 new_pop zeros(pop_size, customer_cnt); for i 1:pop_size idx_a randi(pop_size); idx_b randi(pop_size); if fitness_list(idx_a) fitness_list(idx_b) new_pop(i,:) pop(idx_a,:); else new_pop(i,:) pop(idx_b,:); end end pop new_pop; % 单点交叉随机选一个位置交换两段染色体 for i 1:2:pop_size if rand cross_prob cross_pos randi(customer_cnt-1); temp pop(i,cross_pos1:end); pop(i,cross_pos1:end) pop(i1,cross_pos1:end); pop(i1,cross_pos1:end) temp; end end % 变异随机交换两个客户的位置避免陷入局部最优 for i 1:pop_size if rand mutate_prob pos1 randi(customer_cnt); pos2 randi(customer_cnt); temp pop(i,pos1); pop(i,pos1) pop(i,pos2); pop(i,pos2) temp; end end % 每10代打个日志看看进度 if mod(gen,10) 0 fprintf(第%d代当前最优总里程%.2f km\n, gen, current_best_fit); end end第四步解析最优路线画图展示迭代完了之后我们得把最优的染色体翻译成人类能看懂的路线还要画出来看看效果%% 5. 解析最优路线并打印 % 找到全局最优的个体 final_fitness zeros(pop_size,1); for i 1:pop_size [final_fitness(i), ~] calc_fitness(pop(i,:), customer_info, vehicle_cnt, max_load, depot); end [~, best_idx] min(final_fitness); best_route pop(best_idx,:); % 把最优染色体拆成每辆车的配送顺序 split_pos sort(randperm(customer_cnt-1, vehicle_cnt-1)); final_routes mat2cell(best_route, 1, [split_pos(1), diff(split_pos), customer_cnt-sum(split_pos)]); % 打印每辆车的详细路线 fprintf(\n 最终最优配送方案 \n); for v 1:length(final_routes) route final_routes{v}; if isempty(route) continue; end fprintf(车辆%d仓库 - ,v); total_load 0; total_time 0; last_pos depot; for c 1:length(route) cust_idx route(c); cust customer_info(cust_idx1,:); dist norm(customer_info(last_pos,1:2)-customer_info(cust_idx1,1:2)); drive_time dist * time_per_km; arrive_time total_time drive_time; % 计算等待时间 if arrive_time cust(3) wait_time cust(3) - arrive_time; total_time cust(3); else wait_time 0; total_time arrive_time; end total_time total_time cust(5); total_load total_load cust(6); fprintf(客户%d(%dkg%d:%d~%d:%d) - , cust_idx, cust(6), floor(cust(3)/60), mod(cust(3),60), floor(cust(4)/60), mod(cust(4),60)); last_pos cust_idx1; end % 回仓库 back_dist norm(customer_info(last_pos,1:2)-customer_info(depot,1:2)); total_time total_time back_dist * time_per_km; fprintf(仓库\n 总载货量%dkg总耗时%.2f分钟\n\n, total_load, total_time); end %% 6. 画图展示 figure(Name,VRPTW优化结果,Position,[100,100,1200,500]); % 左图迭代收敛曲线 subplot(1,2,1); plot(best_cost_record,LineWidth,2); title(迭代最优总里程变化); xlabel(迭代次数);ylabel(总行驶里程/km);grid on; % 右图配送路线图 subplot(1,2,2); % 画仓库和客户点 plot(customer_info(1,1),customer_info(1,2),rs,MarkerSize,15,DisplayName,仓库); hold on; for i 2:size(customer_info,1) plot(customer_info(i,1),customer_info(i,2),bo,MarkerSize,8); text(customer_info(i,1)2,customer_info(i,2)2,sprintf(%d:%d~%d:%d,floor(customer_info(i,3)/60),mod(customer_info(i,3),60),floor(customer_info(i,4)/60),mod(customer_info(i,4),60))); end % 画不同车辆的路线用不同颜色区分 color_list [r,g,b,m,c]; for v 1:length(final_routes) route final_routes{v}; if isempty(route) continue; end path [depot; route1; depot]; plot(customer_info(path,1),customer_info(path,2),color_list(mod(v-1,length(color_list))1),LineWidth,2); end legend(Location,bestoutside); title(最优配送路线图);grid on;跑出来的效果咋样我用上面的测试数据跑了100代第50代左右就收敛了最优总里程大概420km比朋友自己排的路线少了快100km而且每个客户都刚好卡在时间窗里载重也没超。画图出来之后朋友一眼就看出来哪条路线最顺路直接拿去给配送队用了。几个实用的小 tips如果客户特别多比如上百个可以把种群数量和迭代次数调高一点不然容易欠拟合要是想换成本计算方式比如把油费算进去直接改timeperkm为油费单价就行嫌随机分割路线不好的话可以改成按客户地理位置聚类之后再分割初始化的种群质量会更高不想手动写参数的话还可以加个GUI界面直接导入Excel的客户数据就行反正这个代码改改就能用在快递、外卖、同城配送的实际场景里比网上找的那些纯论文代码好用多了毕竟都是踩过坑之后改出来的。