Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2023, Vol. 57 Issue (5): 900-910    DOI: 10.3785/j.issn.1008-973X.2023.05.006
    
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
Download: HTML     PDF(1285KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 07 November 2022      Published: 09 May 2023
CLC:  U 9  
Fund:  长安大学中央高校基本科研业务费专项资金资助项目 (300102222105)
Corresponding Authors: Man-man LI     E-mail: jshyang@chd.edu.cn;limanman@chd.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Jing-shuai YANG
Yu-e YANG
Man-man LI
Yuan-yuan LI
Cite this article:

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.

URL:

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


末端配送服务模式与路径联合优化

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


关键词： 物流工程,  末端配送服务模式,  配送路径,  混合整数规划模型,  NSGA-Ⅱ 
Fig.1 Joint optimization diagram of terminal distribution service mode and routing
末端配送服务模式 送货上门 自提柜 自提点
服务形式 车辆配送 客户自取 客户自取
收货地点 客户所在地 自提货柜 超市、商铺等
服务成本 高 中 低
货物类型限制 无 有 无
取货时间限制 客户时间窗 无 营业时间
客户满意度 高 较高 低
Tab.1 Comparison of different terminal distribution service modes
集合 含义
${\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$时已派送的货物量
Tab.2 Notations and meanings of proposed model
Fig.2 Improved NSGA-Ⅱ flowchart
Fig.3 Chromosomal coding of improved NSGA-Ⅱ
Fig.4 Pareto frontier diagram
Fig.5 Crowded degree of Chromosome i
Fig.6 Multi-point crossing operator of improved NSGA-Ⅱ
Fig.7 POCSX crossing operator of improved NSGA-Ⅱ
Fig.8 Inversion mutation operator of improved 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
Tab.3 Experimental parameters and values
配送路径 约束检验
末端配送服务模式 车辆载重 时间窗
选择模式 是否为接受模式 累计载重 是否超载 到达时间/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]
Tab.4 GUROBI results of small-scale example
算例规模 ${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
Tab.5 Algorithm stability analysis of improved 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 ?
Tab.6 Performances of three algorithms to solve terminal distribution service mode and routing model
Fig.9 Pareto frontier of 60 customer cases
算例规模 模式 目标
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
Tab.7 Distribution cost and customer satisfaction with different terminal distribution service modes
配送方案 对比值
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
Tab.8 Lowest cost distribution scheme with different number of parcel lockers and pick-up points
Fig.10 Minimum distribution cost with different time window width multiples
原时间窗宽度 对比值
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
Tab.9 Distribution schemes with different time window width multiples
[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] Huang LI,Hong-juan GE,Ying MA,Yong-shuai WANG. Parameters optimization design of dual-input dual-buck inverter system based on hyperplane NSGA-II[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(3): 606-615.
[2] Ze-qiang ZHANG,Pei-yu XU,Jin JIANG,Yu ZHANG. Optimization of parallel disassembly line balancing problem with different operators between workstations[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(10): 1795-1805.
[3] ZHOU Bing-hai, PENG Tao. Part-supply scheduling of automobile assembly line with hybrid teaching-learning-based optimization algorithm[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(10): 1854-1863.
[4] WANG Zi li, ZHANG Shu you, QIU Le miao. Energy consumption analysis of plastic injection equipment plastic design based on confidence intervals[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(2): 328-335.
[5] ZHANG Jun hong, GUO Qian, WANG Jian, XU Zhe xuan, CHEN Kong wu. Multi-objective optimization of ribs design parameters for plastic oil cooler cover[J]. Journal of ZheJiang University (Engineering Science), 2016, 50(7): 1360-1366.
[6] HE Zhong-hua,YUAN Yi-xing. Reliability optimization design of water distribution system based on surplus energy entropy[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(7): 1188-1194.
[7] TUN Yin-Hua, ZHANG Cha-Jiao, HUANG E-Dong, et al. Reliability-based multi-objective sensor location in water distribution systems[J]. Journal of ZheJiang University (Engineering Science), 2009, 43(6): 1060-1064.