董丽薇(1981-), 女, 讲师, 博士生, 从事供应链管理的研究, E-mail:
黄敏(1968-), 女, 教授, 博士生导师, 从事企业物流与供应链管理、现代集成制造系统等研究, E-mail:
匡韩斌(1984-), 男, 讲师, 博士, 从事冲突分析方法的理论及其在水资源和环境领域的应用、物流与供应链等研究, E-mail:
王兴伟(1968-), 男, 教授, 博士生导师, 从事下一代互联网、自组织网络等研究, E-mail:
最后一公里分销网络可以帮助企业达成高响应性的供应链管理目标, 集成最后一公里四方物流网络设计问题成为网络设计的一个重要研究方向.解决该问题需要对分销中心的位置, 三方物流的选择、分配以及其车辆路径规划进行决策.在满足车辆路径规划、流守恒等约束条件下, 以最小化网络构建费用为目标建立混合整数规划模型.由于该问题的NP-难特性, 可将该问题分解成两个子问题并设计两阶段启发式算法, 通过迭代算法解决两个子问题.在数值实验中, 将启发式算法分别与CPLEX和粒子群优化算法求出的解进行比较, 实验结果验证了启发式算法的有效性; 同时, 将提出的启发式算法成功地应用到实际规模的问题中, 表明所提出的算法能够为解决集成最后一公里四方物流网络设计问题提供有效的工具.
A distributor storage network with last-mile delivery can be used to achieve the supply chain management objective of high responsiveness. The fourth party logistics network design problem with last-mile delivery is an important research in the network design problem, which needs to be solved by simultaneously making decisions on issues of the distribution center location, the selection, allocation and routing programming of the third party logistics. A mix-integer programming model is established to minimize the total system cost with satisfying the constraints of vehicle routing programming and flow conservation and so on. Because the problem is NP-hard, this paper presents a two-phase heuristic algorithm for the fourth party logistics network design problem with last-mile delivery by dividing the problem into two subproblems. The algorithm solves the subproblems in an iterative manner. In the numerical tests, by comparing with the solutions calculated by the CPLEX and the particle swarm optimization algorithm, the heuristic algorithm outperforms the other two algorithms, which illustrates that the heuristic algorithm can provide an efficient solution to the fourth party logistics network design problem with last-mile delivery; meanwhile, the heuristic algorithm is successfully applied in the experiment of practical scale, which also shows that it can offer an effective tool in the field.
当今, 越来越多的第三方物流(3PL)参与到物流的传递中[
Perl等[
4PL-LRP可以描述为产品从供应点通过3PL以满载的形式运送到各分销中心, 3PL再按一定的路径将产品交付到用户手中, 4PL通常要对分销中心的位置和3PL的选择进行决策(主问题), 同时要解决从供应点到分销中心的3PL分配问题和从分销中心到用户的3PL路径规划问题(子问题).
一个四方物流网络可以用一个有向多重图
4PL网络
决策主要考虑潜在分销中心和3PL的选择, 从制造商到分销中心3PL的市场流量分配, 从分销中心到用户的3PL路径规划. 4PL的决策目标是最小化最后一公里分销网络设计的总费用, 包括分销中心和三方物流的固定费用, 分销中心的产品存储费用, 制造商到分销中心的3PL运输费用, 以及分销中心到用户的3PL车辆路径运输费用.
4PL-LRP需要在实现车辆路径规划的基础上同时考虑不同的3PL合作费用和单位距离运输费用, 这为建模带来一定的挑战.为了建模和求解的方便, 本文假设每个用户都可被任意的3PL服务, 且每个用户只能被某个3PL的一辆车服务, 即每个用户只能出现在一条3PL的车辆路径上.因为本文是根据文献[
根据文献[
目标函数(1)最小化总的费用, 包括分销中心的固定费用, 3PL在分销中心的固定费用, 分销中心的存储费用, 制造商到分销中心的3PL运输费用和分销中心到用户的3PL车辆运输费用.约束(2)确保每个用户都要被服务, 且只能被某个3PL的一辆车服务.约束(3)是3PL车辆的能力限制约束.约束(4)确保从某个制造商到某个分销中心运输的量不超过选中3PL的运输能力.约束(5)确保3PL的车辆路径上必须包含一个分销中心.约束(6)是点守恒约束.约束(7)是3PL的车辆路径上仅有一个被选中的分销中心.约束(8)是流守恒约束.约束(9)是分销中心的能力约束.约束(10)确保3PL的车辆路径包含用户
LRP本身是NP难问题, 4PL-LRP在LRP的基础上还要完成3PL的分配, 路径规划以及选择, 其算法的设计就更加具有挑战性, 本文根据提出的问题模型设计了启发式算法, 完成了实际规模问题的求解.
本文根据4PL-LRP的定义将问题划分为两个子问题设计二阶段启发式算法, 子问题的分解如下.
阶段1: 3PL车辆路径问题;
阶段2: 4PL选址-分配问题.
二阶段启发式算法在解决两个子问题的同时考虑子问题之间的内在关系, 通过对两个子问题的迭代求解, 使得两个子问题之间的内在联系在算法中得以体现.在3PL车辆路径子问题中, 因其主要求的是3PL的路径, 所以根据Hansen等[
在本节首先根据子问题的描述, 给出两个子问题的数学模型; 然后通过广义节约方法设计3PL车辆路径, 在解4PL选址-分配问题时采用CPLEX进行求解; 最后给出求解4PL-LRP的启发式算法.
根据3PL车辆路径问题描述建立线性规划模型, 模型中涉及的集合, 参数和决策变量同4PL-LRP模型中的一样, 建立的3PL车辆路径问题模型为
模型的约束条件为4PL-LRP的部分约束条件, 目标函数是使得3PL的车辆路径费用最小化.从模型可以看出4PL-LRP的可行解中3PL车辆路径的解是3PL车辆路径分配问题的可行解, 同时3PL车辆路径问题最优解为4PL-LRP解中的3PL路径费用提供了下界.因此3PL车辆路径问题可以为4PL-LRP提供路径的初始解.
根据4PL选址-分配问题描述建立线性规划模型, 模型中涉及的集合、参数和决策变量除了4PL-LRP定义的以外, 作如下增加: 集合
根据上述变量和参数, 建立4PL选址-分配模型
目标函数(19)为最小化总费用, 包括分销中心的固定费用, 3PL在分销中心的固定费用, 分销中心的存储费用, 制造商到分销中心的运输费用和分销中心到路径的3PL车辆运输费用.约束(20)确保每条路径都要被服务, 且只能被一个3PL服务.约束(21)是3PL车辆的能力限制约束.约束(22)是流守恒约束.约束(23)确保如果路径
证明两个模型目标函数等价, 需要证明两个模型中3PL的车辆路径运输费用
4PL-LRP的3PL车辆路径运输费用可写成
由4PL-LRP的约束(5)和(7)可知, 3PL的车辆路径上只允许有一个分销中心并且必须有一个分销中心, 因此有
路径上和分销中心相连接的点仅仅是用户路径的起点和终点, 因此有
其中
根据之前对符号集合的定义, 式(26)可以被重新写成如下形式:
根据4PL选址-分配模型中对决策变量
因此式(27)可写成
根据假设, 3PL
根据干线距离的解释, 式(29)和4PL选址-分配模型目标函数中
显而易见, 当路径已知时, 4PL选址-分配模型的可行解对4PL-LRP是可行的, 反之亦然.
定理1说明了二阶段启发式算法的有效性, 即对两个子问题分别进行求解, 再将各自的解作为输入条件进行迭代, 4PL-LRP可以得到相对有效的解.
3PL车辆路径问题是车辆路径问题的广义, 因此是NP难问题.本节将提出一个启发式算法用于解决3PL车辆路径问题.算法首先设定初始的3PL车辆路径, 再对路径进行改进.本文初始路径的产生源于perl提出的广义节约方法(MGSAV)[
根据路径费用最小化的目标函数, 希望选择加入已知路径的用户满足两个条件: 1) 此用户重新开辟一条新路径的花费越大越好; 2) 用户加入到已有路径
其中:
其次要解决加入到哪两个点之间, 假设
式(31)表示加入到
由式(30)和(31)可得出, 在已知路径
需要决策用户
根据本文给定的改进的广义节约公式, 应用Perl提出的初始化路径的方法[
在完成了3PL路径的初始化后, 首先对每一条路径进行用户顺序和连接分销中心的调整, 本文采用lin等[
由定理1可知, 当路径给定时, 4PL-LRP和4PL选址-分配问题的模型是等价的, 因此当利用3PL车辆路径问题启发式算法求解出相关路径时, 可以通过CPLEX对4PL选址-分配模型进行求解. 3PL车辆路径解出的路径只是为4PL-LRP提供一个下界, 分销中心和3PL的选择也会影响路径的分配; 因此, 在选择出分销中心和3PL后还要返回到3PL车辆路径子问题中, 调整3PL车辆路径子问题中的
4PL-LRP启发式算法流程
本节通过与CPLEX解的精确解以及基于PSO智能优化算法的比较, 评估第2节提出的启发式算法的有效性.测试的数据集合根据对京东物流的规模调研结果均匀随机产生.京东物流目前构建的是经典的最后一公里分销网络, 京东在北京地区各区域的分销中心从2个到25个不等, 其最终用户是各个小区的代收站. 基于调研结果, 本文设潜在分销中心的个数
本文的模型是线性规划模型, 因此可以用优化软件CPLEX求出最优解, 但本文模型中约束(5)的个数超过了
启发式和CPLEX比较结果
测试案例 | 启发式 | CPLEX | Gap |
|||
目标值 | 时间 |
目标值 | 时间 |
|||
1-2-4-3 | 18 737 | 0.05 | 18 737 | 1.39 | 0 | |
1-2-4-5 | 12 733 | 0.08 | 12 733 | 1.48 | 0 | |
1-2-5-3 | 19 032 | 0.06 | 19 030 | 9.00 | 0 | |
1-2-5-5 | 20 214 | 0.06 | 20 214 | 15.54 | 0 | |
1-3-5-4 | 23 056 | 0.06 | 23 056 | 9.67 | 0 | |
1-3-5-5 | 17 400 | 0.09 | 17 400 | 56.94 | 0 | |
1-3-6-4 | 22 560 | 0.09 | 22 560 | 478.83 | 0 | |
1-3-6-5 | 20 406 | 0.09 | 20 406 | 2 469.51 | 0 | |
1-4-7-4 | 26 545 | 0.16 | 26 545 | 1 251.53 | 0 | |
1-4-7-5 | 19 164 | 0.05 | 19 164 | 806.13 | 0 | |
5-10-50-8 | 63 712 | 16.35 | 152 213 | 28 780 | ||
8-25-75-8 | 1 218 262 | 91.99 | ||||
8-30-100-8 | 171 070 | 102.29 | ||||
8-40-130-8 | 227 692 | 99.97 | ||||
10-18-57-6 | 98 226 | 29.72 | 600 362 | 33 186.6 | ||
10-50-160-7 | 341 237 | 154.83 | ||||
10-50-170-7 | 253 077 | 141.96 |
启发式与PSO比较结果
测试案例 | 启发式 | CPLEX | Gap |
|||
目标值 | 时间 |
目标值 | 时间 |
|||
5-10-50-8 | 63 712 | 16.35 | 79 983 | 10.05 | ||
8-25-75-8 | 121 826 | 91.99 | 161 922 | 29.23 | ||
8-30-100-8 | 171 070 | 102.29 | 178 014 | 43.7 | ||
8-40-130-8 | 227 692 | 99.97 | 259 189 | 64.68 | ||
10-18-57-6 | 98 226 | 29.72 | 101 997 | 19.51 | ||
10-50-160-7 | 341 237 | 154.83 | 420 095 | 131.51 | ||
10-50-170-7 | 253 077 | 141.96 | 385 822 | 107.67 |
丰台区网络设计方案
本文根据京东在北京市丰台区大致的分销中心位置, 随机生成50个用户点, 其距离根据欧几里德度量.对最后一公里分销网络进行设计, 给出最后一公里分销中心的选址和3PL路径规划方案, 如图 6所示.其中DC表示分销中心, 根据设计方案, 分销中心DC1、DC2、DC5被选择, 在这些分销中心中都选中了3PL4为用户服务.
最后一公里分销网络在各种分销网络的设计方案中具有响应时间快、用户体验好等优势, 如何更好地完成集成最后一公里网络的4PL网络设计问题在当今变得越来越重要. 4PL-LRP的模型可以很好地完成网络设计中分销中心的选址和3PL的选择及3PL的车辆路径规划.本文首先根据4PL-LRP的模型特点, 将模型分为3PL车辆路径模型和4PL选址-分配模型, 并证明模型分解后的求解对原模型求解的有效性, 通过顺序地求解两个子模型完成4PL-LRP模型中决策变量的求解.本文通过启发式算法, CPLEX和PSO算法分别对问题进行求解, 分析了启发式算法的有效性, 并将启发式算法应用到实际规模问题上, 说明启发式算法的实用性.本文提出的启发式算法为解决集成最后一公里4PL网络设计问题提供了有效的工具.本文应用4PL-LRP的模型只考虑了确定的情景, 而在4PL网络设计中不确定性对网络的设计也会产生重要的影响, 在今后的研究中可以考虑需求不确定下4PL最后一公里分销网络设计问题.
责任编委: 孙艺红.
Huang M, Ren L, Lee L H, et al. 4PL routing optimization under emergency conditions[J]. Knowledge-Based Systems, 2015, 89: 126-133.
Huang M, Tu J, Chao X L, et al. Quality risk in logistics outsourcing: A fourth party logistics perspective[J]. European Journal of Operational Research, 2019, 276(3): 855-879.
Gattorna J. Strategic supply chain alignment: best practice in supply chain management[M]. London: Gower Publishing, 1998: 425-445.
李锐, 黄敏, 王兴伟. 基于混合概率解发掘算法的第四方物流弹复性网络设计[J]. 控制与决策, 2013, 28(10): 1536-1540.
Li R, Huang M, Wang X W. Resilient network design for fourth-party logistics based on hybrid probability solution discovery algorithm[J]. Control and Decision, 2013, 28(10): 1536-1540.
Li J, Liu Y Q, Hu Z J. Routing optimization of fourth party logistics with reliability constraints based on Messy GA[J]. Journal of Industrial Engineering and Management, 2014, 7(5): 1097-1111.
Rohaninejad M, Sahraeian R, Tavakkoli-Moghaddam R. Multi-echelon supply chain design considering unreliable facilities with facility hardening possibility[J]. Applied Mathematical Modelling, 2018, 62: 321-337.
Chopra S. Designing the distribution network in a supply chain[J]. Transportation Research Part E: Logistics and Transportation Review, 2003, 39(2): 123-140.
Perl J, Daskin M S. A warehouse location-routing problem[J]. Transportation Research Part B: Methodological, 1985, 19(5): 381-396.
Xie W J, Ouyang Y F, Wong S C. Reliable location-routing design under probabilistic facility disruptions[J]. Transportation Science, 2016, 50(3): 1128-1138.
Zheng X J, Yin M X, Zhang Y X. Integrated optimization of location, inventory and routing in supply chain network design[J]. Transportation Research Part B: Methodological, 2019, 121: 1-20.
Capelle T, Cortés C E, Gendreau M, et al. A column generation approach for location-routing problems with pickup and delivery[J]. European Journal of Operational Research, 2019, 272(1): 121-131.
Hansen P H, Hegedahl B, Hjortkjær S, et al. A heuristic solution to the warehouse location-routing problem[J]. European Journal of Operational Research, 1994, 76(1): 111-127.
Dong L W, Kuang H B, Huang M. Fourth party logistics location-routing problem[C]. 2018 Chinese Control and Decision Conference (CCDC). Shenyang, 2018: 1187-1191.
Perl J. The multi-depot routing allocation problem[J]. American Journal of Mathematical and Management Sciences, 1987, 7(1/2): 7-34.
Lin S, Kernighan B W. An effective heuristic algorithm for the traveling-salesman problem[J]. Operations Research, 1973, 21(2): 498-516.