Application of heuristic methods for solving a meal delivery routing problem

Abstract

Meal delivery has gained a lot of popularity throughout the years, leading to an increase in meal delivery operations worldwide. For this reason, many companies are interested in having a fast, reliable and cost-efficient delivery process. During the last few years, several optimization techniques have been proposed with the aim of solving large delivery routing problems in reasonable time. In this study, data obtained from a local company which provides daily meal delivery service, James Caterers, is used to design routes that the company’s vehicles must follow in order to minimize the total delivery cost. The underlying meal delivery routing problem is a closed and homogeneous Capacitated Vehicle Routing Problem (CVRP) whose objective is to minimize total delivery cost. Since any CVRP is known to be NP-hard, exact methods are only capable of solving small instances in reasonable time. Thus, heuristic methods are typically used for obtaining fast and good-quality solutions. In this study, two constructive heuristics, the Nearest Neighbour (NN) and the Parallel Savings (PS), are used to generate initial routes which are subsequently improved using Local Search (LS) improvement heuristics. Since the LS method has a tendency to get stuck in local optima, the GLS meta-heuristic is applied on the LS routes in order to further improve them. Results show that the PS solutions are better than the NN solutions and that the LS method converges to deep local optima.