Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions
J. Bossek, A. Neumann, F. Neumann, in: Parallel Problem Solving from Nature (PPSN XVI), Springer-Verlag, Berlin, Heidelberg, 2020, pp. 346–359.
Download
No fulltext has been uploaded.
Conference Paper
| Published
| English
Author
Bossek, JakobLibreCat 
;
Neumann, Aneta;
Neumann, Frank
;
Neumann, Aneta;
Neumann, FrankDepartment
Abstract
The Traveling Salesperson Problem (TSP) is one of the best-known combinatorial optimisation problems. However, many real-world problems are composed of several interacting components. The Traveling Thief Problem (TTP) addresses such interactions by combining two combinatorial optimisation problems, namely the TSP and the Knapsack Problem (KP). Recently, a new problem called the node weight dependent Traveling Salesperson Problem (W-TSP) has been introduced where nodes have weights that influence the cost of the tour. In this paper, we compare W-TSP and TTP. We investigate the structure of the optimised tours for W-TSP and TTP and the impact of using each others fitness function. Our experimental results suggest (1) that the W-TSP often can be solved better using the TTP fitness function and (2) final W-TSP and TTP solutions show different distributions when compared with optimal TSP or weighted greedy solutions.
Publishing Year
Proceedings Title
Parallel Problem Solving from Nature (PPSN XVI)
Page
346–359
ISBN
LibreCat-ID
Cite this
Bossek J, Neumann A, Neumann F. Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions. In: Parallel Problem Solving from Nature (PPSN XVI). Springer-Verlag; 2020:346–359. doi:10.1007/978-3-030-58112-1_24
Bossek, J., Neumann, A., & Neumann, F. (2020). Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions. Parallel Problem Solving from Nature (PPSN XVI), 346–359. https://doi.org/10.1007/978-3-030-58112-1_24
@inproceedings{Bossek_Neumann_Neumann_2020, place={Berlin, Heidelberg}, title={Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions}, DOI={10.1007/978-3-030-58112-1_24}, booktitle={Parallel Problem Solving from Nature (PPSN XVI)}, publisher={Springer-Verlag}, author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2020}, pages={346–359} }
Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions.” In Parallel Problem Solving from Nature (PPSN XVI), 346–359. Berlin, Heidelberg: Springer-Verlag, 2020. https://doi.org/10.1007/978-3-030-58112-1_24.
J. Bossek, A. Neumann, and F. Neumann, “Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions,” in Parallel Problem Solving from Nature (PPSN XVI), 2020, pp. 346–359, doi: 10.1007/978-3-030-58112-1_24.
Bossek, Jakob, et al. “Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions.” Parallel Problem Solving from Nature (PPSN XVI), Springer-Verlag, 2020, pp. 346–359, doi:10.1007/978-3-030-58112-1_24.
Google Scholar
ISBN Search