An efficient transformation of the generalized traveling salesman problem

摘要: AbstractThe Generalized Traveling Salesman Problem (GTSP) is a useful model for problems involving decisions of selection and sequence. The problem defined on directed graph in which the nodes have been pregrouped into m mutually exclusive exhaustive nodesets. Arcs are only between belonging to different nodesets with each arc having an associated cost. GTSP finding minimum cost m-arc cycle includes exactly one node from nodeset. In this paper, we show how efficiently transform standard asymmetric (TSP) over same number nodes. transformation allows certain routing involve discrete alternatives be modeled using TSP framework. One such heterogenous Multiple (MTSP) provide formulation.