Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/126984
Citations
Scopus Web of Science® Altmetric
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBossek, J.en
dc.contributor.authorCasel, K.en
dc.contributor.authorKerschke, P.en
dc.contributor.authorNeumann, F.en
dc.date.issued2020en
dc.identifier.citationProceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO'20), 2020 / vol.abs/2002.01070, pp.1286-1294en
dc.identifier.isbn9781450371285en
dc.identifier.urihttp://hdl.handle.net/2440/126984-
dc.description.abstractSeveral 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.en
dc.description.statementofresponsibilityJakob Bossek, Katrin Casel, Pascal Kerschke, Frank Neumannen
dc.language.isoenen
dc.publisherAssociation for Computing Machineryen
dc.rights© 2020 Copyright held by the owner/author(s). Publication rights licensed to Association for Computing Machinery.en
dc.source.urihttps://dl.acm.org/doi/proceedings/10.1145/3377930en
dc.subjectEvolutionary algorithms; dynamic optimization; running time analysis; theoryen
dc.titleThe node weight dependent Traveling Salesperson Problem: Approximation algorithms and randomized search heuristicsen
dc.typeConference paperen
dc.identifier.rmid1000014739en
dc.contributor.conferenceGenetic and Evolutionary Computation Conference (GECCO) (08 Jul 2020 - 12 Jul 2020 : Cancún, Mexico)en
dc.identifier.doi10.1145/3377930.3390243en
dc.publisher.placeNew Yorken
dc.identifier.pubid519248-
pubs.library.collectionComputer Science publicationsen
pubs.library.teamDS03en
pubs.verification-statusVerifieden
pubs.publication-statusPublisheden
dc.identifier.orcidBossek, J. [0000-0002-4121-4668]en
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]en
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.