A Hybrid BSO-ACS Algorithm for Vehicle Routing Problem with Time Windows on Road Networks

摘要

The Vehicle Routing Problem with Time Windows (VRPTW) is NP-hard which has many real-world applications in logistics and transportation. The traditional VRPTW is defined on a complete graph with customers as nodes, but in the real-world, VRPTWs are more based on road networks. To better simulate the real-world scenarios, this paper studies the VRPTW on road networks. Most researchers solve the VRPTW on road networks by utilizing exact algorithms which can not deal with large size problem. In this paper, a hybrid BSO-ACS algorithm, which combines Brain Storm optimization (BSO), Ant Colony System (ACS) and Local Search (LS), is proposed to solve the VRPTW on road networks. A set of instances based on the road network of southwest Shenzhen, China are generated as benchmark problems. The computational experiments demonstrate the effectiveness of the proposed algorithm.