domain: math spi

text:
L Chauvier

G Damy

J Ch

Gilbert

N Pichon

Optimal control of a deep-towed vehicle by optimization techniques

We consider the problem of controlling a subsea vehicle used to investigate the ocean floor and focus on deepocean systems deployed through a cable several thousand meters long. The objective is to evolve optimized orders to be sent to the bridge or directly to the ship dynamic positioning system in order to minimize the duration of non productive maneuvers. Various constraints acting on the vehicle can be expressed such as minimum altitude, maximum velocity, etc. An optimization algorithm has been developed, which may take such inequality constraints acting on the system state variables into account.

Introduction

Tethered vehicles are commonly used to investigate the sea-bottom or objects lying on it. They belong to two main categories: towed vehicles (either passive or controlled through steerable fins) and ROVs. At a depth ranging between 1000 and 6000 m, ROVs can no longer be operated directly from the surface through a roughly buoyant umbilical. Instead, they are deployed using a weighty intermediate body suspended from the surface through the main cable. The dynamic behavior of this body is nevertheless similar to that of towed vehicles in that their position is only controlled through winch action and surface support maneuvering.

Operating deep systems is specifically difficult and time consuming because the towing speed is practically limited to 2-2.5 knots, the response to ship maneuvers involves quite long delays (for example, a 3000 m long cable and weight system initially deployed vertically takes around two hours to reach a steady state towing configuration at 2 knots), and the horizontal distance between vessel and towed body typically equals the immersion (at 2 knots).

Until recently, deep tethered vehicles (sometimes called "fish" below) were essentially used to perform scientific studies of the sea-bottom and expertise of wrecks with military or historical interest. Deep surveys are now performed in relation with the exploitation of deep oilfields and telecom optical cable laying operations. To guarantee the safety of human groups, routine surveys might be performed to detect sediment instabilities on continental margins and slopes and to monitor the evolution of active submarine seismic structures. In this context, a higher attention is given to systems productivity. This can be achieved through a more efficient control of the towfish position.

A first attempt to evolve optimized orders to the bridge using a research algorithm is reported in [START_REF] Mudie | Computer aided piloting of a deeply towed vehicle[END_REF]. A software was developed to determine the ship's course to ensure that the towed vehicle will pass within a minimum distance from a specified target. In [START_REF] Hover | Methods for Positioning Deeply-Towed Underwater Cables[END_REF], the problem of inverting the cable dynamics to make the towfish follow a prescribed trajectory is considered. More recently, Pichon [8] addressed the optimal control problem of finding a vessel trajectory bringing the vehicle from a given position to another one in a minimum time. The final state inequality constraints were taken into account by means of a penalization technique. However, the determination of adequate values for the various weighting coefficients was a delicate task. Therefore, it appeared necessary to use an optimization tool where the inequality constraints acting on the state variables could be handled in a more efficient manner.

The work presented in this paper also deals with the minimum time deep-towed vehicle control problem. To be able to tackle more difficult situations, we have developed a new optimization algorithm, in the class of nonlinear interior point methods (see [START_REF] Byrd | A trust region method based on interior point techniques for nonlinear programming[END_REF][START_REF] Chauvier | Commande Optimale d'Engins Sous-Marins avec Contraintes[END_REF]), which has the potentiality to solve problems with many inequality constraints. In the present case, such constraints can be related to a required position at the end of a maneuver or to the presence of natural obstacles, such as the relief of the sea bed.

The paper is organized as follows. In section 2, we describe the towfish-cable model, which allows for winding and unwinding actions on the cable. The discretization in space (using a variational technique) and in time (by the BDF scheme) is discussed in section 3. In section 4, we briefly explain the numerical optimization method and discuss the results obtained with this new approach in section 5. We conclude in section 6. We use a model already considered by other authors, see [START_REF] Damy | Integrated short term navigation of a towed underwater body[END_REF][START_REF] Marichal | Étude dynamique des systèmes sous-marins remorqués à l'aide de câbles de longueur variable[END_REF] for example. The cable position y and the tension T satisfy, for all s ∈ ]0, ℓ[ and t ∈ ]0, t max [,

Modelization of the problem

m c ÿ -(T y ′ ) ′ = d c + m c (g -ü)
(2.1a)

|y ′ | = 1. (2.1b)
Equation (2.1a) results from Newton's law of motion for an infinitely flexible cable. The hydrodynamic drag force per unit length d c acting on the cable is given by

d c = -c t | v t | v t -c n | v n | v n
, where v t and v n are the tangential and normal components of the cable speed (both depend on ẏ, u and y ′ ). We assume that the cable is inextensible, which is expressed by (2.1b). The tension can then be viewed as a multiplier associated with this constraint.

The evolution partial differential equations (2.1) first need boundary conditions. For all t ∈ ]0, t max [, y(ℓ, t) = 0 (2.2a)

m f ÿ(0, t) = (T y ′ )(0, t) + d f + m f (g -ü(t)). (2.2b)
Equation (2.2a) means that the cable is fixed to the vessel, while (2.2b) is Newton's law, applied here to the vehicle. The drag force

d f = -c h | v h | v h -c z | v z | v z
depends on v h and v z , the horizontal and vertical components of the vehicle velocity. Our model also needs initial conditions for the position of the cable. For all

s ∈ ]0, ℓ[, y(s, 0) = y 0 (s) and ẏ(s, 0) = v 0 (s), (2.3)
where y 0 and v 0 are the given initial position and speed of the cable w.r.t. the ship. There are neither boundary conditions nor initial conditions for the tension.

Variable length cables

In practice, it may be interesting to wind or unwind the cable from the ship deck to speed up a maneuver. We show in this section how to adapt the model above to take this possibility into account. We denote by ℓ(t) the length of the immersed part of the cable at time t. It is clear that the dynamics of the system is still described by (2.1), but now for s ∈ ]0, ℓ(t)[. The fact that the length of the cable may change and the dynamics linked to this are simply expressed by modifying the boundary condition (2.2a), which becomes: for all t ∈ ]0, t max [ y(ℓ(t), t) = 0.

(2.4)

The initial conditions (2.3) now hold for s ∈ ]0, ℓ(0)[. A possible strategy to solve this new model is to express the cable dynamics on the constant interval [0, 1], thanks to the change of variable ŝ = s/ℓ(t). The resulting equations could then be integrated in space on [0, 1]. However, their nature may depend on how fast ℓ(t) varies with t. Furthermore, the stability of the discretized equations may also be influenced by the cable winding. For these reasons we have preferred another technique, which preserves the structure of equations (2.1) and has the advantage of being easier to implement.

Let ℓ max denote the maximum length of the cable, so that ℓ(t) must be taken in ]0, ℓ max [. In our approach, we integrate equations (2.1) not only on ]0, ℓ(t)[, but on ]0, ℓ max [. To realize condition (2.4), we leave free the upper end of the cable (for s = ℓ max ) and impose the boundary condition

y(ℓ max , t) = κ(t),
where κ is an unknown function. Roughly speaking, at any time, the new system has one more unknown (κ(t) ∈ R 3 ) and one more equation ((2.4) with values in R 3 also). Numerical experiments have shown that it is as easy to solve as the previous model. Of course, we are finally only interested in y(s, t), for s ∈ ]0, ℓ(t)[.

Optimization of the vessel displacement

We can now formulate the minimum time deep-towed vehicle control problem. The state variables are y, ẏ, T , and κ and the control parameters are u, t max , and ℓ. The aim is to minimize the total time t max , while preserving certain constraints.

The state equations (2.1), (2.2), and (2.3) (with the appropriate changes discussed in section 2.2) are viewed as equality constraints for the minimization problem.

We also consider inequality constraints on the state and control variables. Here are some examples. The final position of the cable has to belong to the tube of radius r y > 0 defined by | y(•, t max ) -y(•) | ≤ r y , where y is some prescribed final position. Similar constraints can be given on the final speed of the cable. Also, to take care of the relief of the sea bed, the vehicle altitude y 3 (0, •) has to be above a certain surface given by a function ϕ. This constraint can be expressed by ϕ(y 1 (0, •), y 2 (0, •)) ≤ y 3 (0, •).

Discretization of the equations

For simplicity, we discuss the discretization in space and time when the cable has a constant length.

Discretization in space

We propose a space discretization based on a variational formulation of equations (2.1) and (2.2). Consider two appropriate function spaces Y and T and the problem: find, for each fixed t, y (•, t) ∈ Y and T (•, t) ∈ T such that for all z ∈ Y and τ ∈ T ,

m c ℓ 0 ÿ z + m f ÿ(0, t) z(0) + ℓ 0 T y ′ z ′ = ℓ 0 d c z + d f z(0) + m c ℓ 0 (g -ü) z + m f (g -ü) z(0) and 1 2 ℓ 0 | y ′ | 2 -1 τ = 0.
A sufficiently smooth solution of this problem satisfies (2.1) and (2.2). We get a discretization of these equations by replacing Y and T by some finite element spaces Y h and T h . For compatibility reasons, the elements of Y h must be of higher order than those of T h .

To define Y h and T h , we introduce a grid of [0, ℓ] and consider piecewise affine approximations of y and T . The vectors of values approximating y and T at the nodes of the grid are denoted by the same letters y and T . The components of y are computed at each node (except at s = ℓ, since it is known that y(ℓ, •) = 0), while the components of T approximate the tension at one node out of two. The spaces T h and Y h are respectively referred to as P1 and P1-iso-P2 finite element spaces. The discrete variational formulation results in the following index-3 differential-algebraic system of unknowns y, v and T

     ẏ = v M v + R(y) ⊤ T = B(y, v) C(y) = 0, (3.5)
where B is also a function of u and ü, and C ′ (y) = R(y).

Discretization in time

Equation (3.5) is integrated in time using a backward differentiation formula (BDF) scheme (see [START_REF] Brenan | Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations[END_REF]). The integration interval [0, t max ] is divided in n t subintervals of constant length dt (the timestep). Let y i , v i , and T i be the approximations of y, v, and T at the times i dt, i = 1, . . . , n t . Has to be solved for each i

                         y i = dt b i v i + ri j=1 a i,j y i-j v i = dt b i M -1 B(y i , v i ) -R(y i ) ⊤ T i + ri j=1 a i,j v i-j C(y i ) = 0, (3.6)
where a i,j , b i , and r i are constants depending on the scheme order, y 0 and v 0 are the initial position and speed y 0 and v 0 .

We suppose that the number of timesteps is fixed to n t , so that to minimize the total time of the maneuver t max = n t dt, one has to minimize the value of dt.

Optimization techniques

In this section, we denote by x = (Y, U ) ∈ R n the vector of variables to optimize. It is formed of the state variables Y = (y, ẏ, T, κ) ∈ R mE and control variables U = ( u, dt, ℓ) ∈ R n-mE . Then, equations (3.6) can be written c E (x) = 0, where c E is some nonlinear function from R n to R mE . Similarly, the inequality constraints acting on the state and control variables can be written c I (x) ≤ 0, for some function c I : R n → R mI . With this notation, the optimization problem can be written

   min f (x) c E (x) = 0 c I (x) ≤ 0, (4.7)
where the criterion is simply f (x) = dt. This problem is first transformed in a canonical form by introducing slack variables s ∈ R mI and by writing the inequality constraints as c I (x) + s = 0 and s ≥ 0. It is known that if x is a regular solution, there exist Lagrange multipliers λ E ∈ R mE and λ I ∈ R mI associated with the constraints of (4.7), such that there holds

           ∇f (x) + A E (x) ⊤ λ E + A I (x) ⊤ λ I = 0 Sλ I = 0 c E (x) = 0 c I (x) + s = 0 (s, λ I ) ≥ 0, (4.8)
where A E (x) = c ′ E (x) is the m E × n Jacobian of the equality constraints, A I (x) = c ′ I (x), and S is the diagonal matrix formed with the components of s. The first equation in (4.8) is conveniently written ∇ x L(x, λ) = 0, where L(x, λ) = f (x) + λ ⊤ c(x) is the Lagrangian of the problem, λ = (λ E , λ I ), and c = (c E , c I ).

So-called primal-dual nonlinear interior point methods solve approximately a perturbed version of the optimality system (4.8), namely

           ∇ x L(x, λ) = 0 Sλ I = µe c E (x) = 0 c I (x) + s = 0 (s, λ I ) > 0, (4.9)
for a sequence of perturbation parameters µ > 0 converging to zero. In (4.9), e = (1 • • • 1) ⊤ is the vector of all ones. The advantage of this approach is that (4.9), as opposed to (4.8), is a set of equalities (the positive constraints on (s, λ I ) are in fact easier to handle than nonnegativity constraints), without the combinatorial problem of determining which of the variables s i or λ i has to vanish, and with a Newton step that is well defined in the neighborhood of a regular solution. On the other hand, several nonlinear systems of that type have to be solved.

Solving (4.9) approximately requires sophisticated numerical techniques, which we briefly describe (see [START_REF] Chauvier | Commande Optimale d'Engins Sous-Marins avec Contraintes[END_REF] for more details). The basic idea is to compute an appropriate approximation of the Newton direction associated with (4.9). The latter is the solution d = (dx, ds, dλ E , dλ I ) of the linear system (we drop the function dependencies for simplicity):

    ∇ 2 xx L 0 A ⊤ E A ⊤ I 0 Λ I S -1 0 I A E 0 0 0 A I I 0 0         dx ds dλ E dλ I     = -     ∇xL λ I -µS -1 e c E c I + s     ,
where Λ I is the diagonal matrix formed with the elements of λ I . Since the matrix above uses the Hessian of the Lagrangian ∇ 2 xx L, second derivatives of f and c must be computed or approximated. In our algorithm, only Hessian-vector products (∇ 2 xx L)v are required. Close to a solution of (4.9), Newton's direction d is very efficient, but far away it may be inadequate. To improve d, its component in the space tangent to a constraint manifold is approached by solving a reduced form of the linear system above by truncated conjugate gradient iterations. Truncation occurs on several circumstances, but certainly before the possible nonconvexity of the problem is detected.

The above strategy has a second advantage. The modified Newton direction d is a descent direction of the merit function in the variable z = (x, s, λ E , λ I )

Θ(z) = f (x) -µ mI i=1 log s i + λ ⊤ I c I (x) -µ mI i=1 log(λ i s i ) + σ E c E (x) + σ I c I (x) + s .
For judicious positive values of σ E and σ I , adapted by the algorithm, the solutions of (4.9) are minimizers of Θ (exact penalty property). Therefore it makes sense to force the decrease of Θ along the direction d, which gives a step-size α > 0. Then, z is updated by

z + = z + α d.
By this technique, one can force the convergence of the iterates from remote starting points.

Numerical experiments

In the experiments, we assume that in a prospecting campaign a rectangular subsea area is explored rows by rows with the cable-vehicle system in steady state. When the vehicle leaves a row, it is desired that it enters the next row as fast as possible. The aim is therefore to make a U-turn in a minimum time. This problem can be set in the framework introduced in the previous sections.

Here are the data of the experiments. The distance between two successive rows is 500 m. The vessel has a nominal speed of 1 m/s, which must be maintained between 0. To analyze this situation and the possibilities of the optimization algorithm, we have developed a software in Matlab. For the results below, the discretization is made using 8 equidistant points in space (for the position y) and 15 timesteps. Compared to the steady state solution, which can be computed very accurately by integrating an ordinary differential equation, this discretization in space gives already a rather good approximation. For example, for a cable 4000 m long at 1 m/s, the error on the position of the vehicle is 9 m.

The constraints at the end of the U-turn require that the cable be in a tube of specified radius r y around the steady state position and that the velocity be between 0.9 and 1.1 m/s. We have compared the optimal times for values of r y ranging between 1 m and 100 m and for fixed or variable length cables. The results are given in the figure below. Not surprisingly, more precise the final position must be, more time the maneuver takes, and the dependency is monotone. The time of the U-turn is also longer for a constant length cable, since there is one degree of freedom less than for variable length cables. According to the figure, the possibility to wind the cable during the maneuver is all the more beneficial when high precision is required on the final position. For example, for a precision of 1 m, 40 % of the time is saved when the length of the cable may vary.

In the following tests, the final position tolerance is r y = 40 m, that is to say 1% of the cable nominal length. We represent, on the left and on the right of the figure below, the optimal vessel-cable-vehicle trajectories in the absence or presence of a sea bed relief. The optimal trajectories are seen from above. They correspond to solutions to the optimality system (4.8). The figure in the middle is the solution of (4.9) with the perturbation parameter µ = 10 4 .

The respective optimal times are 5520 s, 10820 s, and 8350 s. We show below, from top to bottom, these trajectories seen from the left hand side.

One can observe that the need to avoid the underwater obstacle results in very different optimal trajectories. These pictures also highlight the fact that solutions to (4.9) may vary significantly when µ decreases to zero. This is confirmed by the figures hereafter, which are all related to the test with obstacle. They successively depict, with their bounds, the distance between the cable nodes and their prescribed position, the vessel speed, the cable winding speed, and the cable length, for solutions to (4.9) with µ = 10 4 (dashed line) and µ = 0 (solid line). The last two pictures give the towfish depth (top line) and the relief of the sea bed along its trajectory (bottom line), for µ = 10 4 (on the left) and µ = 0 (on the right). Observe that these constraints are inactive when µ is positive. This makes the perturbed optimality conditions (4.9) easier to solve than the optimality conditions (4.8). Moreover, the pictures suggest that allowing for variable length cables not only offers a reduction of the total time, but is also an efficient way of avoiding obstacles.

Conclusion

The optimization algorithm presented above is to be included into an integrated computer-aided piloting system for deep-towed/deep-tethered vehicles. It concerns not only U-turn maneuvers but also short transits between investigated areas, surveys along non-straight routes, etc. Simultaneously, Ifremer has started operating a new Ultra Short Base Line acoustic positioning system. This system, recently developed by Thomson Marconi Sonars is accurate to within 1% of the range. It will provide the data necessary to identify current-induced biases in the cable model. It also opens the possibility for a closedloop adjustment of the preshaped ship trajectory. Further work will focus on taking ship maneuverability constraints into account and interfacing with ship's dynamic positioning systems.

The algorithm presented in this paper, though it can be considered as a prototype software element, appears sufficiently promising in terms of time-effectiveness and robustness. This development is a major step towards the achievement of the complete system.

  5 and 1.5 m/s. The cable weighs m c = 0.986 kg/m, it has a nominal and maximal length of 4000 m and 5000 m respectively, and it can be wound and unwound at 1 m/s at most. The vehicle mass is m f = 1500 kg. The drag coefficients c n , c t , c h , and c z are estimated by the formulae c n = ρ D C n /2, c t = ρ D C t /2, c h = ρ S h C/2, and c z = ρ S z C/2 (ρ: water mass per unit volume, D: cable diameter, S h : horizontal cross-section area, S z : vertical cross-section area, and C n = 2.3, C t = C n /100, C are empirical drag coefficients). We took c n = 23 kg/m 2 , c t = 0.23 kg/m 2 , and c h = c z = 500 kg/m.

  IN S.) W.R.T. FINAL POSITION ACCURACY (IN M.)

† INRIA Rocquencourt, BP 105, 78153 Le Chesnay Cedex, France, Laurent.Chauvier@inria.fr, Jean-Charles.Gilbert@inria.fr (corresponding author).‡ IFREMER, Centre de Brest, BP 70, 29280 Plouzané, France, Gilbert.Damy@ifremer.fr.


Ivan Peña-Arenas

Cyril Fonlupt

Deep reinforcement learning for combinatorial optimization: case study orienteering problems By

Keywords: Team orienteering problems, deep learning, optimal split, decoder-encoder mechanisms

In the Team Orienteering Problem (TOP) a set of routes is determined with the objective of maximizing the profit gained from visiting customers without exceeding a travel cost/time limit. Currently, the use of machine learning approaches along with optimization techniques in order to solve complex combinatorial problems has been proved successfully. We present an hybrid algorithm which combines a deep learning neural network with an efficient splitting algorithm to solve the TOP. The objective is to compare the efficiency of the proposed method in terms of both, quality of the solution and running times, against previous optimization methods proposed in the literature.

Introduction

The Orienteering Problem is a combinatorial optimization problem that has been proven NP-Hard [START_REF] Golden | The orienteering problem[END_REF], and which has different practical applications ranging from logistics to telecommunications. There are different variants of the problem such as, the Team Orienteering Problem (see, [START_REF] Chao | The team orienteering problem[END_REF], [START_REF] Tang | A tabu search heuristic for the team orienteering problem[END_REF], [START_REF] Dang | An effective pso-inspired algorithm for the team orienteering problem[END_REF]), the Orienteering Problem with Time Windows (see, [START_REF] Yu | A matheuristic approach to the orienteering problem with service time dependent profits[END_REF], [START_REF] Roozbeh | A solution approach to the orienteering problem with time windows and synchronisation constraints[END_REF], [START_REF] Saeedvand | Novel hybrid algorithm for team orienteering problem with time windows for rescue applications[END_REF]) and Team Orienteering Problem with Time Windows (see, [START_REF] Vansteenwegen | The orienteering problem: A survey[END_REF], [START_REF] Amarouche | Effective neighborhood search with optimal splitting and adaptive memory for the team orienteering problem with time windows[END_REF]). And several heuristics have been proposed to obtain high quality solutions.

Recent advances in machine learning techniques, particularly on deep learning model architectures like Pointer Networks and Graph Attention Networks, have shown a good performance in a wide variety of fields. These results have encouraged the interest in using those kind of techniques to tackle combinatorial problems. Some examples of this type of strict machine machine learning approaches can be seen in [START_REF] Vinyals | Pointer networks[END_REF], [START_REF] Khalil | Learning combinatorial optimization algorithms over graphs[END_REF] and [START_REF] Nowak | Revised note on learning quadratic assignment with graph neural networks[END_REF].

The heuristics are tailored methods that work case-by-case, thus not easy to generalize and which usually require a great deal of expertise to be developed. However, they are efficient solution techniques that rely on their programmed behavior [START_REF] De Costa | Learning 2opt heuristics for routing problems via deep reinforcement learning[END_REF]. Machine learning models, make decisions and solve problems, extracting useful information directly from the data without having a particular knowledge of the problem. Nevertheless, as the size and complexity of the problems increases, the performance of the neural network diminishes because the computational time of the learning process should be reduced.

To take advantage of both solution methods, we propose to integrate an efficient splitting algorithm to solve the TOP with a machine learning technique. Unlike previous hybrid approaches, the giant tour (a sequence of customers/locations) is created at once by the neural network and in a second step it is evaluated by the heuristic. In addition, in the best of our knowledge these hybrid approach has not been proposed to tackle the TOP and the TOPTW. This document is organized as follows. First, we make a brief discussion of machine learning and hybrid methods applied to combinatorial problems. Later, we introduce the general architecture of the Graph Attention Network (GAN). And finally, some preliminary results and perspectives are presented.

Literature review

Among strict machine learning approaches applied to solve combinatorial problems, [START_REF] Vinyals | Pointer networks[END_REF] present a Pointer Network (PN) architecture to solve the planar Travel Salesman Problem. In this work they apply supervised learning to train the Neural Network (NN). The main issue with this type of training, is that it relies on the quality of the solutions which are used. Thus, there is a good performance for small size problems, where optimal or near to optimal solutions are known, however for large problems the performance is bounded by the quality of the training set solutions.

Afterwards, [START_REF] Bello | Neural combinatorial optimization with reinforcement learning[END_REF] apply the same architecture however, they propose a different training method called Reinforcement Learning (RL).

In this type of training, it is not necessary an external input (solution) to train the NN.

Moreover, the NN adapts its behaviour at each step, receiving positive or negative rewards whether the movements (decisions) increase or decrease the objective function value. They empirically demonstrate that RL significantly improves over supervised learning.

An alternative deep learning architecture based on a decoder coupled with an attention mechanism is presented in [START_REF] Nazari | Reinforcement learning for solving the vehicle routing problem[END_REF] applied to the Capacitated Vehicle Routing Problem (CVRP). Furthermore, they use RL to train the NN; during in this process the algorithm computes the reward and verifies the feasibility at the same time. The comparison is done against Google's OR-Tools, and for instances of 50 and 100 customers in roughly 61% of the cases the algorithm provides shorter tours. In addition, the same architecture can solve the CVRP with stochastic demands and allowing split deliveries. [START_REF] Kool | Attention, learn to solve routing problems![END_REF]

Methods

We propose a Graph Attention Network integrated to an efficient splitting algorithm to solve the TOP. Several methods that combine machine learning and heuristics have been proposed in the past [START_REF] Gama | A reinforcement learning approach to the orienteering problem with time windows[END_REF]. However, most the previous approaches build a sequence in a constructive way, that is to say, inserting a new client/location into the sequence after imposing feasibility at each step, making the learning process difficult and slow. Our main idea is to use the GAN to create a permutation (sequence) of all accessible locations (usually referred as giant Tour) at once and afterwards, call the splitting algorithm to construct the set of optimal tours. In this sense, striving to accelerate the learning process, while keeping good quality solutions.

Our model is a Recursive Neural Network based on a Graph Attention Network, composed by an encoder-decoder mechanism [START_REF] Kool | Attention, learn to solve routing problems![END_REF]. The encoder has three encoder layers connected in a cascade fashion. Therefore, the information treatment is independent, and once the information is treated by a layer it is sent to next layer, see Figure 1. Each encoder layer is composed by one Multi-head attention (MHA) and one Feed Forward Layer (FFL) linked by dropout and batch normalization functions. The decoder is composed by one MHA and a FFL, linked by T hanh function. The decoding of the giant Tour is done sequentially, at each time step t ∈ {1, 2, .., n}, the selected node (location) π t is decoded based on the embeddings from the encoder and the previous outputs π ′ t generated at time t ′ < t. In particular, at each iteration the context consists of the graph embedding and the embeddings of the first and the previous output (node) of the current tour. In addition, the final probabilities are computed using a single-head attention mechanism.

The context vector encodes all the information coming from the encoder in a sequence to sequence Neural Network. Furthermore, the attention mechanism applied to the context allows the decoder to focus on particular sections of the outputs from the encoder [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF]. As mentioned, in the current architecture the context consists of the embedding of the graph, the previous (last) node π t-1 and the first node π 1 . At each iteration π t-1 is updated and the nodes that cannot be visited (since they are already in the sequence) are masked. Figure 2 presents an example of decoding the process. In this architecture, the attention mechanism algorithm assigns the message weights between the nodes in the graph. Since the attention is linked to the changes in the context and the graph, it also has to be updated at each iteration. The weight of the message value that a node receives from a neighbor depends on the compatibility of its query with the key of the neighbor (see, [START_REF] Vaswani | Attention is all you need[END_REF]).

We start with the OP version of the problem to later move forward to the TOP and the TOPTW. The attention Neural Network defines a stochastic policy p θ (π|s) for selecting a tour (sequence) π given the problem instance s and the parameters θ.

Moreover, we define J(θ|s) as the policy objective function, which is the total score of the tour given the instance s. Also, we use policy gradients methods to search for a local maximum in J(θ|s) by ascending gradient policy, w.r.t parameters θ, defined as:

∇ θ J(θ|s) = E p θ (π|s) [∇ θ log p θ (π|s)(G(π) -b(s))]
The value of the gradient function ∇ θ J(θ|s) is equal to the expected value of the multiplication between the functions score and advantage. The gradient (∇ θ log p θ (π|s)) is a measure of the movement of the function in the solution space (score function).

While, the difference between the score G(π) of the tour π, and the baseline b(s) is the advantage function. To optimize the expected score we use REINFORCE [START_REF] Williams | Simple statistical gradient-following algorithms for connectionist reinforcement learning[END_REF] gradient estimator, and a greedy roll-out baseline.

Results and perspectives

As a preliminary result, we start with the implementation of the Graph Attention Network for the OP, and we compare their results against a MILP version of the problem [START_REF] Vansteenwegen | The orienteering problem: A survey[END_REF], using small size instances of five locations.

During the training process, as the number the epochs increases, the GAN improves its performance achieving better scores as Figure 3 presents. We want to emphasize that implementing and training a sequence to sequence architecture requires a considerable investment of time. Neural Networks are powerful but complex models. Thus, the process of implementing and training these kind of models requires in-depth expertise and a great deal of experimentation. Finally, we would like to list some of the possible progress steps in the project:

1. Compare the GNA against the MILP model using instances of with n = {10, 50, 100}.

2. Compare the GNA implementation for the OP against the results reported in [START_REF] Kool | Attention, learn to solve routing problems![END_REF].

3. Implement the hybrid algorithm to solve the TOP, and compare it against the results reported in [START_REF] Dang | An effective pso-inspired algorithm for the team orienteering problem[END_REF].

4. Modify the algorithm to solve the TOPTW, and compare it against the results reported in [START_REF] Amarouche | Effective neighborhood search with optimal splitting and adaptive memory for the team orienteering problem with time windows[END_REF].

5. Implement different ways to make the embeddings (GNN, GNC...etc) and compare with self-attention.

  present an encoder-decoder NN coupled with an Attention Mechanism (AM). In order to improve the training algorithm they test different baselines, such as, roll-out, exponential and using a critic. Moreover, the AM is compared with a Pointer Network (PN) under different baselines. The results show that the AM outperforms the PN using any baseline, and the roll-out baseline improves the quality and the convergence speed of both AM and PN. Recently there have been presented different hybrid approaches combining heuristics with machine learning approaches to solve combinatorial problems. Hottung and Tierney (2019) propose a Neural Large Neighbourhood Search (NLNS) method to solve the CVRP and the Split Delivery Vehicle Routing Problem (SDVRP), in which the neighbourhood is explored by a Recurrent Neural Network (RNN). The learning mechanism is based on a deep neural network with an attention mechanism, and it is designed to perform the complex task of developing repair operators. The experiments show that on SDVRP instances, the NLNS is able to outperform the state-of-the-art method SplitILS on instances with 100 customers. A RNN is trained to learn a neighbourhood search mechanism based on 2-Opt operators to solve vehicle routing problems in de Costa et al. (2021). They present a new approach to explore the neighbourhood, where the 2-Opt method is modeled as a Markov Decision Process (MDP), where the states are defined by the tuple S, S ′ which are the the current and lowest-cost solution, and the transitions are given by the tuple of actions (a1, a2) which are the index positions to exchange. The handicap of this method is that it requires a large amount of iterations during the training to achieve the performance of the classical methods. Gama and L. Fernandes (2021) present a RNN based on Pointer Networks applied to the Orienteering Problem with Time Windows (OPTW) and the Tourist Trip Design Problem (TTDP). Their model is based on the PN architecture proposed in Vinyals et al. (2015), albeit they introduce three different aspects with respect to previous PN architectures: New set representation at each iteration, transformer with recursion and masked self-attention. The algorithm significantly outperforms the standard competitive heuristic Iterated Local Search, with inference times that are suitable for real time on-line applications. However, since the feasibility is verified while creating the sequence, the method requires long training times.

Figure

  Figure 1: Encoder.

Figure 2 :

 2 Figure 2: Example decoding mechanism.

Figure 3 :

 3 Figure 3: Average tour score per epoch during training.

Figure 4 :

 4 Figure 4: Comparison between MILP vs. GAN using instances of five locations.