The vehicle routing problem : a hybrid approach using meta-heuristic and exact algorithms

Abstract

The Vehicle Routing Problem (VRP) deals with assigning the optimal set of routes to a fleet of vehicles in order to deliver or provide a service to a set of customers. Apart from being a relevant and significant real-world problem, the fascination with the VRP arises from the fact that it is NP-hard, and hence no exact algorithm which solves large datasets within polynomial time has been found to exist. Therefore, heuristic thinking is often applied to optimise approximate such solutions by designing steps that are likely to lead towards a significant improvement. Although several meta-heuristic algorithms have been found to obtain solutions of high quality, this comes at the cost of large computation times. In real-life applications, where demands are constantly changing and efficiency is of extreme importance, there is the need for quick algorithms that obtain the best possible solution within a reasonable amount of time. This project aims to compare solutions for a real-life set of anonymised customer data using both; a time-consuming Genetic Algorithm (GA), as well as, a quick two-phase heuristic. Furthermore, one of the major factors affecting solution quality arises from errors when approximating the distance between customer locations. Within this project, these errors were reduced by the development of a regression model which converts any calculated Haversine distance into a value more convergent to real-life.