Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/128593
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | A non-dominated sorting based customized random-key genetic algorithm for the bi-objective traveling thief problem |
Author: | Chagas, J.B.C. Blank, J. Wagner, M. Souza, M.J.F. Deb, K. |
Citation: | Journal of Heuristics, 2021; 27(3):297-301 |
Publisher: | Springer |
Issue Date: | 2021 |
ISSN: | 1381-1231 1572-9397 |
Statement of Responsibility: | Jonatas B. C. Chagas, Julian Blank, Markus Wagner, Marcone J. F. Souza, Kalyanmoy Deb |
Abstract: | In this paper, we propose a method to solve a bi-objective variant of the well-studied traveling thief problem (TTP). The TTP is a multi-component problem that combines two classic combinatorial problems: traveling salesman problem and knapsack problem. We address the BI-TTP, a bi-objective version of the TTP, where the goal is to minimize the overall traveling time and to maximize the profit of the collected items. Our proposed method is based on a biased-random key genetic algorithm with customizations addressing problem-specific characteristics. We incorporate domain knowledge through a combination of near-optimal solutions of each subproblem in the initial population and use a custom repair operator to avoid the evaluation of infeasible solutions. The bi-objective aspect of the problem is addressed through an elite population extracted based on the non-dominated rank and crowding distance. Furthermore, we provide a comprehensive study showing the influence of each parameter on the performance. Finally, we discuss the results of the BI-TTP competitions at EMO-2019 and GECCO-2019 conferences where our method haswon first and second places, respectively, thus proving its ability to find high-quality solutions consistently. |
Keywords: | Combinatorial optimization; multi-objective optimization; real-world optimization problem; traveling thief problem; NSGA-II |
Description: | Published: 20 September 2020 |
Rights: | © Springer Science+Business Media, LLC, part of Springer Nature 2020 |
DOI: | 10.1007/s10732-020-09457-7 |
Published version: | http://dx.doi.org/10.1007/s10732-020-09457-7 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.