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

一、问题建模与数学描述

多车场车辆路径问题（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 > capacity
            penalty = penalty + 1000; 
        end
        total_dist = total_dist + route_dist;
    end
    fitness = 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:n
        if ptr > n
            ptr = 1;
        end
        if ~ismember(parent2(i), child)
            child(ptr) = parent2(i);
            ptr = ptr+1;
        end
    end
end

变异：交换突变与车场重分配

function mutated = swap_mutation(chromosome, prob)
    if rand < prob
        idx1 = randi(size(chromosome,2));
        idx2 = randi(size(chromosome,2));
        % 交换不同车场的客户
        while chromosome(1,idx1) == chromosome(1,idx2)
            idx2 = randi(size(chromosome,2));
        end
        temp = 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 improved
        improved = false;
        for i = 1:n-2
            for j = i+2:n
                new_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_dist
                    route(i:j) = new_seg;
                    improved = true;
                end
            end
        end
    end
    new_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 ~= j
                if dominates(population(i), population(j))
                    dominates{i} = [dominates{i}, j];
                elseif dominates(population(j), population(i))
                    dominated_count(i) = dominated_count(i) + 1;
                end
            end
        end
        if dominated_count(i) == 0
            ranks(i) = 1;
            fronts{1} = [fronts{1}, i];
        end
    end
    
    front_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) == 0
                    ranks(j) = front_idx + 1;
                    next_front = [next_front, j];
                end
            end
        end
        front_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_size
        parent1 = 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_size
    fitness(i) = calc_fitness(population(i,:), ...);
end

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

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