Applications of a dynamic programming approach to the traveling salesman problem.

摘要

Consider the following restricted (symmetric or asymmetric) traveling salesman problem: given an initial ordering of the n cities and an integer ;The algorithm of (5) constructs a layered network with a layer of nodes for each position in the tour, such that source-sink paths in this network are in 1-1 correspondence with tours that satisfy the postulated precedence constraints. In this paper we discuss an implementation of the dynamic programming algorithm for the general case when the integer k is replaced with city-specific integers ;We discuss applications to, and computational experience with, TSP's 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 Just-in-Time scheduling problems. For TSP's that do not satisfy the postulated precedence constraints, 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.;Finally, we include the specifics for the dynamic programming model when applied to the Prize Collecting TSP, highlighting the differences in the two models for implementation.