Enhancing Vehicle Routing Solutions: Custom Heuristic and Local Search Algorithms for Capacitated Vehicle Routing Problems

Abstract

When compared to traditional heuristics algorithms, local search algorithms offer significant computational advantages to solve combinatorial optimisation problems, such as the Vehicle Routing Problem (VRP). However, the actual usefulness of existing searching-based algorithms is generally limited by their inability to handle a fixed number of vehicles. These algorithms often avoid the challenging issue of assigning customers to a fixed number of available vehicles. However, in practical situations, logistic service providers need to find solutions that work with a certain fleet size and can quickly adjust to sudden changes in the number of vehicles or solve the Capacitated Vehicle Routing Problem (CVRP). Therefore, the main goal of this paper is to apply custom heuristic algorithms to solve the CVRP to determine the best vehicle delivery routes while keeping in mind each vehicle’s maximum carrying capacity. The problem is initially solved by the heuristics presented in this paper, and subsequently, specific local search algorithms are used to further improve the heuristics’ findings. The implementation of two heuristic algorithms includes one that is based on the nearest-neighbour strategy and another that is motivated by clustering nearby customers. Two custom local search algorithms are also introduced. The proposed algorithms are compared to well-used benchmarks that have undergone extensive testing and validation.