基于离散教与学算法求解车辆路径问题

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

摘要: 教与学算法是一种通过模拟班级授课的“教”与“学”过程来实现对连续优化模型进行优化的群体智能算法。为了求解车辆路径问题，提出一种离散的教与学算法，设计了一种新的个体解码方法对教与学算法的实数个体进行解码。为了尽可能不丢失迭代中的最优解，在离散教与学算法中引入精英策略，同时通过随机变异的方法对重复的个体进行变异以保持种群个体的多样性。最后将2-OPT局部搜索与所提的离散教与学算法混合以提高算法的局部搜索能力。对车辆路径问题的基准实例测试表明，所提的离散教与学算法可以获得基准实例的当前最优解。

Abstract:  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.