A Hybrid Swarm Intelligence Algorithm for Vehicle Routing Problem With Time Windows

Yang Shen; Mingde Liu; Jian Yang; Yuhui Shi; Martin Middendorf

doi:10.1109/ACCESS.2020.2984660

IEEE Access (Jan 2020)

A Hybrid Swarm Intelligence Algorithm for Vehicle Routing Problem With Time Windows

Yang Shen,
Mingde Liu,
Jian Yang,
Yuhui Shi,
Martin Middendorf

Affiliations

Yang Shen: ORCiD; Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China
Mingde Liu: ORCiD; Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China
Jian Yang: ORCiD; Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China
Yuhui Shi: Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China
Martin Middendorf: Department of Computer Science, Leipzig University, Leipzig, Germany

DOI: https://doi.org/10.1109/ACCESS.2020.2984660
Journal volume & issue: Vol. 8
pp. 93882 – 93893

Abstract

Read online

The Vehicle Routing Problem with Time Windows (VRPTW) has drawn considerable attention in the last decades. The objective of VRPTW is to find the optimal set of routes for a fleet of vehicles in order to serve a given set of customers within capacity and time window constraints. As a combinatorial optimization problem, VRPTW is proved NP-hard and is best solved by heuristics. In this paper, a hybrid swarm intelligence algorithm by hybridizing Ant Colony System (ACS) and Brain Storm Optimization (BSO) algorithm is proposed, to solve VRPTW with the objective of minimizing the total distance. In the BSO procedure, both inter-route and intra-route improvement heuristics are introduced. Experiments are conducted on Solomon's 56 instances with 100 customers benchmark, the results show that 42 out of 56 optimal solutions (18 best and 24 competitive solutions) are obtained, which illustrates the effectiveness of the proposed algorithm.

Published in IEEE Access

ISSN: 2169-3536 (Online)
Publisher: IEEE
Country of publisher: United States
LCC subjects: Technology: Electrical engineering. Electronics. Nuclear engineering
Website: https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=6287639

About the journal

Abstract

Keywords