A non-dominated sorting based customized random-key genetic algorithm for the bi-objective traveling thief problem

Jonatas B. C. Chagas (), Julian Blank (), Markus Wagner (), Marcone J. F. Souza () and Kalyanmoy Deb ()
Additional contact information
Jonatas B. C. Chagas: Universidade Federal de Ouro Preto
Julian Blank: Michigan State University
Markus Wagner: The University of Adelaide
Marcone J. F. Souza: Universidade Federal de Ouro Preto
Kalyanmoy Deb: Michigan State University

Journal of Heuristics, 2021, vol. 27, issue 3, No 1, 267-301

Abstract: 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 has won 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 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-020-09457-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:27:y:2021:i:3:d:10.1007_s10732-020-09457-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-020-09457-7

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().