An Improved Heuristic Based on Clustering and Genetic Algorithm for Solving the Multi-Depot Vehicle Routing Problem
Fadoua Oudouar1, Abdellah El Fallahi2, El Miloud Zaoui3
1Fadoua Oudouar, EMI, Mohammed V University, Rabat, Morocco.
2Abdellah El Fallahi, ENSA, Abdelmalek Essaadi University, Tetuan, Morocco.
3El Miloud Zaoui, EMI, Mohammed V University, Rabat, Morocco.
Manuscript received on 21 August 2019. | Revised Manuscript received on 25 August 2019. | Manuscript published on 30 September 2019. | PP: 6535-6540 | Volume-8 Issue-3 September 2019 | Retrieval Number: C5256098319/2019©BEIESP | DOI: 10.35940/ijrte.C5256.098319
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: This paper introduces the multi depot vehicle routing problem (MDVRP) with location depot, a hard combinatorial optimization problem arising in several applications. The MDVRP with location depot based on two well-known NP-hard problems: the facility location problem (FLP) and the multi depot vehicle routing problem (MDVRP) with location depot. In the first phase, the problem consists of selecting on which sites to install a warehouse and assigning one and only one warehouse to each customer. In the second phase, for each depot, we search to solve a vehicle routing problem (VRP), multiple vehicles homogenous leave from a single depot and return to the same one. Each route must respect the capacity of each vehicle. The goal of this problem is to minimize the total distances to the performed routes. The MDVRP with location depots is classified as an NP-hard problem. Hence, the use of exact optimization methods may be difficult to solve this problem. In this work, we propose a method to solve it to optimality. The proposed procedure initially uses K-means algorithm to optimize the location selection and customer assignment, then planning the routes from the selected warehouses to a set of customers using Clarke and Wright saving method. The routes from the resulting multi-depot vehicle-routing problem (MDVRP) are improved using a Genetic Algorithm (GA). The proposed approach is tested and compared on a set of twelve benchmark instances from the MDVRP literature. The computational experiments confirm that our heuristic is able to find best solutions.
Keywords: Location Depots, Routing, K-means Method, Clarke and Wright Algorithm, Genetic Algorithm.
Scope of the Article: Clustering