Two metaheuristic approaches for solving the multi-compartment vehicle routing problem
- PDF / 1,868,347 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 61 Downloads / 231 Views
Two metaheuristic approaches for solving the multi‑compartment vehicle routing problem Hiba Yahyaoui1,2 · Islem Kaabachi1 · Saoussen Krichen1 · Abdulkader Dekdouk2
Received: 27 September 2017 / Revised: 22 February 2018 / Accepted: 10 May 2018 © The Author(s) 2018
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 NPhardness 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
* Hiba Yahyaoui [email protected] 1
Institut Supérieur de Gestion, LARODEC laboratory, Université de Tunis, Tunis, Tunisia
2
College of Arts and Applied Sciences, Dhofar University, Salalah, Sultanate of Oman
13
H. Yahyaoui et al.
1 Introduction The multi-compartment vehicle routing problem (MCVRP) is an extension of the capacitated vehicle routing problem (CVRP), where the MCVRP consists of designing a set of minimal cost routes to serve demands for different types products of a set of customers. The MCVRP arises frequently in petrol distribution systems. Our focus in this paper will be devoted to procedures in the petroleum company’s operations. (a) Different types of petroleum products have to be delivered by the company to a set of geographically dispersed stations by a fleet of identical tank-trucks departing from a single depot. (b) Each station orders known quantities of one or more products. (c) However, these products are incompatible, they must be transported together in separate compartments of the same truck. (d) Trucks are partitioned into a constant number of compartments with fixed capacities. Each compartment is reserved for only one product. Moreover, all products ordered by each station must be delivered by only one truck. (e) Note that each truck is equipped with a flow metres. This means that the total stations’ demand assigned to any route
Data Loading...
