TY - JOUR
T1 - A non-dominated sorting based customized random-key genetic algorithm for the bi-objective traveling thief problem
AU - Chagas, Jonatas B.C.
AU - Blank, Julian
AU - Wagner, Markus
AU - Souza, Marcone J.F.
AU - Deb, Kalyanmoy
N1 - Funding Information:
The authors thank Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) - Finance code 001, Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG), Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), Universidade Federal de Ouro Preto (UFOP), Universidade Federal de Viçosa (UFV) for supporting this research. The authors would also like to thank the HPI Future SOC Lab and its team for enable this research by providing access to their compute infrastructure, https://www.hpi.de/future-soc-lab .
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2021/6
Y1 - 2021/6
N2 - 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 has won first and second places, respectively, thus proving its ability to find high-quality solutions consistently.
AB - 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 has won first and second places, respectively, thus proving its ability to find high-quality solutions consistently.
KW - Combinatorial optimization
KW - Multi-objective optimization
KW - NSGA-II
KW - Real-world optimization problem
KW - Traveling thief problem
UR - http://www.scopus.com/inward/record.url?scp=85091183474&partnerID=8YFLogxK
U2 - 10.1007/s10732-020-09457-7
DO - 10.1007/s10732-020-09457-7
M3 - Article
AN - SCOPUS:85091183474
SN - 1381-1231
VL - 27
SP - 267
EP - 301
JO - Journal of Heuristics
JF - Journal of Heuristics
IS - 3
ER -