Scientific Program > Talks by Speaker > Álvarez MartÍnez David

A Metaheuristic Approach for the Two-dimensional Loading Vehicle Routing Problem with Heterogeneous Fleet
David Álvarez MartÍnez  1, *@  , Luis Escobar-FalcÓn  2@  , John Escobar  3@  
1 : Universidad de los Andes  (Uniandes)  -  Website
Nº 18A- 12 Bogotá -  Colombia
2 : Universidad Tecnológica de Pereira  (UTP)  -  Website
3 : Pontificia Universidad Javeriana  -  Website
* : Corresponding author

In this work, we present a metaheuristic approach for the 2L-HFVRP with sequential loading constraints. This problem combines two well-known NP-hard problems: the heterogeneous fleet vehicle routing problem (HFVRP) and the two-dimensional sequential loading problem (2D-LP). The proposed approach for the considered problem uses a set of initial solutions generated by a specialized constructive algorithm, trying to get an initial population based on a set of good solution for a TSP problem. A Genetic Algorithm (GA) was developed to manage the search process. Prins' auxiliary graph is used to encode each chromosome. Meanwhile, the feasibility of the solutions regarding the loading constraints is checked by a reactive GRASP algorithm. The GRASP verifies if, for a route, the demand of the customers can be loaded considering sequential loading constraints (multi-drop constraints). Five different crossover methods SJX, PMX, OX, CX, and OBX were implemented. In this case, after applying the crossover methods, the algorithm checks the packing feasibility of the new offspring. The best individuals can be mutated with a randomized shaking procedure. Therefore, the population is updated if better solutions are found. Finally, the proposed approach shows good quality results on benchmarking instances, improving some of the best-known previous solutions.

Online user: 1 RSS Feed