收送货同时的城市无人物流配送问题研究

doi:10.15960/j.cnki.issn.1007-6093.2023.03.004

运筹学学报 ›› 2023, Vol. 27 ›› Issue (3): 53-67.doi: 10.15960/j.cnki.issn.1007-6093.2023.03.004

收送货同时的城市无人物流配送问题研究

张昀蔚¹^,², 韩曙光¹^,*()

1. 浙江理工大学理学院, 浙江杭州 310018
2. 东南大学数学学院, 江苏南京 211189

收稿日期:2021-08-09 出版日期:2023-09-15 发布日期:2023-09-14
通讯作者: 韩曙光 E-mail:zist001@163.com
作者简介:韩曙光, E-mail: zist001@163.com
基金资助:
国家自然科学基金(12071436)

Research on city unmanned logistics distribution with simultaneous delivery and pickup

Yunwei ZHANG¹^,², Shuguang HAN¹^,*()

1. School of Science, Zhejiang Sci-Tech University, Hangzhou 310018, Zhejiang, China
2. School of Mathematics, Southeast University, Nanjing 211189, Jiangsu, China

Received:2021-08-09 Online:2023-09-15 Published:2023-09-14
Contact: Shuguang HAN E-mail:zist001@163.com

摘要/Abstract

摘要：

随着节能减碳的需求和人工智能的快速发展，以无人电动车等为配送装置的城市无人物流配送渐成现实。本文考虑电池容量约束和取送货同时装载容量约束，以最小配送成本为目标函数构建数学规划模型（E-VRPSDP）；以列生成法和双向动态标签算法为基础，设计了分支定价算法实现模型的精确求解；针对大规模E-VRPSDP，设计改进模拟退火算法，引入构造可行解算子，将原始解进化成符合约束的可行解，提高了算法的搜索能力；最后，利用已有标准测试集生成测试算例以验证所设计的算法。本文可以为城市无人物流配送的发展提供理论指导和算法支持。

关键词: 车辆路径问题, 无人配送, 收送货同时, 分支定价, 模拟退火

Abstract:

With the requirement for the protection of energy saving and emission reduction and also the development of the artificial intelligence, the city logistics distribution that uses unmanned aerial vehicle as distribution device has gradually turned into reality. Considering the battery capacity constraints of device, the charging decision and the pickup and delivery simultaneous demands, a mathematical programming model is constructed with the objective of minimizing the distribution cost (E-VRPSDP). A new branch-cut-and-price algorithm is provided to solve the exact solution based on the column generation method and bi-directional dynamic programming. To solve the large size E-VRPSDP, an improved simulated annealing algorithm is designed. A new operator is introduced as the constructing feasible solution operator which evolves the original solution into a feasible solution, thereby improving the searching ability of the algorithm. Finally, the suitable data examples are generated based on the standard test set to verify the proposed algorithms. The theoretical guidance and algorithm support for city logistics enterprises is provided to develop the driver-less logistics distribution.

Key words: vehicle routing problems, unmanned distribution, delivery and pickup simultaneous, branch-cut-and-pricing, simulated annealing

中图分类号:

O221.2

张昀蔚, 韩曙光. 收送货同时的城市无人物流配送问题研究[J]. 运筹学学报, 2023, 27(3): 53-67.

Yunwei ZHANG, Shuguang HAN. Research on city unmanned logistics distribution with simultaneous delivery and pickup[J]. Operations Research Transactions, 2023, 27(3): 53-67.

图/表 8

图1

图2

图3

表1

表2

表3

表4

表5

参考文献 18

1	国务院. 国务院关于加快建立健全绿色低碳循环发展经济体系的指导意见[EB/OL]. (2021-02-22)[2021-07-28]. http://www.gov.cn/zhengce/content/2021-02/22/content_5588274.htm.
2	Dantzig G , Ramser R . The truck dispatching problem[J]. Management Science, 1959, 6 (1): 80- 91. doi: 10.1287/mnsc.6.1.80
3	Erdogan S , Miller-Hooks E . A green vehicle routing problem[J]. Transportation Research Part E Logistics & Transportation Review, 2012, 48 (1): 100- 114.
4	Schneider M , Stenger A , Goeke D . The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48 (4): 500- 520. doi: 10.1287/trsc.2013.0490
5	Min H . The multiple vehicle routing problem with simultaneous delivery and pick-up points[J]. Transportation Research Part A: General, 1989, 23 (5): 377- 386. doi: 10.1016/0191-2607(89)90085-X
6	Dell'Amico M , Righini G , Salani M . A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection[J]. Transportation Science, 2006, 40 (2): 235- 247. doi: 10.1287/trsc.1050.0118
7	Dantzig G , Wolfe P . Decomposition principle for linear programs[J]. Operations Research, 1960, 8 (1): 101- 111. doi: 10.1287/opre.8.1.101
8	Desaulniers G , Errico F , Irnich S , et al. Exact algorithms for electric vehicle-routing problems with time windows[J]. Operations Research, 2016, 64 (6): 1388- 1405. doi: 10.1287/opre.2016.1535
9	Feillet D , Dejax P , Gendreau M , et al. An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems[J]. Networks, 2004, 44 (3): 216- 229. doi: 10.1002/net.20033
10	Righini G , Salani M . Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints[J]. Discrete Optimization, 2006, 3 (3): 255- 273. doi: 10.1016/j.disopt.2006.05.007
11	Roberti R , Wen M . The electric traveling salesman problem with time windows[J]. Transportation Research Part E: Logistics & Transportation Review, 2016, 89, 32- 52.
12	Montane F , Galvao R . A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J]. Computers & Operations Research, 2006, 33 (3): 595- 615.
13	Montane F , Galvao R , Avci M , et al. A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery[J]. Expert Systems with Applications, 2006, 33 (3): 595- 615.
14	Montane F , Galvao R . A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J]. Computers & Operations Research, 2016, 53, 160- 171.
15	Chen J , Wu T . Vehicle routing problem with simultaneous deliveries and pickups[J]. Journal of the Operational Research Society, 2006, 57 (5): 579- 587. doi: 10.1057/palgrave.jors.2602028
16	Solomon M . Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35 (2): 254- 265. doi: 10.1287/opre.35.2.254
17	Salhi S , Nagy G . A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J]. Journal of the Operational Research Society, 1999, 50 (10): 1034- 1042. doi: 10.1057/palgrave.jors.2600808
18	Ryan D , Foster B . An integer programming approach to scheduling[J]. Computer Scheduling of Public Transport, 1981, 1, 269- 280.

编号	坐标	取货需求	送货需求
0	(35, 35)	0	0
1	(41, 49)	2	11
2	(35, 17)	4	7
3	(35, 45)	2	14
4	(55, 20)	12	19
5	(15, 30)	13	27
6	(35, 35)	0	0
7	(48, 17)	0	0
8	(44, 17)	0	0

用户规模	数据集	LINGO计算结果			改进分支定价算法计算结果
用户规模	数据集	车辆数量	总距离	运行时间/s	车辆数量	总距离	运行时间/s
$ 5 \times 3 $	r101-2	1	115.23	187	1	115.23	<1
$ 5 \times 3 $	r101-3	1	169.59	211	1	169.59	<1
$ 10 \times 4 $	r101-1	$ - $	$ - $	$ - $	2	199.29	9
	r101-2	$ - $	$ - $	$ - $	2	267.45	7
	r101-3	$ - $	$ - $	$ - $	2	187.45	3
$ 15 \times 5 $	r101-1	$ - $	$ - $	$ - $	3	527.71	63
	r101-2	$ - $	$ - $	$ - $	3	555.07	79
	r101-3	$ - $	$ - $	$ - $	3	773.36	88
$ 20 \times 5 $	r101-1	$ - $	$ - $	$ - $	4	770.17	183
	r101-2	$ - $	$ - $	$ - $	2	773.87	206
	r101-3	$ - $	$ - $	$ - $	2	757.18	280

数据集	客户点规模	充电站规模	车辆数量	总距离	运行时间/s
CMT1	50	10	6	597.92	449
CMT2	75	10	12	967.98	632.91
CMT3	100	20	8	1 042.75	803.67
CMT4	150	30	13	1 549.28	1 088.92
CMT5	199	40	19	2 324.07	1 400.56
CMT6	50	10	6	622.94	521.80
CMT7	75	10	12	958.97	938.28
CMT8	100	20	9	1 142.47	999.97
CMT9	150	30	13	1801.1	1 412.54
CMT10	199	40	19	2 125.22	1 699.45
CMT11	120	20	8	1 379.04	1 130.33
CMT12	100	20	11	1 083.94	956.98
CMT13	120	20	8	1 373.88	1 169.37
CMT14	100	20	11	1 230.85	908.76

算例	0.9			1.0			1.1			1.2
算例	充电次数	车辆数	总距离	充电次数	车辆数	总距离	充电次数	车辆数	总距离	充电次数	车辆数	总距离
r101-1	1	2	217.71	1	2	199.29	0	2	198.21	0	2	198.21
r101-2	4	2	277.27	3	2	267.45	2	2	268.02	1	2	260.56
r101-3	2	2	199.45	0	2	187.45	0	2	187.45	0	2	187.45

算例	0.5			0.75			1
算例	充电次数	车辆数	总距离	充电次数	车辆数	总距离	充电次数	车辆数	总距离
r101-1	1	3	224.41	1	2	216.71	1	2	199.29
r101-2	2	4	453.72	1	2	310.58	3	2	267.45
r101-3	0	4	250.38	0	3	245.77	0	2	187.45

收送货同时的城市无人物流配送问题研究

Research on city unmanned logistics distribution with simultaneous delivery and pickup

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 18

相关文章 6

编辑推荐

Metrics

本文评价

[1]	吴廷映, 王瑶, 周支立, 任亚婷. 具有设施容量选择的两阶段设施选址问题研究[J]. 运筹学学报, 2023, 27(3): 83-95.
[2]	周成昊, 吕博轩, 周翰宇, 鲁海燕. 以商圈为中心的O2O动态外卖配送路径优化模型与算法[J]. 运筹学学报, 2022, 26(3): 17-30.
[3]	朱征露, 鲁习文. 带学习效应的两台平行机时间表长问题[J]. 运筹学学报, 2018, 22(1): 55-66.
[4]	宁涛, 陈荣, 郭晨, 梁旭. 一种基于双链量子编码的动态车辆路径问题解决策略[J]. 运筹学学报, 2015, 19(2): 72-82.
[5]	帅天平，余金果，孙玲. 一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法[J]. 运筹学学报, 2013, 17(2): 41-47.
[6]	汤丹. 基于模拟退火的CRS算法[J]. 运筹学学报, 2011, 15(4): 124-128.