Analysis of the Traveling Salesman Problem with Flexible Colors

This paper analizes a new variant of the Traveling Salesman Problem (TSP) in which nodes belong to various color classes and each color class must be visited as an entity. We show that the problem is APX-hard and provide exact solutions for special cases and a two-phase heuristic for the general case. Lastly, we analyze the worst case and asymptotic performanc of the heuristic

MoreLess

Year of publication:	2010
Authors:	Roemer, Thomas
Other Persons:	Ahmadi, Reza (contributor) ; Dasu, Sriram (contributor)
Publisher:	[2010]: [S.l.] : SSRN
Subject:	Rundreiseproblem \| Travelling salesman problem \| Tourenplanung \| Vehicle routing problem \| Theorie \| Theory \| Algorithmus \| Algorithm \| Heuristik \| Heuristics

Extent:	1 Online-Ressource (16 p)
Series:	Marshall School of Business Working Paper ; No. FBE 12-10
Type of publication:	Book / Working Paper
Language:	English
Notes:	Nach Informationen von SSRN wurde die ursprüngliche Fassung des Dokuments February 1, 2010 erstellt
Other identifiers:	10.2139/ssrn.1571842 [DOI]
Source:	ECONIS - Online Catalogue of the ZBW

Persistent link: https://ebvufind01.dmz1.zbw.eu/10013146709