An Optimal Control Theory for the Traveling Salesman Problem and Its Variants
Loading...
Authors
Ross, I.M.
Proulx, R.J.
Karpenko, M.
Subjects
traveling salesman problems
functionals
optimal control theory
neighborhoods
forbidden neighborhoods
profits
time window
routing
functionals
optimal control theory
neighborhoods
forbidden neighborhoods
profits
time window
routing
Advisors
Date of Issue
2020-05
Date
Publisher
ArXiv
Language
Abstract
We show that the traveling salesman problem (TSP) and its many variants may be modeled as functional optimization problems over a graph. In this formulation, all vertices and arcs of the graph are functionals; i.e., a mapping from a space of measurable functions to the field of real numbers. Many variants of the TSP, such as those with neighborhoods, with forbidden neighborhoods, with time-windows and with profits, can all be framed under this construct. In sharp contrast to their discrete-optimization counterparts, the modeling constructs presented in this paper represent a fundamentally new domain of analysis and computation for TSPs and their variants. Beyond its apparent mathematical unification of a class of problems in graph theory, the main advantage of the new approach is that it facilitates the modeling of certain application-specific problems in their home space of measurable functions. Consequently, certain elements of economic system theory such as dynamical models and continuoustime cost/profit functionals can be directly incorporated in the new optimization problem formulation. Furthermore, subtour elimination constraints, prevalent in discrete optimization formulations, are naturally enforced through continuity requirements. The price for the new modeling framework is nonsmooth functionals. Although a number of theoretical issues remain open in the proposed mathematical framework, we demonstrate the computational viability of the new modeling constructs over a sample set of problems to illustrate the rapid production of end-to-end TSP solutions to extensively-constrained practical problems.
Type
Preprint
Description
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funding
Format
24 p.
Citation
Ross, Isaac Michael, Ronald J. Proulx, and Mark Karpenko. "An Optimal Control Theory for the Traveling Salesman Problem and Its Variants." arXiv preprint arXiv:2005.03186 (2020).
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.