Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2023, Vol. 57 Issue (5): 900-910    DOI: 10.3785/j.issn.1008-973X.2023.05.006
计算机技术与控制工程     
末端配送服务模式与路径联合优化
杨京帅(),杨玉娥,李嫚嫚*(),李园园
长安大学 汽车学院，陕西 西安 710021
Joint optimization of terminal distribution service mode and distribution routing
Jing-shuai YANG(),Yu-e YANG,Man-man LI*(),Yuan-yuan LI
School of Automobile, Chang’an University, Xi’an 710021, China
 全文: PDF(1285 KB)   HTML
摘要：

考虑末端配送服务模式对服务质量和配送成本的影响，提供一种末端配送服务模式与路径联合优化方法. 以配送成本和客户满意度为双目标建立混合整数规划模型，改进NSGA-Ⅱ求解模型，并且利用GUROBI求解器验证所建模型的有效性. 通过求解不同规模算例发现，改进NSGA-Ⅱ具有求解稳定性，并且仅用GUROBI求解时间的1/10便能够得到高质量Pareto解集，与传统NSGA-Ⅱ相比，改进NSGA-Ⅱ求解时间平均仅增加23 s，求解质量平均提升3.37%，表明改进NSGA-Ⅱ优于GUROBI求解器和传统NSGA-Ⅱ. 通过敏感度分析发现，与仅利用单一末端配送服务模式相比，物流企业综合利用多种末端配送服务模式能够更好地平衡配送成本与客户满意度水平，合理增加自提柜和自提点数量，拓宽客户收货时间窗宽度有助于降低配送成本.
关键词： 物流工程;  末端配送服务模式;  配送路径;  混合整数规划模型;  NSGA-Ⅱ    
Abstract:

Considering the effect of terminal distribution service mode on service quality and distribution cost, a mixed integer programming model was established with the bi-objectives of distribution cost and customer satisfaction, and NSGA-Ⅱ was improved to solve the model. The validity of the model was verified by the solver GUROBI. The performance of improved NSGA-Ⅱ solution was proved to be stable by solving several cases. The improved NSGA-Ⅱ could obtain high-quality Pareto solution sets with only 1/10 of the computation time of GUROBI. Compared with the traditional NSGA-Ⅱ, the computation time only increased 23 s on average, while the quality of solutions improved 3.37% on average. The improved NSGA-Ⅱ was superior to the GUROBI solver and the traditional NSGA-Ⅱ. The sensitivity analysis shows that the comprehensive utilization of multiple distribution modes is better than the single distribution mode in balancing profit and customers’ satisfaction levels. The distribution cost can be reduced by reasonably increasing the number of parcel lockers and pick-up points and widening customers’ time windows.
Key words: logistics engineering    terminal distribution service mode    distribution routing    mixed integer programming model    NSGA-II
收稿日期: 2022-11-07 出版日期: 2023-05-09
CLC:  U 9  
基金资助: 长安大学中央高校基本科研业务费专项资金资助项目 (300102222105)
通讯作者: 李嫚嫚     E-mail: jshyang@chd.edu.cn;limanman@chd.edu.cn
作者简介: 杨京帅（1978—），男，教授，从事物流工程与管理研究. orcid.org/ 0000-0002-5702-7904. E-mail: jshyang@chd.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
杨京帅
杨玉娥
李嫚嫚
李园园

引用本文:

杨京帅,杨玉娥,李嫚嫚,李园园. 末端配送服务模式与路径联合优化[J]. 浙江大学学报(工学版), 2023, 57(5): 900-910.

Jing-shuai YANG,Yu-e YANG,Man-man LI,Yuan-yuan LI. Joint optimization of terminal distribution service mode and distribution routing. Journal of ZheJiang University (Engineering Science), 2023, 57(5): 900-910.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2023.05.006    或    https://www.zjujournals.com/eng/CN/Y2023/V57/I5/900

图 1  末端配送服务模式与路径联合优化问题示意图
末端配送服务模式 送货上门 自提柜 自提点
服务形式 车辆配送 客户自取 客户自取
收货地点 客户所在地 自提货柜 超市、商铺等
服务成本 高 中 低
货物类型限制 无 有 无
取货时间限制 客户时间窗 无 营业时间
客户满意度 高 较高 低
表 1  不同末端配送服务模式对比
集合 含义
${\boldsymbol{O}}$ 配送中心集合， ${\boldsymbol{O}} = \left\{ 0 \right\}$
$ {{\boldsymbol{N}}_{\text{c}}} $ 客户点集合， ${N_{\rm{c} } } = \left\{ {1,2,3,\cdots,\left. n \right\} } \right.$
$N$ 节点集合， $N = O \cup {N_{\rm{c}}}$
$M$ 末端配送服务模式集合， $M = \left\{ {1,2,3} \right\}$.1为送货上门模式，2为自提柜模式，3为自提点模式
$K$ 配送车辆集合, $K = \left\{ {1,2,3,\cdots,} \right.\left. k \right\}$
参数 含义
${d}_{i,j}^{m,{m}^{\prime } }$ 当客户 $i$采用 $m$末端配送服务模式，客户 $j$采用 $m'$末端配送服务模式时，车辆从客户 $i$到客户 $j$的距离
${v_{\text{c}}}$ 车辆行驶速度
${t}_{ i,j}^{m,{m}^{\prime } }$ 客户 $i$采用 $m$末端配送服务模式，客户 $j$采用 $m'$末端配送服务模式时，车辆从客户 $i$到客户 $j$的时间
${q_i}$ 客户 $i$的需求量
$\beta _i^m$ 如果客户 $i$接受 $m$末端配送服务模式，则 $\beta _i^m = 1$；否则 $\beta _i^m = 0$
${\theta _{ {\text{1} } } }$ 时间窗早到惩罚成本
${\theta _{ {\text{2} } } }$ 时间窗晚到惩罚成本
$Q$ 车辆的额定载重量
$ [{E}_{\text{ }i} ,{L}_{\text{ }i}] $ 客户点 $i$的服务时间窗要求
${c_{\text{d}}}$ 单位里程的车辆行驶成本
${c_{\text{v}}}$ 车辆的固定使用成本，包括折旧和驾驶员工资
${c_m}$ $m$末端配送服务模式下的单位需求量服务成本，m=(1,2,3)
${S _m}$ $m$末端配送服务模式下的客户满意度， ${S_m} = 1.0、0.8、0.7$分别为送货上门、自提柜、自提点模式下的客户满意度
$U$ 无穷大的数
决策变量 含义
$x_i^{m,k}$ 当客户 $i$由车辆 $k$采用 $m$末端配送服务模式时为1；否则为0
$ {y}_{ i,j}^{m,{m}^{\prime }} $ 当客户 $i$采用 $m$末端配送服务模式，客户 $j$采用 $m'$末端配送服务模式，车辆从客户 $i$到客户 $j$时为1；否则为0
${t_i}$ 车辆到达节点 $i$的时间
${\delta _i}$ 车辆离开节点 $i$时已派送的货物量
表 2  所提模型定义的符号及含义
图 2  改进NSGA-Ⅱ的流程
图 3  改进NSGA-Ⅱ的染色体编码
图 4  Pareto前沿示意图
图 5  染色体i拥挤度
图 6  改进NSGA-Ⅱ的多点交叉算子
图 7  改进NSGA-Ⅱ的POCSX交叉算子
图 8  改进NSGA-Ⅱ的反转变异算子
参数 取值 参数 取值
${v_{\text{c}}}$/（km·h?1） 60 ${\theta _1}$/（元·h?1） 1.00
$Q$ 200 ${\theta _2}$/（元·h?1） 3.00
${c_{\text{d}}}$/（元·km?1） 1 ${c_1}$/元 2.18
${c_{\text{v}}}$/元 100 ${c_2}$/元 1.71
${\rm{C}}{{\rm{S}}_{\min } }$ 0.7 ${c_3}$/元 1.38
表 3  算例参数及取值
配送路径 约束检验
末端配送服务模式 车辆载重 时间窗
选择模式 是否为接受模式 累计载重 是否超载 到达时间/min 客户收货时间窗
1 1 是 0 否 0 [0,1 236]
↓
6 2 是 2 否 38.42 [15,67]
↓
3 2 是 22 否 48.42 [825,870]
↓
4 3 是 30 否 77.39 [65,146]
↓
5 3 是 49 否 87.39 [727,782]
↓
2 1 是 72 否 105.88 [912,967]
↓
1 1 是 72 否 119.30 [0,1 236]
表 4  GUROBI对小规模算例的求解结果
算例规模 ${C_1}$/元 ${C_2}$/元 ${\rm{Gap}}$/%
5 328.14 331.32 0.97
10 427.52 433.09 1.30
15 691.35 702.68 1.64
20 864.72 875.12 1.20
25 1 139.30 1 157.45 1.59
30 1 401.65 1 423.59 1.57
35 1 549.90 1 566.23 1.05
40 1 908.04 1 924.35 0.85
60 2 768.94 2 797.44 1.03
80 3 605.01 3 652.57 1.32
100 4 712.09 4 759.59 1.01
表 5  改进NSGA-Ⅱ算法稳定性分析
客户规模 GUROBI 传统NSGA-Ⅱ 改进NSGA-Ⅱ
${C_4}$/元 ${t_1}$/s ${C_{\text{3}}}$/元 ${t_2}$/s $ {\rm{Ga}}{{\rm{p}}_1} $/% ${C_1}$/元 ${t_1}$/s $ {\rm{Ga}}{{\rm{p}}_2} $/%
注：表中加粗数据为最优配送总成本.
5 328.14 0.62 328.14 7.84 0.00 328.14 7.95 0.00
8 379.81 13.61 379.81 8.24 0.00 379.81 8.10 0.00
10 427.52 1 907 427.52 7.04 0.00 427.52 11.17 0.00
12 485.95 2 000 486.84 19.25 0.18 486.45 13.84 0.10
15 691.84 2 000 693.03 11.78 0.17 691.35 15.45 ?0.07
18 778.49 2 000 853.26 23.61 9.60 777.19 17.21 ?0.17
20 862.31 2 000 867.34 21.92 0.58 864.72 32.60 0.28
22 1 041.16 2 000 1 098.32 25.14 5.49 1 041.16 32.00 0.00
25 1 141.36 2 000 1 192.04 64.77 4.44 1 139.30 75.75 ?0.18
28 1 374.71 2 000 1 398.04 31.52 1.70 1 378.31 47.96 0.26
30 1 400.46 2 000 1 424.48 47.63 1.72 1 401.65 91.76 0.09
32 1 438.93 2 000 1 481.33 72.40 2.95 1 432.38 97.74 ?0.46
35 1 568.04 2 000 1 658.35 81.48 5.76 1 549.90 91.25 ?1.16
40 ? ? 1 933.94 103.15 ? 1 908.04 144.67 ?
60 ? ? 2 857.98 114.22 ? 2 768.94 198.44 ?
80 ? ? 3 812.10 171.75 ? 3 605.01 252.70 ?
100 ? ? 4 922.93 230.35 ? 4 712.09 292.69 ?
表 6  三种算法求解末端配送服务模式与路径联合优化模型的性能
图 9  60个客户案例求解到的Pareto前沿
算例规模 模式 目标
C/元 S
30 送货上门 1 768.64 0.87
自提柜 1 398.08 0.65
自提点 1 205.29 0.54
混合模式 1 401.65 0.79
40 送货上门 2 386.60 0.90
自提柜 1 890.74 0.66
自提点 1 616.21 0.54
混合模式 1 908.04 0.81
60 送货上门 3 570.58 0.88
自提柜 2 720.96 0.65
自提点 2 297.28 0.54
混合模式 2 768.94 0.80
80 送货上门 4 581.11 0.87
自提柜 3 454.38 0.65
自提点 3 004.65 0.55
混合模式 3 605.01 0.80
100 送货上门 5 767.31 0.86
自提柜 4 352.84 0.65
自提点 3 969.52 0.55
混合模式 4 712.09 0.81
表 7  不同末端配送服务模式的配送总成本与客户满意度
配送方案 对比值
C/元 Ct/元 Cf/元 Cs/元 Cw/元
7个自提柜+5个自提点 4 712.09 927.08 800.00 2 462.59 522.42
10个自提柜+8个自提点 4 596.15 816.94 800.00 2 450.18 529.03
表 8  不同自提柜和自提点数量下成本最低的配送方案
图 10  不同时间窗宽度倍数下的最低配送成本
原时间窗宽度 对比值
C/元 Ct/元 Cf/元 Cs/元 Cw/元
0.8倍原时间窗宽度 4 725.60 943.43 800.00 2 424.22 557.95
2.0倍原时间窗宽度 4 592.54 945.67 800.00 2 414.25 432.62
表 9  不同时间窗宽度倍数下的配送方案
15 周翔, 许茂增, 吕奇光, 等 基于客户点行政地址的自提点选址—路径优化[J]. 计算机集成制造系统, 2019, 25 (8): 2069- 2078
ZHOU Xiang, XU Mao-zeng, LV Qi-guang, et al Location-routing problem of pickup point based on administrative address of customer points[J]. Computer Integrated Manufacturing Systems, 2019, 25 (8): 2069- 2078
doi: 10.13196/j.cims.2019.08.021
16 邱晗光, 李海南, 宋寒 需求依赖末端交付与时间窗的城市配送自提柜选址—路径问题[J]. 计算机集成制造系统, 2018, 24 (10): 2612- 2621
QIU Han-guang, LI Hai-nan, SONG Han Reception box locating-vehicle routing problems in urban distribution considering demand depending on last-mile delivery and time slots[J]. Computer Integrated Manufacturing Systems, 2018, 24 (10): 2612- 2621
17 戴海燕. 基于随机选择行为的“最后一公里”配送自提点选址与路径规划研究[D]. 上海: 同济大学, 2019: 48-53.
DAI Hai-yan. Research on location and path planning of “last mile” distribution pick-up point based on random selection behavior [D]. Shanghai: Tongji University, 2019: 48-53.
18 TILK C, OLKIS K, IRNICH S The last-mile vehicle routing problem with delivery options[J]. OR Spectrum, 2021, 43 (4): 877- 904
doi: 10.1007/s00291-021-00633-0
19 SUWATCHARACHAITIWONG S, LIN C C, HUANG W, et al On the medication distribution system for home health care through convenience stores, lockers, and home delivery[J]. Health Informatics Journal, 2020, 26 (4): 3163- 3183
doi: 10.1177/1460458220936395
20 熊国文, 张敏, 许文鑫 基于众包模式的两级开闭混合车辆路径优化[J]. 浙江大学学报:工学版, 2021, 55 (12): 2397- 2408
XIONG Guo-wen, ZHANG Min, XU Wen-xin Vehicle routing optimization of two echelon opening and closing hybrid based on crowdsourcing mode[J]. Journal of Zhejiang University: Engineering Science, 2021, 55 (12): 2397- 2408
21 MURUGAN P, KANNAN S, BASKAR S NSGA-II algorithm for multi-objective generation expansion planning problem[J]. Electric Power Systems Research, 2009, 79 (4): 622- 628
doi: 10.1016/j.jpgr.2008.09.011
22 RABBANI M, HEIDARI R, YAZDANPARAST R A stochastic multi-period industrial hazardous waste location-routing problem: integrating NSGA-II and Monte Carlo simulation[J]. European Journal of Operational Research, 2019, 272 (3): 945- 961
doi: 10.1016/j.ejor.2018.07.024
1 BERGMANN F M, WAGNER S M, WINKENBACH M Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution[J]. Transportation Research Part B: Methodological, 2020, 131: 26- 62
doi: 10.1016/j.trb.2019.09.013
2 RANIERI L, DIGIESI S, SILVESTRI B, et al A review of last mile logistics innovations in an externalities cost reduction vision[J]. Sustainability, 2018, 10 (3): 1- 18
3 MILIOTI C, PRAMATARI K, ZAMPOU E Choice of prevailing delivery methods in e-grocery: a stated preference ranking experiment[J]. International Journal of Retail and Distribution Management, 2020, 49 (2): 281- 298
doi: 10.1108/IJRDM-08-2019-0260
4 IWAN S, KIJEWSKA K, LEMKE J Analysis of parcel lockers’ efficiency as the last mile delivery solution the results of the research in Poland[J]. Transportation Research Procedia, 2016, 12: 644- 655
doi: 10.1016/j.trpro.2016.02.018
5 KEDIA A, KUSUMASTUTI D, NICHOLSON A Acceptability of collection and delivery points from consumers’ perspective: a qualitative case study of Christchurch city[J]. Case Studies on Transport Policy, 2017, 5 (4): 587- 595
doi: 10.1016/j.cstp.2017.10.009
6 SONG L, CHERRETT T, MCLEOD F, et al Addressing the last mile problem: transport impacts of collection and delivery points[J]. Transportation Research Record, 2009, 2097 (1): 9- 18
doi: 10.3141/2097-02
7 ORENSTEIN I, RAVIV T, SADAN E Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis[J]. EURO Journal on Transportation and Logistics, 2019, 8 (5): 683- 711
doi: 10.1007/s13676-019-00144-7
8 GRABENSCHWEIGER J, DOERNER K F, HARTL R F, et al The vehicle routing problem with heterogeneous locker boxes[J]. Central European Journal of Operations Research, 2021, 29 (3): 113- 142
9 SITEK P, WIKAREK J Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): model and implementation using hybrid approach[J]. Annals of Operations Research, 2019, 273 (1): 257- 277
10 DU Y, FU S, LU C, et al Simultaneous pickup and delivery traveling salesman problem considering the express lockers using attention route planning network[J]. Computational Intelligence and Neuroscience, 2021, 2021: 1- 18
11 YU V F, SUSANTO H, YEH Y H, et al The vehicle routing problem with simultaneous pickup and delivery and parcel lockers[J]. Mathematics, 2022, 10 (6): 920- 941
doi: 10.3390/math10060920
12 ENTHOVEN D L J U, JARGALSAIKHAN B, ROODBERGEN K J, et al The two-echelon vehicle routing problem with covering options: city logistics with cargo bikes and parcel lockers[J]. Computers and Operations Research, 2020, 118: 1- 17
13 REDI A A N P, JEWPANYA P, KURNIAWAN A C, et al A simulated annealing algorithm for solving two-echelon vehicle routing problem with locker facilities[J]. Algorithms, 2020, 13 (9): 218- 231
doi: 10.3390/a13090218
14 ZHOU L, BALDACCI R, VIGO D, et al A multi-depot two echelon vehicle routing problem with delivery options arising in the last mile distribution[J]. European Journal of Operational Research, 2018, 265 (2): 765- 778
doi: 10.1016/j.ejor.2017.08.011
23 PIERRE D M, ZAKARIA N Stochastic partially optimized cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows[J]. Applied Soft Computing, 2016, 52: 863- 872
24 MORGANTI E, DABLANC L, FORTIN F Final deliveries for online shopping: the deployment of pickup point networks in urban and suburban areas[J]. Research in Transportation Business and Management, 2014, 11: 23- 31
doi: 10.1016/j.rtbm.2014.03.002
25 YUEN K F, WANG X, NG L T W, et al An investigation of customers’ intention to use self-collection services for last-mile delivery[J]. Transport Policy, 2018, 66: 1- 8
doi: 10.1016/j.tranpol.2018.03.001
26 杨海兰. 考虑客户价值的冷链物流多目标LRPTW问题优化研究[D]. 西安: 长安大学, 2018: 70-71.
YANG Hai-lan. Optimization of cold chain logistics multi-objective LRPTW problem considering customer value[D]. Xi’an: Chang’an University, 2018: 70-71.
27 常宏远. 网络购物环境下城市最后一公里配送成本研究[D]. 重庆: 重庆大学, 2017: 61-65.
Chang Hong-yuan, Cost study on urban last mile distribution under online shopping[D]. Chongqing: Chongqing University, 2017: 61-65.
[1] 张则强,许培玉,蒋晋,张裕. 站间操作者不同的并行拆卸线平衡问题优化[J]. 浙江大学学报(工学版), 2021, 55(10): 1795-1805.
[2] 吴敬理,伊国栋,裘乐淼,张树有. 高温混合障碍空间中的移动机器人路径规划[J]. 浙江大学学报(工学版), 2021, 55(10): 1806-1814.
[3] 周炳海, 彭涛. 基于混合教-学算法的汽车装配线物料供应调度[J]. 浙江大学学报(工学版), 2018, 52(10): 1854-1863.
[4] 虞介泽,李聪,张土乔,毛欣炜. 改进的水质服务水平与加氯费用优化分析[J]. J4, 2013, 47(7): 1140-1147.