LAUSR

This article proposes extensions of exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows, which are a limited enlargement of the generally referred to as hard time windows. The service of a customer can be started before or after the hard time window at a penalty cost. The addressed problem thus requires the determination of a sequence of customers and their respective service start times in order to minimize the sum of traveling cost with earliness and lateness cost. Computational tests are conducted on a variety of symmetric and asymmetric instances proposed in the literature, and the advantages of flexible windows are stressed.