An Optimal Control Theory for the Traveling Salesman Problem and Its Variants

Although continuity of a label space trajectory is sufficiently smooth to generate a Hamiltonian cycle (Cf. Theorem 1), we now consider the space of absolutely continuous functions for the convenience of using the derivative of $t\mapsto{\boldsymbol{l}}$ to define arc lengths. To this end, let $\dot{\boldsymbol{l}}(t)$ denote the time derivative of ${\boldsymbol{l}}(t)$; then, a distance functional may be defined according to,

The integrand in (21) is any finite-dimensional norm. If the two-norm is used, then the numerical value of $J_{dist}$ is consistent with the notion of Euclidean distance illustrated in Fig. 2. Combining (21) with Theorem 2, a shortest distance TSP can be formulated as,

The last constraint equation in (25) simply ensures that the resulting label-space trajectory is a closed control-walk.

In comparing it with the various discrete variable optimization formulations of a TSP [5, 7, 15], it is apparent that (25) contains no explicit subtour-type elimination constraints. This is because the (absolute) continuity of the label space trajectory ensures (by Theorem 1) that the closed control-walk generated by (25) is a single Hamilton cycle.

A TSP may also be formulated (in the sense of a $\mathcal{T}$-graph) using the time-on-task functional to construct a new indicator-type functional.

Using $W^{i}$ as an indicator of a vertex visit, we arrive at an alternative formulation of a TSP:

Equations (30) and (25) are identical except for the imposition of degree constraints. Formulation ($I$-TSP) requires that the vertex be visited at least once.

A comparison between the $\mathcal{T}$-graph and discrete-variable problem formulations is summarized in Table 1. As noted in the second row of Table 1, the $\mathcal{T}$-graph formulations do not require the explicit construction of the arc/edge weights; i.e., the cost matrix for the computation of the objective function in the discrete-variable formulation. This data is “generated” simultaneously via (21) as part of the process of solving the problem. That is, in terms of the concepts introduced in Section 2, the $\mathcal{T}$-graph formulation incorporates the simultaneous selection of the function sequence and the functions themselves from the domains of the vertex and arc functionals.

Let $\sigma^{i}>0$ be the score associated with each $\mathbb{L}^{i}(t)$. Define a score functional according to:

where, $W^{i}$ is given by (26). An orienteering problem (OP) may now be defined as,

The payoff functional is the sum of the score functionals. The maximum allowable time is $t_{max}>0$. The time constraint in (35) is written in terms of the integral of one to merely illustrate the fact that the resource constraint is a functional. The domain of ${\boldsymbol{l}}(\cdot)$ in (35) is the space of continuous functions in accordance with Theorem 1.

Problem (OP) given by (35) was motivated by the usual orienteering problem discussed in the literature [11]. Using the atomic return function concept introduced in (10), we may now score a traversal through a neighborhood based on the values of the atomic return functional (Cf. (11)). Although there are many ways to score a traversal, we illustrate a problem formulation based on the following construction,

In (36), $r^{i}>0$ is a required “revenue” from a visit to $\mathbb{L}^{i}(t)$. If a label-space traversal $t\mapsto{\boldsymbol{l}}$ across the city does not generate a revenue of at least $r^{i}$ as measured by the return functional $R^{i}$, then the salesman gets no commission (i.e., zero score). On the other hand, if the salesman performs a judicious travel through the city to generate a revenue of at least $r^{i}$, then, he is rewarded by $\sigma^{i}>0$. The salesman makes no extra commission for generating a revenue greater than $r^{i}$ at $\mathbb{L}^{i}$; i.e., he is encouraged to expand the market by visiting a different city. This situation arises in astronomy [4] where a telescope is required to scan a portion of the sky to collect a specific frequency of electromagnetic (EM) radiation [18]. Scientific value is generated based on the integration of EM collects. A critical amount of EM collects ($r^{i}$) is necessary to perform useful science. No extra science is generated once the targeted amount $r^{i}$ is reached; hence, the telescope is awarded $\sigma^{i}$ for performing a task successfully with no “extra” credit. Thus, the orienteering problem with neighborhoods may be defined according to,

In (41), the constraints $C^{k}[{\boldsymbol{l}}(\cdot),t_{0},t_{f}]\leq C^{k}_{max},\ \forall\ k\in N_{C}$ are $N_{C}\subset\mathbb{N}$ generic resource constraint, where $C^{k}_{max}>0$ is the maximum “capacity” associated with the $k$-th resource.

Minimizing distance traveled does not necessarily equate to minimum time; this fact has been known since Bernoulli posed his famous Brachistochrone problem as a mathematical challenge in the year 1696 [22, 28]. In framing a more interesting minimum-time TSP, we let $\tau^{i}>0$ be an additional constraint of a minimum required dwell-time over $\mathbb{L}^{i}(t)$. In this case, a fast (i.e., minimum-time) TSP may be framed as follows:

For the same reason as the formulation of the constraint in (35), the cost function in (45) is written as an integral to emphasize the fact that the travel-time is a functional. The functional $T^{i}$ in (45) is given by (13). Furthermore, while the dwell-time constraint in (45) may, in principle, be written as an equality, $T^{i}[{\boldsymbol{l}}(\cdot),t_{0},t_{f}]=\tau^{i}$, the advantage of an inequality is that it allows the solution to satisfy the stipulated requirement without incurring a penalty in performance for “navigating through the city” to find an optimal exit point at an optimal exit time.

Because $\mathbb{L}^{i}(t),i\in N_{v}$ are “moving cities,” dynamic TSPs are are explicitly incorporated in all of the preceding problem formulations. These formulations have also implicitly incorporated time windows because of the following argument: Let $t_{a}^{i}\in[t_{0},t_{f}]$ and $t_{b}^{i}\in[t_{0},t_{f}]$ be two given clock-times associated with each $\mathbb{L}^{i}(t)$ with $t_{a}^{i}<t_{b}^{i}$. Consider the augmented set defined by,

Then, it is clear that the space defined by,

is a label space, whose disjoint sets are defined by (46). Hence, by defining a new label-space variable ${\boldsymbol{l}}_{aug}:=({\boldsymbol{l}},t)$, it is apparent that no additional theoretical developments are necessary to incorporate time-window constraints in the proposed $\mathcal{T}$-graph formulations. Furthermore, note that the time window in (46) may itself also vary with respect to time.

In view of economic considerations that go beyond distance and time, a significantly greater degree of flexibility in modeling can be obtained by transforming the preceding $\mathcal{T}$-graph “variational” formulations to their optimal-control versions.

In many applications such as robotics [13], the natural home space for the “salesman” is some state space $\mathbb{X}$ that is not necessarily the label space. Furthermore, the dynamics of the salesman is given by some nonlinear controllable ordinary differential equation of the type,

where, $\boldsymbol{x}\in{\mathbb{R}}^{N_{x}}$ is a state variable, ${\boldsymbol{u}}\in{\mathbb{R}}^{N_{u}}$ is the control variable and ${\boldsymbol{f}}:{\mathbb{R}}^{N_{x}}\times{\mathbb{R}}^{N_{u}}\times\mathbb{R}\to{\mathbb{R}}^{N_{x}}$ is the nonlinear dynamics function. Because all aspects of the problem definition so far are described in terms of a label space, it is necessary to connect it to the state space. Let this connection be given by some algebraic equation,

where, ${\boldsymbol{g}}:{\mathbb{R}}^{N_{l}}\times{\mathbb{R}}^{N_{x}}\times\mathbb{R}\to{\mathbb{R}}^{N_{g}}$ is called a connexion function. An example of a physical description of state space, label space and the connexion function is illustrated in Fig. 5.

In this example, an uninhabited aerial vehicle (UAV) is tasked to collect over a geographic region [9, 24]. The areas of interest vary from a point area to a broad area of scan. Technical properties associated with the areas of interest are defined in label space. The state variables of the UAV is given in terms of of its position, velocity and the orientation of the maneuverable camera. The connexion function is the mathematical model that connects the label space variables to the state space variables based on the precise position and orientation of the camera at a given instant of time.

From (53) and (54), it follows that (47) may be written implicitly as a differential algebraic equation,

The significance of replacing (47) by the state-space representation is that it facilitates a direct means to incorporate the full nonlinear dynamics of a salesman in the optimization problem formulation.

As a result of (55), the decision variables expand to the tuple, $({\boldsymbol{l}}(\cdot),\boldsymbol{x}(\cdot),{\boldsymbol{u}}(\cdot),t_{0},t_{f})$. This can be taken to great advantage by formulating cost, payoff and/or constraint functionals in their more natural “home spaces.” For example, in the electric vehicle-routing problem [25], the capacity constraint of the battery is more naturally expressed as a functional constraint in terms of the state $\boldsymbol{x}$ of the vehicle [26],

In (56), $S$ is the state-of-charge and $C_{safe}$ is a battery charge required for safe operations. In the absence of extending the decision variables to incorporate the state vector, (56) would need to be transformed to a label space constraint using (54). This difficult task is completely circumvented by incorporating the state vector as part of the optimization variable. The alternative is to generate proxy models [25] as a means to extend the scope of vehicle routing problems [29].

In (45), the travel time is an implicit functional of the label-space trajectory ${\boldsymbol{l}}(\cdot)$. Replacing (47) by (55), the travel time now becomes an implicit functional of ${\boldsymbol{l}}(\cdot),\boldsymbol{x}(\cdot)$ and ${\boldsymbol{u}}(\cdot)$. That is, the functional,

with constraints given by (55) offers a more accurate model of travel time with obvious business implications in practical routing problems. Note that (57) also allows the clock time to be optimized. Equation (57) may be further modified to take into account gas/power consumption depending upon the vehicle type (standard/hybrid/electric). Analogous to (56), gas/power consumption may be written in terms of an integral,

where, $f_{0}$ is a function that models the time-varying gas/power consumption rate. This function may be well-modeled using the physics of the automobile power train [26]. A convex combination of (58) with (57) generates the functional,

The parameter $\alpha$ in (59) offers a sliding scale over the “trade-space” of time and energy consumption.

Substituting (55) in (52) while simultaneously adding additional levels of abstraction for the functionals associated with the vertices and arcs of the underlying $\mathcal{T}$-graph, we arrive at:

In (69), the objective function is simply stated in terms of an abstract functional $J$ in order to facilitate the formulation of a generic cost functional that go beyond those discussed in Sec. 5.2. Likewise, the functionals $K^{m}$ in (69) may be time-on-task functionals, walk-indicator functionals, degree functionals, capacity-constraint functionals or some other functionals. Furthermore, because each vertex may have several constraints, the total number of these constraints may be greater than $\left|N_{v}\right|$. The index sets $N_{=0}$ and $N_{\geq 0}$ simply organize the constraint functionals into equalities and inequalities. The set $\mathbb{L}^{b}\subseteq\mathbb{L}$ stipulates the boundary conditions for the label space trajectory. Also included in (69) are state variable constraints $\boldsymbol{x}(t)\in\mathbb{X}(t)$ and state-dependent control constraints given by ${\boldsymbol{u}}(t)\in\mathbb{U}(t,\boldsymbol{x}(t))$. Such constraints are included in Problem $(\mathcal{T_{X}}P)$ because they are critically important in practical applications[22, 28] as well as coordinate transformations of optimal control problems[22].

Because (69) is a generalization of the problems discussed in Sections 3–5, it is evident that a fairly large class of traveling-salesman-like problems can be modeled as instances of Problem $(\mathcal{T_{X}}P)$.