Two meta-heuristics for solving the capacitated vehicle routing problem: the case of the Tunisian Post Office

Postal sector has a significant role in promoting and improving the services intended for companies and citizens via its various services and its capacity to provide a communication network which ensures rapidity in collecting, transferring and delivering correspondences, funds and goods across the world. Therefore, optimization of the routing system for collection and transport of letters and parcels constitutes an important component of an effective delivery management system. Generally, postal distribution problems are formulated as a Capacitated vehicle routing problem (CVRP) that consists of designing a set of routes, starting and terminating at a central depot and utilize a set of homogenous vehicles to deliver demands to a set of vertices. The objective is to minimize the total transportation cost. Due to its NP-Hardness, we develop in this paper a hybrid metaheuristic that embeds a Variable Neighborhood Search (VNS) in a Genetic Algorithm (GA) in order to accelerate the convergence of the GA to high quality solutions. This combination aims to take advantage of GA’s strength in the exploration and the VNS’s powerful exploitation of the solution space. We propose to include the VNS in the mutation operator of the GA so that the individual space is enlarged and more diversified. Hence, the hybrid algorithm is able to exploit and explore new regions of the search space. The proposed approach is compared to existing methods while applied on benchmark instances. Empirical results driven on five benchmark datasets with a total of 186 instances show that our proposed approach is very competitive in terms of the obtained solutions. Overall, our experiments illustrated that the Hybrid GA-VNS could be a very efficient method for solving the CVRP and its results are comparable with the results of the state-of-the-art. To operationalize our modeling and solution approach, we considered a real case study: the Tunisian Post Office. Results indicate that the proposed HGA-VNS approach improves considerably the solution regarding the existing methods adopted by the Tunisian Post Office.