Two metaheuristic approaches for solving the multi-compartment vehicle routing problem

Hiba Yahyaoui (), Islem Kaabachi, Saoussen Krichen and Abdulkader Dekdouk
Additional contact information
Hiba Yahyaoui: Université de Tunis
Islem Kaabachi: Université de Tunis
Saoussen Krichen: Université de Tunis
Abdulkader Dekdouk: Dhofar University

Operational Research, 2020, vol. 20, issue 4, No 7, 2085-2108

Abstract: Abstract We address in this paper a multi-compartment vehicle routing problem (MCVRP) that aims to plan the delivery of different products to a set of geographically dispatched customers. The MCVRP is encountered in many industries, our research has been motivated by petrol station replenishment problem. The main objective of the delivery process is to minimize the total driving distance by the used trucks. The problem configuration is described through a prefixed set of trucks with several compartments and a set of customers with demands and prefixed delivery. Given such inputs, the minimization of the total traveled distance is subject to assignment and routing constraints that express the capacity limitations of each truck’s compartment in terms of the pathways’ restrictions. For the NP-hardness of the problem, we propose in this paper two algorithms mainly for large problem instances: an adaptive variable neighborhood search (AVNS) and a Partially Matched Crossover PMX-based Genetic Algorithm to solve this problem with the goal of ensuring a better solution quality. We compare the ability of the proposed AVNS with the exact solution using CPLEX and a set of benchmark problem instances is used to analyze the performance of the both proposed meta-heuristics.

Keywords: Metaheuristics; Multi-compartment; Vehicle routing problem; Variable neighborhood search; Genetic algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s12351-018-0403-4 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:20:y:2020:i:4:d:10.1007_s12351-018-0403-4

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

DOI: 10.1007/s12351-018-0403-4

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 ().