• 日期: 2028-06-12
  • 标签: 常规

基于遗传算法的配送路线优化 - 时间窗口约束和服务时间

本代码使用遗传算法解决带有时间窗口约束和服务时间的配送路线优化问题，旨在找到最优的配送路线，以最小化总行驶距离。代码包括数据导入、种群初始化、适应度评估、选择、交叉、变异、局部搜索等操作。

%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

代码说明

  1. 数据导入: 代码从 'a1.txt' 文件中导入数据，数据包含配送中心和客户的信息，包括位置坐标、时间窗口和服务时间。

  2. 参数设置: 设置遗传算法相关参数，例如种群大小、最大迭代次数、交叉概率、变异概率等。

  3. 种群初始化: 生成初始种群，每个个体代表一条配送路线。

  4. 适应度评估: 计算每个个体的适应度值，即路线的总行驶距离。

  5. 选择: 选择适应度值高的个体进行繁殖。

  6. 交叉: 将选择的个体进行交叉操作，生成新的个体。

  7. 变异: 对新的个体进行变异操作，增加种群的多样性。

  8. 局部搜索: 对个体进行局部搜索，以优化路线。

  9. 重复消除: 删除种群中的重复个体。

  10. 结果展示: 展示最优解，包括最优路线、总行驶距离、车辆数量等信息。

时间窗口和服务时间

代码中定义了配送中心的时间窗口 (depot_time_window1 和 depot_time_window2) 和每个客户的服务时间 (service_time)。这些信息在适应度评估和解码过程中被使用，以确保路线满足时间窗口约束和服务时间要求。

总结: 本代码使用遗传算法解决配送路线优化问题，并考虑了时间窗口和服务时间约束，为物流配送提供了有效解决方案。

基于遗传算法的配送路线优化 - 时间窗口约束和服务时间

原文地址: https://www.cveoy.top/t/topic/nP6O 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录