Learning-based Ant Colony Optimization Algorithm for Solving a Kind of Complex 2-Echelon Vehicle Routing Problem

doi:10.16182/j.issn1004731x.joss.22-0682

Abstract

Abstract:

Aiming at green 2-echelon vehicle routing problem with simultaneous pick-up and delivery, a learning-based ant colony optimization algorithm combined with clustering decomposition is proposed. The objective function to be minimized is total transportation cost wherein carbon emission cost is specially considered. Associated with the mutual coupling features of the 2-echelon vehicle routing problem, we propose a distance-based clustering method to decompose the original problem into a set of sub-problems. Then, a learning-based ant colony optimization algorithm is presented to find the solutions of the sub-problems based on which the solution of the original problem can be obtained. In the algorithm, we introduce a problem-dependent three-dimensional probability matrix to represent pheromone matrix, which is used to learn valuable information about high-quality solutions and improve global search ability. Thereafter, we propose a local search strategy based on the search behavior of the algorithm to learn information about excellent individuals for six dedicated neighborhood search operators, so as to enhance local search ability. Results of numerical experiments and algorithm comparisons demonstrate the effectiveness of the proposed algorithm.

Key words: green 2-echelon vehicle routing problem, ant colony optimization algorithm, clustering decomposition, machine learning, Three-dimensional probabilistic model, simultaneous pick-up and delivery

CLC Number:

TP391.9

Chen Xue, Hu Rong, Wang Hui, Li Zuocheng, Qian Bin, Li Yixu. Learning-based Ant Colony Optimization Algorithm for Solving a Kind of Complex 2-Echelon Vehicle Routing Problem[J]. Journal of System Simulation, 2023, 35(11): 2476-2495.

Figures/Tables 18

Fig. 1

Table 1

Symbols and interpretations

符号	释义
$V$	节点集
$S$	配送中心及中转站集
$S s$	中转站集
$s 0$	配送中心
$C$	客户点集， $C = {1,2, …, n}$
$K 1 D$	一级车辆中进行送货服务的车辆集
$K 1 P$	一级车辆中进行取货服务的车辆集
$K 2$	二级车辆集
$d i j$	点 $i$ 与点 $j$ 之间的距离
$D f 1$	一级配送中中转站 $f$ 处的送货量
$P f 1$	一级配送中中转站 $f$ 处的取货量
$D a 2$	二级配送中客户点 $a$ 处的送货量
$P a 2$	二级配送中客户点 $a$ 处的取货量
$ρ 1$	车辆单位距离行驶成本
$b i 1$	一级配送中用于消除子环回路的变量
$b i 2$	二级配送中用于消除子环回路的变量
$Q 1$	一级车辆最大载重
$Q 2$	二级车辆最大载重
$M$	中转站最大容量
$x i j k$	决策变量：1，车辆 $k$ 从点 $i$ 行驶到点 $j$ ；0，其他
$y i j k$	决策变量：车辆 $k$ 由点 $i$ 行驶到点 $j$ 的载货量

Table 1

Table 2

Parameters of adopted carbon emission model

参数	释义	取值
$ω c$	每升燃油释放二氧化碳的质量/t	0.002 7
$E f$	车辆单位重量单位距离耗油量L/(t·km)	0.016 53
$ρ 2$	排放每单位二氧化碳产生的成本	$20$
$G 1$	一级车辆单位质量/t	$16.2$
$G 2$	二级车辆单位质量/t	$10.2$
$μ$	车辆质量利用系数	5.017 5

Table 2

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 3

Key parameter level table

参数	水平设置
参数	1	2	3	4
$α$	0.5	1	1.5	2
$β$	0.5	1	1.5	2
$ρ$	0.1	0.3	0.5	0.7
$Q$	1	2	3	4
$a n t n$	20	30	40	50

Table 3

Table 4

Orthogonal table of parameter settings

标号	水平设置					$A V G$
标号	$α$	$β$	$ρ$	$Q$	$a n t n$	$A V G$
1	1	1	1	1	1	1 017.6
2	1	2	2	2	2	1 038.6
3	1	3	3	3	3	1 030.0
4	1	4	4	4	4	1 031.5
5	2	1	2	3	4	1 018.4
6	2	2	1	4	3	1 038.0
7	2	3	4	1	2	1 024.2
8	2	4	3	2	1	1 005.0
9	3	1	3	4	2	1 010.5
10	3	2	4	3	1	1 026.4
11	3	3	1	2	4	1 053.4
12	3	4	2	1	3	1 029.0
13	4	1	4	2	3	1 041.4
14	4	2	3	1	4	1 042.2
15	4	3	2	4	1	1 028.4
16	4	4	1	3	2	1 014.1

Table 4

Table 5

Average response value of each parameter

水平	$α$	$β$	$ρ$	$Q$	$a n t n$
1	1 029.4	1 022.0	1 030.8	1 028.3	1 019.4
2	1 021.4	1 036.3	1 028.6	1 034.6	1 021.9
3	1 029.8	1 034.0	1 021.9	1 022.2	1 034.6
4	1 031.5	1 020.0	1 030.9	1 027.1	1 036.4
极差	10.1	16.3	9	12.4	17
影响力排名	4	2	5	3	1

Table 5

Fig. 7

Table 6

Comparison results of LACO with ACO1 ACO2(2Ns)

$n_s$	ACO			ACO₁			ACO₂			LACO
$n_s$	最大值	最小值	平均值	最大值	最小值	平均值	最大值	最小值	平均值	最大值	最小值	平均值
30_3	672.5	563.5	610.5	651.4	556.2	607.6	514.9	487.4	495.1	518.3	487.4	494.5
40_3	893.3	800.8	839.9	916.7	797.7	844.6	648.8	553.9	592.9	628.7	554.2	586.9
50_3	1 069.8	987.9	1 021.6	1 133.9	1 001.1	1 072.0	764.0	687.5	736.9	768.9	690.7	736.4
60_3	1 184.5	1 071.8	1 125.1	1 314.7	1 178.1	1 237.4	737.5	676.8	704.3	755.7	680.9	711.9
70_3	1 439.1	1 270.4	1 371.9	1 596.1	1 442.3	1 529.7	913.4	814.3	871.5	863.0	806.1	829.4
80_3	1 637.8	1 504.2	1 566.3	1 856.2	1 719.7	1 789.6	1 025.3	887.1	932.5	1 032.8	877.8	916.9
50_5	1 006.4	922.6	969.4	1 020.2	918.8	961.9	845.3	731.9	776.3	843.6	735.4	779.6
60_5	1 086.9	999.9	1 047.8	1 107.0	1 027.7	1 068.8	855.0	767.1	794.6	861.0	767.8	811.4
70_5	1 261.6	1 111.7	115.8	1 293.1	1 158.7	1 228.8	939.1	851.3	892.6	941.3	843.7	873.9
80_5	1 412.9	1 280.3	1 328.5	1 536.5	1 386.6	1 444.0	991.4	886.3	935.0	955.1	872.3	910.8
90_5	1 598.2	1 433.9	1 509.3	1 679.8	1 539.6	1 624.5	1 067.2	969.2	1 022.2	1 028.9	929.5	966.7
100_5	1 723.8	1 560.9	1 622.5	1 897.0	1 718.9	1 797.6	1 134.1	969.7	1 073.9	1 096.4	965.7	1 042.6
60_8	1 081.0	921.6	1 030.7	1 483.9	1 275.0	1 397.4	895.4	771.9	824.9	901.7	781.8	847.1
80_8	1 407.2	1 274.8	1 325.4	1 823.7	1 581.1	1 689.2	1 105.1	928.6	1 006.3	1 094.3	931.4	987.1
100_8	1 661.7	1 458.0	1 564.1	2 036.3	1 843.6	1 918.3	1 267.3	1 129.1	1 182.8	1 250.2	1 091.0	1 159.2
120_8	1 842.9	1 684.9	1 759.7	2 460.4	2 214.4	2 324.0	1 469.3	1 187.1	1 341.3	1 348.9	1 168.5	1 243.3
140_8	2 168.1	1 940.0	2 067.7	2 713.7	2 468.4	2 599.6	1 551.9	1 285.3	1 437.1	1 517.7	1 279.6	1 404.0
160_8	2 423.9	2 214.6	2 331.5	3 115.1	2 896.7	3 011.1	1 693.1	1 459.3	1 568.3	1 661.7	1 452.9	1 544.4
100_10	1 487.8	1 270.3	1 386.6	1 510.3	1 332.7	1 409.1	1 286.3	1 092.8	1 181.6	1 293.0	1 080.8	1 186.6
120_10	1 607.1	1 424.5	1 522.1	1 752.9	1 504.8	1 600.1	1 420.3	1 195.7	1 271.6	1 373.6	1 181.0	1 264.3
140_10	1 888.1	1 659.8	1 783.1	2 029.6	1 748.8	1 896.9	1 575.2	1 274.3	1 399.0	1 549.4	1 265.3	1 392.6
160_10	2 085.6	1 783.4	1 978.6	2 249.9	2 042.6	2 127.5	1 701.3	1 383.1	1 502.8	1 667.8	1 368.1	1 494.8
180_10	2 279.4	2 025.9	2 166.2	2 543.0	2 246.1	2 396.3	1 785.9	1 439.2	1 579.3	1 666.6	1 409.1	1 568.4
200_10	2 621.5	2 356.1	2 499.6	2 877.4	2 556.5	2 703.5	1 966.3	1 603.5	1 803.9	1 945.0	1 598.5	1 779.3

Table 6

Table 7

Comparison results of LACO with VND_LS and CW_LS(2Ns)

$n_s$	VND_LS			CW_LS			LACO
$n_s$	最大值	最小值	平均值	最大值	最小值	平均值	最大值	最小值	平均值
30_3	525.5	509.6	513.4	499.4	483.6	489.2	518.3	487.4	494.5
40_3	679.5	631.1	653.0	654.9	596.9	624.5	628.7	554.2	586.9
50_3	788.1	718.2	753.3	763.1	658.7	693.4	768.9	690.7	736.4
60_3	871.4	758.4	817.6	868.7	707.9	795.7	755.7	680.9	711.9
70_3	994.0	826.7	911.8	905.4	778.4	859.9	863.0	806.1	829.4
80_3	1 093.9	1 013.5	1 037.1	1 032.3	897.0	950.8	1 032.8	877.8	916.9
50_5	820.9	711.3	750.8	773.9	717.9	744.0	843.6	735.4	779.6
60_5	887.4	793.7	827.1	895.4	804.0	838.0	861.0	767.8	811.4
70_5	966.0	824.9	894.9	961.7	838.5	877.0	941.3	843.7	873.9
80_5	1 058.3	946.4	990.8	1 051.2	952.2	991.5	955.1	872.3	910.8
90_5	1 218.5	1 052.6	1 126.1	1 226.8	1 063.1	1 138.1	1 028.9	929.5	966.7
100_5	1 287.0	1 145.9	1 221.1	1 241.7	1 109.9	1 186.6	1 096.4	965.7	1 042.6
60_8	1 016.2	780.0	912.3	967.6	815.4	895.1	901.7	781.8	847.1
80_8	1 151.5	978.2	1 072.0	1 167.6	1 037.7	1 120.2	1 094.3	931.4	987.1
100_8	1 392.5	1 141.0	1 243.3	1 454.4	1 179.6	1 314.5	1 250.2	1 091.0	1 159.2
120_8	1 500.7	1 296.6	1 382.5	1 442.3	1 270.1	1 359.2	1 348.9	1 168.5	1 243.3
140_8	1 646.0	1 405.0	1 527.4	1 696.6	1 479.4	1 582.1	1 517.7	1 279.6	1 404.0
160_8	1 766.9	1 537.9	1 688.9	1 824.3	1 637.3	1 744.5	1 661.7	1 452.9	1 544.4
100_10	1 394.6	1 112.6	1 260.3	1 377.5	1 107.0	1 269.9	1 293.0	1 080.8	1 186.6
120_10	1 455.3	1 228.7	1 369.4	1 506.1	1 252.9	1 369.5	1 373.6	1 181.0	1 264.3
140_10	1 733.4	1 394.1	1 561.4	1 732.2	1 448.7	1 525.8	1 549.4	1 265.3	1 392.6
160_10	1 751.3	1 481.1	1 651.4	1 792.6	1 537.1	1 670.1	1 667.8	1 368.1	1 494.8
180_10	2 027.6	1 616.6	1 781.4	1 974.7	1 777.8	1 869.6	1 666.6	1 409.1	1 568.4
200_10	2 304.1	1 900.3	2 179.3	2 096.1	1 818.4	1 976.9	1 945.0	1 598.5	1 779.3

Table 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

References 33

1	Dantzig G B, Ramser J H. The Truck Dispatching Problem[J]. Management Science, 1959, 6(1): 80-91.
2	Perboli G, Tadei R, Vigo D. The Two-echelon Capacitated Vehicle Routing Problem: Models and Math-based Heuristics[J]. Transportation Science, 2011, 45(3): 364-380.
3	Wang Meihua, Tian Xuhong, Chang Shan, et al. Hybrid Ant Colony Optimization Algorithm for Two Echelon Vehicle Routing Problem[J]. Procedia Engineering, 2011, 15: 3361-3365.
4	Breunig U, Schmid V, Hartl R F, et al. A Large Neighbourhood Based Heuristic for Two-echelon Routing Problems[J]. Computers & Operations Research, 2016, 76: 208-225.
5	Crainic T G, Perboli G, Mancini S, et al. Two-echelon Vehicle Routing Problem: A Satellite Location Analysis[J]. Procedia - Social and Behavioral Sciences, 2010, 2(3): 5944-5955.
6	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 & Operations Research, 2020, 118: 104919.
7	Marques G, Sadykov R, Deschamps J C, et al. An Improved Branch-cut-and-price Algorithm for the Two-echelon Capacitated Vehicle Routing Problem[J]. Computers & Operations Research, 2020, 114: 104833.
8	He Pengfei, Li Jing. The Two-echelon Multi-trip Vehicle Routing Problem with Dynamic Satellites for Crop Harvesting and Transportation[J]. Applied Soft Computing, 2019, 77: 387-398.
9	Li Hongqi, Wang Haotian, Chen Jun, et al. Two-echelon Vehicle Routing Problem with Time Windows and Mobile Satellites[J]. Transportation Research Part B: Methodological, 2020, 138: 179-201.
10	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.
11	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.
12	闫军, 常乐, 王璐璐, 等. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76.
	Yan Jun, Chang Le, Wang Lulu, et al. A Solution Algorithm for the Problem of Taking Delivery Vehicle Path at the Same Time with Time Window[J]. Industrial Engineering Journal, 2021, 24(5): 72-76.
13	张烜荧, 胡蓉, 钱斌. 超启发式分布估计算法求解带软时间窗的同时取送货车辆路径问题[J]. 控制理论与应用, 2021, 38(9): 1427-1441.
	Zhang Xuanying, Hu Rong, Qian Bin. Hyper-heuristic Estimation of Distribution Algorithm for Solving Vehicle Routing Problem with Simultaneous Pickup and Delivery and Soft Time Windows[J]. Control Theory & Applications, 2021, 38(9): 1427-1441.
14	李博威, 户佐安, 贾叶子, 等. 带软时间窗的同时取送货车辆路径问题研究[J]. 工业工程, 2020, 23(5): 75-81.
	Li Bowei, Hu Zuoan, Jia Yezi, et al. A Research on Vehicle Routing Problem with Simultaneous Pick-up and Delivery and Soft Time Windows[J]. Industrial Engineering Journal, 2020, 23(5): 75-81.
15	张景玲, 刘金龙, 赵燕伟, 等. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
	Zhang Jingling, Liu Jinlong, Zhao Yanwei, et al. Hyper-heuristic for Time-dependent VRP with Simultaneous Delivery and Pickup[J]. Computer Integrated Manufacturing Systems, 2020, 26(7): 1905-1917.
16	赵志学, 李夏苗, 周鲜成. 考虑拥堵区域的多车型绿色车辆路径问题优化[J]. 计算机应用, 2020, 40(3): 883-890.
	Zhao Zhixue, Li Xiamiao, Zhou Xiancheng. Green Vehicle Routing Problem Optimization for Multi-type Vehicles Considering Traffic Congestion Areas[J]. Journal of Computer Applications, 2020, 40(3): 883-890.
17	马艳芳, 应斌, 康凯, 等. 模糊需求下绿色同时取送货问题与算法研究[J]. 计算机工程与应用, 2020, 56(16): 248-257.
	Ma Yanfang, Ying Bin, Kang Kai, et al. Algorithms for Green Simultaneous Pickup and Delivery Problem with Fuzzy Demand[J]. Computer Engineering and Applications, 2020, 56(16): 248-257.
18	Utama D M, Fitria T A, Garside A K. Artificial Bee Colony Algorithm for Solving Green Vehicle Routing Problems with Time Windows[J]. Journal of Physics: Conference Series, 2021, 1933(1): 012043.
19	Sadati M E H, Çatay Bülent. A Hybrid Variable Neighborhood Search Approach for the Multi-depot Green Vehicle Routing Problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2021, 149: 102293.
20	珠兰, 马潇, 刘卓凡. 时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187-194.
	Zhu Lan, Ma Xiao, Liu Zhuofan. Time-dependent Green Vehicle Routing Problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 187-194.
21	李正雯, 胡蓉, 钱斌, 等. 学习型离散排超联赛算法求解带时间窗的绿色多车型两级车辆路径问题[J]. 控制理论与应用, 2023, 40(3): 549-557.
	Li Zhengwen, Hu Rong, Qian Bin, et al. A Learning Discrete Volleyball Premier League Algorithm for Solving Green Two-echelon Heterogeneous-fleet Vehicle Routing Problem with Time Windows[J]. Control Theory & Applications, 2023, 40(3): 549-557.
22	Dorigo M, Maniezzo V, Colorni A. Ant System: Optimization by a Colony of Cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996, 26(1): 29-41.
23	陈希琼, 胡大伟, 杨倩倩, 等. 多目标同时取送货车辆路径问题的改进蚁群算法[J]. 控制理论与应用, 2018, 35(9): 1347-1356.
	Chen Xiqiong, Hu Dawei, Yang Qianqian, et al. An Improved Ant Colony Algorithm for Multi-objective Vehicle Routing Problem with Simultaneous Pickup and Delivery[J]. Control Theory & Applications, 2018, 35(9): 1347-1356.
24	李奇才, 舒远仲, 洪宇轩. 一种蚁群算法与自适应机制的路径规划算法优化[J]. 机械科学与技术, 2022, 41(7): 1095-1101.
	Li Qicai, Shu Yuanzhong, Hong Yuxuan. Optimizing Path Planning Algorithm Based on Ant Colony Algorithm and Adaptive Mechanism[J]. Mechanical Science and Technology for Aerospace Engineering, 2022, 41(7): 1095-1101.
25	Li Yongbo, Soleimani H, Zohal M. An Improved Ant Colony Optimization Algorithm for the Multi-depot Green Vehicle Routing Problem with Multiple Objectives[J]. Journal of Cleaner Production, 2019, 227: 1161-1172.
26	Brito J, Martínez F J, Moreno J A, et al. An ACO Hybrid Metaheuristic for Close-open Vehicle Routing Problems with Time Windows and Fuzzy Constraints[J]. Applied Soft Computing, 2015, 32: 154-163.
27	胡蓉, 陈文博, 钱斌, 等. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
	Hu Rong, Chen Wenbo, Qian Bin, et al. Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem[J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
28	Yang Hongming, Yang Songping, Xu Yan, et al. Electric Vehicle Route Optimization Considering Time-of-use Electricity Price by Learnable Partheno-genetic Algorithm[J]. IEEE Transactions on Smart Grid, 2015, 6(2): 657-666.
29	Jabir E, Panicker V V, Sridharan R. Design and Development of a Hybrid Ant Colony-variable Neighbourhood Search Algorithm for a Multi-depot Green Vehicle Routing Problem[J]. Transportation Research Part D: Transport and Environment, 2017, 57: 422-457.
30	Ji Jinchao, Pang Wei, Zhou Chunguang, et al. A Fuzzy K-prototype Clustering Algorithm for Mixed Numeric and Categorical Data[J]. Knowledge-Based Systems, 2012, 30: 129-135.
31	Mladenović N, Hansen P. Variable Neighborhood Search[J]. Computers & Operations Research, 1997, 24(11): 1097-1100.
32	Belgin O, Karaoglan I, Altiparmak F. Two-echelon Vehicle Routing Problem with Simultaneous Pickup and Delivery: Mathematical Model and Heuristic Approach[J]. Computers & Industrial Engineering, 2018, 115: 1-16.
33	Li Hongqi, Zhang Lu, Tan Lü, et al. The Two-echelon Time-constrained Vehicle Routing Problem in Linehaul-delivery Systems[J]. Transportation Research Part B: Methodological, 2016, 94: 169-188.

[1]	Xinyu Gao, Jing Ni. Optimization of Dynamic Post-disaster Emergency Distribution Network under Perspective of Rescue Efficiency [J]. Journal of System Simulation, 2022, 34(4): 806-816.
[2]	Zhang Qi, Zeng Junjie, Xu Kai, Qin Long, Yin Quanjun. Behavior Modeling for Computer Generated Forces Based on Machine Learning [J]. Journal of System Simulation, 2021, 33(2): 280-287.
[3]	Bi Zhenbo, Zhang Shiyou, Yang Hua, Wu Yuanhong. Survey of Ship Detection in Video Surveillance Based on Shallow Machine Learning [J]. Journal of System Simulation, 2021, 33(12): 2792-2807.
[4]	Chen Ying, Shen Li. Monocular Depth Image Mark-less Pose Estimation Based on Feature Regression [J]. Journal of System Simulation, 2020, 32(2): 269-277.
[5]	Feng Zhenjie, Fan Yu. Chaotic Time Series Prediction Based on Gaussian Processes Mixture [J]. Journal of System Simulation, 2019, 31(7): 1387-1396.
[6]	Yang Yongli, Hu Xiaofeng, Rong Ming, Yin Xiaojing, Wang Wenxiang. Characteristic Index Digging of Combat SoS Capability Based on Machine Learning [J]. Journal of System Simulation, 2019, 31(6): 1048-1054.
[7]	Jia Lishan, Liu Zhe, Sun Yi. Intelligent Diagnosis of Aircraft Electrical Faults Based on RMBP Neural Network [J]. Journal of System Simulation, 2018, 30(9): 3493-3501.
[8]	Tianyu Huang, Yunying Guo. Research of Nonlinear Time Series Prediction Method for Motion Capture [J]. Journal of System Simulation, 2018, 30(7): 2808-2815.
[9]	Li Qi, Hu Xingqi, Zhao Jianmin. Optimizing Control of Total Heat Supply Based on Machine Learning [J]. Journal of System Simulation, 2018, 30(3): 1134-1143.
[10]	Chen Yan, Li Kangshun, Yang Lei. GEP Automatic Clustering Algorithm with Dynamic Penalty Factors [J]. Journal of System Simulation, 2016, 28(4): 806-814.
[11]	Wang Hai, Gao Ling, Chen Dongqi, Ren Jie. Embedded Power Optimization Method Based on User Behavior [J]. Journal of System Simulation, 2015, 27(2): 320-326.