A weighted-sum method for solving the bi-objective traveling thief problem. (February 2022)

• Record Type: Journal Article
• Authors: Chagas, Jonatas B.C.; Wagner, Markus
• Is Part Of: Computers & operations research. Volume 138(2022)
• Publication Date: 2022-02
• Subjects: Traveling salesperson problem -- Knapsack problem -- Multi-component problems -- Bi-objective formulations; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105560
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Many real-world optimization problems have multiple interacting components. Each of these can be an NP -hard problem, and they can be in conflict with each other, i.e., the optimal solution for one component does not necessarily represent an optimal solution for the other components. This can be a challenge for single-objective formulations, where the respective influence that each component has on the overall solution quality can vary from instance to instance. In this paper, we study a bi-objective formulation of the traveling thief problem, which has as components the traveling salesperson problem and the knapsack problem. We present a weighted-sum method that makes use of randomized versions of existing heuristics, that outperforms participants on 6 of 9 instances of recent competitions, and that has found new best solutions to 379 single-objective problem instances. Highlights: We approach the Bi-objective Traveling Thief Problem. We propose a heuristic algorithm based on the weighted-sum method for the problem. We analyze the influence of the algorithm's parameters on different types of instances. The proposed algorithm overcomes results presented in two recent optimization competitions.