0.   引言

物流网络优化问题包括商品从原材料供应商到制造商, 经过中间库存和配送中心到最终客户的整个流程中有关设施选址、物流路径、产量、运输量及库存量的确定等决策项目, 其目的是在满足客户需求的基础上, 使设施设置费用、生产费用、运输与配送费用及库存费用最小化。但是由于这些决策项目涉及到多个阶段和多个层次, 利用数理手段解决此类问题变得异常复杂和困难, 为此, 许多研究者将问题分为若干个子问题, 将子问题作为独立的问题进行研究, 取得了可喜的成果, 如车辆路径问题(VRP)、设施选址问题(FLP) 等。但这些问题只能解决物流网络中的局部优化, 无法解决物流网络的整体优化, 为此, 许多研究者将局部优化问题加以整合与扩展, 进行了大量的更贴近现实的研究。Dhaenens-Flipo提出了多个设施的生产与配送问题(Multi-Facility Production and Distribution Problem), 将生产与配送问题组合在一起进行整体优化, 并采用分枝定界法求得了最优解^[1]; Melkote与Daskin将设施选址与运输网络问题加以整合, 提出了选址与网络同时优化问题, 并利用混合整数规划软件求得了最优解^[2]; Goetschalckx^[3]提出了将国际运输问题与生产、配送问题整合在一起进行同时优化的数学模型, 并采用主分割法(Primal Decomposition) 等启发式算法开发了近似解法; Hwang提出了在保证既定的服务水平的前提下, 将工厂、仓库与配送中心的选址及配送路径进行同时优化的问题, 并利用集合覆盖问题(Set-Covering Problem) 的方法、0-1规划法(0-1 Programming Method) 及改良的遗传算法(Improved Genetic Algorithm) 进行了求解^[4]; Wu利用模拟退火法(Simulated Annealing: SA) 和禁忌搜索法(Tabu-Search: TS) 开发了多物流中心条件下的LRP (Multi-Depot Location-Routing Problem : MDLRP) 的近似解法^[5]; Syam将古典FLP加以扩展, 提出了将原材料库存成本、生产成本、成品库存成本、订货成本、运输成本及工厂与仓库固定成本进行同时优化的问题, 并利用模拟退火法与拉格朗日松弛法分别求得最优解^[6]; Amiri提出了供应链系统中的运输与配送网络优化问题, 将工厂、仓库与配送中心的位置、数量与容量及货物的运输配送路径进行同时优化, 并用拉格朗日松弛法导出了下界值^[7]; Gena提出了将生产、配送与库存问题组合起来, 对生产设施的选址、配送路径及库存调整进行同时优化的问题, 并利用基于Spanning Tree法的遗传算法开发了近似解法^[8]。

本文以商品从供应商, 经过物流中心(或配送中心), 配送到最终用户的整个过程中产生的费用最小化为目的, 求得供应商的最佳位置与数量、配送中心的最佳位置与数量以及从配送中心到最终用户的最佳配送路径优化问题, 即MSDLRP, 提出了数学模型和基于启发式算法与智能算法的混合近似解法。

1.   问题的描述

1.1   问题的假设

多个客户分散在各个不同的地区, 每天的需求量是随机的; 多个物流中心(配送中心) 分散在各个不同的地区, 可以为任意的客户提供配送服务; 多个商品供应商分散在各个不同的地区, 可以为任意的物流中心供货; 物流中心(配送中心) 每天的货流量有容量限制; 从物流中心(配送中心) 到客户的配送车辆为同一种类型的车辆, 有载质量限制; 一条配送路径上至少有2个(含2个) 以上的客户。

不考虑库存问题。

1.2   问题的数学描述

最小目标函数为

$\begin{array}{l}{\displaystyle \sum _{g\in G}{\displaystyle \sum _{i\in {\rm T}}L}}{}_{gi}p{}_{gi}+{\displaystyle \sum _{i\in {\rm T}}{\rm H}}{}_{i}w{}_i+{\displaystyle \sum _{i\in {\rm T}{\displaystyle \cup C}}{\displaystyle \sum _{J\in {\rm T}{\displaystyle \cup C}}{\displaystyle \sum _{k\in {\rm K}}C}}}{}_{ij}x{}_{ijk}+\\ {\displaystyle \sum _{i\in {\rm I}}\alpha }{\displaystyle \sum _{j\in J}d}{}_{j}z{}_{ij}+{\displaystyle \sum _{k\in {\rm K}}F}{}_k{\displaystyle \sum _{i\in {\rm I}}{\displaystyle \sum _{j\in J}x}}{}_{ijk}(1)\end{array}$

约束条件为

$\begin{array}{l}{\displaystyle \sum _{k\in {\rm K}}{\displaystyle \sum _{i\in {\rm T}{\displaystyle \cup C}}x}}{}_{ijk}=1(j\in C)(2)\\ x{}_{iik}=0(i\in {\rm T}{\displaystyle \cup C},k\in {\rm K})(3)\\ {\displaystyle \sum _{i\in {\rm T}}{\displaystyle \sum _{j\in {\rm T}}x}}{}_{ijk}=0(k\in {\rm K})(4)\\ {\displaystyle \sum _{i\in {\rm T}{\displaystyle \cup C}}x}{}_{ijk}=y{}_{jk}(j\in C,k\in {\rm K})(5)\\ {\displaystyle \sum _{k\in {\rm K}}y}{}_{jk}=1(j\in C)(6)\\ {\displaystyle \sum _{i\in C}D}{}_{j}y{}_{jk}\le Q{}_k(k\in {\rm K})(7)\\ {\displaystyle \sum _{j\in {\rm T}{\displaystyle \cup C}}x}{}_{ijk}={\displaystyle \sum _{j\in {\rm T}{\displaystyle \cup C}}x}{}_{jik}(i\in {\rm T}{\displaystyle \cup C},k\in {\rm K})(8)\\ {\displaystyle \sum _{i\in {\rm T}}{\displaystyle \sum _{j\in C}x}}{}_{ijk}\le 1(k\in {\rm K})(9)\\ {\displaystyle \sum _{j\in C}d}{}_{j}z{}_{ij}\le V{}_{i}w{}_i(i\in {\rm T})(10)\\ {\displaystyle \sum _{h\in {\rm T}{\displaystyle \cup C}}(}x{}_{ihk}+x{}_{hjk})-z{}_{ij}\le 1(i\in {\rm T},j\in C,k\in {\rm K})(11)\\ {\displaystyle \sum _{i\in {\rm T}}z}{}_{ij}=1(j\in C)(12)\\ {\displaystyle \sum _{i\in S}{\displaystyle \sum _{j\in S}x}}{}_{ijk}\le S-1(S\subseteq C,S\ge 2,S={\displaystyle \sum _{j\in S}y}{}_{jk},k\in {\rm K})(13)\\ U{}_{ik}-U{}_{jk}+{\rm N}x{}_{ijk}\le {\rm N}-1(i,j\in S,k\in {\rm K})(14)\\ {\displaystyle \sum _{g\in G}p}{}_{gi}\ge {\displaystyle \sum _{j\in C}D}{}_{j}z{}_{ij}(i\in {\rm T})(15)\\ {\displaystyle \sum _{i\in {\rm T}}p}{}_{gi}\le B{}_g(g\in G)(16)\end{array}$

x_ijk∈{0, 1} (i, j∈T∪C, k∈K) (17)

w_i∈{0, 1} (i∈T) (18)

z_ij∈{0, 1} (i∈T, j∈C) (19)

y_jk∈{0, 1} (i∈C, k∈K) (20)

式中: G为供应商的集合; T为配送中心的集合; C为客户的集合; K为车辆的集合; Q_k为车辆k的最大载质量; S为C的部分集合; C_ij为从点i到点j的距离; B_g为供应商g的最大供应量; V_i为配送中心i的最大货物通过量; D_j为客户j的需求量; H_i为配送中心i的固定费用; L_gi为从供应商g到配送中心i的单位运输费用; F_k为车辆k的固定费用; α为与通过量有关的系数; x_ijk为对于车辆k, 如果点i以后的访问点是点j, 即为1, 否则为0;y_jk为如果点j的货物由车辆k配送, 即为1, 否则为0;w_i为如果使用配送中心i, 即为1, 否则为0;z_ij为如果客户j由配送中心i提供服务, 即为1, 否则为0;p_gi为从供应商g到配送中心i的供应量。其中x_ijk、w_i、y_jk、z_ij和p_gi为决策变量。

2.   问题的求解

为了验证上述数学模型的正确性, 用数理规划商用软件LINGO 8.0对小规模问题进行了数值计算, 结果见表 1。可以看出, 随着问题的规模扩大, 计算时间急剧增加; 当客户达到14个时, 计算时间长达45 h, 显然无法满足解决现实问题的需要。为了满足解决现实问题的需要, 有必要开发出一种能够在合理的时间内求得准最优解的近似算法。

表  1  小规模问题的计算结果

Table  1.  Computation result of small-scaled problem

最优解
问题规模	目标值	运行时间/s
NG=3, NT=3, NC=8	388.5	3
NG=3, NT=3, NC=10	421.2	21
NG=3, NT=3, NC=12	685.0	580
NG=3, NT=3, NC=14	874.1	162 000
注: NG为供应商数量, NT为配送中心数量, NC为客户数量。

下载: 导出CSV 

| 显示表格

传统启发式算法能够在短时间内求得局部最优解, 但往往容易陷于局部最优, 而无法求得全局最优解。智能启发式算法能够求得全局最优解, 但计算时间相对较长。如果能够将两者结合起来, 既可以防止求解过程陷于局部搜索无法跳出, 保证全局解的搜索, 又可以缩短搜索时间, 达到在短时间内求得全局最优解的目的。基于上述考虑, 本文提出了图 1的将传统启发式算法与智能启发式算法相结合的混合算法, 以期在短时间内求得全局最优解^[9]。

图  1  基于SA的混合启发式算法

Figure  1.  Mixed heuristic algorithm based on SA

下载: 全尺寸图片 幻灯片

3.   计算分析

为了对SA的参数进行设定, 进行了预备实验, 并确定参数如下: 初始温度T₀为200, 冷却率α为0.7, 与温度相关的循环次数调整参数β为1.1, 最大循环次数将按照问题规模的大小做适当的设定, 数据采用人工生成数据, 在200 km×200 km的区域内随机生成指定个数的供应商、配送中心和客户, 并生成距离矩阵和客户需求量; 采用C语言编程, 计算结果见表 2。从表 2中的结果比较可以看出, 本算法求得的近似解与LINGO 8.0计算的最优解之间的误差很小, 但计算时间却大大缩短了。依据结果虽然无法判定所提出的混合启发式算法对于大规模问题的有效性, 但可以看出, 对于求解小规模问题是有效和良好的。对于大规模问题, 将利用实例进行计算验证。

表  2  最优解与近似解比较

Table  2.  Comparison of optimal solution and approximate solution

问题规模	最优解		近似解		误差/%
	目标值	运行时间/s	目标值	运行时间/s
NG=3, NT=3, NC=8	388.5	3	396.5	< 1	2.1
NG=3, NT=3, NC=10	421.2	21	421.2	< 1	0.0
NG=3, NT=3, NC=12	685.0	580	692.0	< 1	1.0
NG=3, NT=3, NC=14	874.1	162 000	889.5	< 1	2.1

下载: 导出CSV 

| 显示表格

4.   应用实例

在应用实例中, 将港口作为供应商来考虑, 以进口货物从港口经配送中心配送到客户过程中发生的费用最小化为目的, 以港口的数量和位置、配送中心数量和位置作为对象进行优化。实例的区域选择山东省, 候选港口为天津港、烟台港、威海港、青岛港、日照港和连云港等6处, 候选配送中心设置于山东省除港口城市以外的13个地级市, 设定客户分别位于90个县(包括县级市)。为了分析候选港口和配送中心的数量及位置与目标值之间的关系, 在计算过程中, 候选港口和配送中心的数量分别从1开始增加(港口的位置为随机选择), 计算结果见图 2、3。

图  2  港口数量与目标函数值关系

Figure  2.  Relation of object value and ports number

下载: 全尺寸图片 幻灯片

图  3  配送中心数量与目标函数值关系

Figure  3.  Relation of object value and changing depots number

下载: 全尺寸图片 幻灯片

可以看出, 随着候选港口数量的增加, 目标值呈下降趋势, 说明可供选择的港口越多, 求得最优解的机会越大, 但本例中, 当候选港口的数量增加到5个时, 目标值达到最小(实际被选中的港口为3个); 候选配送中心数量的变化也呈相同的趋势, 当候选配送中心数量达到9个时, 目标值达到最小(实际被选中的配送中心为8个); 本实例的计算时间都在8 s以内, 虽然无法判断所求解为最优解, 但从计算结果来看, 基本接近最优, 因此可以认为本算法对于求解大规模问题也是有效和良好的。

5.   结语

本文将研究范围界定在商品从供应商到配送中心, 再从配送中心到客户这一典型的物流过程, 涉及运输与配送2个阶段和供应商、配送中心和客户3个层次, 提出了多供应商、多物流中心情况下的物流路径与配送路径优化问题, 给出了问题的数学模型, 利用传统启发式算法与模拟退火法开发了混合近似解法, 通过人工生成数据和实例计算验证, 可以看出所提出的数学模型可以准确地描述此类问题, 具有良好的适应性, 所提出的混合近似解法能够在短时间内求解问题, 并得到接近于最优解的近似解, 具有较高的实用价值。但本模型没有考虑库存问题与供应商的成本问题, 无法达到物流网络中各个环节的整体优化, 有待于今后进一步研究。