Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2021, Vol. 55 Issue (12): 2397-2408    DOI: 10.3785/j.issn.1008-973X.2021.12.021
    
Vehicle routing optimization of two-echelon opening and closing hybrid based on crowdsourcing mode
Guo-wen XIONG1(),Min ZHANG1,2,*(),Wen-xin XU1()
1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China
2. Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Chengdu 610031, China
Download: HTML     PDF(1139KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A two-echelon crowdsourcing logistics distribution strategy with optimal transfer stations was proposed, aiming at the problem of insufficient logistics transportation resources and low utilization rate of enterprise and social resources under the state of demand blowout. In the strategy, enterprise vehicles were used to complete the first-level distribution, and social vehicles were used to complete secondary distribution. Considering the customer’s requirements for service time, a mathematical model with time window for vehicle path planning of two-echelon open close hybrid was established to minimize the sum of path cost and service delay penalty cost. According to the characteristics of the model, a discrete sparrow search algorithm based on heuristic strategy was constructed. The operation operator in the iterative process was selected adaptively in the algorithm. The effectiveness of the algorithm was verified by comparing the results of GUROBI exact solver and genetic algorithm optimization example. By comparing various costs under different distribution modes, it is verified that the proposed strategy can effectively reduce logistics transportation costs and improve customer satisfaction.

Key words： demand blowout      two-echelon crowdsourcing logistics      opening and closing hybrid      vehicle routing      discrete sparrow search algorithm     
Received: 26 January 2021      Published: 31 December 2021
CLC:  TP 301.6  
Fund:  国家重点研发计划资助项目(2020YFB1712200)；中国博士后科学基金资助项目(2020M673279)；四川省科技计划资助项目(2020JDTD0012)
Corresponding Authors: Min ZHANG     E-mail: 969810112@qq.com;zhmzhangmin16@126.com;15883956442@163.com
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Guo-wen XIONG
Min ZHANG
Wen-xin XU
Cite this article:

Guo-wen XIONG,Min ZHANG,Wen-xin XU. Vehicle routing optimization of two-echelon opening and closing hybrid based on crowdsourcing mode. Journal of ZheJiang University (Engineering Science), 2021, 55(12): 2397-2408.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2021.12.021     OR     https://www.zjujournals.com/eng/Y2021/V55/I12/2397


基于众包模式的两级开闭混合车辆路径优化

针对在需求井喷状态下的物流运力资源不足和物流企业自身与社会闲散资源利用率不高的问题，提出采用企业车辆完成一级配送，社会车辆完成二级配送的具有最优中转站的两级众包物流配送策略. 考虑客户对服务时间的要求，以路径成本与服务延迟惩罚成本总和最小为优化目标，建立带时间窗的两级开闭混合式车辆路径规划数学模型. 根据模型特点构建基于启发式策略的离散麻雀搜索算法，该算法在迭代过程中可以自适应选择操作算子. 通过与GUROBI精确求解器和遗传算法优化算例的结果对比，验证所提算法的有效性. 对比不同配送模式下的各项成本，结果表明所提策略能够有效降低物流运输成本和提高客户满意度.


关键词： 需求井喷,  两级众包物流,  开闭混合式,  车辆路径,  离散麻雀搜索算法 
Fig.1 Route diagram of two-echelon crowdsourced vehicles
符号 参数 符号 参数
D 仓库集合 E 企业车辆 e 集合
C 需求点集合 K 众包车辆 k 集合
Q1 企业车辆最大载重 qi 需求点i的需求量
Q2 众包车辆最大载重 qj 需求点 j 的需求量
c1 企业车辆单位距离成本 N 中转站最大数量
c2 众包车辆单位距离成本 M 足够大的实数
c3 单位时间延时惩罚成本 Tij 车辆从 i到 j所需时间
dij 节点 i到节点 j间的距离 Ti 需求点 i期望服务时间
Tab.1 Mathematical model parameters with time windows for vehicle path planning of two echelon open close hybrid
符号 说明 符号 说明
fi、fj 需求点i 、j被选作为中转站，fi、fj=1；否则，fi、fj=0 Ue e被使用， Ue=1；否则，Ue=0
zki k经过中转站 j，zki=1；否则，zki=0 $r_{ij}^e $ e访问中转站i后访问中转站 j， $r_{ij}^e $ =1；否则， $r_{ij}^e $ =0
uk k被使用，uk=1；否则，uk =0 gie e给中转站 j的货物量
ski k经过需求点 j，ski=1；否则，ski=0 lie 消除企业车辆路径子回路的中间变量
$x_{ij}^k $ k访问需求点i后访问需求点 j, $x_{ij}^k $ =1；否则， $x_{ij}^k $ =0 hie e到中转站的时间
Lik 消除众包车辆路径子回路的中间变量 F 企业车辆到达中转站的最大时间
Sijk 需求点i的货物由 k从中转站 j获取 ti 货物到达需求点 i的实际用时
yie、yje e服务中转站 i、j，yie、 yje=1；否则，yie、yje=0 Ri 货物到达需求点 i的延迟时间
y0e e服务配送中心 ，y0e=1；否则，y0e=0 Vim ti?Ti > 0， Vi1 =1;否则， Vi2=0，m∈{1, 2}
Hik k到达客户i所用时间 uie e到中转站 i的时间为企业车辆到达中转站的最大时间，uie =1；否则，uie =0
wj 中转站 j的总货物需求量
Tab.2 Decision variables of mathematical model with time window for vehicle path planning of two-echelon open close hybrid
Fig.2 Sparrow coding
Fig.3 Sparrow follow operation
Fig.4 Sparrow escape operation
Fig.5 Flow chart of discrete sparrow search algorithm
编号 X/km Y/km q T/h 编号 X/km Y/km q T/h
0 145 215 0 0 16 141 206 2 100 4
1 151 264 1 100 3 17 147 193 1 000 4
2 159 261 700 4 18 164 193 900 3
3 130 254 800 6 19 129 189 2 500 6
4 128 252 1 400 5 20 155 185 1 800 6
5 163 247 2 100 4 21 139 182 700 5
6 146 246 400 3 22 140 213 900 6
7 161 242 800 4 23 160 180 1 000 5
8 142 239 100 3 24 136 196 800 4
9 163 236 500 6 25 143 208 400 3
10 148 232 600 3 26 126 228 900 5
11 128 231 1 200 5 27 150 190 600 6
12 156 217 1 300 5 28 169 202 1 000 6
13 129 214 1 300 6 29 119 178 300 4
14 146 208 300 3 30 128 240 500 5
15 164 208 900 3 31 113 192 600 6
Tab.3 Set2a example data after customer scale expansion
客户规模 GUROBI GA DSSA
f0/元 GAP/% V0/s f1/元 avg1/元 gap′/% V1/s f2/元 avg2/元 gap′/% V2/s
13 169.60 0.00 56 170.45 172.59 0.50 22 169.60 172.10 0.00 19
15 188.86 0.00 38 192.22 195.31 1.78 25 188.86 191.60 0.00 20
17 210.48 0.00 123 210.48 215.51 0.00 28 210.48 215.29 0.00 23
19 243.91 0.00 283 247.34 250.99 1.40 30 245.27 247.14 0.56 28
21 263.33 0.00 322 265.27 276.85 0.74 33 264.68 272.92 0.51 31
23 275.45 5.63 1000 274.50 283.27 ?0.34 34 273.14 282.57 ?0.84 33
25 283.49 9.09 1000 281.93 289.52 ?0.55 36 277.69 285.96 ?2.05 34
27 311.02 17.80 1000 288.00 302.56 ?7.40 37 287.84 297.51 ?7.45 35
29 366.64 26.80 1000 319.23 330.68 ?12.90 38 311.63 323.52 ?15.00 38
31 388.91 28.20 1000 341.27 359.50 ?12.20 41 340.84 356.60 ?12.40 40
平均值 270.17 8.75 582 259.07 267.68 ?2.90 32 257.00 264.52 ?3.67 30
Tab.4 Optimization results of different methods with shortest path as objective
客户规模 GUROBI GA DSSA
f0/元 GAP/% V0/s f1/元 avg1/元 gap′/% V1/s f2/元 avg2/元 gap′/% V2/s
13 188.54 518 0.00 191.11 194.71 1.36 23 191.11 191.11 1.36 20
15 209.64 1000 11.80 219.22 222.27 4.57 25 213.56 215.92 1.87 22
17 230.37 1000 10.30 230.37 234.03 0.00 28 230.37 232.60 0.00 26
19 265.45 818 0.00 269.06 276.32 1.36 31 265.45 271.54 0.00 28
21 292.29 1000 11.80 295.39 301.65 1.06 31 284.86 295.50 ?2.54 30
23 297.44 1000 13.70 309.60 317.50 4.09 34 301.90 310.73 1.50 32
25 303.85 1000 14.70 305.63 322.68 0.59 37 303.37 321.37 ?0.16 36
27 374.49 1000 31.40 312.15 328.75 ?16.60 39 311.73 326.97 ?16.8 37
29 350.51 1000 22.70 358.92 376.46 2.40 40 348.53 368.84 ?0.57 40
31 388.91 1000 28.20 393.46 408.65 1.17 45 379.93 394.84 ?2.31 44
平均值 290.15 934 14.46 288.49 298.30 0.00 33 283.08 292.94 ?1.77 32
Tab.5 Optimization results of different methods considering service delay
Fig.6 Discrete sparrow search algorithm iterative chart
Fig.7 Genetic algorithm iterative chart
c1/元 c2/元 c3 配送模式 C1/元 C2/元 nDL TL/h TC/元
1 1 0 两级开闭混合 59.59 205.10 15 31.43 327.55
1 1 0 两级闭环 87.51 278.22 18 65.60 496.93
1 1 2 两级开闭混合 36.50 226.82 8 10.77 284.86
1 1 0 两级闭环 56.83 325.59 11 21.53 425.48
Tab.6 Optimization results of discrete sparrow search algorithm under different distribution modes
Fig.8 Vehicle route chart of discrete sparrow search algorithm under different distribution modes
c1 c2 c3 C3 C4 P/%
1.0 1.0 2.0 284.86 425.48 33.05
2.0 1.0 2.0 321.37 480.79 33.12
3.0 1.0 2.0 357.87 521.87 31.43
3.0 1.5 2.0 471.28 701.95 32.86
3.0 2.0 2.0 584.69 864.75 32.39
Tab.7 Influence of vehicle unit distance cost on DSSA optimization results
Q1 Q2 C3 C4 P/%
11 000 6 000 293.40 433.86 32.37
13 000 6 000 293.40 425.49 31.04
15 000 6 000 284.86 425.48 33.05
15 000 5 000 298.44 436.07 31.56
15 000 4 000 300.74 463.99 35.18
Tab.8 Influence of vehicle capacity on DSSA optimization results
N C3 C4 P/%
2 306.44 446.26 31.33
3 293.40 437.03 32.87
不限制 293.40 433.86 32.37
Tab.9 Influence of the number of transfer stations on the optimization results for DSSA
[1]   吕俊杰, 冯谦 基于客户分流策略的电商促销下车辆路径问题研究[J]. 计算机应用与软件, 2019, 36 (5): 29- 34
LU Jun-jie, FENG Qian Vehicle routing under E-commerce promotion based on customer segregation strategy[J]. Computer application and software, 2019, 36 (5): 29- 34
doi: 10.3969/j.issn.1000-386x.2019.05.006
[2]   石荣丽 分享经济视阈下的众包物流信息服务平台模型构建[J]. 华南理工大学学报:社会科学版, 2017, 19 (2): 15- 21
SHI Rong-li Constructing crowd-sourcing logistics information service platform model from the perspective of sharing econ-omy[J]. Journal of South China University of Technology:social science edition, 2017, 19 (2): 15- 21
[3]   AYMERIC P, AMANDA S Modeling the acceptability of crowdsourced goods deliveries: role of context and experience effects[J]. Transportation Research Part E: Logistics and Transportation Review, 2017, 105: 18- 38
doi: 10.1016/j.tre.2017.06.007
[4]   任斐 众包物流的发展现状及前景分析[J]. 商场现代化, 2017, (23): 48- 49
REN Fei Analysis on the development status and prospect of crowdsourcing logistics[J]. Mall modernization, 2017, (23): 48- 49
[5]   刘春玲, 王俊峰, 黎继子, 等 众包模式下冷链物流配送模型的仿真和优化分析[J]. 计算机集成制造系统, 2019, 25 (10): 2666- 2675
LIU Chun-ling, WANG Jun-feng, LI Ji-zi, et al Simulation and optimization model of cold chain logistics delivery under crowdsourcing mode[J]. Computer integrated manufacturing system, 2019, 25 (10): 2666- 2675
[6]   葛显龙, 薛桂琴 基于场景动态度的两级配送路径问题[J]. 控制与决策, 2019, 34 (6): 1195- 1202
GE Xian-long, XUE Gui-qin Two-echelon distribution routing problem based on scene dynamics degree[J]. Control and decision, 2019, 34 (6): 1195- 1202
[7]   YANG P, ZENG L Models and methods for two-echelon location routing problem with time constraints in city logistics[J]. Mathematical Problems in Engineering, 2018, 2018: 1- 9
[8]   陈立伟, 唐权华 基于Memetic算法的两级车辆路径优化[J]. 重庆大学学报, 2017, 40 (3): 95- 104
CHEN Li-wei, TANG Qian-hua Two stage vehicle routing optimization based on Memetic algorithm[J]. Journal of Chongqing University, 2017, 40 (3): 95- 104
doi: 10.11835/j.issn.1000-582X.2017.03.011
[9]   WANG K Z, SHAO Y M, ZHOU W H Matheuristic for a two-echelon capacitated vehicle routing problem with environmental considerations in city logistics service[J]. Transportation Research Part D: Transport and Environment, 2017, 57: 262- 276
doi: 10.1016/j.trd.2017.09.018
[10]   BELGIN O, KARAOGLAN I, ALTIPARMAK F Two-echelon vehicle routing problem with simultaneous pickup and delivery: mathematical model and heuristic approach[J]. Computers and Industrial Engineering, 2018, 115: 1- 16
doi: 10.1016/j.cie.2017.10.032
[11]   DAVID L J U, ENTHOVEN, JARGALSAIKHAN B, 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: 104919
doi: 10.1016/j.cor.2020.104919
[12]   CHENG X, GOU Q L, YUE J F, et al Equilibrium decisions for an innovation crowdsourcing platform[J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 125 (3): 241- 260
[13]   DEVARI A, NIKOLAEV A G, HE Q. Crowdsourcing the last mile delivery of online orders by exploiting the social networks of retail store customers [J]. Transportation Research Part E: Logistics and Transportation Review, 2017, 105: 105-122.
[14]   GUO X Z, JARAMILLO Y J L, JACQUELINE B R, et al. On integrating crowdsourced delivery in last-mile logistics: a simulation study to quantify its feasibility [J], Journal of Cleaner Production, 2019, 241(24): 1-13.
[15]   曾正洋, 许维胜, 徐志宇, 等 城市物流中的开闭混合式两级车辆路径问题[J]. 信息与控制, 2014, 43 (6): 744- 749
ZENG Zheng-yang, XU Wei-sheng, XU Zhi-yu, et al Open-close mixed two-echelon vehicle routing problem in city logistics[J]. Information and Control, 2014, 43 (6): 744- 749
[16]   PICHKA K, BAJGIRAN A H, PETERING M E H et al The two-echelon open location routing problem: mathematical model and hybrid heuristic[J]. Computer and Industrial Engineering, 2018, 121 (7): 97- 112
[17]   KAFLE N, ZOU B, LIN J Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery[J]. Transportation Research Part B: Methodological, 2017, 99: 62- 82
doi: 10.1016/j.trb.2016.12.022
[18]   HUANG K C, ARDIANSYAH M N A decision model for last-mile delivery planning with crowdsourcing integration[J]. Computers and Industrial Engineering, 2019, 135: 898- 912
doi: 10.1016/j.cie.2019.06.059
[19]   LIU T, LUO Z X, HU Q, et al A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints[J]. European Journal of Operational Research, 2018, 266 (2): 487- 497
doi: 10.1016/j.ejor.2017.10.017
[20]   YUAN B, LIU R, JIANG Z A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements[J]. International Journal of Production Research, 2015, 53 (24): 7450- 7464
doi: 10.1080/00207543.2015.1082041
[21]   ADULYASAK Y, CORDEAU J F, JANS R Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems[J]. Informs Journal on Computing, 2014, 26 (1): 103- 120
doi: 10.1287/ijoc.2013.0550
[22]   GUILLAUME M, RUSLAN S, DESCHAMPS J C, et al An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem[J]. Computers and Operations Research, 2020, 114: 104833
doi: 10.1016/j.cor.2019.104833
[23]   穆东, 王超, 王胜春 基于并行模拟退火算法求解时间依赖型车辆路径问题[J]. 计算机集成制造系统, 2015, 21 (6): 1626- 1636
MU Dong, WANG Chao, WANG Sheng-chun Solving time dependent vehicle routing problem based on parallel simulated annealing algorithm[J]. Computer integrated manufacturing system, 2015, 21 (6): 1626- 1636
[24]   CORDEAU J, GENDREAU M, LAPORTE G A tabu search heuristic for periodic and multi-depot vehicle routing problems[J]. Networks, 2015, 30 (2): 105- 119
[25]   李明燏, 梁丽萍, 鲁燕霞 基于改进禁忌搜索算法的车辆路径问题模型[J]. 公路交通科技, 2017, 34 (10): 108- 114
LI Ming-yu, LIANG Li-ping, LU Yan-xia A model of vehicle routing problem based on improved tabu search algorithm[J]. Highway transportation science and technology, 2017, 34 (10): 108- 114
[26]   LIU R, TAO Y, HU Q, et al Simulation-based optimisation approach for the stochastic two-echelon logistics problem[J]. International Journal of Production Research, 2016, 55 (1): 187- 201
[27]   BREUNIG U, SCHMID V, HARTL R F, et al A large neighbourhood based heuristic for two-echelon routing problems[J]. Computers and Operations Research, 2016, 76: 208- 225
doi: 10.1016/j.cor.2016.06.014
[28]   HEMMELMAYR V C, CORDEAU J F, CRAINIC T G An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics[J]. Computers and Operations Research, 2012, 39 (12): 3215- 3228
doi: 10.1016/j.cor.2012.04.007
[29]   GRANGIER P, GENDREAU M, LEHUÉDÉ F, et al An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization[J]. European Journal of Operational Research, 2016, 254 (1): 80- 91
doi: 10.1016/j.ejor.2016.03.040
[30]   WANG K, LAN S, ZHAO Y A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service[J]. Journal of the Operational Research Society, 2017, 68: 1409- 1421
doi: 10.1057/s41274-016-0170-7
[1] Xiao-bo CHEN,Ling CHEN,Shu-rong LIANG,Yu HU. Robust cooperative target tracking under heavy-tailed non-Gaussian localization noise[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(5): 967-976.
[2] Xiao-xin DU,Hao WANG,Lian-he CUI,Jin-qi LUO,Yan LIU,Jian-fei ZHANG,Yi-ping WANG. Dragonfly algorithm based on clustering and detection elite guidance[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(5): 977-986.
[3] Jian-sha LU,Wen-qian ZHAI,Jia-feng LI,Wen-chao YI,Hong-tao TANG. Multi-constrained vehicle routing optimization based on improved hybrid shuffled frog leaping algorithm[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 259-270.
[4] Xiao-feng FU,Li NIU,Zhuo-qun HU,Jian-jun LI,Qing WU. Deep micro-expression spotting network training based on concept of transition frame[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(11): 2128-2137.
[5] DONG Li yan, ZHU Qi, LI Yong li. Model combination algorithm based on consensus maximization[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(2): 416-421.
[6] MIAO Feng, XIE An-huan, WANG Fu-an, YU Feng, ZHOU Hua. Method for multi-stage alternative grouping parallel machines scheduling problem[J]. Journal of ZheJiang University (Engineering Science), 2015, 49(5): 866-872.
[7] NI Guang-yi, ZHANG Xiao-can, SU Cheng, YU Wei-bin. Count adaptive clustering algorithm based on multiple-chromosome evolution[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(6): 980-986.
[8] KONG Yong-qi, PAN Zhi-geng. Segmentation algorithm of recessed image based on vector field of suction[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(6): 1024-1033.
[9] LIU Jia-hai, YANG Mao-lin, LEI Hang, LIAO Yong. Multicore real-time task allocation algorithms with shared resource constraints[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(1): 113-117.
[10] ZHAO Shi-kui, FANG Shui-liang, GU Xin-jian. Genetic algorithm with new initialization mechanism for flexible job shop scheduling[J]. Journal of ZheJiang University (Engineering Science), 2013, 47(6): 1022-1030.
[11] ZHANG Jun-chao, YUE Mao-xiong, LIU Hua-feng. Dynamic PET image reconstruction with Geometrical structure
prior constraints[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(6): 961-966.
[12] LIU Yi, LI Ping, GAO Zeng-liang. Quality prediction of hot metal in blast furnace using improved
support vector regression[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(5): 830-836.
[13] FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui. Improved genetic algorithm for flexible job shop scheduling[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(4): 629-635.
[14] YU Hai-qing, LIU Yi, CHEN Kun, JI Jun1, LI Ping. Robust recursive kernel learning modeling method with
application to blast furnace[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(4): 705-711.
[15] LIU Jia-hai, YANG Mao-lin. Fair scheduling algorithm on multi-core platforms based platforms[J]. Journal of ZheJiang University (Engineering Science), 2011, 45(9): 1566-1570.