一、问题建模与数学描述
多车场车辆路径问题(MDVRP)可建模为带约束的组合优化问题:
-
目标函数:最小化总运输成本(距离/时间/费用)
其中\(K\)为车场数,\(P_k\)为第\(k\)辆车的路径,\(d_ij\)为节点间距离
-
约束条件: 每个客户仅被访问一次 车辆从所属车场出发并返回 车辆载重不超过容量限制 时间窗约束(若适用)
二、遗传算法设计
1. 染色体编码
采用多染色体编码表示多车场路径:
% 示例:4车场,10客户
chromosome = [3,1,5,2; 4,6,7,8; 9,10,3,2; 1,4,5,6];
% 每行表示一个车场的客户访问序列,数字代表客户编号
2. 适应度函数
综合路径长度与约束违反惩罚:
function fitness = calc_fitness(chromosome, dist_matrix, demand, capacity)total_dist = 0;penalty = 0;for i = 1:size(chromosome,1)route = chromosome(i,:);route_dist = 0;load = 0;for j = 2:length(route)route_dist = route_dist + dist_matrix(route(j-1), route(j));load = load + demand(route(j));end% 时间窗惩罚(示例)if load > capacitypenalty = penalty + 1000; endtotal_dist = total_dist + route_dist;endfitness = 1/(total_dist + penalty);
end
3. 遗传操作
-
选择:锦标赛选择(Tournament Selection)
function winner = tournament_selection(pop, fitness, tournament_size)candidates = randperm(size(pop,1), tournament_size);[~, idx] = min(fitness(candidates));winner = pop(candidates(idx),:); end
-
交叉:改进顺序交叉(OX)保留车场连续性
function child = ox_crossover(parent1, parent2)n = size(parent1,2);child = zeros(1,n);% 随机选择两个交叉点p1 = randperm(n,2);p1 = sort(p1);% 复制父代1的中间段child(p1(1):p1(2)) = parent1(p1(1):p1(2));% 填充父代2剩余基因ptr = p1(2)+1;for i = 1:nif ptr > nptr = 1;endif ~ismember(parent2(i), child)child(ptr) = parent2(i);ptr = ptr+1;endend end
-
变异:交换突变与车场重分配
function mutated = swap_mutation(chromosome, prob)if rand < probidx1 = randi(size(chromosome,2));idx2 = randi(size(chromosome,2));% 交换不同车场的客户while chromosome(1,idx1) == chromosome(1,idx2)idx2 = randi(size(chromosome,2));endtemp = chromosome(1,idx1);chromosome(1,idx1) = chromosome(1,idx2);chromosome(1,idx2) = temp;end end
三、改进
1. 自适应参数调整
-
动态交叉率:
pc=pc0⋅e−λ⋅favg/fmax
-
变异率与种群多样性关联
2. 混合启发式算法
-
2-opt局部搜索优化子路径:
function new_route = two_opt(route, dist_matrix)n = length(route);improved = true;while improvedimproved = false;for i = 1:n-2for j = i+2:nnew_seg = route(i:j);new_dist = sum(dist_matrix(new_seg(1:end-1), new_seg(2:end)));old_dist = sum(dist_matrix(route(i:j-1), route(j:end)));if new_dist < old_distroute(i:j) = new_seg;improved = true;endendendendnew_route = route; end
3. 多目标优化
采用NSGA-II算法处理多目标:
% 帕累托前沿维护
function fronts = fast_non_dominated_sort(population)fronts = {};ranks = zeros(size(population,1),1);dominated_count = zeros(size(population,1),1);dominates = cell(size(population,1),1);for i = 1:size(population,1)for j = 1:size(population,1)if i ~= jif dominates(population(i), population(j))dominates{i} = [dominates{i}, j];elseif dominates(population(j), population(i))dominated_count(i) = dominated_count(i) + 1;endendendif dominated_count(i) == 0ranks(i) = 1;fronts{1} = [fronts{1}, i];endendfront_idx = 1;while ~isempty(fronts{front_idx})next_front = [];for i = fronts{front_idx}for j = dominates{i}dominated_count(j) = dominated_count(j) - 1;if dominated_count(j) == 0ranks(j) = front_idx + 1;next_front = [next_front, j];endendendfront_idx = front_idx + 1;fronts{front_idx} = next_front;end
end
四、MATLAB实现流程
%% 参数设置
num_depots = 4; % 车场数量
num_customers = 50;% 客户数量
vehicle_capacity = 100; % 车辆容量
pop_size = 100; % 种群大小
max_generations = 500; % 最大迭代次数%% 数据加载
load('depot_customers.mat'); % 包含坐标、需求等数据%% 初始化种群
population = initialize_population(pop_size, num_depots, num_customers);%% 主循环
for gen = 1:max_generations% 适应度计算fitness = arrayfun(@(i) calc_fitness(population(i,:), dist_matrix, demand, vehicle_capacity), 1:pop_size);% 选择new_population = [];for i = 1:pop_sizeparent1 = tournament_selection(population, fitness, 5);parent2 = tournament_selection(population, fitness, 5);% 交叉child = ox_crossover(parent1, parent2);% 变异child = swap_mutation(child, 0.02);new_population = [new_population; child];end% 更新种群population = new_population;% 输出当前最优[best_fitness, best_idx] = max(fitness);best_route = population(best_idx,:);fprintf('Generation %d: Best Fitness = %.2f\n', gen, best_fitness);
end%% 结果可视化
plot_routes(best_route, depot_coords, customer_coords);
参考代码 遗传算法求解多车场车辆路径问题 www.youwenfan.com/contentcni/64104.html
五、性能优化
-
精英保留策略:每代保留前5%最优个体
-
邻域搜索增强:在变异操作中嵌入3-opt优化
-
并行计算:利用MATLAB Parallel Toolbox加速适应度计算
parfor i = 1:pop_sizefitness(i) = calc_fitness(population(i,:), ...); end
-
动态仓库分配:根据客户分布聚类调整车场服务区域
% K-means聚类分配客户到车场 [idx, centers] = kmeans(customer_coords, num_depots); depot_assignment = idx;