【matlab 路径规划】基于改进遗传粒子群算法的药店配送路径优化

一背景介绍

本文分享的是一个基于订单合并的订单分配和路径规划联合优化，主要背景是骑手根据客户需求，从药店取药之后进行配送，配送的过程中考虑路径的长度、客户的服务时间窗、车辆的固定成本等要素，经过建模和优化得到最优的配送方案。

二模型介绍

2.1基本假设

配送的具体流程和现实情况,建立的数学模型基于以下假设条件:
(1)O2O 药品零售平台旗下的各个门店能够满足已下单顾客的需求量，即不存在供不应
求的情况。
(2)已知消费者下单商品数量、地理位置及时间窗和每个消费者的需求量不会发生变化
(3)骑手在每个配送点服务时间恒定且相同，由于服务时间较短所以忽略不计。
(4)骑手从药店出发，中途不可返回药店取货，完成所有的配送任务后需要返回药店。
(5)在骑手对各配送点进行配送的过程中，不考虑交通堵塞、车辆故障、天气恶劣等突
发状况的影响。

2.2目标函数

在这里插入图片描述

2.3 约束条件

在这里插入图片描述

三算法介绍

遗传算法是一种模拟自然进化过程的优化算法，用于解决优化问题。它模拟了生物进化的过程，通过对优良个体的选择、交叉和变异，逐步优化解的质量，最终找到最优解。

遗传算法的基本步骤包括：

初始化种群：随机生成一组初始解作为种群，通常采用随机数生成的方式。

适应度评价：根据问题的具体要求，采用适应度函数对每个个体进行评估，得到其适应度值。

选择操作：根据个体的适应度值，按照一定的选择概率选择优良个体作为父代，通常采用轮盘赌选择方法。

交叉操作：从选出的父代个体中选取一对个体，通过某种交叉方式生成新的个体。

变异操作：对新生成的个体进行一定的变异操作，改变其基因的值，增加种群的多样性。

更新种群：将新生成的个体加入到种群中，得到更新后的种群。

终止条件判断：判断是否满足终止条件，如达到最大迭代次数或找到满足要求的解。

返回最优解：返回种群中适应度最好的个体作为最优解。

遗传算法通过迭代优化的方式，不断改进解的质量，寻找到全局最优解或较好的局部最优解。它在解决复杂问题、搜索空间大的问题等方面具有很好的性能。

四算例分析

算例1 本文使用30个节点的算例，1个配送节点 29个需求节点（分为三个优先级）
在这里插入图片描述

车辆编号.1: 0 -> 7 -> 1 -> 12 -> 15 -> 24 -> 22 -> 11 -> 27 -> 26 -> 29 ->
25 -> 0 到达时间节点: 0 - 4.7 - 9.9 - 11.4 - 12.4 - 14.9 - 15.6 - 17.4 -
19.6 - 24 - 26.7 - 28.4 - 33.7 min 行驶距离: 8413.36 m, 总时间: 33.7 min; 行驶成本 (C1): 21.03, 惩罚成本 (C2): 50.88
------------------------------------------------------------- 车辆编号.2: 0 -> 8 -> 19 -> 0 到达时间节点: 0 - 7.9 - 10.2 - 19.7 min 行驶距离: 4931.47
m, 总时间: 19.7 min; 行驶成本 (C1): 12.33, 惩罚成本 (C2): 29.59
------------------------------------------------------------- 车辆编号.3: 0 -> 18 -> 13 -> 4 -> 5 -> 16 -> 28 -> 0 到达时间节点: 0 - 2.5 - 6 - 7.5 -
10.1 - 13.6 - 15.1 - 16.6 min 行驶距离: 4138.40 m, 总时间: 16.6 min; 行驶成本 (C1): 10.35, 惩罚成本 (C2): 29.81
------------------------------------------------------------- 车辆编号.4: 0 -> 10 -> 6 -> 9 -> 20 -> 0 到达时间节点: 0 - 5.9 - 10 - 12.4 - 15.5 -
20.1 min 行驶距离: 5020.18 m, 总时间: 20.1 min; 行驶成本 (C1): 12.55, 惩罚成本 (C2): 33.81
------------------------------------------------------------- 车辆编号.5: 0 -> 23 -> 17 -> 14 -> 21 -> 30 -> 0 到达时间节点: 0 - 6.2 - 7.2 - 8.2 -
11.8 - 20.5 - 22.8 min 行驶距离: 5695.44 m, 总时间: 22.8 min; 行驶成本 (C1): 14.24, 惩罚成本 (C2): 37.93
------------------------------------------------------------- 车辆编号.6: 0 -> 2 -> 3 -> 0 到达时间节点: 0 - 1.5 - 5.7 - 9.5 min 行驶距离: 2363.65 m,
总时间: 9.5 min; 行驶成本 (C1): 5.91, 惩罚成本 (C2): 14.18

算例2 本文使用10个节点的算例，1个配送节点 9个需求节点（分为三个优先级）

在这里插入图片描述
**

车辆编号.1: 0 -> 2 -> 3 -> 1 -> 5 -> 4 -> 7 -> 8 -> 9 -> 6 -> 0 到达时间节点:
0 - 1.5 - 5.7 - 13.8 - 15.3 - 16.9 - 18.5 - 22.1 - 27.2 - 29.5 - 32.4
min 行驶距离: 8090.30 m, 总时间: 32.4 min; 行驶成本 (C1): 20.23, 惩罚成本 (C2):
54.26

六项目分享

部分源码

clc
clear
close all
tic % 保存当前时间

dataloader
%% 初始化问题参数
CustomerNum = size(Position, 1) - 1; % 需求点个数

%% 需求点绘图
figure
hold on
xx = Position(:, 1);
yy = Position(:, 2);
idx1 = find(order_priority == 1);
idx2 = find(order_priority == 2);
idx3 = find(order_priority == 3);
scatter(xx(idx1), yy(idx1), 25, 'filled', 'go', 'DisplayName', '第一优先级')
scatter(xx(idx2), yy(idx2), 25, 'filled', 'bo', 'DisplayName', '第二优先级')
scatter(xx(idx3), yy(idx3), 25, 'filled', 'yo', 'DisplayName', '第三优先级')
scatter(xx(1), yy(1), 200, 'filled', 'rp', 'DisplayName', '药店')
legend
title('需求点散点图')

%% 初始化算法参数
NIND = 1000; % 粒子数量
MAXGEN = 100; % 最大迭代次数
mutation_prob = 0.05; % 变异概率
crossover_prob = 0.8; % 交叉概率
tournament_size = 5; % 锦标赛规模

%% 为预分配内存而初始化的0矩阵
Population = zeros(NIND, CustomerNum * 2 + 1); % 预分配内存，用于存储种群数据
PopDistance = zeros(NIND, 1); % 预分配矩阵内存
GbestDisByGen = zeros(MAXGEN, 1); % 预分配矩阵内存

penalty_costs = zeros(NIND, 1);
travel_costs = zeros(NIND, 1);
vehicle_costs = zeros(NIND, 1);
total_distances = zeros(NIND, 1);
penalty_orders = cell(NIND, 1);

for i = 1:NIND
    %% 初始化各粒子
    Population(i, :) = InitPop(CustomerNum, Distance, setting); % 使用GRASP算法生成TSP路径

    %% 计算路径长度
    PopDistance(i) = CalcDis(Population(i,:),Distance,TimeWindow,order_priority,setting); % 计算路径长度
end
%% 存储Pbest数据
Pbest = Population; % 初始化Pbest为当前粒子集合
PbestDistance = PopDistance; % 初始化Pbest的目标函数值为当前粒子集合的目标函数值

%% 存储Gbest数据
[mindis, index] = min(PbestDistance); % 获得Pbest中
Gbest = Pbest(index, :); % 初始Gbest粒子
GbestDistance = mindis; % 初始Gbest粒子的目标函数值

%% 开始迭代
gen = 1;

while gen <= MAXGEN
    %% 选择算子（锦标赛选择）
    new_population = zeros(size(Population));
    for i = 1:NIND
        new_population(i, :) = Selection(Population, PopDistance, tournament_size); % 锦标赛选择
    end
    Population = new_population;

    %% 每个粒子更新
    for i = 1:NIND
        %% 粒子与Pbest交叉
        if rand < crossover_prob
            Population(i, 2:end-1) = Crossover(Population(i, 2:end-1), Pbest(i, 2:end-1)); % 交叉
        end

        % 新路径长度变短则记录至Pbest
         PopDistance(i) = CalcDis(Population(i,:),Distance,TimeWindow,order_priority,setting); % 计算路径长度
        if PopDistance(i) < PbestDistance(i) % 若新路径长度变短
            Pbest(i, :) = Population(i, :); % 更新Pbest
            PbestDistance(i) = PopDistance(i); % 更新Pbest距离
        end

        %% 根据Pbest更新Gbest
        [mindis, index] = min(PbestDistance); % 找出Pbest中最短距离
        if mindis < GbestDistance % 若Pbest中最短距离小于Gbest距离
            Gbest = Pbest(index, :); % 更新Gbest
            GbestDistance = mindis; % 更新Gbest距离
        end

        %% 粒子与Gbest交叉
        if rand < crossover_prob
            Population(i, 2:end-1) = Crossover(Population(i, 2:end-1), Gbest(2:end-1));
        end

        % 新路径长度变短则记录至Pbest
        PopDistance(i) = CalcDis(Population(i,:),Distance,TimeWindow,order_priority,setting); % 计算路径长度
        if PopDistance(i) < PbestDistance(i) % 若新路径长度变短
            Pbest(i, :) = Population(i, :); % 更新Pbest
            PbestDistance(i) = PopDistance(i); % 更新Pbest距离
        end

        %% 粒子自身变异
        if rand < mutation_prob
            Population(i, :) = Mutate(Population(i, :), Distance); % 传递Distance矩阵
        end

        % 新路径长度变短则记录至Pbest
        PopDistance(i) = CalcDis(Population(i,:),Distance,TimeWindow,order_priority,setting); % 计算路径长度
        if PopDistance(i) < PbestDistance(i) % 若新路径长度变短
            Pbest(i, :) = Population(i, :); % 更新Pbest
            PbestDistance(i) = PopDistance(i); % 更新Pbest距离
        end

        %% 根据Pbest更新Gbest
        [mindis, index] = min(PbestDistance); % 找出Pbest中最短距离
        if mindis < GbestDistance % 若Pbest中最短距离小于Gbest距离
            Gbest = Pbest(index, :); % 更新Gbest
            GbestDistance = mindis; % 更新Gbest距离
        end
    end

    %% 显示此代信息
    fprintf('迭代次数 = %d, 最小成本 = %.2f   \n', gen, GbestDistance)

    %% 存储此代最短距离
    GbestDisByGen(gen) = GbestDistance;

    %% 更新迭代次数
    gen = gen + 1;
end

% 删去路径中多余1
for i = 1:length(Gbest) - 1
    if Gbest(i) == Gbest(i + 1)
        Gbest(i) = 0; % 相邻位都为1时前一个置零
    end
end
Gbest(Gbest == 0) = []; % 删去多余零元素

Gbest = Gbest - 1; % 编码各减1，与文中的编码一致

%% 计算结果数据输出到命令行
disp('-------------------------------------------------------------')
toc % 显示运行时间
TextOutput(Gbest, Distance, TimeWindow, setting); % 显示最优路径
disp('-------------------------------------------------------------')

%% 迭代图
figure
plot(GbestDisByGen, 'LineWidth', 2) % 展示目标函数值历史变化
xlim([1 gen - 1]) % 设置 x 坐标轴范围
set(gca, 'LineWidth', 1)
xlabel('迭代次数')
ylabel('最小成本')
title('遗传粒子群迭代曲线图')

%% 绘制实际路线
DrawPath(Gbest, Position, idx1, idx2, idx3)