conference paper published Jakob Bossek author 1029790000-0002-4121-4668 Katrin Casel author Pascal Kerschke author Frank Neumann author 819 department Several important optimization problems in the area of vehicle routing can be seen as variants of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the Traveling Thief Problem (TTP) has gained increasing interest over the last 5 years. In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour. This provides abstractions of important TSP variants such as the Traveling Thief Problem and time dependent TSP variants, and allows to study precisely the increase in difficulty caused by weight dependence. We provide a 3.59-approximation for this weight dependent version of TSP with metric distances and bounded positive weights. Furthermore, we conduct experimental investigations for simple randomized local search with classical mutation operators and two variants of the state-of-the-art evolutionary algorithm EAX adapted to the weighted TSP. Our results show the impact of the node weights on the position of the nodes in the resulting tour. Association for Computing Machinery2020 eng dynamic optimizationevolutionary algorithmsrunning time analysistheory 978-1-4503-7128-510.1145/3377930.3390243 1286–1294 yes J. Bossek, K. Casel, P. Kerschke, and F. Neumann, “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 1286–1294, doi: <a href="https://doi.org/10.1145/3377930.3390243">10.1145/3377930.3390243</a>. Bossek, Jakob, Katrin Casel, Pascal Kerschke, and Frank Neumann. “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1286–1294. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href="https://doi.org/10.1145/3377930.3390243">https://doi.org/10.1145/3377930.3390243</a>. Bossek J, Casel K, Kerschke P, Neumann F. The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’20. Association for Computing Machinery; 2020:1286–1294. doi:<a href="https://doi.org/10.1145/3377930.3390243">10.1145/3377930.3390243</a> @inproceedings{Bossek_Casel_Kerschke_Neumann_2020, place={New York, NY, USA}, series={GECCO ’20}, title={The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics}, DOI={<a href="https://doi.org/10.1145/3377930.3390243">10.1145/3377930.3390243</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Casel, Katrin and Kerschke, Pascal and Neumann, Frank}, year={2020}, pages={1286–1294}, collection={GECCO ’20} } Bossek, Jakob, et al. “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 1286–1294, doi:<a href="https://doi.org/10.1145/3377930.3390243">10.1145/3377930.3390243</a>. J. Bossek, K. Casel, P. Kerschke, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 1286–1294. Bossek, J., Casel, K., Kerschke, P., &#38; Neumann, F. (2020). The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1286–1294. <a href="https://doi.org/10.1145/3377930.3390243">https://doi.org/10.1145/3377930.3390243</a> 488512023-11-14T15:58:53Z2023-12-13T10:43:33Z