OJTT  >> Vol. 3 No. 1 (January 2014)

    A Discrete Teaching-Learning-Based Optimization Algorithm for the Capacitated Vehicle Routing Problem

  • 全文下载: PDF(375KB) HTML    PP.16-21   DOI: 10.12677/OJTT.2014.31004  
  • 下载量: 2,425  浏览量: 7,088  


刘秀城,刘 琼:华中科技大学,数字制造装备与技术国家重点实验室,武汉

教与学算法车辆路径问题个体解码方法精英策略Teaching-Learning-Based Optimization Algorithm; Vehicle Routing Problem; Solution Decoding Method; Elitist Strategy



 Teaching-learning-based optimization (TLBO) is a recently proposed population based algorithm which simulates the teaching-learning process of the class room. In order to solve the capacitated vehicle routing problem, a discrete teaching-learning-based optimization algorithm (DTLBO) is proposed with a new solution representation and decoding method in this paper. An elitist strategy is introduced in the TLBO algorithm to preserve the best individuals from generation to generation. At the same time, duplicate solutions are modified by mutation on randomly selected dimensions of the duplicate solutions to keep the diversity of the population. Then the 2-OPT local search is combined to improve the local search ability of the hybrid discrete teaching-learning-based optimization. Tested on the several benchmarking capacitated vehicle routing problems, the hybrid discrete teaching-learning-based optimization can achieve the optimal solutions of all selected instances.

刘秀城, 刘琼. 基于离散教与学算法求解车辆路径问题[J]. 交通技术, 2014, 3(1): 16-21. http://dx.doi.org/10.12677/OJTT.2014.31004


[1] Laporte, G. (1992) The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59, 345-358.
[2] Rao, R.V., Savsani, V.J. and Vakharia, D.P. (2011) Teachinglearning-based optimization: A novel method for constrained mechanical design optimization problems. Computer-Aided Design, 43, 303-315.
[3] Waghmare, G. (2013) Comments on “a note on teaching-learning-based optimization algorithm”. Information Sciences, 229, 159169.
[4] Rao, R.V., Savsani, V.J. and Balic, J. (2012) Teaching-learningbased optimization algorithm for un-constrained and constrained real-parameter optimization problems. Engineering Optimization, 44, 1447-1462.
[5] Toğan, V. (2012) Design of planar steel frames using teachinglearning based optimization. Engineering Structures, 34, 225232.
[6] Lin, S. (1965) Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44, 2245-2269.
[7] Ho, W., Ho, G.T., Ji, P., et al. (2008) A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21, 548-557.
[8] Augerat, P., Belenguer, J.M., Benavent, E., et al. (1995) Computational results with a branch and cut code for the capacitated vehicle routing problem. Rapport De Re-cherché-IMAG.
[9] Ai, T.J. and Kachitvichyanukul, V. (2009) Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 56, 380-387.
[10] Moghaddam, B.F., Ruiz, R. and Sadjadi, S.J. (2012) Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm. Computers & Industrial Engineering, 62, 306-317.