Analysis of the selective traveling salesman problem with time-dependent profits

Vol.:(0123456789) TOP https://doi.org/10.1007/s11750-022-00632-6 1 3 ORIGINAL PAPER Analysis oftheselective traveling salesman problem withtime‑dependent profits EvaBarrena1 · DavidCanca2· LeandroC.Coelho3· GilbertLaporte4 Received: 29 July 2021 / Accepted: 3 April 2022 © The Author(s) 2022 Abstract We consider a generalization of the selective traveling salesman problem (STSP) in which the benefit of visiting a location changes over time. This new problem, called the selective travelling salesman problem with time-dependent profits (STSP-TDP), is defined on a graph with time-dependent profits associated with the vertices, and consists of determining a circuit of maximal total profit. In the STSP-TDP the tour length must not exceed a maximum value, and its starting and ending times must both lie within a prespecified planning horizon. This problem arises in planning tourist itineraries, mailbox collection, military surveillance, and water sampling, where the traveler accumulates different profits upon visiting the locations throughout the day. We focus on analyzing several variants of the problem depending on the shape of the time-dependent profit function. If this function is not monotonic, it may be worth visiting a site more than once. We propose formulations for the single-visit case and for when multiple visits are allowed, in which case the problem reduces to an STSP, which is adapted to be solved as a longest path problem. These formulations are then solved for piecewise-linear profit functions using a general-purpose solver, and tested on several artificially created instances and on four TSPLib instances involving up to 535 vertices. A detailed analysis of the problem and the solution is performed. Keywords Selective traveling salesman problem· Time-dependent profits· Multiple visits Mathematics Subject Classifications 90B06· 90C10· 90C05· 90C27 This work was partly supported by the Canadian Natural Sciences and Engineering Research Council (NSERC) under grants 2019-00094 and 2015-06189, by the Ministry of Science, Innovation and Universities of Spain, the European Regional Development Fund (ERDF) and Junta de Andalucía, FEDER-UPO Research & Development Call under grants PID2019-104263RB-C41, PID2019-106205GB-I00, US-1381656 and UPO-1263769. This support is gratefully acknowledged.Thanks are due to the editors and to the referees for their valuable comments. * Eva Barrena ebar[email protected] Extended author information available on the last page of the article E.Barrena et al. 1 3 1 Introduction In several contexts, a traveler holds a list of potential sites of interest, but it may not be possible nor desirable to visit all of them. Some sites will be selected and then visited by means of a single tour. With each solution is associated a profit derived from visiting the sites. One example of this setting occurs in the planning of tourist trips. An interesting application cited in Vansteenwegen etal. (2011) is the Mobile Tourist Guide of Souffriau etal. (2008). Similar tourist trip problems are mentioned by Wang etal. (2008); Schilde etal. (2009) , and daSilva etal. (2018) where the profit is measured in terms of the interest associated with visiting the sites. Another example arises in the collection of letters from mailboxes. Here the benefit can be measured by the mail volume accumulated in the mailbox at each visit. Other applications are encountered in the surveillance activities of submarines or unmanned aircraft (Wang et al. 2008), and in water sampling Zhang etal. (2020). A recent application arises in the context of a parking warden distributing fines for irregularly parked cars (Bruglieri (2020)), where the profit associated with an inspection depends on the time elapsed since the previous inspection. This problem is known as the selective traveling salesman problem (STSP) Laporte and Martello (1990), sometimes called orienteering problem (Golden et al. 1987; Vansteenwegen et al. 2011), if the profits are time-independent. However, there also exist several settings where the profits are time-dependent. For example, the pleasure associated with a tourist attraction is often related to crowdiness and, therefore, to the time of the day. In postal applications it is clear that mail accumulation is time-dependent. In military applications the profit associated with surveillance activities may vary over time. Hence, we study an extension of the STSP with time-dependent profits (STSP-TDP). We assume that the problem is defined over a given time horizon and that the sites are to be visited by a single uncapacitated vehicle during a work shift whose length does not exceed that of the planning horizon. Waiting before starting the tour is allowed, i.e., the shift does not necessarily start at the beginning of the planning horizon. Each site has a time window and a service time, and it may be beneficial for the vehicle to wait along its route to let the profit increase at some sites, as is the case of the mail collection application. As we will describe, in some versions of the problem it may be beneficial to visit the same site more than once. For reviews of the STSP the interested reader is referred to Feillet etal. (2005), Vansteenwegen etal. (2011), Archetti etal. (2014) and Gunawan etal. (2016). Of interest in the context of the STSP-TDP is the survey of Gavalas etal. (2014) which presents a detailed description of the tourist trip design problem. These authors observe that this problem can be viewed as a bicriteria generalization of the TSP, i.e., maximizing the collected profit and minimizing the travel cost. Yu etal. (2019b) investigate the team orienteering problem with time windows and time-dependent scores. In this work, each vertex is associated with a basic score and several recommendation factors that vary depending on the time of visit. The authors propose a mathematical formulation and a hybrid artificial bee colony algorithm to compute optimal solutions for small instances and near-optimal solutions for larger instances. 1 3 Analysis oftheselective traveling salesman problem with… There also exists a rich literature on several variants of the STSP-TDP studied in this paper, which is summarized in Table1 but, to the best of our knowledge, our variant is unique and we are the first to provide a formulation solved by means of an exact branch-and-cut algorithm capable of solving instances much larger than was previously achievable. In our version of the STSP-TDP, the starting time of the route is also optimized within the planning horizon and waiting at the sites is allowed in order to arrive at a site when the profit to be collected is optimal. Here we introduce, model, and solve this problem exactly. We perform tests on artificial instances and on TSPLib instances, and we derive insights based on the problem characteristics and on the computational results. The remainder of this paper is organized as follows. In Sect. 2, we formally describe the problem and a number of its variants, and we propose corresponding mathematical programming models. An analysis of some properties of the problem depending on the shape of the profit functions is presented in Sect.3. This is followed by computational results in Sect.4 and by conclusions in Sect.5. 2 Formal definition andmathematical models The STSP-TDP is defined on a directed graph G=(V,A) , where V is the vertex set, 0∈V is the depot and V�={1, …,n} is the set of sites. The arc set is defined as A= {(i,j)∶i,j∈V,i≠j }. A travel time 𝜏ij is associated with each arc (i,j). The problem is defined over a planning horizon of length T, and time can be discretized into a set of moments t∈T={1, …,T} . Each site i has an associated profit pi(t) that depends on t. A solution is a closed circuit not exceeding L time units ( L≤T ), leaving the depot at time td 0 , returning to the depot at time ta 0≤T and visiting a subset of the sites, where ta 0 −t d 0≤L . The goal of the problem is to find a solution of maximal total profit for the selective traveling salesman problem with time-depend- ent profits (STSP-TDP). We assume that there are no vehicle capacity constraints and that one of the following two time-dependent profits is considered: 1. Profit is cumulative, i.e., the profit function is monotonically increasing. The later a vertex is visited, the higher is the collected profit. It follows that if a vertex is visited several times, one can achieve the total profit by performing only the last visit. An example of this setting is letter collection in mailboxes. 2. Profit depends just on the time the vertex is visited. The profit function is not necessarily monotonically increasing. Then it may be beneficial to visit a vertex more than once. Examples include parking tickets, publicity delivery, or fund collection by humanitarian organizations. It follows from the second profit function type that a site may be visited more than once, and in both cases imposing a waiting time between successive visits to the same site may be appropriate since the collected profit is the one observed upon arrival. E.Barrena et al. 1 3 Table 1 Variants of the STSP-TDP References Length limit on tours Time windows Profit function Multiple visits each visit Collect all profit Number of vehicles Exact algorithm (largest size) Heuristic Erkut and Zhang (1996) Yes No Decreasing No No 1 Branch-and-bound (20) Greedy Erdoğan and Laporte (2013) Yes No Service time dependent Yes Yes 1 Branch-and-cut (200) – Afsar and Labadie (2013) Yes No Decreasing No No ≥1 Column generation (100) Evolutionary local search Yu etal. (2019b)Yes Yes Arbitrary No No ≥1 – Bees Yu etal. (2019a)Yes No Service time dependent No No 1 – Matheuristic Yu etal. (2021)Yes Deadlines Decreasing No No ≥1 Branch-and-cut (200) Modified coordinate search This paper Yes Yes Increasing or arbitrary Yes Yes 1 Branch-and-cut (535) – 1 3 Analysis oftheselective traveling salesman problem with… 2.1 At most one visit persite allowed We first model the case in which at most one visit to each site is allowed. The formulation we propose requires that the profit functions be linear or piecewise linear, with time as a dependent variable. In this case, a time discretization is not required. We define variables xij equal to one if and only if arc (i,j)∈A is used in the solution, and variables ti equal to the time at which vertex i∈V� is visited. In what follows, M is a large positive number. The problem for the continuous single-visit case (SF) is then formulated as follows: subject to The objective function (1) represents the total collected profit to be maximized. Constraints (2) are the flow conservation conditions and ensure that there is at most one incoming and one outgoing arc for each site. Constraint (3) ensures that there is one incoming and one outgoing arc for the depot. Constraint (4) imposes a maximal route duration of L (time units). Constraints (5)–(7) ensure that travel times are respected and eliminate subtours. Finally, constraints (8) and (9) define the domains of the variables. Note that the case of “exactly one visit” is a particular case arising in the traveling salesman problem with time-dependent profits (TSP-TDP), and hence, its formulation is obtained by just changing “ ≤1 ” with “ =1 ” in constraints (2). (1) ( SF)maximize ∑ i∈V � pi(ti ) (2) ∑ j∈V,j≠i xij = ∑ j∈V,j≠i xji ≤1i∈V � (3) ∑ j∈ V� x0j= ∑ i∈ V� xi0= 1 (4) ta 0 −t d 0≤L (5) tj≥ t i +𝜏 ij −M(1−x ij )i,j∈V � ,i ≠j (6) tj ≥t d 0 +𝜏 0j −M(1−x 0j )j∈V � (7) ta 0≥ t j +𝜏 j0 −M(1−x j0 )j∈V � (8) ti ∈[0, T]i∈V � (9) xij ∈{0, 1}(i,j)∈A. E.Barrena et al. 1 3 We can impose the following bounds on the timing variables, which indicate that one cannot arrive at vertex i earlier than 𝜏0i : A similar reasoning can be applied at the end of the planning horizon: one can compute the latest arrival time at vertex i such that one still arrives back at the depot at time T. The following upper bound on ti can be imposed: 2.2 Multiple visits tosites allowed There are two main ways to model problems in which multiple visits to the same site are allowed. Some models do not replicate the sites and allow multiple visits by controlling the number of times a site is visited (see, e.g., Bruck and Iori 2017; Salazar-González and Santos-Hernández 2015; Erdoğan and Laporte 2013, and Munari and Savelsbergh 2022). The other approach is to make several copies of the same site (see, e.g., Gribkovskaia etal. 2007 and Hoff et al. 2009). Here we adopt the second modeling technique. More specifically, we make use of an auxiliary two-dimensional directed graph G=(V,A) (see Fig. 1) whose x-axis represents the periods of the planning horizon and whose y-axis represents the sites and the depot. The graph G extends the graph G=(V,A) , so that for every vertex v∈V and every period t∈T , there is one vertex v∈V identified with the pair (t,v) , which is labelled as v=t ⋅ |V|+v . It follows then that, for each given vertex v∈V we can obtain the corresponding period t and site v in graph G as follows: t(v)=⌊v∕�V�⌋ and v(v)=v∕�V�−⌊v∕�V�⌋ . We denote by t(i) and v(i) the time t∈T and the vertex v∈V corresponding to the vertex i∈V , (10) ti≥ 𝜏 0i i∈V �. (11) ti≤ T−𝜏 i0 i∈V �. Fig. 1 Auxiliary graph G=(V,A) , where |V|=N 1 3 Analysis oftheselective traveling salesman problem with… respectively. Therefore, the profit function at vertex v is pv=pv(t) . Note that not all arcs are allowed in G and that the starting and ending vertices must correspond to the depot. After predefining the set A , we need to solve a selective TSP with profit on G , with a maximum route length L no larger than the duration T of the planning horizon. We have then no predefined starting and ending vertices, but these must be selected within a subset {t ⋅ | V |∶t= 0, 1, ..., T}⊂V representing the set of depot vertices (T copies of the depot). The set of site vertices is V�= V ⧵{t ⋅ | V |∶t= 0, 1, ..., T} . The set of available arcs A is composed of the set A1 of arcs linking vertices from the same site at consecutive periods (for waiting times), and the set A2 of arcs linking vertices from different sites and whose difference between their periods equals the travel time between these sites. Therefore, and A =A 1 ∪A 2 = {(i,j) |( (v(i)=v(j)) ∧ (t(j)= t(i)+1) ) ∨( (v(i)≠v(j)) ∧ (t(j)−t(i)=𝜏 ij ) ) } . Note that Fig.1 shows a representation of the horizontal arcs from the set A1 and a partial representation of the set A2 (dashed arcs). For the sake of clarity, from the latter we only represent arcs departing from the depot. Note that if L=T , the problem over G is very similar to the STSP with profits (see Laporte and Martello 1990 and Vansteenwegen etal. 2011). In the extended graph G=( V , A ) , the problem is similar to the STSP, where we have a set of | V |=N ⋅ (T+1)−1 vertices, each with an associated profit. The difference between our problem in the auxiliary graph and the STSP is that, in our case, the starting and end vertices are not fixed, but belong to the set of depot vertices with zero profit. In order to obtain the STSP, we add two artificial vertices B1 and B2 , which will be the starting and ending vertices of the Hamiltonian path, respectively. Accordingly, a set of zero length arcs joining B1 and the depot vertices and the latter with B2 is also added. So, from now on, the problem is defined on  G=(  V,  A ) , where  V =V∪{B 1 ,B 2} and  A =A∪ {(i,B 2 ) | i∈V⧵V � }∪{(B 1 ,i) | i∈V⧵V �} . We use directed continuous variables yij representing the flow over arc (i,j) and binary variables 𝛾i equal one if the shift starts at vertex i∈{0, ..., T−L} . Note that the graph  G is a time-ordered graph, which enables us (for fixed depot departure and arrival times td 0 and ta 0 , being ta 0 −t d 0 = L ) to model the problem as a longest path problem. In doing so, we transfer the profit associated with a vertex j to its incoming arcs in A2 . That is, each arc ( i,j)∈A 2 has an associated profit pij =pj . The profit associated with the remaining arcs in  A equals zero. The problem for the discretized multiple-visit case (MF) over  G is formulated as follows: subject to A 1= {(i,j) |( (v(i)=v(j))∧(t(j)= t(i)+1) ) }, A2 = {(i,j) |( (v(i)≠v(j))∧(t(j)−t(i)=𝜏 ij ) ) } , (12) ( MF)maximize ∑ (i,j)∈  A pij ⋅y ij E.Barrena et al. 1 3 The objective function (12) is the total collected profit. Recall that the profit is collected when the vehicle arrives at the vertex. Constraints (13), where 𝛿+(i) and 𝛿−(i) are the sets of successors and predecessors of vertex i in graph  G , respectively, ensure that exactly one arc departs from the artificial vertex A to the set of depot vertices, that one unit of flow arrives at B from the same set, and enforce the flow conservation conditions for the remaining vertices, which are the site vertices. Constraints (14) and (15) impose a maximal route duration by means of the 𝛾 variables. There are as many 𝛾yL variables as T−L time periods. By selecting only one of the 𝛾yL variables, constraints (16) ensure that the route starts at one time instant and ends after exactly L periods. Finally, constraints (17) and (18) impose the binary condition of the 𝛾 variables and the non-negativity condition of the y variables, respectively. 3 Analysis oftheproblem andshapes oftheprofit function As explained in Sect.2, depending on the shape of the profit function, the problem possesses certain characteristics. These will not only be influenced by the monotonicity condition of the profit functions, but also by their specific shape. Observation 1. Let pi∶T → ℝ represent the accumulated profit at vertex i∈V� arising from a positive non-cumulative profit function p� i∶T →ℝ + , that is, the accumulated profit at vertex i during the time interval [0,t] is calculated as pi (t)=∫ t 0 p� i (t) dt . Then, pi is a monotonically increasing function and the total profit collected visiting vertices i at time t1 and t2∈T ( t1<t2 ) equals the profit collected by visiting vertices i only once at time t2 . Proof If vertex i∈V� is visited at time units t1 and t2∈T , the total collected profit equals ∫t 1 0 p� i (t)dt +∫ t 2 t1 p� i (t)dt =∫ t 2 0 p� i (t) dt . (13) � j∈𝛿+(i) yij −� j∈𝛿−(i) yji = ⎧ ⎪ ⎨ ⎪ ⎩ 1 if i=B1 0 if i≠B1,B 2 −1 if i=B2 (14) yAi ≤𝛾t(i),i∶v(i)=0 and t(i)∈{0, ..., T−L} (15) yi+L,B≤𝛾t(i),i∶v(i+L)=0 and t(i)∈{0, ..., T−L} (16) ∑ i∈{0,...,T−L} 𝛾i= 1 (17) 𝛾i∈{0, 1}i∈{0, ..., T−L} (18) yij ≥0(i,j)∈  A . 1 3 Analysis oftheselective traveling salesman problem with… If vertex V′ is visited only once at time unit t2 , the total collected profit equals pi (t 2 )=∫ t 2 0 p � i (t)dt . ◻ Observation 2. If pi(t)=𝛼i for all i∈V� , 𝛼i≥0 , then the STSP-TDP when at most one visit per site is allowed obviously becomes the STSP. In this case, it does not matter whether L=T or L<T since the collected profit is not time dependent. Observation 3. Let us assume that L is large enough to visit all vertices in any order and that each site can be visited at most once (following formulation (SF) presented in Sect.2.1). If all profit functions are linear, i.e., pi(t)=𝛼it for all i∈V� , 𝛼i≥0 , 𝛼i≤ 𝛼 i+1 , and 𝜏0,i≥𝜏0,i+1 for all i∈ V �⧵{N} , then xi,i+1=1 for all i∈ V �⧵{N,N−1} and xN0=1 . xi,j=0 for all j≠i+1 , i∈ V �⧵{N,N−1} . That is, under the described conditions, if the vertices are labeled in increasing order with respect to the slope ( 𝛼i≤ 𝛼 i+1 ), the visiting order coincides with the labeling order. Proof Given two vertices i and i+1∈V� satisfying the above mentioned conditions, it is always beneficial to first visit the one with the lower slope (in this case i since 𝛼i≤𝛼i+1 ). Let p(i, j, t) be the profit collected at vertices i and j if vertex i is visited at time t and vertex j at time t+𝜏ij . Then, starting from vertex 0, the collected profit obtained by visiting first vertex i and then vertex i+1 is p(i,i+1, 𝜏0,i)=𝛼i𝜏0,i+𝛼i+1(𝜏0,i+𝜏i,i+1) . The collected profit if vertex i+1 is visited before vertex i is p(i+1, i,𝜏0,i+1)=𝛼i+1𝜏0,i+1+𝛼i(𝜏0,i+1+𝜏i+1,i) . Let us demonstrate that the collected profit is larger if vertex i is visited before vertex i+1 , that is, p(i,i+1, 𝜏0,i)≥p(i+1, i,𝜏0,i+1) : By reductio ad absurdum, if p(i,i+1, 𝜏 0,i) < p(i+1, i, 𝜏 0,i+1) , then Since 𝜏i+1,i=𝜏i,i+1 , the inequality can be written as follows: which is not respected given that 𝜏i,i+1 , 𝛼i+1−𝛼i , and 𝛼i+1+𝛼i are positive values and 𝜏0,i+1−𝜏0,i≤0 . Therefore, the left-hand side of the inequality is positive and the right-hand side is negative. ◻ Observation 4. The STSP-TDP can be viewed as a generalization of the STSP with time windows by setting the profit function as a stepwise function equal to a negative number outside the time window, and equal to a positive constant during the time window interval. That is, if p(i,i+1, 𝜏 0,i )=𝛼 i 𝜏 0,i +𝛼 i+1 (𝜏 0,i +𝜏 i,i+1 )=𝛼 i 𝜏 0,i +𝛼 i+1 𝜏 0,i +𝛼 i+1 𝜏 i,i+1 , p(i+1, i,𝜏 0,i+1 )=𝛼 i+1 𝜏 0,i+1 +𝛼 i (𝜏 0,i+1 +𝜏 i+1,i )=𝛼 i+1 𝜏 0,i+1 +𝛼 i 𝜏 0,i+1 +𝛼 i 𝜏 i+1,i. 𝛼i𝜏0,i+𝛼i+1𝜏0,i+𝛼i+1𝜏i,i+1<𝛼 i+1𝜏0,i+1+𝛼i𝜏0,i+1+𝛼i𝜏i+1,i. 𝜏i,i+1(𝛼i+1−𝛼i)<(𝛼i+1+𝛼i)(𝜏0,i+1−𝜏0,i), E.Barrena et al. 1 3 Fig. 5 Mesh instances. Experiments 21 to 25 with 30 vertices, counterclockwise order Fig. 6 Piecewise linear profit functions with negative values outside time windows 1 3 Analysis oftheselective traveling salesman problem with… Table 4 Meshshape instances with time windows.Formulation (MF) Formulation (MF) Peak profit in increasing order of labels |V| L T Profit td 0 Gap (%) Vertices visited Time window Visiting times Time Max. time 15 240 240 10515.00 0.00 0.00 4 5 6 7 8 1 [−4, 196] [28, 228] [60, 260] [92, 292] [124, 324] – 49 87 125 163 201 240 0.16 900 15 240 480 31242.00 240.00 0.00 14 15 1 [316,516] [348,548] – 366 404 480 12.21 900 15 240 1440 49884.00 310.00 0.00 14 15 1 [316, 516] [348, 548] – 436 398, 474 550 32.94 900 15 480 480 62328.00 0.00 0.00 4 5 6 8 9 11 12 14 15 1 [−4, 196] [28, 228] [60, 260] [124, 324] [156, 356] [220, 420] [252, 452] [316, 516] [348, 548] – 52 90 128 182 220 274 312 366 404 480 2.31 900 15 480 1440 103566.00 140.00 0.00 8 9 11 12 13 14 15 1 [124, 324] [156, 356] [220, 420] [252, 452] [284, 484] [316, 516] [348, 548] – 178 216 270 308 346 384, 460 422, 498 584 15.85 900 E.Barrena et al. 1 3 4.2 TSPLib instances In this section, we consider different TSTLib instances adapted to the characteristics of our problem, that is, assigning one-peak time-dependent profit functions see Eq. (19) to vertices and considering different space measure scales. Assuming that the TSPLib coordinates are given in km, we consider constant speed and different scales to study the problem resolution. In this way, e.g., a scale of 1/1000 means that the coordinates are taken in meters. Tables5 and6 illustrate the sensitivity of the single- and multiple-visit models, respectively, to different scales for instance eil51 and the following parameter values: L=480 , T=1440 , speed =35.5 km/h. The CPU time limit has been set as Max. time=7200 seconds for these experiments. The table headings are defined as follows: – Scale: different values are considered to rescale the instance eil51. Scale 1 indicates that distance is taken in kilometers and 1/1000 in meters. – Profit: total profit obtained, which is the objective function value. – Total distance: total traveled distance in the corresponding scale measure. – Total distance (km): total traveled distance in km. – Time: computation time in seconds. – Gap (%): optimality gap calculated as UB−LB UB ⋅ 100 . – td 0 : departure time from the depot. – #Vertices visited: number of visited vertices in the solution. Since we consider a constant speed, the smaller the scale, the smaller the distances and, therefore, the more time is available to visit the vertices. It can be observed that this effect influences the resulting solutions, mostly in terms of total collected profit and computation time. Observe that, for the single-visit case (Table5), the higher the scale, the smaller the total profit obtained and the larger the computing times, being even not possible to obtain a feasible solution within the CPU time limit Max. time=7200 for scale 1/1. The starting time of the shift also changes with the scale, tending to start earlier when the scale is smaller. This is due to the fact that the considered speed is constant and, therefore, the smaller the scale, the larger the freedom to visit the vertices. Table6, which shows the results obtained for the multiple-visit case, exhibits a similar behavior in terms of the objective function. Although, as expected, much higher values of the objective function are obtained for the multiplevisit case, these values also increase as the scale decreases. However, with respect to the computing times, for the multiple-visit case, the behavior of the computing times is not uniform. In this case, different scales lead to different travel times and, therefore, different arc set A2 . Since the model allows to wait at the same site, shorter travel times enable to arrive with more flexibility at a site, thus leading to equal or better profits but not necessarily better computing times. Table7 presents the results obtained for the single- and multiple-visit cases for TSPLib instances eil51, st70, a280, and ali535. For these experiments, the maximum length of the route L=480 , the planning horizon T=1440 , the threshold on the computing time is Max. time = 7200 s and the scale is 1/1000, which is 1 3 Analysis oftheselective traveling salesman problem with… equivalent to considering the original coordinates in meters instead of in kilometers. The table headings are defined as follows: – TSPLib instance: indicates the name of the benchmark instances. – Profit: the total profit obtained, which is the objective function value. – Gap (%): optimality gap calculated as UB−LB UB ⋅ 100 . – #Vertices visited: number of visited vertices in the solution. – Time: computation time in seconds. – Total distance: total traveled distance in meters (corresponding to scale 1/1000). – td 0 : departure time from the depot. As expected, for both cases, the larger the number of vertices, the larger the total collected profit and the computation time. For the multiple-visit case, only instances eil51 and st70 could be solved to optimality within Max. time. For these instances, although the number of visited nodes in the multiple-visit case is considerably lower than for the single-visit case, these nodes are visited several times obtaining more than ten times higher values of the objective function (collected profit). Figure 7 illustrates the resulting routes with Formulation (SF) for the instances presented in Table7. Since the problem aims at maximizing the total Table 5 Variations to scale for instance eil51 Single-visit case (Formulation (SF)) Scale Profit Total distance Total distance (km) Time Gap (%) td 0 #Vertices visited 1/1 – – – – – – – 1/5 3034136.16 246.34 1231.70 7200 0.40 475.75 51 1/10 3047909.70 131.35 1313.50 9.0 0.00 472.94 51 1/20 3048000.00 65.67 1313.40 0.9 0.00 471.76 51 1/50 3048000.00 26.27 1313.50 0.9 0.00 471.06 51 1/100 3048000.00 13.14 1314.00 0.9 0.00 470.82 51 Table 6 Variations to scale for instance eil51 Multiple-visit case (Formulation (MF)) Scale Profit Total distance Total distance (km) Time Gap (%) td 0 #Vertices visited 1/1 – – – – – – 1/5 54331764.71 215.75 1078.74 611.6 0.00 688 3 1/10 54726074.12 108.77 1087.68 281.08 0.00 688 3 1/20 55918907.67 226.14 4522.74 688.92 0.00 692 4 1/50 58765875.17 250.77 12538.24 259.88 0.00 706 3 1/100 58765875.17 125.38 12538.24 431.39 0.00 706 3 E.Barrena et al. 1 3 collected profit, the resulting routes differ significantly from those obtained with the usual TSP, where the objective is to minimize the total distance traveled. As expected, when the objective function is to maximize the total collected profit, the total distance increases with respect to that obtained from a TSP solution. A trade-off analysis between the collected profit and the total distance may shed some light on these differences. To this end, it becomes appropriate to use a multi-objec- tive approach. 4.3 Trade‑off betweenthecollected profit andthetotal distance. Multi‑objective approach Starting from formulation (SF), we consider the 𝜖 -constraints method proposed by Marglin (1967). That is, we include constraint (20) limiting the total distance of the route to a maximum of 𝜖 and the route is then obtained by maximizing the total collected profit and varying parametrically the maximum total distance 𝜖 : Table 8 represents the results obtained by the 𝜖 -constraints method for the TSPLib instance eil51 and the following parameter values: L=480 , T=1440 , speed =35.5km/h , scale =1∕10 . The table headings are defined as follows: – Threshold 𝜖 : threshold on the route total distance. – Profit: total profit obtained, which is the objective function value. – Total distance: total traveled distance in hectometers (corresponding to scale 1/10). – Time: computation time in seconds. – Gap (%): optimality gap calculated as UB−LB UB ⋅ 100 . (20) ∑ i ,j∈V i≠j 𝜏ijxij ≤𝜖 . Table 7 Results for TSPLib instances for scale 1/1000, L = 480 , T = 1440 TSPLib instance Formulation Profit Gap (%) #Vertices visited Time Total distance td 0 eil51 (SF) 3048000.00 0.00 51 1.2 1.31 470.61 eil51 (MF) 58765875.17 0.00 3 261.65 12.5 706 st70 (SF) 5779440.00 0.00 70 5.5 3.41 473.18 st70 (MF) 81698999.99 0.00 3 709.09 3.89 710 a280 (SF) 93677040.00 0.00 280 185.4 2.82 478.32 a280 (MF) – – – – – – ali535 (SF) 342699840.00 0.00 535 499.1 36.99 479.25 ali535 (MF) – – – – – – 1 3 Analysis oftheselective traveling salesman problem with… Observe that, except for the first four rows, the value of the total distance tends to be similar to that of the upper threshold 𝜖 . This follows from the fact that the larger the total distance, the less constrained is the problem and, therefore, the larger is the total collected profit, which is the objective function. The first four rows stand for values of 𝜖 larger than 131.35, which is the total collected profit when no constraints on the total distance are imposed (see Table5, third row). This explains the constant values for the first four rows of the third column. The first and second columns of Table8 are represented in Figure8 in the form of a Pareto curve for a trade-off between collected profit and maximum total distance. It can be observed that, as expected, the total collected profit increases as the threshold on the total distance increases. However, the profit stabilizes when the threshold 𝜖 reaches 130. In fact, if no threshold is imposed and only the total collected profit is maximized, then the resulting total collected distance equals 131.35. Therefore, for 𝜖 values larger than 131.35, the total collected profit remains constant. (c) a280 (d) ali535 (a) eil51 (b) st70 Fig. 7 Representation of the resulting routes for instances of Table7 with scale 1/1000 E.Barrena et al. 1 3 The routes associated with some of the solutions of Table8 are depicted in Figure9. As 𝜖 decreases, the route length decreases and tends to look like a usual TSP solution, in which the total distance is minimized and profit is not considered. Table 8 Trade-off between collected profit and total distance for instance eil51 at scale 1/10 Threshold 𝜖 Profit Total distance Time Gap (%) 200 3047909.70 131.35 20.8 0.00 180 3047909.70 131.35 19.8 0.00 160 3047909.70 131.35 19.9 0.00 140 3047909.70 131.35 16.6 0.00 130 3047793.97 129.54 24.5 0.00 120 3044886.66 119.54 1800 0.00 100 3030961.07 99.75 1800 0.01 80 3004438.23 79.93 1800 0.01 60 2922777.87 59.95 1800 0.04 50 2849024.68 49.85 1800 0.07 45 2797871.66 44.92 1800 0.06 44 2785162.11 44.00 1800 0.03 43 2760263.52 42.95 139.5 0.00 Fig. 8 Trade-off between collected profit and total distance for instance eil51 at scale 1/10 1 3 Analysis oftheselective traveling salesman problem with… 5 Conclusions We have introduced, modeled, and solved the STSP-TDT. The STSP-TDT is a generalization of other well-known variants of the traveling salesman problems such as the TSP itself, the STSP, as well as the TSP and the STSP with time windows. Some interesting properties arise in the context of time-dependent profits. For example, it sometimes makes sense to visit the same vertex multiple times and to optimize the starting time of the tour. We have proposed and tested a formulation of the single-visit problem that can be used if the profit functions are linear or piecewise linear. We have also proposed and tested an extended formulation for the case when multiple visits to the same vertex are allowed and desirable. In this case, we formulate the problem by means of an extended graph so that this variant reduces to an STSP, adapted to be solved as a longest path problem. We have analyzed the problem by studying the shape of the time-dependent profit functions. We have also performed several experiments on artificially created instances and on some TSPLib instances considering the single- and multiple-visit cases. Our results on artificially created instances validate the model performance and highlight the importance of allowing a variable starting time of the route. We have considered several scale measures and optimally solved instances containing up to 535 vertices for the single-visit case. We have also compared the results obtained for the single- and multiple-visit cases and analyzed the results of our single-visit case experiments by means of a Pareto frontier representing the trade-off between the collected profit and the total distance traveled. We observe that these objectives are naturally opposed to one another. (a) = 140 (b) =100 (c) =60 (d) =50 (e) =45 (f) =43 Fig. 9 Representation of the resulting routes for different values of 𝜖 E.Barrena et al. 1 3 Appendix. Results of15 and50 vertices mesh instances See Figs.10, 11, 12 and 13. Fig. 10 Mesh instances. Experiments 1 to 5. 15 vertices. Clockwise order 1 3 Analysis oftheselective traveling salesman problem with… Fig. 11 Mesh instances. Experiments 16 to 20. 15 vertices. Counterclockwise order