基于密度峰值聚类的VRPTW问题研究

doi:10.3969/j.issn.1007-7375.2020.05.008

摘要/Abstract

摘要： 提出一种密度峰值聚类 (density peak clustering, DPC)与遗传算法(genetic algorithm, GA)相结合的新型混合算法(density peak clustering with genetic algorithm, DGA)，求解带时间窗的车辆路径问题。首先应用DPC对客户进行聚类以缩减问题规模，再将聚类后的客户用GA进行线路优化。结果表明：DGA在9个数据集上的平均值比模拟退火(simulated annealing, SA)和禁忌搜索(Tabu)分别提高了13.41%和4.7%，单个数据集最大提高了26.4%。这证明了该算法是求解车辆调度问题的高效算法。

关键词: 密度峰值聚类, VRPTW问题, 车辆调度, 遗传算法

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

中图分类号:

TP391.9

吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.

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.

参考文献

[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