基于蚁群算法的物流中心选址优化设计与算法实现

2023-06-28陆丽丹，曹陆铖

物流科技 2023年11期

陆丽丹，曹陆铖

摘要：物流中心的选址应在全面考虑选址影响因素基础上，运用数学的方法进行量化比较。物流中心的优化选址需要模型化、数量化，文章将蚁群算法应用到物流中心优化选址问题中，给出模型的构建和实现步骤，应用Matlab编程验证模型和算法的有效性，以某种模型数据假设为例，给出一系列分析数据，从软件分析结果中找出物流中心优化选址方案，最终实验结果表明，利用蚁群算法求解最优路径时具有一定的优越性。

关键词：蚁群算法；物流中心；优化选址；Matlab

中图分类号：F252.14 文献标志码：A DOI：10.13714/j.cnki.1002-3100.2023.11.004

Abstract： The location selection of logistics center should be based on the comprehensive consideration of the factors affecting the location selection， and the quantitative comparison should be carried out using mathematical methods. The optimal location of logistics center needs to be modeled and quantized. In this paper， ant colony algorithm is applied to the optimal location of logistics center， and the construction and implementation steps of the model are given. Matlab programming is used to verify the effectiveness of the model and algorithm. Taking a certain model data assumption as an example， a series of analysis data are given， and the optimal location scheme of logistics center is found out from the software analysis results. The final experimental results show that， ant colony algorithm has some advantages in solving the optimal path.

Key words： Ant Colony（AC）algorithm; logistics centre; optimize site selection; Matlab

物流中心选址与规划是影响物流运行效率的关键因素，研究物流中心选址问题具有重要的现实意义，物流中心选址需要模型化、数量化，这是一个经典的组合优化问题，在运筹学和理论计算机科学中非常重要。从图论的角度来看，由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生n！增长的组合爆炸。由于其在交通运输、物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力。意大利学者Dorigo于20世纪90年代提出蚁群算法，可用于计算此类问题，使计算于短时间内收敛至较优解。本文以物流中心优化选址为应用背景，通过建立数学模型，应用Matlab编程对其进行了算法验证，实验证明该方法能较好地解决物流中心优化选址的问题。

1 问题描述与分析

现实中有一类单配送中心选址问题：在某区域中选择合适配送中心，物流车从配送中心出发，单次遍历所有配送點，作为一个配送周期。使用模型算法选择最优配送中心和最优配送周期路线。配送周期可循环使用，以增大配送频率。

对于单配送中心选址模型而言，林雄[1]曾提出目前所采用的连续模型（如重心法等）要求在区域中任意点皆可建造物流中心，但在现实中无法做到，而蚁群算法可优化上述局限。核心思路在于，首先确定物流中心的备选地址，其次通过蚁群算法计算每一物流中心遍历所有配送站的最短距离，从而进行比较优化。

2 模型的建立

问题的核心函数表达为：D■=minD■+D■+D■+…＋D■，D■。

其中：D■为所有配送点与一个可能的配送中心组成的距离矩阵（矩阵大小为n+1×n+1，n为配送点的个数）第j行，第k列的元素，X■，X■，…，X■，X■为配送站1，2，3，…，n和一个可能的配送中心i的重排列。

2.1 原数据假设

假设区域中的配送点坐标为：B=[1 534 1 559; 3 524 3 035; 2 336 1 488; 2 206 3 418; 2 055 2 874; 3 915 2 253; 3 242

1 535; 3 307 1 242; 4 242 1 476; 3 805 2 978; 3 095 2 461; 2 638 3 388; 2 790 3 246; 2 366 1 553; 3 868 2 329; 2 120 2 518;

1 771 1 195; 3 790 3 453; 4 294 1 121; 2 120 2 370; 2 342 2 044; 1 993 1 983; 4 209 2 400; 1 343 1 298; 3 612 1 375; 2 020

3 170; 4 196 1 770; 2 053 3 001; 3 146 847; 2 401 3 292]。

假设区域中可能的配送中心坐标为：A=[1 761 1 203; 1 823 2 008; 2 068 1 827; 2 626 2 908; 3 837 2 788; 2 723 1 927;

2 382 2 165; 3 955 2 229; 1 516 1 410; 2 468 3 375; 3 207 2 821; 3 403 1 511; 2 211 3 195; 2 005 1 581; 1 345 2 126; 2 319

2 106; 2 150 1 199; 3 502 2 769; 2 681 744; 1 789 1 411; 3 746 719; 4 194 1 957; 1 758 1 017; 2 480 1 255; 2 266 2 591;

2 659 910; 2 862 1 851; 3 710 1 597; 2 135 3 529; 2 936 1 018]

以A1，：为例，将所有配送点和A1，：作为新的遍历集合，记为C，配送点和配送中心分布图如图1所示。

2.2 计算距离矩阵

计算其距离矩阵：

M，N=sizeC;

%M为问题的规模M-1个配送点，1个配送中心

distance=zerosM，M; %用来记录任意两个站点之间的距离

%求任意两个站点之间的距离

for m=1：M

for n=1：M

distancem，n=sqrtsumCm，：-Cn，：.^2;

end

距离矩阵distance为：■。

3 算法的实现

定义如下参数：m为蚂蚁的个数，a为信息素的重要程度，β为启发式因子的重要程度，ρ为信息素蒸发系数，G为迭代次数，Q为信息素增加系数，distance为距离矩阵，η为启发式因子η=1÷distance，τ为信息素矩阵，Tabu为禁忌表，R■为各代的最佳路线，L■为各代最佳路线的长度（初始值假设为无穷大）。

初始时刻，设：所有路径上的信息素都相等τ■t=0=0。蚂蚁kk=1，2，…，m在运动过程中，根据各条路径上的信息素大小以概率P■■t转移方向，其计算公式为：P■■t=■。

在蚁群算法执行过程中，Tabu禁忌表用于记录蚂蚁已经走过的点，allowed■表示蚂蚁未走过，可供选择的点。

在每一个循环周期结束，进入t+1时刻时，对各路径上的信息素进行调整（本文采用ant-circle模型）：

τ■t+1=1-ρ·τ■t+Δτ■t，t+1，Δτ■t，t+1=■Δτ■■t，t+1，Δτ■■t，t+1=■

其中：Δτ■■t，t+1表示第k只蚂蚁在t，t+1时刻内留在路径i，j的信息素量，其值等于信息素增加系数Q除以第k只蚂蚁走过的路径L■，路径越短，信息素增加越多；Δτ■t，t+1表示本次循環中路径i，j的信息素增加量；ρ为信息素蒸发系数，

τ■t+1表示现有信息素量。

算法的主要流程为：初始化参数，将m只蚂蚁放到n个配送点上，根据概率及其禁忌表选择路线，更新禁忌表，并计算待选择配送点的概率，循环至完成所有遍历。根据运行结果，全局更新优化信息素，清空禁忌表，重复上述操作，直至达到循环次数G。

以A1，：为例，将所有配送点和A1，：作为遍历集合，记为C，其计算结果如图2、图3所示。

由图可见，针对配送点和A1，：作为遍历集合的情况，蚁群算法在循环次数150次时成功收敛到较优解，路径为

12 458.578 4。

这意味着如果以A1，：作为配送中心，单次配送需要12 458.578 4长度的路程。接着，只需使用A2，：，A3，：等其他待选配送中心，做同样上述操作，计算所需路程。此后对比所有方案，选择最优解作为配送中心。

Result_Table=zerosheightA，1;