Socially inspired algorithms for the traveling thief problem

Bonyadi, Mohammad Reza, Michalewicz, Zbigniew, Przybylek, Michal Roman and Wierzbicki, Adam (2014). Socially inspired algorithms for the traveling thief problem. In: GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference. 16th Genetic and Evolutionary Computation Conference, GECCO 2014, Vancouver, BC, (421-428). July 12, 2014-July 16, 2014. doi:10.1145/2576768.2598367


Author Bonyadi, Mohammad Reza
Michalewicz, Zbigniew
Przybylek, Michal Roman
Wierzbicki, Adam
Title of paper Socially inspired algorithms for the traveling thief problem
Conference name 16th Genetic and Evolutionary Computation Conference, GECCO 2014
Conference location Vancouver, BC
Conference dates July 12, 2014-July 16, 2014
Proceedings title GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference
Journal name Gecco'14: Proceedings of the 2014 Genetic and Evolutionary Computation Conference
Series GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference
Publication Year 2014
Sub-type Fully published paper
DOI 10.1145/2576768.2598367
ISBN 9781450326629
Start page 421
End page 428
Total pages 8
Language eng
Abstract/Summary Many real-world problems are composed of two or more problems that are interdependent on each other. The interaction of such problems usually is quite complex and solving each problem separately cannot guarantee the optimal solution for the overall multi-component problem. In this paper we experiment with one particular 2-component problem, namely the Traveling Thief Problem (TTP). TTP is composed of the Traveling Salesman Problem (TSP) and the Knapsack Problem (KP).We investigate two heuristic methods to deal with TTP. In the first approach we decompose TTP into two sub-problems, solve them by separate modules/ algorithms (that communicate with each other), and combine the solutions to obtain an overall approximated solution to TTP (this method is called CoSolver ). The second approach is a simple heuristic (called density-based heuristic, DH) method that generates a solution for the TSP component first (a version of Lin-Kernighan algorithm is used) and then, based on the fixed solution for the TSP component found, it generates a solution for the KP component (associated with the given TTP). In fact, this heuristic ignores the interdependency between sub-problems and tries to solve the sub-problems sequentially. These two methods are applied to some generated TTP instances of different sizes. Our comparisons show that CoSolver outperforms DH specially in large instances.
Subjects 1703 Computational Theory and Mathematics
2604 Applied Mathematics
Keyword Co-evolution
Heuristics
Metaheuristics
Multi-objective optimization
Non-separable problems
Real-world optimization problems
Traveling thief problem
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status Unknown

Document type: Conference Paper
Collections: ResearcherID Downloads
Scopus Import
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 3 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 6 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 12 Jul 2016, 14:51:05 EST by System User