Open AccessA biobjective capacitated vehicle routing problem using metaheuristic ILS and decomposition
Author(s) -
Luis Fernando Galindres-Guancha,
Eliana Mirledy Toro-Ocampo,
Ramón Alfonso Gallego
Publication year - 2021
Publication title -
international journal of industrial engineering computations
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.564
H-Index - 26
eISSN - 1923-2926
pISSN - 1923-2934
DOI - 10.5267/j.ijiec.2021.2.002
Subject(s) - mathematical optimization , vehicle routing problem , sorting , benchmark (surveying) , metaheuristic , multi objective optimization , decomposition , tabu search , set (abstract data type) , computer science , iterated local search , routing (electronic design automation) , genetic algorithm , mathematics , algorithm , computer network , ecology , geodesy , biology , programming language , geography
Vehicle routing problems (VRPs) have usually been studied with a single objective function defined by the distances associated with the routing of vehicles. The central problem is to design a set of routes to meet the demands of customers at minimum cost. However, in real life, it is necessary to take into account other objective functions, such as social functions, which consider, for example, the drivers' workload balance. This has led to growth in both the formulation of multiobjective models and exact and approximate solution techniques. In this article, to verify the quality of the results, first, a mathematical model is proposed that takes into account both economic and work balance objectives simultaneously and is solved using an exact method based on the decomposition approach. This method is used to compare the accuracy of the proposed approximate method in test cases of medium mathematical complexity. Second, an approximate method based on the Iterated Local Search (ILS) metaheuristic and Decomposition (ILS/D) is proposed to solve the biobjective Capacitated VRP (bi-CVRP) using test cases of medium and high mathematical complexity. Finally, the nondominated sorting genetic algorithm (NSGA-II) approximate method is implemented to compare both medium- and high-complexity test cases with a benchmark. The obtained results show that ILS/D is a promising technique for solving VRPs with a multiobjective approach.