基于和声搜索算法的多层级物流中心选址问题

汤杼彬

（北京交通大学海滨学院，河北 黄骅 061199）

1 引言

物流中心作为物流运输体系的重要基础设施，对于整个物流网络体系运营效率的发挥具有重要意义。物流中心作为承接物流园区及末端配送节点的关键设施，其选址对于运输成本及运输效率具有至关重要的影响。特别是随着我国电商产业的飞速推进，如何快速满足城市配送的要求，提升用户的购物体验，有效满足用户的时效性需求，也是各个电商平台及物流运输企业主要的战略方向，经济合理地满足用户的服务水平要求也是物流运输发展的重点。而物流中心的位置不但能够影响物流运输的总成本，同时也能对物流的整体服务水平产生重要影响。在此背景下，考虑服务水平的因素，研究物流中心选址问题具有重要的理论和现实意义。

目前在物流中心选址方面，国内外很多学者已经有了大量的研究成果：O'Kelly最先提出了枢纽选址的数学模型[1-2]；Campbell提出p-中位问题、p-hub中心问题、枢纽覆盖问题等四种类型的枢纽选址问题[3]；尹莉考虑多式联运型物流网络中不同运输方式的衔接成本与时间、枢纽点间货物运输产生的规模经济效益和服务时间的约束，建立了多式联运型物流网络的货运枢纽选址模型[4]；李振宇在介绍GIS网络分析技术的基础上，重点分析了影响城市物流配送中心选址的若干因素。结合鲍姆尔-沃尔夫法的选址思想，提出了基于GIS的城市配送中心选址模型，并对模型进行了实证分析[5]。通过对以上研究成果的分析可知，物流中心的选址研究中首先未考虑服务的差异，不同的物流服务对物流中心选址所产生的影响亦有较大的不同，同时现有的研究中也没有从用户需求的角度出发，而是从建设成本及运输成本最小化的角度着手选择物流中心节点，这容易导致在当前的配送体系中，难以满足用户时效性的需求，从而在未来的市场竞争中逐渐失去竞争力。因此，本文考虑运输服务和用户需求对物流中心选址的影响，以时效性作为服务水平的重要评判要素，构建了基于服务水平的物流中心选址模型，并采用和声搜索算法进行求解，从而为运输需求导向下的物流中心选址提供一定的决策依据。

2 物流中心选址模型

2.1 符号定义

（1）参数。I为物流园区集合，i∈I；J为末端配送节点的集合，j∈J；K为物流中心备选节点的集合，k∈K；cik为节点i与k之间的单位运输费用；dik为节点i与节点k之间的运输距离；N为物流中心的总数量；W为区域内重要OD对的集合，w∈W；Ow、Dw分别为OD对w的起点及终点；pw为OD对w的最短路径为0-1参数，当OD对w的最短路径经过节点i、k所构成的弧段时为1，否则为0；tik为节点i与节点k之间的运输时间。

（2）决策变量。xk为0-1决策变量，表示物流中心备选节点k是否为物流中心，如果节点k为物流中心，则xk=1，否则xk=0；yik为0-1决策变量，表示物流园区i是否与备选物流中心k相连，如果两者相连，则yik=1，否则yik=0；ykj为0-1决策变量，表示备选物流中心k是否与末端配送节点j相连，如果两者相连，则ykj=1，否则ykj=0。

2.2 物流中心选址模型

不同物流服务间最大的差异突出表现为运输时间和运输费用的差异，在此也以运输时间及运输费用表征各物流服务。此外为了缩小问题的求解规模，在此考虑物流中心选址影响因素，将可能的物流中心节点放入物流中心备选集合中，即最终的物流中心只能是物流中心备选集合中的部分节点，从而有效缩小了解空间。在此基础上，以满足用户的时效性需求为前提，并考虑物流中心与物流园区及配送节点之间的对应关系，构建物流中心选址模型，具体模型如下：

上述模型中，式（1）为模型的目标函数，表示运输费用最小化；式（2）-式（9）为模型约束，约束（2）为物流中心选址数量约束；约束（3）和约束（4）为联锁关系约束，即物流园区i与备选物流中心k相连，则节点k必为物流中心节点；约束（5）表示对于每一个物流园区，至少有一个物流中心节点与其相连接；约束（6）表示对于每一个末端配送节点，至少有一个物流中心与其相连接；约束（7）表示对于重点OD需求，应该满足其运输时限性要求；约束（8）及约束（9）为决策变量的逻辑约束。

3 求解算法

考虑服务水平的物流中心选址模型为0-1线性规划模型，在此采用和声搜索算法进行求解。和声搜索算法是根据音乐师创制音乐的过程而形成的一种启发式算法[6]，该算法对于求解0-1规划问题具有较好的求解效果，此外该算法也具有原理简单、实现容易的特点。

3.1 和声编码

由于模型的决策变量主要有三个，分别为xk、yik及ykj，但是xk与yik及ykj分别存在连锁关系约束（3）和（4），即通过决策变量yik及ykj的值也可获取xk的值，因此初始解主要由yik及ykj的决策值构成，yik的决策值为一矩阵，其元素个数与物流园区的个数及备选物流中心点的个数有关，同理ykj的元素个数与末端配送节点的个数及备选物流中心点的个数相关，初始解结构如图1所示。

图1 初始解结构示意图

3.2 新和声生成

新和声的生成质量将直接关系到该算法的求解质量，在新和声的生成中共采用两种策略：第一种策略为采用和声记忆库中的决策值，第二种为随机变异策略。假设生成的新和声为新和声生成的步骤为：设置和声记忆库选择概率为Pr，以为例，则该音调以Pr的概率从和声记忆库中随机选择相同位置的音调，否则以1-Pr的概率随机生成；具体的操作如以下公式所示。

定义了该算法的关键步骤后，和声搜索算法的详细步骤见文献[7]，在此不做详述。

4 算例分析

为了验证模型及算法的有效性，在此采用如图2所示的网络对模型及算法进行验证。其中该网络中共有4 个物流园区节点，6 个物流中心备选节点，10个末端配送节点，算例中需要的相关参数见表1。

图2 物流运输网络示意图

表1 各节点之间的距离、时间及费用参数

在此基础上，通过计算上述重点OD对前5条K短路，验证其是否满足运到期限的约束，从而得到重点OD对的起点及终点所途经的备选物流中心节点集合，即在满足运到期限的前提下，重点OD起终点只能途经备选集合中的节点才能满足运到期限的约束，这将有效的缩小问题的求解规模。得到的重点OD对起终点所对应的备选物流中心集合见表2。

表2 重点OD对的备选物流中心集合信息

通过对重点OD对的预处理操作，能够有效的缩小解空间，在此基础上将重点OD对的备选集合信息写入初始解结构中，并设置和声记忆库规模l=10；最大创作次数Tmax=200，和声记忆库选择概率Pr=0.7，设置物流中心数量N=4，采用和声搜索算法计算得到目标函数值为1050，物流中心节点分别为K2、K4、K5、K6。物流中心与物流园区及末端配送节点的连接关系如图3所示。

图3 物流中心位置与分配关系示意图

5 结论

物流中心选址问题是物流体系规划中的关键环节，其对于降低物流运输成本、提升配送时效性具有重要作用。本文考虑物流园区及末端配送节点对物流中心选址的影响，构建了基于服务水平的多层次物流中心选址模型，并根据模型的特点采用和声搜索算法进行求解，最后采用一算例验证了模型及算法的适用性，为物流中心的选址提供一定的决策依据，但是模型中对多交通方式之间服务的差异还缺少考虑，这也是下一步研究的方向。