遗传算法的多车场车辆路径问题求解

一、问题建模与数学描述

多车场车辆路径问题（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

五、性能优化

1. 精英保留策略：每代保留前5%最优个体

2. 邻域搜索增强：在变异操作中嵌入3-opt优化

3. 并行计算：利用MATLAB Parallel Toolbox加速适应度计算

   parfor i = 1:pop_sizefitness(i) = calc_fitness(population(i,:), ...);
   end
   

4. 动态仓库分配：根据客户分布聚类调整车场服务区域

   % K-means聚类分配客户到车场
   [idx, centers] = kmeans(customer_coords, num_depots);
   depot_assignment = idx;