Particle swarm optimization for the vehicle routing problem with time windows

Abstract

The logistic industry is by far one of the most important industries within a modern economy. The management of movement of goods is a signifi cant aspect of the Gross Domestic Product (GDP) of all countries, employing millions of people, and its importance continues to increase in an ever more globalised world. One of the most important branches of the logistic industry is the transportation system where the Vehicle Routing Problem (VRP) plays a central role. Solving efficiently the VRP enables the possibility of fi nding effective transportation routes. This study deals with a symmetric and homogeneous Vehicle Routing Problem with Time Windows (VRPTW), a variant of the VRP which is quite relevant to modern distribution and transportation systems. The VRPTW belongs to the class of NP-hard problems, and therefore exact solution methods tend to be inefficient in solving largescale instances. Recent research, however, has greatly improved the performance of exact methods to solve the VRPTW, particularly when applying the Branch-and-Cut algorithm. Exact methods still fall short of being swift and efficient enough when solving large combinatorial optimization problems, therefore heuristic and metaheuristic methods are used to provide fast and good-quality solutions. In this study, a variant of the Particle Swarm Optimization (PSO) metaheuristic will be explored. Solutions provided by both the Branch-and-Cut and the PSO methods when applied to a benchmark dataset will be provided and analysed.