Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study

Consider the following restricted (symmetric or asymmetric) traveling-sales man 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 in which city i precedes city j whenever j greater than or equal to i + k in t he initial ordering. Balas (1996) has proposed a dynamic-programming algori thm 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 i ts close relatives. The algorithm of Balas (1996) constructs a layered network with a layer of nodes for each position in the tour, such that source-sink paths in this ne twork are in one-to-one correspondence with tours that satisfy the postulat ed precedence constraints. In this payer we discuss an implementation of th e dynamic-programming algorithm for the general case when the integer k is replaced with city-specific integers k(j), j = 1,..., n. We discuss applications to, and computational experience with, TSPs with ti me windows, a model frequently used in vehicle routing as well as in schedu ling 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 exponenti al-size neighborhood. For this case, we implement an iterated version of ou r procedure, based on contracting some arcs of the tour produced by a first application of the algorithm, then reapplying the algorithm to the shrunke n graph with the same k.