基于遗传算法物流配送中心选址研究

摘 要：物流配送中心选址一直是物流领域的重要研究方向，为了提高选址的准确性，通过分析物流配送的运输成本、建设成本，并利用整数规划法，建立单目标规划模型，最后再借助MATLAB软件，运用遗传算法求解单目标规划模型，得到模型的全局最优解。结果表明，遗传算法对所建立模型的求解具有可行性、有效性。

关键词：遗传算法；配送中心；整数规划

中图分类号：U115 文献标志码：A

DOI：10.13714/j.cnki.1002-3100.2024.19.007

Abstract： The location of logistics distribution centers has always been an important research direction in the field of logistics. In order to improve the accuracy of site selection， by analyzing the transportation cost and construction cost of logistics and distribution， and using the integer programming method， a single-objective programming model is established， and finally with the help of MATLAB software， the genetic algorithm is used to solve the established single-objective programming model， and the global optimal solution of the model is obtained. The example results show that the genetic algorithm is feasible and effective for solving the established objective programming model.

Key words： genetic algorithm; distribution center; integer programming

0 引 言

物流配送中心选址问题一直是物流领域所研究的重要问题[1]。早在20世纪初，德国学者Weber A[2]就提出了经典Weber问题，提出通过确定唯一的仓库，实现与多个客户之间的总运输距离最小，该研究也是物流设施选址问题发展的重要开端。

物流设施选址问题通常都是NP-hard问题，目前选址模型建立主要包括定性方法和定量方法。其中最常用的定性方法有模糊综合评判法、层次分析法、数据包络分析法等，常用的定量研究方法主要包括重心法、网络选址法、整数规划法等[3]。倪卫红等[4]利用聚类重心法，研究了物流配送中心选址问题。李晶晶[5]构建0～1混合整数规划模型，确定了连锁超市的配送中心的选址位置。冉昊杰等[6]设计了一种基于改进的模拟退火算法的农产品配送中心选址的方法。秦芳芳等[7]研究了物流配送中心选址问题。

配送中心的选址问题具有复杂性，而针对这一点启发式算法具有较高的求解效率。因此，本文通过建立整数规划模型，并求解该模型，最终证明了算法及模型的可行性与有效性。

1 模型的建立

1.1 模型假设

为了便于问题分析，我们对选址问题进行了以下假设：（1）模型只考虑在单个周期内的运行情况，即时间成本、社会效益、政府政策等不在考虑之中；（2）每一个备选地址都有可能被选中；（3）各个客户点需求量已知，且备选地址供货量充足；（4）单位运输距离及运输成本已知且固定；（5）所有客户点都会被覆盖；（6）一个配送中心可以覆盖多个客户点；（7）一个客户点只能有一个配送中心来配送；（8）各个客户点均采取公路运输方式；（9）只考虑物流中心运输、建设成本，其他成本不考虑。

1.2 模型构建

物流配送中心选址问题就是在满足所有客户点需求的情况下，选出配送中心，使所有费用达到最小化。

目标函数：

minF=qσdcC+qdcC+qα （1）

式中：M表示配送中心地址集合，N表示所有客户点集合，q表示配送中心是否被选中，σ表示客户点j是否有配送中心i配送，d表示客户j到配送中心i的距离，c表示客户j和配送中心i之间单位运输成本， C表示客户j的需求量，d表示从发件中心到配送中心的距离，c表示到配送中心i的单位运输成本，C表示到配送中心i的发件数量，α表示配送中心i建设成本。

约束条件：

（1）从发件网点到配送中心的运输量要等于所有客户点的需求量：

qC=C （2）

（2）配送中心的容量不小于所有客户的需求量，其中V表示配送中心i的容量：

qV≥C （3）

（3）配送中心建设数量要小于配送中心最大可建设数量，其中Q表示最大可建设数量：

q≤Q， q=0，1 （4）

（4）每一个客户点都只能有一个配送中心服务：

σ=1， j∈N， σ=0，1 （5）

（5）配送中心的容量要满足客户需求：

σC≤V， j∈N &nbs1EX3STyQVhQMiTZHf0qDUA==p; （6）

（6）没有选为配送中心的地点不会有客户：

σ≤q （7）

（7）所有客户点的需求都会被满足，不会出现某个客户点没配送的情况，其中n表示客户点数量：

σ=n （8）

2 遗传算法

遗传算法（Genetic Algorithm，GA）[8]于20世纪60年代末期提出，主要有选择、交叉、变异等操作。

2.1 编 码

遗传算法的编码就是将实际问题的解映射到染色体中，因此编码方式至关重要。本文用二进制编码，用0，1来代表基因，其中：0表示没被选中，1表示被选中。

2.2 初始种群产生

产生100个个体，使其满足编码方案，构成初始种群G：

2.3 适应度函数

适应度函数实际上就是为了保证种群的优良性而建立的一个评价个体优劣的函数。适应度函数由目标函数F变换得到，目标函数值越小，适应度函数值就会越大，将自己的基因传给下一代的可能性就会越高，反之亦然。基于此，本文建立适应度函数如下：

2.4 选 择

选择就是通过计算种群个体适应度，挑选适应度高的优秀个体。通过选择，优秀的个体就会保留下来，符合优胜劣汰的自然规则。最后通过选择将优秀个体作为优秀的种群保留下来。

2.5 交 叉

交叉就是从种群里选择两个染色体，随机选取一部分基因片段进行杂交重组。杂交能够产生新一代更加优良的个体，是种群进化的重要手段。本文采用两点交叉，随机设置两个交叉点，交换交叉点间的基因。

2.6 变 异

变异就是指将染色体上的基因在符合编码要求的条件下进行替换，从而形成新个体。变异就是为了获取新个体，当变异概率较小时，不利于新个体的出现，当变异概率较大时，染色体的基因结构不稳定，不利于适应度收敛。因此本文设置变异概率如下：

3 仿真分析

3.1 参数设置

假设在100*100平方千米的区域里，有发件中心一个坐标为（50，50），可选7个配送中心，其坐标、容量和成本如表1所示，有20个客户，其坐标和需求量如表2所示，配送成本为1元/吨公里，设置种群数量为100，最大迭代次数为1 000。

3.2 模型求解

利用MATLAB读取上述数据并运行30次，通过对该实例模型进行求解最终得到2个较优仿真结果方案如图1所示。

最终得到配送方案如表3所示，其中，方案1选取1、2、3、5号配送中心，总成本为553.30万元；方案2选取1、2、3号配送中心，总成本为575.02万元。通过对比，最终决定选取方案1，总成本最低为553.30万元。

4 结 论

本文通过建立整数规划模型，并进行求解得到稳定、可靠的选址方案，证明该算法可用于物流配送中心的选址问题中，对物流配送中心选址具有重要实用价值和指导意义。但由于本文只考虑运输成本和建设成本，并没有考虑其他因素，因此，在今后的研究中可以将社会效益、管理成本等条件加进来，以便求出更合理的配送中心地址。

参考文献：

[1] 周兴龙，金鹏飞. 基于遗传算法的单点物流选址问题探析[J]. 物流工程与管理，2010，32（7）：39-42.

[2] WEBER A. Über den standort der industrien[M]. JCB Mohr， 1909.

[3] 李锦. 秸秆收储中心选址及收集路径优化研究[D]. 郑州：河南农业大学，2021.

[4] 倪卫红，陈太. 基于聚类-重心法的应急物流配送中心选址[J]. 南京工业大学学报（自然科学版），2021，43（2）：255-263.

[5] 李晶晶. 鲜农产品冷链物流配送中心选址研究[D]. 太原：中北大学，2021.

[6] 冉昊杰，王宏智. 基于改进模拟退火算法的生鲜农产品配送中心选址[J]. 计算机与现代化，2022（10）：36-40.

[7] 秦芳芳，张珈瑞，张霆，等. 基于自适应遗传算法的物流配送中心选址[J]. 物流工程与管理，2023，45（8）：1-6.

[8] HOLLAND J H. Adaptation in naturation in natural and artificial systems[J]. The University of Michigan Press， 1975（1）：21-24.