Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2021, Vol. 55 Issue (12): 2397-2408    DOI: 10.3785/j.issn.1008-973X.2021.12.021
电子、通信与自动控制技术     
基于众包模式的两级开闭混合车辆路径优化
熊国文1(),张敏1,2,*(),许文鑫1()
1. 西南交通大学 机械工程学院，四川 成都 610031
2. 轨道交通运维技术与装备四川省重点实验室，四川 成都 610031
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
 全文: PDF(1139 KB)   HTML
摘要：

针对在需求井喷状态下的物流运力资源不足和物流企业自身与社会闲散资源利用率不高的问题，提出采用企业车辆完成一级配送，社会车辆完成二级配送的具有最优中转站的两级众包物流配送策略. 考虑客户对服务时间的要求，以路径成本与服务延迟惩罚成本总和最小为优化目标，建立带时间窗的两级开闭混合式车辆路径规划数学模型. 根据模型特点构建基于启发式策略的离散麻雀搜索算法，该算法在迭代过程中可以自适应选择操作算子. 通过与GUROBI精确求解器和遗传算法优化算例的结果对比，验证所提算法的有效性. 对比不同配送模式下的各项成本，结果表明所提策略能够有效降低物流运输成本和提高客户满意度.
关键词： 需求井喷;  两级众包物流;  开闭混合式;  车辆路径;  离散麻雀搜索算法    
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
收稿日期: 2021-01-26 出版日期: 2021-12-31
CLC:  TP 301.6  
基金资助: 国家重点研发计划资助项目(2020YFB1712200)；中国博士后科学基金资助项目(2020M673279)；四川省科技计划资助项目(2020JDTD0012)
通讯作者: 张敏     E-mail: 969810112@qq.com;zhmzhangmin16@126.com;15883956442@163.com
作者简介: 熊国文(1994—)，男，硕士生，主要从事车辆路径规划研究. orcid.org/0000-0002-5061-302X. E-mail: 969810112@qq.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
熊国文
张敏
许文鑫

引用本文:

熊国文,张敏,许文鑫. 基于众包模式的两级开闭混合车辆路径优化[J]. 浙江大学学报(工学版), 2021, 55(12): 2397-2408.

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.

链接本文:

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

图 1  两级众包车辆路径示意图
符号 参数 符号 参数
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期望服务时间
表 1  带时间窗的两级开闭混合式车辆路径规划数学模型参数
符号 说明 符号 说明
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的总货物需求量
表 2  带时间窗的两级开闭混合式车辆路径规划数学模型决策变量
图 2  麻雀编码
图 3  麻雀跟随操作
图 4  麻雀逃离操作
图 5  离散麻雀搜索算法流程图
编号 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
表 3  客户规模扩充后的Set2a算例数据
客户规模 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
表 4  不同方法以路径最短为目标的优化结果
客户规模 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
表 5  不同方法考虑服务延迟的优化结果
图 6  离散麻雀搜索算法迭代图
图 7  遗传算法迭代图
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
表 6  不同配送模式下离散麻雀搜索算法的优化结果
图 8  不同配送模式下离数麻雀搜索算法的车辆路径图
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
表 7  车辆单位距离成本对DSSA优化结果的影响
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
表 8  车辆容量对DSSA优化结果的影响
N C3 C4 P/%
2 306.44 446.26 31.33
3 293.40 437.03 32.87
不限制 293.40 433.86 32.37
表 9  中转站数量对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] 鲁建厦,翟文倩,李嘉丰,易文超,汤洪涛. 基于改进混合蛙跳算法的多约束车辆路径优化[J]. 浙江大学学报(工学版), 2021, 55(2): 259-270.