A Hybrid BSO-ACO for Dynamic Vehicle Routing Problem on Real-World Road Networks
Mingde Liu, Qi Song, Qi Zhao, Ling Li, Zhiming Yang, Yingbin Zhang
Abstract
The Dynamic Vehicle Routing Problem With Time Windows (DVRPTW) is an NP-hard problem, which has attracted a lot of attention in the past decades due to its many practical applications in logistics. In order to better describe the actual logistics distribution scenario, this paper studies the DVRPTW based on real road networks and proposes the hybrid BSO-ACO algorithm, which is a combination of Brain Storm Optimization (BSO), Ant Colony Optimization (ACO) and Neighborhood Search (2-opt, relocate, exchange). The algorithm 1) uses ACO to generate new individuals from the same cluster formed by BSO, and increases exploitation by ACO’s pheromone accumulation, 2) harnesses the 2-opt, relocate, and exchange to increase exploration to avoid the algorithm from falling into local optima. We construct a test set by extracting the real road networks in Panyu District, Guangzhou, China and compare the hybrid BSO-ACO algorithm with other algorithms on this test set. The computation experiments show the effectiveness and efficiency of the hybrid BSO-ACO algorithm.