Catalogo Articoli (Spogli Riviste)
OPAC HELP
Titolo: Linear time dynamicprogramming algorithms for new classes of restricted TSPs: A computational study
Autore: Balas, E; Simonetti, N;
 Indirizzi:
 Carnegie Mellon Univ, Grad Sch Ind Adm, Pittsburgh, PA 15213 USA Carnegie Mellon Univ Pittsburgh PA USA 15213 dm, Pittsburgh, PA 15213 USA Bryn Athyn Coll New Church, Bryn Athyn, PA 19009 USA Bryn Athyn Coll New Church Bryn Athyn PA USA 19009 yn Athyn, PA 19009 USA
 Titolo Testata:
 INFORMS JOURNAL ON COMPUTING
fascicolo: 1,
volume: 13,
anno: 2001,
pagine: 56  75
 SICI:
 10919856(200124)13:1<56:LTDAFN>2.0.ZU;2N
 Fonte:
 ISI
 Lingua:
 ENG
 Soggetto:
 TRAVELING SALESMAN PROBLEM;
 Keywords:
 dynamic programming; algorithms; complexity; heuristics; vehicle routing; traveling salesman problem;
 Tipo documento:
 Article
 Natura:
 Periodico
 Settore Disciplinare:
 Engineering, Computing & Technology
 Citazioni:
 23
 Recensione:
 Indirizzi per estratti:
 Indirizzo: Balas, E Carnegie Mellon Univ, Grad Sch Ind Adm, Pittsburgh, PA 15213 USA Carnegie Mellon Univ Pittsburgh PA USA 15213 burgh, PA 15213 USA



 Citazione:
 E. Balas e N. Simonetti, "Linear time dynamicprogramming algorithms for new classes of restricted TSPs: A computational study", INFORMS J C, 13(1), 2001, pp. 5675
Abstract
Consider the following restricted (symmetric or asymmetric) travelingsalesman problem (TSP): given an initial ordering of the n cities and an integer k > 0, find a minimumcost feasible tour, where a feasible tour is one inwhich city i precedes city j whenever j greater than or equal to i + k in the initial ordering. Balas (1996) has proposed a dynamicprogramming algorithm that solves this problem in time linear in Ir, though exponential in k. Some important realworld problems are amenable to this model or some of its close relatives. The algorithm of Balas (1996) constructs a layered network with a layer ofnodes for each position in the tour, such that sourcesink paths in this network are in onetoone correspondence with tours that satisfy the postulated precedence constraints. In this payer we discuss an implementation of the dynamicprogramming algorithm for the general case when the integer k isreplaced with cityspecific integers k(j), j = 1,..., n. We discuss applications to, and computational experience with, TSPs with time windows, a model frequently used in vehicle routing as well as in scheduling with setup, release and delivery times. We also introduce a new model, the TSP with target times, applicable to JustinTime scheduling problems. Finally for TSPs that have no precedence restrictions, we use the algorithm as a heuristic that finds in linear time a local optimum over an exponentialsize neighborhood. For this case, we implement an iterated version of our procedure, based on contracting some arcs of the tour produced by a first application of the algorithm, then reapplying the algorithm to the shrunken graph with the same k.
ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 20/01/20 alle ore 10:23:58