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

Ines Sbai (), Saoussen Krichen () and Olfa Limam ()
Additional contact information
Ines Sbai: Université de Tunis
Saoussen Krichen: Université de Tunis
Olfa Limam: Université de Tunis El Manar

Operational Research, 2022, vol. 22, issue 1, No 18, 507-549

Abstract: Abstract 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.

Keywords: Distribution; Post office routing problem; Genetic algorithm; Variable neighborhood search; Hybrid GA-VNS (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-019-00543-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:22:y:2022:i:1:d:10.1007_s12351-019-00543-8

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-019-00543-8

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().