Determination of optimal control strategies for TSP by dynamic programming

The traveling salesman problem (TSP) is considered in this paper with the aim of determining optimal control strategies, which provide the optimal decisions as functions of the system state. The adopted TSP model takes into account the travel time between cities and is characterized by the presence of a constraint on the time instant by which a city has to be visited (due date); in this connection, the cost to be minimized is the total weighted tardiness cost, and the decision variables are those concerning the sequence of cities to be visited. The optimal (closed-loop) strategies are determined through a two-step procedure. In the second part of the paper, an extended version of the TSP model, which includes stopover times, is considered, and optimal control strategies are determined also for this model (in this case, through a four-step procedure).