Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Linear time dynamic-programming 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:
1091-9856(200124)13:1<56:LTDAFN>2.0.ZU;2-N
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 dynamic-programming algorithms for new classes of restricted TSPs: A computational study", INFORMS J C, 13(1), 2001, pp. 56-75

Abstract

Consider the following restricted (symmetric or asymmetric) traveling-salesman problem (TSP): given an initial ordering of the n cities and an integer k > 0, find a minimum-cost 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 dynamic-programming algorithm that solves this problem in time linear in Ir, though exponential in k. Some important real-world 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 source-sink paths in this network are in one-to-one correspondence with tours that satisfy the postulated precedence constraints. In this payer we discuss an implementation of the dynamic-programming algorithm for the general case when the integer k isreplaced with city-specific 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 Justin-Time 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 exponential-size 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