使用遗传算法优化带时间窗口的多配送中心车辆路径问题

该代码利用遗传算法 (GA) 优化带时间窗口的多配送中心车辆路径问题 (VRPTW)。

代码示例：

%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

代码解释：

该代码包含了 GA 算法的典型步骤，包括种群初始化、适应度计算、选择、交叉、变异和局部搜索等。
输入数据：
- 从输入文件中读取测试数据。
- test_date 存储了所有节点的信息，包括坐标、时间窗口和服务时间。
- depot_time_window1 和 depot_time_window2 定义了配送中心的开放和关闭时间。
- time_window1 和 time_window2 定义了每个客户的时间窗口。
- service_time 定义了每个客户的服务时间。
GA 参数：
- population：种群大小。
- maximum_generation：最大迭代次数。
- probability_crossover：交叉概率。
- probability_mutation：变异概率。
种群初始化：
- createInitChrom 函数用于生成初始染色体。
- createInitPopulation 函数用于生成初始种群。
适应度计算：
- calObj 函数用于计算每个染色体的适应度值，该值通常是总行驶距离和违规情况的综合考虑。
选择：
- Select 函数用于根据适应度值选择下一代的染色体。
交叉：
- Recombin 函数用于进行染色体交叉操作。
变异：
- Mutate 函数用于进行染色体变异操作。
局部搜索：
- neighborhoodSearch 函数用于进行局部搜索，以进一步改善染色体的适应度。
解码：
- decode 函数用于将染色体解码成实际的配送路径。
结果分析：
- 代码将输出最优配送路径、总行驶距离、违规路径数、违规顾客数等信息。
可视化：
- drawMap 函数用于可视化最优配送路径。

代码中的时间窗口和服务时间：

该代码使用 time_window1、time_window2 和 service_time 变量来存储每个客户的时间窗口和服务时间。
在解码染色体和计算适应度时，这些信息被用来确定每个路径的行驶时间和违规情况。

总结：

该代码演示了如何使用遗传算法优化带时间窗口的多配送中心车辆路径问题。它包含了 GA 算法的典型步骤，并通过解码和可视化功能提供了清晰的结果展示。

注意：

该代码只是一个简单的示例，您可以根据您的具体需求进行修改和扩展，例如：

您可以添加其他约束条件，例如车辆容量、车辆类型等。
您可以尝试不同的 GA 参数，以找到最佳的优化效果。
您可以使用不同的局部搜索算法，以进一步改善染色体的适应度。
您可以使用不同的可视化工具，以更好地展示优化结果。