基于遗传算法的配送路线优化：单配送中心车辆路径问题求解

基于遗传算法的配送路线优化：单配送中心车辆路径问题求解

本代码使用遗传算法解决单配送中心车辆路径问题，旨在优化配送路线，减少总行驶距离和违规情况。

1. 问题描述

单配送中心车辆路径问题 (Single Depot Vehicle Routing Problem, SDVRP) 是指从一个配送中心出发，使用多辆车辆，按照最优路线为多个客户配送货物，并满足时间窗口和服务时间的约束。

2. 算法流程

遗传算法 (Genetic Algorithm, GA) 是一种启发式优化算法，其核心思想是模拟自然界生物进化过程，通过选择、交叉、变异等操作不断优化种群，最终找到问题的最优解。

主要步骤：

1. 种群初始化: 随机生成初始种群，每个个体代表一个可能的解。
2. 适应度评估: 计算每个个体的适应度值，反映解的优劣程度。
3. 选择: 根据适应度值选择优良个体，进行交叉和变异操作。
4. 交叉: 模拟生物繁殖，将两个个体的基因片段进行交换，产生新的个体。
5. 变异: 模拟基因突变，随机改变个体基因片段。
6. 局部搜索: 对产生的新个体进行局部优化，提高解的质量。
7. 重复步骤 2-6: 直到满足停止条件，例如达到最大迭代次数或最优解稳定。

3. 代码实现

%clear, clc, 
close all;

%% input data
% test_date = importdata('test.xlsx');
test_date = importdata('a1.txt');
% tw1 means the earliest start time, tw2 means the latest start time
depot_time_window1 = test_date(1,5);
depot_time_window2 = test_date(1,6);
time_window1 = test_date(2:end, 5); % tw, start time
time_window2 = test_date(2:end, 6); % tw, end time
service_time = test_date(2:end, 7); % service time 
vertexs = test_date(:, 2:3);
customer_location = vertexs(2:end, :);
customer_number = size(customer_location, 1);

robot_number = 10; % number of vehicles   最大车辆数

% dist matrix 距离矩阵
distance_pair = pdist(vertexs); % pairwise distance
distance_matrix = squareform(distance_pair); 

%% GA parameters 
population = 20;            %种群内个体数（一般20-100个）
generation = 1;              %开始种群代数
maximum_generation = 100;     %终止进化代数（一般100-500代）
probability_crossover = 0.9; %交叉概率（一般0.4-0.99）
probability_mutation = 0.05; %变异概率（一般0.0001-0.1）
rate_gap = 0.9; 
length_chrom = customer_number + robot_number - 1;  %染色体长度：染色体长度为顾客数量加上机器人数量减一，表示所有顾客和机器人的访问顺序。

%% initialize population
init_chrom = createInitChrom(customer_number, time_window1);
%调用 createInitChrom 函数生成一个初始染色体 init_chrom。
chroms = createInitPopulation(population, length_chrom, customer_number, init_chrom);
%调用 createInitPopulation 函数生成一个大小为 population 的种群 chroms，其中每个染色体的长度为 length_chrom，初始染色体为 init_chrom。

% display some values of the initial random population 这段代码用于显示初始随机种群中某个染色体的解码结果
% 调用 decode 函数将染色体解码成多条路径，并计算路径的总行驶距离和违规情况。然后，它会将解码结果输出到控制台，包括车辆数、总行驶距离、违规路径数和违规顾客数等信息。
[VC,NV,TD,violate_num,violate_cus] = decode(chroms(1,:),customer_number,time_window1,time_window2,depot_time_window2,service_time,distance_matrix);
disp('The initial population:');
disp(['Number of Robots: ', num2str(NV), ', Total Distance: ', num2str(TD), ', Number of violated Path: ', num2str(violate_num), ', Number of Violated Customer: ', num2str(violate_cus)]);
fprintf('
');

% calsulate the value of objective function 
%调用 calObj 函数来计算每个染色体的目标函数值，并将计算结果存储在 ObjV 变量中
ObjV = calObj(chroms,customer_number,time_window1,time_window2,depot_time_window2,service_time,distance_matrix);
% the minimal value
%使用 min 函数找到 ObjV 中的最小值，存储在 pre_objective_value 变量中。
pre_objective_value=min(ObjV);
% output the objective function value of current generation
disp(['Generation ', num2str(generation), ': Objective Function Value = ', num2str(min(ObjV))]);


 % Display the change of the objective function value     画图一：最优值迭代图
 figure;                         % figure 函数用于创建一个新的图形窗口
 hold on;   %函数用于保持当前图形窗口,并允许在其上添加新的图形元素
 box on;    %用于在图形窗口中显示坐标轴的边框。
 xlim([0, maximum_generation]); %用于设置横轴的范围
 title('Optimization Process');  %优化过程
 xlabel('Generation');
 ylabel('The Optimal Value'); %最优值

%定义了一些变量，用于记录迭代次数、上一次的目标函数值和停止计数器
iter_time = [];
last_dist = 0;
stop_count = 0;


%% the loop
while generation <= maximum_generation
    
    tic;
    
    % calculate the fitness value
    ObjV = calObj(chroms,customer_number,time_window1,time_window2,depot_time_window2,service_time,distance_matrix);
    % draw the line
    line([generation - 1, generation], [pre_objective_value, min(ObjV)]); pause(0.0001);
    pre_objective_value = min(ObjV);
    FitnV = Fitness(ObjV);
    % select
    SelCh = Select(chroms,FitnV,rate_gap);
    % crossover
    SelCh = Recombin(SelCh,probability_crossover);
    % mutation
    SelCh = Mutate(SelCh,probability_mutation);
    
    
    % local search
    SelCh = neighborhoodSearch(SelCh, customer_number, time_window1, time_window2, depot_time_window2, service_time, distance_matrix);
    % 
    chroms = Reins(chroms,SelCh,ObjV);
    % Delete duplicate chromsomes 
    chroms = DealRepeat(chroms);
    ObjV = calObj(chroms,customer_number,time_window1,time_window2,depot_time_window2,service_time,distance_matrix);
    [minObjV,minInd]=min(ObjV);
    disp(['Generation:' num2str(generation)]);
    [bestVC,bestNV,bestTD,best_vionum,best_viocus]=decode(chroms(minInd(1),:),customer_number,time_window1,time_window2,depot_time_window2,service_time,distance_matrix);
    disp(['Number of Robots: ', num2str(bestNV), ',Objective Function Value : ', num2str(min(ObjV)),', Total Distance: ', num2str(bestTD), ', Number of violated Path: ', num2str(best_vionum), ', Number of Violated Customer: ', num2str(best_viocus)]);
    fprintf('
');
    generation = generation + 1;
    
    iter_time(generation) = toc;
 
    
    %以下为“收敛准则”，当最优适应度值连续 31 次未发生变化时，认为算法已经收敛，并提前结束迭代
    if last_dist == bestTD
        stop_count = stop_count + 1;
        if stop_count > 30
            break;
        end
    else
        last_dist = bestTD;
        stop_count = 0;
    end
    
    
end
ObjV = calObj(chroms,customer_number,time_window1,time_window2,depot_time_window2,service_time,distance_matrix);
[minObjV,minInd]=min(ObjV);

disp('Optimal Result:')
bestChrom=chroms(minInd(1),:);
[bestVC,bestNV,bestTD,best_vionum,best_viocus]=decode(bestChrom, customer_number, time_window1, time_window2, depot_time_window2, service_time, distance_matrix);
disp(['Number of Robots: ', num2str(bestNV), ', Total Distance: ', num2str(bestTD), ', Number of violated Path: ', num2str(best_vionum), ', Number of Violated Customer: ', num2str(best_viocus)]);

flag = Judge(bestVC, time_window1, time_window2, depot_time_window2, service_time, distance_matrix);

% check the missing element in the final result
missing_element = judgeFullElement(bestVC, customer_number);

drawMap(bestVC, vertexs);




total_time = sum(iter_time);
disp(['Total Running Time: ', num2str(total_time), ' s']);
average_time = total_time/generation;
disp(['Average Running Time per Generation: ', num2str(average_time), ' s']);


% close all

4. 代码解读

• 数据输入: 读取包含客户信息、时间窗口、服务时间等数据的文本文件 a1.txt。
• 参数设置: 定义种群大小、最大迭代次数、交叉概率、变异概率等遗传算法参数。
• 种群初始化: 使用 createInitChrom 函数生成一个初始染色体，并使用 createInitPopulation 函数生成一个大小为 population 的初始种群。
• 适应度评估: 使用 calObj 函数计算每个染色体的目标函数值，目标函数值越小，表示解的质量越好。
• 选择: 使用 Select 函数根据适应度值选择优良个体。
• 交叉: 使用 Recombin 函数进行交叉操作，产生新的个体。
• 变异: 使用 Mutate 函数进行变异操作，随机改变个体基因片段。
• 局部搜索: 使用 neighborhoodSearch 函数对产生的新个体进行局部优化。
• 重复迭代: 循环执行适应度评估、选择、交叉、变异和局部搜索操作，直到满足停止条件。
• 输出结果: 打印最优解的车辆数、总行驶距离、违规路径数和违规顾客数，并绘制配送路线图。

5. 总结

本代码使用遗传算法解决单配送中心车辆路径问题，实现了配送路线的优化，并通过代码解读和详细注释，帮助用户理解算法流程和代码实现。

6. 多配送中心问题

该遗传算法代码中并没有考虑多个配送中心的情况，因此需要进行修改才能解决多配送中心问题。具体来说，需要对以下部分进行修改：

1. 时间窗口和服务时间的定义: 在原代码中，时间窗口和服务时间都是针对每个客户单独定义的，因此需要将其改为针对每个配送中心单独定义。可以考虑将时间窗口和服务时间作为数组定义，数组的每个元素对应一个配送中心的时间窗口和服务时间。
2. 计算距离矩阵: 在原代码中，距离矩阵是根据客户的坐标信息计算得出的，因此需要将其改为根据每个配送中心的坐标信息计算得出。
3. 解码函数的修改: 在原代码中，解码函数主要是将染色体转换为路径，并计算路径的总行驶距离和违规情况。需要将其改为考虑多个配送中心的情况，即将染色体转换为多条路径，并计算多条路径的总行驶距离和违规情况。
4. 目标函数的计算: 在原代码中，目标函数主要是计算路径的总行驶距离和违规情况。需要将其改为考虑多个配送中心的情况，即计算多条路径的总行驶距离和违规情况。
5. 种群初始化函数的修改: 在原代码中，种群初始化函数主要是针对单个配送中心进行染色体的随机生成。需要将其改为考虑多个配送中心的情况，即生成多个染色体，每个染色体对应一个配送中心的路径。
6. 选择、交叉和变异函数的修改: 在原代码中，选择、交叉和变异函数都是针对单个染色体进行操作。需要将其改为考虑多个染色体，每个染色体对应一个配送中心的路径。
7. 其他函数的修改: 除了上述函数，还需要对其他函数进行适当的修改，以适应多配送中心的情况。

通过对上述部分的修改，可以将代码扩展到解决多配送中心的车辆路径问题。