A discrete Bat Algorithm for the vehicle routing problem with time windows

摘要

Bat Algorithm (BA) is a new bio-inspired meta-heuristic based on the echolocation behavior of microbats when searching for their prey in nature. Since its first implementation in 2010, BA has been used to solve a broad range of continuous optimization problems. In this paper, we present a new hybrid algorithm that executes a discrete version of the bat algorithm in combination with the Large Neighborhood Search (LNS) framework to solve the well-known Vehicle Routing Problem with Time Windows (VRPTW). Our proposed algorithm, named BA-LNS aims at enhancing the performance of the discrete BA using the destroy and repair paradigm of the LNS, allowing the bat to discover a large part of the solution space. To justify that our proposal is a promising approximation algorithm, we tested its performance on 56 instances of Solomon's benchmark and compared the convergence with the best-known solutions in the literature. Computational results indicate that our proposed approach has a satisfactory performance in solving VRPTW instances.