The traveling salesman problem (TSP) plays an important role in mathematics and finds numerous applications in real-life problems. However, modern engineering challenges lead to dynamic versions of the classic TSP formulation. Namely, trajectories of 'cities' and 'the traveling salesman' must satisfy dynamics in terms of differential equations. The first formulation of the TSP with dynamics dealt with cities moving in a straight line with a constant velocity [1]. In what follows, we use the terminology proposed in papers [2,3,4,7]. Namely, though distances between each pair of cities do depend on the given tour, we still use the notion of the TSP.

Advances in the construction of unmanned aerial vehicles (UAVs), underwater autonomous vehicles, unmanned cars demand a study of the TSP with complex linear or nonlinear dynamics. In this regard, mathematicians and engineers use models, for example, the Dubins vehicle (a nonholonomic controlled object that can move along curves on plane with a limited radius of curvature and is unable to reverse). This model describes quite well the dynamics of UAVs, ships, submarines, etc. At the same time, due to the rapid development of technology and infrastructure, the TSP for such objects has a great practical importance; this leads to studies of the TSP for the Dubins vehicle (DTSP) [2,3,4]. Also the TSP has been studied for the Reeds-Shepp car and the differential drive robot [5].

As the first approximation, dynamics of some objects can be considered as a linear system. For example, it is possible to obtain a good approximation of spacecraft dynamics in deep space by using the double integrator model [6]. Thus, the TSP for controlled objects described by linear differential equations is of interest. A special case of such problem is the TSP for the double integrator (DITSP). Among possible applications leading to DITSP, we should note the task of collecting orbital debris.

Note that the DITSP is poorly studied in comparison with the DTSP. In [7], the double integrator with bounded velocity and bounded control inputs was considered; asymptotic bounds on the time taken to complete the fastest tour in the worst case were obtained; a stochastic version of DITSP was considered (i.e., points are randomly sampled from uniform distribution) and algorithms performing within a constant factor of the optimal strategy with high probability was proposed. The TSP for affine in control systems was studied in [8]. For these systems, the lower bound on the minimum expected travel time of visiting of n uniformly distributed points was obtained; an algorithm generating a tour that system can trace in time that has the same asymptotic order in n as the lower bound was provided [8]. In this paper we do not consider stochastic settings and asymptotic bounds, but we propose a heuristic for the DITSP without any bounds on the velocity between cities.

The complexity of the DITSP and DTSP is caused by 'simultaneous' optimization of the total travel time by a discrete vector parameter (tour) and by a continuous parameter (control). In this regard, they can be called a discrete-continuous problem with the NP-hard discrete part. Moreover, the following fact complicates these problems even more. In general, for a given tour it is not possible to partition the multipoint time-optimal control problem into a set of two-point subproblems without loss of the optimality. To avoid constructions of time-optimal trajectories for all possible tours in the DTSP, the necessary condition for tour optimality was proposed in [9].

Note that N.N. Krasovskii proposed a general approach for solving linear optimal control problems. The approach is based on the duality of optimal control problems and convex programming [10,11]; for details see also [12, ch.6., §9-12]. The approach allows to replace an infinite-dimensional time-optimal control problem with the finite-dimensional optimization problem. Krasovskii's approach was further generalized for multipoint time-optimal control problems; a multipoint analogue of Pontryagin's minimum principle was obtained in [13,Theorem 3.3]. Unfortunately, it is still difficult to find the multipoint time-optimal control numerically for a large number of points. Moreover, even if we imagine that we have learned how to do this efficiently, the problem of searching through all possible tours remains. In this regard, we introduce a heuristic algorithm based on the theoretical results [10,11,13] 2 Problem statement By • we denote Euclidean norm in R 2 . We introduce a mapping π 12 by the rule

and a mapping π 34 by the rule (x i ) i∈1,4 −→ (x i ) i∈3,4 : R 4 → R 2 . Consider a set of m stationary (distinct) nodes to be visited. Each node is located at coordinates y (i) = (y

2 ) ∈ R 2 where i ∈ 1, m. Suppose that for each node i, i ∈ 1, m, a constraint on (visiting) velocity in terms of non-empty set V i , V i ⊂ R 2 , is defined. The dynamics of the object ('the traveling salesman') on the time interval I = [0, ∞[ are set by the differential equations

Thus, 'the traveling salesman' is defined as the double integrator model on plane. Here an open-loop control u = (u i ) i∈1,2 is a piecewise constant function I → R 2 such that u(t) ∈ P ∀t ∈ I, P ⊂ R 2 where P is a convex compact set; let U be the set of all such controls. We suppose that P is given such that the system is controllable. Let T be the set of all vectors (t i ) i∈1,m from I m such that 0 < t 1 < t 2 ... < t m . By φ u = φ u (t) t∈I we denote the trajectory of (1) generated by a control u ∈ U starting from the initial position x 0 ; φ u (t) ∈ R 4 ∀t ∈ I.

By B we denote the set of all bijections 1, m → 1, m. We say that the triplet

we denote the set of all admissible triplets by A.

We introduce the payoff function J : A → I by the rule:

DITSP. Find the triplet (τ 0 , u 0 , b 0 ) ∈ A such that

Obviously, J 0 corresponds to the minimum time required to visit the given set of points by the double integrator complying with velocity constraints at nodes. Recall that in DITSP we need to find not only the optimal permutation (the best tour), but also the time-optimal control to visit all points according to the best tour. The last 'control subproblem', in general, does not allow the partitioning to two-point time-optimal control problems without losing the optimality. This fact dramatically complicates the exact solution of DITSP. In this regard, it is rational to propose a heuristic algorithm for DITSP.

The proposed algorithm reflects the classical concept in mathematics: if a continuous problem is hard to solve, then it is worth to try a discretization to obtain an approximate solution for the original problem. For the DTSP this concept led to an algorithm based on heading discretization [3]. The proposed heuristic algorithm for the DITSP consists of the following 4 steps:

1. We fix a parameter d of the discretization of admissible velocity sets

We complement the geometric coordinates of the nodes y (i) , i ∈ 1, m with velocity coordinates obtained after the discretization in the following way: each original node i is transformed into d nodes with the same geometric coordinate y (i) and distinct velocity coordinates v[j] (i) , j ∈ 1, d.

2. We form a path weights matrix using the optimal time as the 'travel cost' between cities of different sets. This requires us to find time-optimal controls for all two-point problems corresponding to the 'travel' from a node (y

) where i, k ∈ 1, m, i = k, and j, l ∈ 1, d. Now we apply Krasovskii's approach. We fix two different points in the phase space with coordinates a = (y

Our goal is to find the 'travel cost' c (i,j),(k,l) from point i to point k. We assume that a given point is visited, if the trajectory of the system intersects ε-neighborhood of the point where ε, ε > 0, is small enough. We introduce the functional for the minimum time estimation (see [11, p. 131], [

here S 3 is the unit 3-sphere. Next we find the minimal time instant θ * such that σ(a, b, θ * ) < ε; we apply iterative procedure for this. Let θ * ∈ I. If σ(a, b, θ * ) > ε, then on the next iteration we increase θ * . If σ(a, b, θ * ) ≤ 0, then on the next iteration we decrease θ * . If 0 < σ(a, b, θ * ) ≤ ε, then we stop searching and set c (i,j),(k,l) = θ * . Note that one can obtain the time-optimal control. If θ * is the optimal time, l 0 ∈ S 3 maximizes σ(a, b, θ * ), then the optimal control u * (•) satisfies the specific version of Pontryagin's minimum principle:

3. We solve the (asymmetric) Generalized TSP (GTSP, also known as the set TSP) with the path weights matrix obtained in the previous step. The length of the shortest possible tour is an upper bound for the value J 0 of DITSP. The optimal permutation (tour) defines velocity of 'the salesman' at these points and the control that ensures the upper bound.

To solve the GTSP, one may apply transformation [14] of the GTSP into the standard asymmetric TSP, use integer programming algorithm [15] or iterative heuristic algorithm [16].

4. Repeat steps 1-3 applying heuristics for obtaining a better velocity discretization at nodes. For these purposes, one can use swarm optimization, genetic algorithms, etc.

The paper deals with the hard discrete-continuous problem that currently does not allow to get exact solutions. In this regard, the proposed heuristic can be useful for applications. Since Krasovskii's approach was proposed for a general linear control problem, the heuristic can be used with the controlled object defined by a generic linear system. To keep things simple, we considered the double integrator model only. The proposed heuristic can be easily extended to any finite dimensional state space. The duality proposed by N.N. Krasovskii simplifies the solution of two-point time-optimal control problems for linear systems (comparing to optimal control methods associated with Pontryagin's minimum principle [17]). Recall that based on the duality, an analogue of Pontryagin's minimum principle for multipoint linear control problems was proposed in [13]; we will use this result to further develop of the proposed heuristic. We also plan to extend numerical experiments to get a better understanding of the heuristic performance. From theoretical prospective, it is of interest to study the question of convergence of results under the discretization procedure and to provide error bounds.