A Bumble Bees Mating Optimization algorithm for the Open Vehicle Routing Problem

作者：Marinakis Yannis^*; Marinaki Magdalene

来源：Swarm and Evolutionary Computation, 2014, 15: 80-94.

DOI：10.1016/j.swevo.2013.12.003

• Bumble Bees Mating Optimization
• Open Vehicle Routing Problem
• Iterated Local Search
• Expanding Neighborhood Search

Bumble Bees Mating Optimization (BBMO) algorithm is a relatively new swarm intelligence algorithm that simulates the mating behaviour that a swarm of bumble bees performs. In this paper, an improved version of the BBMO algorithm is presented for successfully solving the Open Vehicle Routing Problem. The main contribution of the paper is that the equation which describes the movement of the drones outside the hive has been replaced by a local search procedure. Thus, the algorithm became more suitable for combinatorial optimization problems. The Open Vehicle Routing Problem (OVRP) is a variant of the classic vehicle routing problem. In the OVRP the vehicles do not return to the depot after the service of the customers. Two sets of benchmark instances were used in order to test the proposed algorithm. The obtained results were very satisfactory as in most instances the proposed algorithm found the best known solutions. More specifically, in the fourteen instances proposed by Christofides, the average quality was 0.09% when a hierarchical objective function was used, where, first, the number of vehicles is minimized and, afterwards, the total travel distance is minimized and the average quality was 0.11% when only the travel distance was minimized while for the eight instances proposed by Li et al. when a hierarchical objective function was used the average quality was 0.06%. The algorithm was, also, compared with a number of metaheuristic, evolutionary and nature inspired algorithms from the literature.

• 出版日期2014-4