Paper Info
Title
Determination of optimal control strategies for TSP by dynamic programming
Abstract
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).
Year
DOI
Venue
2008
10.1109/CDC.2008.4739290
CDC
Keywords
Field
DocType
closed loop systems,dynamic programming,optimal control,travelling salesman problems,closed-loop strategies,dynamic programming,optimal control strategies,optimal decisions,traveling salesman problem
Dynamic programming,Decision variables,Mathematical optimization,Tardiness,Optimal control,Computer science,Travelling salesman problem,Travel time
Conference
ISSN
Citations 
PageRank 
0743-1546
1
0.36
References 
Authors
2
3
Name
Order
Citations
PageRank
Michele Aicardi120423.73
Davide Giglio23512.05
Riccardo Minciardi38421.56