Effective hybrid population-based incremental learning algorithm for vehicle routing problem with time windows

MENG Xiang-hu, HU Rong, QIAN Bin

Systems Engineering - Theory & Practice ›› 2014, Vol. 34 ›› Issue (10) : 2701-2709.

PDF(601 KB)
中国科学院数学与系统科学研究院期刊网
PDF(601 KB)
Systems Engineering - Theory & Practice ›› 2014, Vol. 34 ›› Issue (10) : 2701-2709. DOI: 10.12011/1000-6788(2014)10-2701

Effective hybrid population-based incremental learning algorithm for vehicle routing problem with time windows

  • MENG Xiang-hu1,2, HU Rong1,2, QIAN Bin1,2
Author information +
History +

Abstract

A hybrid population-based incremental learning algorithm, namely HPBIL, is proposed to simultaneously minimize the number of vehicles and total travel distance for the vehicle routing problem with time windows (VRPTW). In the presented HPBIL, the improved probability model of PBIL is devised to enhance global exploration ability, and a two-phase local search based on the insert and two points neighborhood exchange methods is developed to strengthen local exploitation ability. Simulation results and comparisons with other algorithms demonstrate the effectiveness and robustness of HPBIL.

Key words

population-based incremental learning algorithm / vehicle routing problem with time windows / probabilistic model / global exploration / local exploitation

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
MENG Xiang-hu , HU Rong , QIAN Bin. Effective hybrid population-based incremental learning algorithm for vehicle routing problem with time windows. Systems Engineering - Theory & Practice, 2014, 34(10): 2701-2709 https://doi.org/10.12011/1000-6788(2014)10-2701

References

[1] Baluja S. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning[R]. Pittsburgh: Carnegie Mellon University, 1994.
[2] Larranaga P, Lozano J A. Estimation of distribution algorithms: A new tool for evolutionary computation[M]. Boston: Kluwer Press, 2002.
[3] 周树德, 孙增圻. 分布估计算法综述[J]. 自动化学报, 2007, 33(2): 113-124.Zhou Shude, Sun Zengqi. A survey on estimation of distribution algorithms[J]. Acta Automatica Sinica, 2007, 33(2): 113-124.
[4] 王圣尧, 王凌, 方晨. 分布估计算法研究进展[J]. 控制与决策, 2012, 27(7): 961-974.Wang Shengyao, Wang Ling, Fang Chen. Advances in estimation of distribution algorithms[J]. Control and Decision, 2012, 27(7): 961-974.
[5] 王丽芳. Copula分布式估计算法[M]. 北京: 机械工业出版社, 2012.Wang Lifang. Copula estimation of distribution algorithm[M]. Beijing: China Machine Press, 2012.
[6] 金炳尧, 蔚承建, 何振亚. PBIL进化算法及其应用[J]. 浙江师大学报:自然科学版, 1999, 8(4): 44-49.Jin Bingyao, Wei Chengjian, He Zhenya. PBIL algorithm and its applications[J]. Journal of Zhejiang Normal University: Natural Science, 1999, 8(4): 44-49.
[7] 汪存富, 蔚承建. 一种新的求解ATSP问题的PBIL算法[J]. 计算机工程与应用, 2005, 41(27): 66-69.Wang Cunfu, Wei Chengjian. A new population-based incremental learning method for the asymmetric TSP[J]. Computer Engineering and Applications, 2005, 41(27): 66-69.
[8] Zhang Q F, Sun J Y, Tsang E, et al. Estimation of distribution algorithm with 2-opt local search for the quadratic assignment problem[C]//Lozana J, Larranaga P, Inza I, et al. Towards a New Evolutionary Computation: Advances in Estimation of Distribution Algorithms. Springer-Verlag, 2006: 281-292.
[9] Salhi A, Rodriguez J A V, Zhang Q F. An estimation of distribution algorithm with guided mutation for a complex flow shop scheduling problem[C]//Proceedings of the Genetic and Evolutionary Computation Conference. London, 2007: 570-576.
[10] Pang H L, Hu K Y, Hong Z Y. Adaptive PBIL algorithm and its application to solve scheduling problems[C]//Proceedings of the IEEE International Conference on Computer Aided Control Systems Design. Munich, 2006: 784-789.
[11] Jarboui B, Eddaly M, Siarry P. An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems[J]. Computers & Operations Research, 2009, 36(9): 2638-2646.
[12] 王圣尧, 王凌, 许烨, 等. 求解混合流水车间调度问题的分布估计算法[J].自动化学报, 2012, 38(3): 437-443.Wang Shengyao, Wang Ling, Xu Ye, et al. An estimation of distribution algorithm for solving hybrid flowshop scheduling problem[J]. Acta Automatica Sinica, 2012, 38(3): 437-443.
[13] Qun J, Yang O, Dong S D. Optimizing curriculum scheduling problem using population based incremental learning algorithm[C]//Proceedings of the Second Workshop on Digital Media and Its Application in Museum and Heritages. Chongqing, 2007: 448-453.
[14] 王凌, 王圣尧, 方晨. 一种求解多维背包问题的混合分布估计算法[J]. 控制与决策, 2011, 26(8): 1121-1125.Wang Ling, Wang Shengyao, Fang Chen. A hybrid distribution estimation algorithm for solving multidimensional knapsack problem[J]. Control and Decision, 2011, 26(8): 1121-1125.
[15] Folly K A. Design of power system stabilizer: A comparison between genetic algorithms (GAs) and population-based incremental[C]//Proceedings of Power Engineering Society General Meeting. Montreal, 2006: 626-633.
[16] Wan S S, Qiu D W. Vehicle routing optimization problem with time constraint using advanced PBIL algorithm[C]//Proceedings of the IEEE International Conference on Service Operations and Logistics, and Informatics. Beijing, 2008: 1394-1398.
[17] Thangiah S R, Nygard K E, Juell P L. A genetic algorithm system for vehicle routing with time windows[C]//Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications. Miami, 1991: 322-328.
[18] Pelikan M, Goldberg D E, Cantu-Paz E. BOA: The Bayesian optimization algorithm[C]//Proceedings of the Genetic and Evolutionary Computation Conference. Orlando, 1999: 525-532.
[19] Marcio H S, Roberto S. An approach using quantum PBIL to solve the traveling salesman problem[C]//Proceedings of the International Conference on Mathematics and Computational Methods Applied to Nuclear Science and Engineering. Brazil, 2011: 1-7.
[20] 李琳, 刘士新, 唐加福. 改进蚁群算法求解带时间窗的车辆路径问题[J]. 控制与决策, 2010, 25(9): 1379-1383.Li Lin, Liu Shixin, Tang Jiafu. Improved ant colony algorithm for solving vehicle routing problem with time windows[J]. Control and Decision, 2010, 25(9): 1379-1383.
[21] Tan X, Zhou X L, Zhang J. Ant colony system for optimizing vehicle routing problem with time windows (VRPTW)[C]//Lecture Notes in Computer Science. Springer, 2006, 4115: 33-38.
[22] 刘霞, 齐欢.带时间窗的动态车辆路径问题的局部搜索算法[J]. 交通运输工程学报, 2008, 8(5): 114-120.Liu Xia, Qi Huan. Local search algorithm of dynamic vehicle routing problem with time window[J]. Journal of Traffic and Transportation Engineering, 2008, 8(5): 114-120.
PDF(601 KB)

407

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉