A Research on Vehicle Routing Problems with Time Windows Based on Density Peak Clustering

doi:10.3969/j.issn.1007-7375.2020.05.008

Abstract

Abstract: A new hybrid algorithm (DGA) combining density peak clustering (DPC) and genetic algorithm (GA) is proposed to solve the vehicle routing problems with time windows. The DPC is used to cluster the customers to reduce the scale of the problem, and then the clustered customers are optimized by GA. The experimental results show that the average value of DGA on the nine data sets is 13.41% and 4.7% higher than simulated annealing (SA) and Tabu search, respectively, and the maximum increase of single data set is 26.4%. It is proved that the algorithm is an efficient method for solving vehicle scheduling problems.

Key words: density peak clustering, vehicle routing problems with time windows (VRPTW), vehicle scheduling, genetic algorithm

CLC Number:

TP391.9

WU Bin, SONG Yan, CHENG Jing, DONG Min. A Research on Vehicle Routing Problems with Time Windows Based on Density Peak Clustering[J]. Industrial Engineering Journal, 2020, 23(5): 58-66,74.

References

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91
[2] ZHANG D, CAI S, YE F, et al. A hybrid algorithm for a vehicle routing problem with realistic constraints[J]. Information Science, 2017, 394: 167-182
[3] CORDEAU J F, MAISCHBERGER M. A parallel iterated tabu search heuristic for vehicle routing problems[J]. Computers & Operations Research, 2012, 39(9): 2033-2050
[4] DEY S, BHATTACHARYYA S, MAULIK U. Quantum inspired genetic algorithm and particle swarm optimization using chaotic map model based interference for gray level image thresholding[J]. Swarm and Evolutionary Computation, 2014, 15: 38-57
[5] VALDEZ F, MELIN P, CASTILLO O. Modular neural networks architecture optimization with a new nature inspired method using a fuzzy combination of particle swarm optimization and genetic algorithms[J]. Information Sciences, 2014, 270: 143-153
[6] ESCOBAR J W, LINFATI R, TOTH P, et al. A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem[J]. Journal of Heuristics, 2014, 20(5): 483-509
[7] BALSEIRO S R, LOISEAU I, RAMONET J. An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows[J]. Computers & Operations Research, 2011, 38(6): 954-966
[8] SZETO W Y, WU Y, HO S C. An artificial bee colony algorithm for the capacitated vehicle routing problem[J]. European Journal of Operational Research, 2011, 215(1): 126-135
[9] ANBUUDAYASANKAR S P, GANESH K, KOH S C L, et al. Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls[J]. Expert Systems with Applications, 2012, 39(3): 2296-2305
[10] KHOUADJIA M R, SARASOLA B, ALBA E, et al. A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests[J]. Applied Soft Computing, 2012, 12(4): 1426-1439
[11] JIANG D, JIANG W, HUANG Z. A hybrid algorithm for vehicle routing problem with time windows[C]. International Symposium on Intelligence Computation & Applications. Berlin, Heidelberg: Springer, . 2008.
[12] XU S H, LIU J P, ZHANG F H, et al. A combination of genetic algorithm and particle swarm optimization for vehicle routing problem with time windows[J]. Sensors, 2015, 15(9): 21033-21053
[13] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496
[14] 邹旭华, 叶晓东, 谭治英. 一种密度峰值聚类的彩色图像分割方法[J]. 小型微型计算机系统, 2017, 38(4): 868-871
ZOU Xuhua, YE Xiaodong, TAN Zhiying. Color image segmentation method based on density peak clustering[J]. Journal of Chinese Computer Systems, 2017, 38(4): 868-871
[15] CHEN Y W, LAI D H, QI H, et al. A new method to estimate ages of facial image for large database[J]. Multimedia Tools and Applications, 2016, 75(5): 2877-2895
[16] WANG B, ZHANG J, DING F, et al. Multi-document news summarization via paragraph embedding and density peak clustering[C]. 2017 International Conference on Asian Language Processing (IALP).Singopore: IEEE, 2017: 260-263.
[17] DING S, DU M, SUN T, et al. An entropy based density peaks clustering algorithm for mixed type data employing fuzzy neighborhood[J]. Knowledge-Based Systems, 2017, 133: 294-313
[18] MEHMOOD R, ZHANG G, BIE R, et al. Clustering by fast search and find of density peaks via heat diffusion[J]. Neurocomputing, 2016, 208: 210-217
[19] TAN K C, LEE L H, ZHU Q L, et al. Heuristic methods for vehicle routing problem with time windows[J]. Artificial Intelligence in Engineering, 2001, 15(3): 281-295
[20] 王洋, 张桂珠. 自动确定聚类中心的密度峰值算法[J]. 计算机工程与应用, 2018, 54(8): 137-142
WANG Yang, ZHANG Guizhu. Automatically determine density of cluster center of peak algorithm[J]. Computer Engineering and Applications, 2018, 54(8): 137-142
[21] WANG S, WANG D, LI C, et al. Clustering by fast search and find of density peaks with data field[J]. Chinese Journal of Electronics, 2016, 25(3): 397-402
[22] BARANY I, VU V. Central limit theorems for Gaussian polytopes[J]. The Annals of Probability, 2007, 35(4): 1593-1621
[23] TORABI S A, GHOMI S M T F, KARIMI B. A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chains[J]. European Journal of Operational Research, 2006, 173(1): 173-189
[24] LAU H C, SIM M, TEO K M. Vehicle routing problem with time windows and a limited number of vehicles[J]. European Journal of Operational Research, 2003, 148(3): 559-569
[25] ROCHAT Y, TAILLARD É D. Probabilistic diversification and intensification in local search for vehicle routing[J]. Journal of Heuristics, 1995, 1(1): 147-167