An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem

doi:10.23919/JSEE.2021.000030

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (2): 365-379.doi: 10.23919/JSEE.2021.000030

• INTELLIGENT OPTIMIZATION AND SCHEDULING • Previous Articles Next Articles

An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem

Yindong SHEN^1,*(), Liwen PENG¹(), Jingpeng LI²()

¹ Key Laboratory of Image Processing and Intelligent Control, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
² Division of Computing Science and Mathematics, University of Stirling, Stirling FK94LA, UK

Received:2020-11-30 Online:2021-04-29 Published:2021-04-29
Contact: Yindong SHEN E-mail:yindong@hust.edu.cn;2537531989@qq.com;jli@cs.stir.ac.uk
About author:|SHEN Yindong was born in 1965. She received her Ph.D. degree from the School of Computing, University of Leeds, UK in 2001. She is a professor in the School of Artificial Intelligence and Automation, Huazhong University of Science and Technology. Her research interests include operation and optimization, vehicle routing optimization, public transport vehicle scheduling, and crew scheduling.E-mail: yindong@hust.edu.cn||PENG Liwen was born in 1994. He is currently working toward his M.S. degree in Huazhong University of Science and Technology, China. His research interests are intelligent computing, multi-compartment vehicle routing optimization and electric vehicle routing optimization.E-mail: 2537531989@qq.com||LI Jingpeng was born in 1969. He received his Ph.D. degree from University of Leeds, UK in 2002. He is a reader at the Division of Computer Science and Mathematics, University of Stirling, UK. His research focuses on computational search methodologies and models emerging from the complexity and uncertainty of real-world optimization problems and decision support systems.E-mail: jli@cs.stir.ac.uk
Supported by:
This work was supported by the National Natural Science Foundation of China (71571076) and the National Key R&D Program for the 13th-Five-Year-Plan of China (2018YFF0300301);This work was supported by the National Natural Science Foundation of China (71571076) and the National Key R&D Program for the 13th-Five-Year-Plan of China (2018YFF0300301)

Abstract

Abstract:

The multi-compartment electric vehicle routing problem (EVRP) with soft time window and multiple charging types (MCEVRP-STW&MCT) is studied, in which electric multi-compartment vehicles that are environmentally friendly but need to be recharged in course of transport process, are employed. A mathematical model for this optimization problem is established with the objective of minimizing the function composed of vehicle cost, distribution cost, time window penalty cost and charging service cost. To solve the problem, an estimation of the distribution algorithm based on Lévy flight (EDA-LF) is proposed to perform a local search at each iteration to prevent the algorithm from falling into local optimum. Experimental results demonstrate that the EDA-LF algorithm can find better solutions and has stronger robustness than the basic EDA algorithm. In addition, when comparing with existing algorithms, the result shows that the EDA-LF can often get better solutions in a relatively short time when solving medium and large-scale instances. Further experiments show that using electric multi-compartment vehicles to deliver incompatible products can produce better results than using traditional fuel vehicles.

Key words: multi-compartment vehicle routing problem, electric vehicle routing problem (EVRP), soft time window, multiple charging type, estimation of distribution algorithm (EDA), Lévy flight

Yindong SHEN, Liwen PENG, Jingpeng LI. An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem[J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 365-379.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Table 1

Table 2

Table 3

Table 4

Fig.4

Table 5

Fig.5

Fig.6

Fig.7

Table 6

Table 7

References 46

1	PANG Y, LUO H, XING L N, et al A survey of vehicle routing optimization problems and solution methods. Control Theory & Applications, 2019, 36 (10): 1573- 1584.
2	CHEN L, LIU Y, LANGEVIN A A multi-compartment vehicle routing problem in cold-chain distribution. Computers & Operations Research, 2019, 111, 58- 66.
3	MOFID-NAKHAEE E, BARZINPOUR F A multi-compartment capacitated arc routing problem with intermediate facilities for solid waste collection using hybrid adaptive large neighborhood search and whale algorithm. Waste Management & Research, 2019, 37 (1): 38- 47.
4	ZHANG Y K, SUN L J, HU X P Multi-compartment vehicle dispatching and routing for product oil distribution. Operations Research and Management Science, 2017, 26 (7): 1- 9.
5	ABDULKADER M M S, GAJPAL Y, ELMEKKAWY T Y Hybridized ant colony algorithm for the multi-compartment vehicle routing problem. Applied Soft Computing, 2015, 37, 196- 203. doi: 10.1016/j.asoc.2015.08.020
6	BROWN G G, GRAVES G W Real-time dispatch of petroleum tank trucks. Management Science, 1981, 27 (1): 19- 32. doi: 10.1287/mnsc.27.1.19
7	OSTERMEIER M, HUEBNER A Vehicle selection for a multi-compartment vehicle routing problem. European Journal of Operational Research, 2018, 269 (2): 682- 694. doi: 10.1016/j.ejor.2018.01.059
8	GOCMEN E, EROL R Location and multi-compartment capacitated vehicle routing problem for blood banking system. International Journal of Engineering Technologies, 2018, 4 (1): 1- 12.
9	KANDILLER L, ELIIYI D T, TASAR B A multi-compartment vehicle routing problem for livestock feed distribution. Proc. of the Operations Research Conference, 2017, 149- 155.
10	PAREDES-BELMAR G, MARIANOV V, BRONFMAN A, et al A milk collection problem with blending. Transportation Research Part E−Logistics and Transportation Review, 2016, 94, 26- 43. doi: 10.1016/j.tre.2016.07.006
11	KESKIN M, LAPORTE G, CATAY B Electric vehicle routing problem with time-dependent waiting times at recharging stations. Computers & Operations Research, 2019, 107, 77- 94.
12	SHI Y, BOUDOUH T, GRUNDER O A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert Systems with Applications, 2017, 72, 160- 176. doi: 10.1016/j.eswa.2016.12.013
13	KESKIN M, CATAY B A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Computers & Operations Research, 2018, 100, 172- 188.
14	PEREZ-RODRIGUEZ R, HERNANDEZ-AGUIRRE A Bivariate dependency for the vehicle routing problem with time windows. International Journal of Industrial Engineering-Theory Applications and Practice, 2020, 27 (3): 473- 499.
15	PEREZ-RODRIGUEZ R, HERNANDEZ-AGUIRRE A A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows. Computers & Industrial Engineering, 2019, 130, 75- 96.
16	HENKE T, SPERANZA M G, WAESCHER G A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes. Annals of Operations Research, 2019, 275 (2): 321- 338. doi: 10.1007/s10479-018-2938-4
17	CHEN J M, SHI J A multi-compartment vehicle routing problem with time windows for urban distribution—a comparison study on particle swarm optimization algorithms. Computers & Industrial Engineering, 2019, 133, 95- 106.
18	ZHAN H X, WANG X P, SUN Z L, et al Variable neighborhood search for the multi-objective multi-compartment optimization of refined products distribution. Systems Engineering—Theory & Practice, 2019, 39 (10): 2660- 2675.
19	WANG X, JI Q K, HU X P A hybrid guided reactive tabu search for heterogeneous fixed fleet multi-compartment vehicle routing problem. Engineering Management, 2016, 30 (3): 179- 187.
20	GOODSON J C A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands. European Journal of Operational Research, 2015, 241 (2): 361- 369. doi: 10.1016/j.ejor.2014.09.031
21	LU S C, WANG X F Discrete firefly algorithm for clustered multi-temperature joint distribution with fuzzy travel times. International Journal of Computational Intelligence Systems, 2018, 11 (1): 195- 205. doi: 10.2991/ijcis.11.1.15
22	BARCO J, GUERRA A, MUNOZ L, et al Optimal routing and scheduling of charge for electric vehicles: a case study. Mathematical Problems in Engineering, 2017, 2017 (Pt.11): 1- 16.
23	VERMA A Electric vehicle routing problem with time windows, recharging stations and battery swapping stations. Euro Journal on Transportation and Logistics, 2018, 7 (4): 415- 451. doi: 10.1007/s13676-018-0136-9
24	SHAO S, GUAN W, RAN B, et al Electric vehicle routing problem with charging time and variable travel time. Mathematical Problems in Engineering, 2017, 2017 (2): 1- 13.
25	CATAY B, KESKIN M The impact of quick charging stations on the route planning of electric vehicles. Proc. of the IEEE Symposium on Computers and Communications, 2017, 152- 157.
26	LIN J, ZHOU W, WOLFSON O Electric vehicle routing problem. Transportation Research Procedia, 2016, 12, 508- 521. doi: 10.1016/j.trpro.2016.02.007
27	KANCHARLA S R, RAMADURAI G. An adaptive large neighborhood search approach for electric vehicle routing with load-dependent energy consumption. Transportation in Developing Economies, 2018. DOI: 10.1007/s40890-018-0063-3.
28	ZHAO M T, LU Y W. A heuristic approach for a real-world EV routing problem. Algorithms, 2019. DOI: 10.3390/a12020045.
29	MONTOYA A, GUERET C, MENDOZA J E, et al The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B—Methodological, 2017, 103, 87- 110. doi: 10.1016/j.trb.2017.02.004
30	KESKIN M, CATAY B Partial recharge strategies for the EV routing problem with time windows. Transportation Research Part C—Emerging Technologies, 2016, 65, 111- 127. doi: 10.1016/j.trc.2016.01.013
31	DESAULNIERS G, ERRICO F, IRNICH S, et al Exact algorithms for electric vehicle-routing problems with time windows. Operations Research, 2016, 64 (6): 1388- 1405. doi: 10.1287/opre.2016.1535
32	LIU R, TAO Y Y, XIE X L An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits. Computers & Operations Research, 2019, 101, 250- 262.
33	WU C G, WANG L, ZHENG X L An effective estimation of distribution algorithm for solving uniform parallel machine scheduling problem with precedence constraints. Proc. of the IEEE Congress on Evolutionary Computation, 2016, 2626- 2632.
34	SHEN J N, WANG L, WANG S Y A bi-population EDA for solving the no-idle permutation flow-shop scheduling problem with the total tardiness criterion. Knowledge-Based Systems, 2015, 74, 167- 175. doi: 10.1016/j.knosys.2014.11.016
35	VISWANATHAN G M, AFANASYEV V, BULDYREV S V, et al Levy flight search patterns of wandering albatrosses. Nature, 1996, 381 (6581): 413- 415. doi: 10.1038/381413a0
36	TSALLIS C, LEVY S V F, SOUZA A M C, et al Statistical-mechanical foundation of the ubiquity of Levy distributions in nature. Physical Review Letters, 1995, 75 (20): 3589- 3593. doi: 10.1103/PhysRevLett.75.3589
37	SUMPUNSRI S, PUANGDOWNREONG D Multiobjective Levy-flight firerly algorithm for optimal PIDA controller design. International Journal of Innovative Computing Information and Control, 2020, 16 (1): 173- 187.
38	SHI W G, GUO M Network delay prediction based on model of modified ensemble empirical mode decomposition-permutation entropy and cuckoo search-wavelet neural network. Systems Engineering and Electronics, 2020, 42 (1): 184- 190.
39	OUAARAB A, AHIOD B, YANG X S, et al Discrete cuckoo search algorithm for job shop scheduling problem. Proc. of the IEEE International Symposium on Intelligent Control, 2014, 1872- 1876.
40	REED M, YIANNAKOU A, EVERING R An ant colony algorithm for the multi-compartment vehicle routing problem. Applied Soft Computing, 2014, 15, 169- 176. doi: 10.1016/j.asoc.2013.10.017
41	SOLOMON M M Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 1987, 35 (2): 254- 265. doi: 10.1287/opre.35.2.254
42	WANG Q Y, LI Y, LI H Battery swap station location-routing problem of electric vehicles with soft time windows. Industrial Engineering and Management, 2019, 24 (3): 99- 106.
43	MAVROVOUNIOTIS M, ELLINAS G, POLYCARPOU M Ant colony optimization for the electric vehicle routing problem. Proc. of the 8th IEEE Symposium Series on Computational Intelligence, 2018, 1234- 1241.
44	GUO Z F, LI Y, JIANG X D, et al The electric vehicle routing problem with time windows using genetic algorithm. Proc. of the 2nd IEEE Advanced Information Technology, Electronic and Automation Control Conference, 2017, 635- 639.
45	KOCH H, HENKE T, WASCHER G. A genetic algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes. https://www.fww.ovgu.deffww_media/femm/femm_2016/2016_04.pdf.
46	FENG W, FIGLIOZZI M A Conventional vs electric commercial vehicle fleets: a case study of economic and technological factors affecting the competitiveness of electric commercial vehicles in the USA. Proc. of the 7th International Conference on City Logistics, 2012, 702- 711.

Parameter	Description	Value	Reference
${\beta _1}$	Slow charging rate	0.625 kW·h/min	[24]
${\beta _2}$	Regular charging rate	1.25 kW·h/min
${\beta _3}$	Fast charging rate	5 kW·h/min
$e$	Per-unit distance power consumption	1 kW·h/km	[42]
${c_2}$	Per-unit distance distribution cost	0.6 yuan/km	[42]
${v_0}$	Vehicle speed	50 km/h	[43]
${c_3}$	Per-unit early arrival penalty cost	20 yuan/h	[44]
${c_4}$	Per-unit delay arrival penalty cost	30 yuan/h	[44]
${c_{e1}}$	Per-unit service cost for slow charging	0.1 yuan/kW·h	NDRC Document No. 1688 of 2014
${c_{e2}}$	Per-unit service cost for regular charging	0.2 yuan/kW·h
${c_{e3}}$	Per-unit service cost for fast charging	0.3 yuan/kW·h
${c_1}$	Per-unit fixed vehicle cost	1 000 yuan	This paper
$B$	Battery capacity of the vehicles	150 kW·h
Q₁:Q₂	The ratio of compartment capacity	1800 kg:600 kg

Experiment number	Factor				RV
Experiment number	${P_ - }{\rm{size}}$	$\eta $	$\alpha (0)$	$b$	RV
1	1	1	1	1	3 888.195
2	1	2	2	2	3 870.645
3	1	3	3	3	3 898.374
4	1	4	4	4	3 888.832
5	2	1	2	3	3 886.850
6	2	2	1	4	3 861.283
7	2	3	4	1	3 884.690
8	2	4	3	2	3 846.059
9	3	1	3	4	3 900.421
10	3	2	4	3	3 822.744
11	3	3	1	2	3 869.779
12	3	4	2	1	3 794.425
13	4	1	4	2	3 895.055
14	4	2	3	1	3 815.151
15	4	3	2	4	3 760.516
16	4	4	1	3	3 903.280

Level	${P_ - }{\rm{size}}$	$\eta $	$\alpha (0)$	$b$
1	3 886.512	3 892.630	3 880.634	3 845.615
2	3 869.721	3 842.456	3 828.109	3 870.385
3	3 846.842	3 853.340	3 865.001	3 877.812
4	3 843.501	3 858.149	3 872.830	3 852.763
Delta	43.011	50.174	52.525	32.197
Rank	3	2	1	4

Instance	${P_ - }{\rm{size}}$	$\eta $	$\alpha (0)$	$b$
25C101	150	0.2	0.3	0.1
25R101	150	0.3	0.3	0.1
25RC101	150	0.2	0.3	0.2
50C101	200	0.2	0.5	0.1
50R101	150	0.2	0.5	0.1
50RC101	200	0.2	0.5	0.1
100C101	150	0.3	0.7	0.1
100R101	150	0.2	0.7	0.2
100RC101	200	0.3	0.7	0.1

Instance	EDA-LF	GA	$ {\Delta _{{\rm{E - G}}}}$
25C101	3 641.12	3 526.66	114.46
25C102	3 452.69	3 366.02	86.67
25C103	3 310.58	3 242.19	68.39
25R101	3 838.06	3 857.14	?19.08
25R102	3 597.19	3 485.98	111.21
25R103	3 385.55	3 220.15	165.4
25RC101	3 952.84	3 854.62	98.22
25RC102	3 785.50	3 639.48	146.02
25RC103	3 707.64	3 614.13	93.51
50C101	6 953.58	7 137.88	?184.30
50C102	6 164.64	6 311.49	?146.85
50C103	5 967.82	5 871.14	96.68
50R101	8 781.23	9 123.15	?341.92
50R102	7 924.20	8 243.74	?319.54
50R103	7 426.37	7 593.56	?167.19
50RC101	8 825.67	8 981.91	?156.24
50RC102	8 502.28	8 637.63	?135.35
50RC103	8 066.88	8 269.33	?202.45
100C101	19 334.72	19 794.61	?459.89
100C102	17 026.35	17 748.72	?722.37
100C103	15 329.84	15 822.68	?492.84
100R101	18 446.71	18 940.55	?493.84
100R102	17 223.95	17 670.46	?446.51
100R103	16 176.47	16 639.92	?463.45
100RC101	20 320.62	21 047.13	?726.51
100RC102	19 771.89	20 241.48	?469.59
100RC103	18 596.53	19 310.20	?713.67

An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 15

References 46

Related Articles 0

Recommended Articles

Metrics

Comments

Parameter	Factor level
Parameter	1	2	3	4
${P_ - }{\rm{size}}$	50	100	150	200
$\eta $	10	20	30	40
α(0)	0.1	0.3	0.5	0.7
$b$	10	20	30	40

Instance	MCEVRP	MCFVRP	RPD/%
25C101	3 712.534	4 079.279	?8.99
25C102	3 483.933	3 786.238	?7.98
25C103	3 368.160	3 627.447	?7.15
25R101	3 934.316	4 147.696	?5.14
25R102	3 645.238	3 784.554	?3.68
25R103	3 506.247	3 578.674	?2.02
25RC101	4 075.413	4 415.153	?7.69
25RC102	3 879.339	4 309.977	?9.99
25RC103	3 801.743	3 994.450	?4.82
50C101	6 982.788	7 931.015	?11.9
50C102	6 285.829	7 225.835	?13.0
50C103	6 049.459	6 838.175	?11.5
50R101	8 887.140	9 030.583	?1.59
50R102	8 085.606	8 273.162	?2.27
50R103	7 612.346	7 786.252	?2.23
50RC101	9 101.333	9 658.091	?5.76
50RC102	8 695.609	9 190.063	?5.38
50RC103	8 271.000	8 873.101	?6.79
100C101	18 728.26	20 856.47	?10.2
100C102	16 343.28	18 395.62	?11.1
100C103	14 874.99	16 986.01	?12.4
100R101	17 862.33	18 808.19	?5.03
100R102	16 879.04	17 473.99	?3.40
100R103	15 676.09	16 119.14	?2.75
100RC101	19 755.47	21 048.47	?6.14
100RC102	19 195.64	19 948.48	?3.77
100RC103	17 755.99	18 616.22	?4.62
Average	?	?	?6.57