{'fraction_non_alphanumeric': 0.03601786009591533, 'fraction_numerical': 0.008632379692409459, 'mean_word_length': 4.36670216542421, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Spatio-Temporal Representation for the Orienteering Problem with Time-Varying Profits

We consider an orienteering problem (OP) where an agent needs to visit a series (possibly a subset) of depots, from which the maximal accumulated profits are desired within given limited time budget. Different from most existing works where the profits are assumed to be static, in this work we investigate a variant that has time-dependent profits. Specifically, the profits to be collected change over time and they follow different (e.g., independent) time-varying functions. The problem is essentially NP-hard. To tackle the challenge, we present a simple and effective framework that incorporates time-variations into the fundamental planning process. Specifically, we propose a deterministic spatio-temporal representation where both spatial description and temporal logic are unified into one routing topology. By employing existing basic sorting and searching algorithms, the routing solutions can be computed in an extremely efficient way. The proposed method is easy to implement and extensive numerical results show that our approach is time efficient and generates near-optimal solutions.


Introduction
The rapid progress of smart vehicle technologies allow us to envision that, in the future autonomous vehicles are able to carry out various tasks with little or even no human effort. We are interested in designing an efficient routing method to navigate an vehicle (agent) among a number of known and fixed depots, where each depot has some profit (e.g., score, benefit, utility, load) to be collected. If the travel time is limited, it is likely that the agent is not able to traverse all depots due to the limited time budget. This variant of routing problems is called the orienteering problem (OP) [10]. In a nutshell, an OP aims to find a tour traversing a subset of depots so that the accumulated profit collected from those traversed depots are maximized.
Different from many existing vehicle routing problems which focus on analyzing path properties in the static context (i.e., unchanging environment/topology with stationary Figure 1: An autonomous vehicle needs to route through depots with time-varying profits (loads). The goal is to maximize overall collected profits within given limited time. The task can be persistent.
cost metrics) [16,11], in this work we are intrigued to investigate a time-varying variant of OPs, i.e., each depot has a time-varying profit.
Here are a few motivational examples: • As illustrated in Fig. 1, an autonomous truck needs to pick up goods from a number of fixed depots where manufacturing factories are located. The goods are produced consistently and accumulated as time goes by -so they are time-varying. The growing speeds/patterns of goods at different factories may be nonidentical: larger factories grow faster and smaller ones grow slower. Assume the truck has sufficiently large capacity and it empties all goods from a depot when it arrives there. The objective is to find a route so that the truck will load the most goods in a given time window. Similar application scenarios also include, e.g., mail/garbage trucks and smart taxis since the volumes of mails/garbage and the number of passengers are also time-varying. • In environmental monitoring, autonomous robots are deployed to collect environment data in order to estimate an underlying environment state. However, the environment attributes at different locations can be time-varying (e.g., dissolved chemical compounds and algae blooms in the water vary both spatially and temporally.) An important objective of environment monitoring is to plan so-called "informative paths" [4] that navigate the robots to acquire data from those most information-rich spots which best help estimate the environment. The learned environment model allows us to intervening with the environment. For instance, given a learned ocean model with known algae bloom growing patterns, marine robots can be routed to clear up the algae blooms as efficient as possible.
In this paper, we present our initial study for the timevarying OP. We start our analysis from the single agent planning case, and attempt to establish a new framework that is different from traditional modeling and solving routines. We are showing that, a big challenge of the time-varying OP (even for single agent case) lies in the requirement of a special treatment in an extra dimension -the time dimension, which inevitably introduces extra complexity as we need to model, predict, and integrate future dynamics.

Related Works
The routing problems have been well studied topics in many research domains including the operations research, theoretical computer science, and transportation systems [2,3,6]. Typical routing problems involve incorporation of constraints expressed from the nature of the target problems, which also narrow the space of searching for solutions [18]. We are interested in a variant of routing problems called the orienteering problems (OPs) [10,21]. An OP considers both travel cost (e.g., travel time) and scores/credits collected along the travel. The goal of the OP is to determine which subset of vertices to visit and in which order so that the collected score within a given period is maximized. The OPs integrate characteristics of both knapsack problems (KPs) [14] and travelling salesman problems (TSPs) [18], and OPs are NP-hard as well. In contrast to the TSP, not all vertices of an OP need to be visited due to the limited time budget. During the past a few decades, several variants of OPs have been studied, such as time-dependent OPs, Team OPs, (Team) OPs with Time Windows and OPs with stochastic profits. Recent survey papers [21,11] have profoundly discussed state-of-the-art techniques of these variants as well as their applications.
While OPs can be formulated as mixed integer programs (MIPs), the problem size typically is too large to directly use commercial solvers. A wide range of decomposition methods such as branch-and-price algorithms have been developed so that a large-scale MIP can be decomposed into smaller problems (e.g., a master problem and a series of sub-problems) which can then be iteratively solved by commercial solvers [12,15]. In order to reduce the heavy computational burden in decomposition methods, heuristics and metaheuristics have been extensively studied, typically including tabu-based or neighborhood search based procedures [5,20,23].
Although in general OPs have been well researched, the time-dependent OPs (TOPs) have received relatively less attention comparing with other variants [9,11]. Even so, most of existing TOPs discuss the time-varying properties that are associated with the real travel time between pairwise nodes, and assume that travel time between two nodes depends on the departure time at the first (or an earlier) node [8,7,22,17,24]. Very rarely we could find the works that discuss about time-varying scores/credits of OPs. One work that share certain similarity with this proposed prob-lem is [1], where multiple vehicles need to serve a number of clients and the profit of each client follows a decreasing function of time. The work analyzed a lower bound and upper bound based on a classic MIP formulation.
Instead of employing conventional techniques such as the column generation approach used in [1], in this work we present our first study that models and tackles the problem from a different perspective: we start from establishing a representation built from the spatial and temporal constraints, so that the time dependence attribute is transferred from the bulk MIP to a separate and intuitive representation. With that, fast approximate OP solutions can be found by employing and extending order-sensitive topological algorithms.

Problem Description and Formulation
A routing problem can be represented with a graph G = (V, E), where V is the set of vertices and E denotes the set of edges. Let us denote the number of vertices as |V | = n + 1, and suppose every edge takes time to traverse. Although the travel time, in many situations, depends on the properties of traffic network such as congestion and capacity, we assume that the travel time τ ij between two vertices v i and v j is time-invariant for simplicity * . We associate each vertex v i with a time-varying value, called profit, which is denoted by f i (t) ≥ 0 at time t ≥ 0. Here f i (·) is of arbitrary nonlinear function form. We assume that function f i (·) is known or can be predicted or approximated.
Suppose that the agent (vehicle) starting from a dummy node v 0 at time 0 travels across a subset of vertices on the graph G. When the agent visits vertex v i at time t i , it will collect the profit f i (t i ). The remaining profit at the vertex v i right after the agent leaves becomes 0 and accumulates again. Additionally, the profit at v 0 is assumed to be 0, i.e., f 0 (t) = 0. Assuming the agent visits each vertex once, the objective is to determine the order of a subset of vertices to visit so that total profits collected by the agent is maximized within a given planning period T . Note that we do not assign a specific destination to the agent, as the problem with a fixed end vertex is a special case for our problem.
Let x ij = 1 if the agent travels from v i to v j , and 0 otherwise. Let t 0 = 0. We also introduce extra variables u i with u 0 = 0 to eliminate the subtours. Then the problem in this study can be formulated as the following mixed-integer program.
Eq. (1) is to maximize the total collected profit. Constraint (2) guarantees that the path starts at dummy node v 0 . Constraints (3) ensure the connectivity of the path and guarantee that every vertex is visited at most once. The limited time budget is ensured by Constraint (4), while Constraint (5) determines the visiting time t i along the path. Constraints (6) and (7), so called Miller-Tucker-Zemlin (MTZ) formulation in the traveling sales problem [18], are used to prevent subtours.

A Spatio-Temporal Representation
It appears a daunting task to solve the problem (1)-(8) due to the complexity of objective function. Most of existing literature in OPs either lumps all constraints together and solves it by conventional solvers of MIPs [19,21], or decouples the constraints into master-subproblem modules such as column generation [1], or use certain heuristics such as centerof-gravity heuristic [10]. In contrast, we desire to develop a framework starting from a constraint-included representation that is intuitive to understand, easy to implement from scratch, and flexible to modify and extend. In this section, we present a means for embedding constraints into a spatiotemporal representation built on which the original routing problem can be tackled by efficient methods (though it is still a NP-hard problem).
As the problem essentially aims to determine the visiting time and order of vertices, it inspires us to incorporate a time dimension to extend the 2-dimensional graph on a spatial plane to a 3-dimensional graph (topology). To make the model implementable, the time range [0, T ] is discretized into a sequence of time intervals ∆ t of equal length, and the interval ∆ t is used as a time unit that specifies discrete time resolution. Thus, the travel time τ ij can be expressed as multiple times of the time unit. For example, τ ij = n ij ∆ t and T = n T ∆ t , where n ij and n T are integers. Figure 2 shows two examples that describe the basic idea. Intuitively, one can imagine that each spatial graph vertex ( Fig. 2(a)) is extended to a sequence of vertices expanding in the time dimension, where each vertex is on an unique time layer/interval corresponding to a future time moment ( Fig. 2(b)). Then edges are added by concatenating vertices of different time layers, constrained by the real travel time. Formally, two vertices on different time layers form an edge if and only if the two vertices are spatially traversable and the time difference between the two time layers is exactly equal to the anticipated real travel time between the two vertices.
Each vertex contains a profit and the profit is timevarying. In other words, the profit values at different time layers are not the same. Therefore, the problem is equivalent to finding a path from the given start vertex at time 0 such that the path transits other vertices within time T and the total collected profit is maximized. It is worth mentioning that, the spatio-tempral edges are "directed" since each edge must start from a vertex at an earlier time layer and ends at one at a later moment; Because the time is unidirectional and cannot travel backwards, it is impossible to form a loop or cycle on the spatio-temporal graph. As a result, such a spatio-temporal representation is equivalent to a vertex-weighted Directed Acyclic Graph (DAG). This allows us to conveniently develop our own routing method built on many existing efficient DAG algorithms.
More formally, the spatio-temporal representation is a vertex-weighted DAG, denoted by . Keep in mind that u = n u ∆ t and a similar equation holds for s. As an example, suppose that we have a complete graph G with 3 vertices, ∆ t = 1, and T = 5. In the spatio-temporal representation G shown in Fig. 2(b), there are 18 vertices v 0,0 , v 0,1 , ..., v 2,5 , each vertex in the original graph G is duplicated at the discrete time in T = {0, 1, 2, 3, 4, 5}. If τ 01 = 3 and τ 21 = 5, then vertex v 0,0 is directed to v 1,3 and v 2,0 is directed to v 1,5 . In this example, we have 9 directed edges in total.
With graph G = (V, E) and given time limit T , the spatio-temporal graph G = (V , E , W ) can be constructed by Alg. 1. Assume there are n vertices in G, the time complexity of Alg. 1 is O(n 2 T /∆ t ) because there are three for loops each of which is associated with either n or T . Also there are n(T /∆ t + 1) vertices in G , so the space complexity is O(nT /∆ t ) .
for each vi's neighbor vj do 11: if t + τij is equal to t AND t <= T then 12: put edge e ijtt into the edge set E 13: push v jt into vector v it .successors 14: update indegree of v it . 15: put v it into the vertex set V 16: set the v 0,0 .sum to 0 17: return graph G = (V , E , W ) Note: fi(t) is the time-varying profit function of vertex vi at time t. v 0,0 is the start vertex in G , and .sum is used to store accumulated profit from prior traversal along a path. The label .parent points to the predecessor vertex.

Routing Algorithm
An important advantage of the spatio-temporal graph lies in that, the time related constraints have been incorporated into such a spatio-temporal representation, so that temporal related constraints can be decoupled and eliminated from the process of optimizing the profits. Thus, the problem (1)- (8) is equivalent to finding a path P from vertex v 0,0 = (v 0 , 0) to v ks on G where s ≤ T such that (v i u)∈P w iu is maximum.
Since the spatio-temporal graph is essentially a DAG, we develop our routing solution via extending classic DAG algorithms. Specifically, we found that the profit maximization can be transformed to a longest path problem by accu-mulating the profits collected from vertices instead of summing up edge lengths along a path. We manipulate the DAG so that vertices are sorted in a topological order along the temporal dimension, and then employ a dynamic programming paradigm to compute the maximal profit path.
It is also noteworthy that, while developing a solution to the time-varying OP, we take into account of two concerns that are related to applications.
• Specification of a Routing Destination: Many routing problems, including classic OPs, require to specify a routing destination. The destination can be the original depot where the agent departures (e.g., a mail truck needs to return a central processing office); the destination can also be an arbitrary depot located somewhere else (e.g., a freight truck needs to pick up goods and unload them into some specified processing location that is different from the starting depot).
• Persistent Task: Many long-term missions need repetitive and persistent routing, for which specifying a routing destination is not necessary or even inappropriate. For instance, in the persistent environmental monitoring task, we do not need the robot to stop at some specified location, as the robot will need to resume to next round of routing after the completion of current one. Thus, the routing destination should be computed on the fly based on the profit optimization constrained by time T , instead of being manually specified.
We will show that the proposed framework works for both specified and unspecified routing destinations.

Topological Sorting of DAG in Temporal Dimension
The main purpose of topological sorting of the DAG is that, the vertices are "placed" onto different "stages" according to their temporal constraints, so that a dynamic programming structure (discussed in the following subsection) can be applied.
Formally, a topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge e uv from vertex u to vertex v, u comes before v in ordering. A topological sort of a graph requires that the graph must be a DAG. We employ a well-known algorithm developed by Kahn [13] to sort our spatial-temporal graph G , with main steps psudo-coded in Alg. 2. Briefly, we first find a list of vertices that have no incoming edges (with deg − (v) = 0), and insert them into a set S. Note, at least one such vertex must exist in a non-empty graph. Then we traverse the set S. Each time we remove a vertex v from S, and add it to the tail of the list L. After removing v, the indegree of its successors should be decreased by 1. Then we insert those vertices with updated indegree equal to 0 in the set S.
To analyze the time complexity, assume there are n vertices in G, so there will be n(T /∆ t + 1) vertices in G . For each vertex v it , there will be at most n − 1 directed edges. Therefore |E | = O(n 2 T /∆ t ), and the time complexity of Alg. 2 is O(|V | + |E |) = O(n 2 T /∆ t ).
Algorithm 2: TopologicalSort (G ) 1: L: an empty list that will contain the sorted elements 2: S: a set of all nodes with no incoming edges 3: while S is not empty do 4: remove a vertex v from S 5: add v to the end of L 6: for each successor u of v do 7: if deg − (u) equals to 0 then 9: insert u into S 10: return L (a topologically sorted order) Note: G is a DAG, the indegree of v is denoted as deg − (v).

Computing Maximal Profit Path
We transfer the time-varying OP to a longest path problem in a DAG. The classic longest path problem is the problem of finding a simple path of maximum length in a given graph. We employ a dynamic programming structure to memorize incumbent maximal accumulated profit at each vertex of topologically sorted stages. Note that, in our problem, we need to optimize profits collected from vertices, instead of adding up length of edges. Therefore, instead of using the longest path update function between two successive stages: where l[w] is the largest distance from start vertex to w, we utilize an update function: (10) Main procedures of computing the maximal profit path is described in Alg. 3. Briefly, the topologically sorted vertices V of the spatio-temporal graph G is used as an input. Then vertices from different stages form dynamic programming subproblems and they are updated with accumulated profits recursively, starting from v 0,0 . Here we use v it .path to store vertices along the path from start v 0 to v i (Note, only spatial information is recorded). To prevent from forming routing subtours, we check and discard those already visited vertices before each value update.
After the completion of dynamic programming, each vertex contains information of the maximal profit path that routes from v 0,0 to it. Since the graph G has incorporated the time limit T , every vertex is feasible to the time constraint. To find a maximal profit path to a specified vertex (destination) v i ∈ G, one simply needs to enumerate all states v ij ∈ G , ∀j of vertex v i and retrieve the path with the largest value. If a destination is not specified, one needs to enumerate all states of all vertices and find out the maximal one among them. The time complexity of Alg. 3 is O(n 2 T /∆ t ) due to its two for loops.

Main Routing Algorithm
With the components descried above, the main algorithm is shown in Alg. 4. According to the analysis of each part, the overall time complexity of our algorithm is n 2 T /∆ t , and the space complexity is n 2 T /∆ t as well. for each vertex v jt in v it .successors do 4: if vertex vj is not in the v it .path then 5: if v it .sum + v jt .prof it > v jt .sum then 6: v jt .sum = v it .sum + v jt .prof it 7: update the v jt .parent to v it 8: v jt .path = v it .path + vj 9: for each vertex v it in G do 10: find the maximal sum 11: retrieve a path P by backtracking from end to start 12: return P Note: The label .path is a vector that stores all visited vertices from start to vi Our method has a polynomial time complexity given a fixed ∆ t , but cannot guarantee to find the optimal solution to this NP-hard problem. The main reason for reaching at possible sub-optimality lies in that, we added a non-subtour constraint in order to (1) prevent the path from traversing back and forth among a small subset of adjacent vertices and (2) comply with the structure of dynamic programming. Such a constraint eliminates certain feasible searching space which possibly contains the optimal solution. One may regard this as a trade-off between solution quality and practical runtime. Nevertheless, our evaluation results with extensive trials show that on average our method produces nearoptimal solutions.

Discussion: Effects of Discretization
The time interval ∆ t plays a critical role in our framework as the total profits are actually evaluated at time steps equal to multiple ∆ t . Yet it may be impractical to select such time interval because it would result in an extremely large size of DAG. One possible implementation is to round the travel time to a value closet to some integer times of ∆ t . Hence, it is important to analyze the impact of errors due to such rounding procedure.
Assume that the profit function f i (t) satisfies the following Lipschitz condition: where K is a constant independent of i. Suppose that the optimal objective value for the problem (1)-(8) is z, and the optimal objective value by the proposed framework is z . Then we have the result as follows.
proof: Let P be the optimal path in the graph G for the problem (1)-(8) and let P be the optimal path in the proposed spatio-temporal DAG G . By the construction of G , P must correspond to a pathP in the graph G . Letz be the total profits (i.e. the value of objective (1) on this path) for the pathP . Since the difference between the discrete time in our framework and the original real-valued time is within ∆ t , the fact that any path contains no more than n vertices and the condition (11) lead to |z −z| ≤ nK∆ t . As P rather thanP is the optimal path in G , we havez ≤ z . By combining these results, we should have z − z ≤ nK∆ t . Conversely, by construction any feasible path on the graph G must correspond to a feasible path on G. Using similar arguments, we have z − z ≤ nK∆ t . Therefore, the result (12) holds. It is worthwhile noting that the constraint that the path in G or G contains no subtours is critical to the result (12).

Results
We conducted numerical evaluations to validate the proposed method. We compared our method with other algorithms, all of which were implemented in C++. The experiments were performed on a system with an Intel i5 2.2GHz processor and 4GB RAM. In our experiments, vertices are randomly generated in the area [−50, 50] × [−50, 50] on the x-y plane, and each vertex has a profit (weight) following certain time-varying functions. The distance between two vertices is Euclidean distance.

Routing Feature of "Orienteering"
First, we demonstrate that our solution has the basic orienteering property: given limited time, the path always goes through those vertices with large profits. Fig. 3 shows an example. We purposely manipulate the profit distribution among the vertices, such that in the upper right corner, there are more vertices with larger profits. For better visualization, in the figure the size of a vertex is proportional to the profit on it. Additionally, we purposely put the starting vertex on the left and do not specify a destination. From Fig. 3 we can see that, in order to obtain more profits, the route goes to the upper-right corner almost directly from the start vertex. In this way, a big part of time is used among traversing those vertices with large profits.

Routing Properties under Temporal Variations
To examine the effects caused by temporal variations, we manipulate the profit functions. Specifically, we divide the space into four regions (quadrants) I,II,III and IV, as shown in Fig. 4. The profit functions are the same if the vertices are in the same region, but different if not. For example, in region I, the profit function for each v it is where w i is the weight of vertex v i in graph G. (Keep in mind that, w i is different from w it which is time-varying. Here the weight w i refers to a fixed parameter for profit function.) Similarly, the profit functions in regions II, III and IV are Figure 4 reveals that, the path first transits the vertices in region II, because during the first half T , vertices in region II have larger profits than those in region III. After the path enters region I and after the time passes T /2, vertices in region IV contain larger profits. Such variations attract the path to go through vertices in region IV. This example inidicates that our algorithm is sensitive to the time-varying profit functions.

Comparison with Optimal Solution
We compare the result of our method with the optimal solution that is obtained by enumerating all solutions in a brute-force way. Because of the prohibitive time complexity O(n!) for searching for the optimal solution, the practical runtime for 13 vertices requires more than 10 minutes. Thus, we tested up to 12 vertices to compare with the optimal solutions. We investigated three representative profit functions in the form of linear, quadratic and logarithmic, respectively. The results are shown in Fig. 5. We can see that the results of our method are very close to those of the optimal solutions, for all the three functions. Figure 6 shows a group of paths produced from our method and the optimal solution. We use a linear function f i (t) = w i t/T for this example. In many cases, our algorithm get the same results as those of the optimal solution, as shown in Fig. 6(a) and Fig. 6(b). Sometimes the paths are different, such as Fig. 6(c) and Fig. 6(d), but the collected profits are quite similar (in this example, ours obtains 183.5 whereas the optimal is 185.0). Fig. 6(e) and Fig. 6(f) show another example.

Comparison with Classic OP Algorithm
We also compared our method with the classic OP algorithms. We implemented a well-known heuristic called center-of-gravity [10], and tested with both time-invariant and time-variant profit functions. Fig. 7 demonstrates the differences between the results of our approach and those of the OP. Fig. 8 show statistics of numerical evaluations with 200 vertices. We can see that, our method outperforms the OP for both the time-invariant and time-varying profit functions. Particularly, the difference margin is larger for the time-varying profits. Actually, the classic OP cannot handle time-varying profits and the total profit curve quickly converges (with fixed given time T , the overall profit of OP stops growing along with the increment of the number of vertices).
The running time is compared in Fig. 9, from which we can observe that, in practice our algorithm costs less time than that of the OP using the center-of-gravity heuristic.

Path Quality under Different Time Intervals
Time interval ∆ t determines time discretization resolution, and therefore affacts the optimality as well. Table 1 shows statistics of the route's quality under different time intervals. In the table, numbers in the first row are interval values, and numbers in the first column are the number of vertices. The remaining values are the collected profits from our method. We can see that, in general the route's quality is better when the time interval is smaller. However, obviously a smaller time interval will inevitably lead to a larger graph and thus require a larger running time.

Conclusion and Future Work
We presented a framework for addressing the orienteering problem with time-varying profits. Instead of following traditional mixed integer program solution routines, we develop an intuitive and effective framework that incorporates time-variations into the fundamental planning process. Specifically, we first construct a deterministic spatiotemporal representation where both spatial description and temporal logic are unified into one routing topology, and then we extend existing sorting and searching algorithms, so that the routing solutions can be computed in an extremely efficient way. Finally, we validated our method with numerical evaluations and the results show that our framework produces near-optimal solutions in a very efficient way. In this paper we provided an initial framework to tackle the difficulties and complexities caused by the temporal variations, for a single agent planning case. In the future, we are interested in extending the current framework to multivehicle routing scenarios. The problem is important because as we can envision that, the profits of smart vehicles (e.g., clients of driverless taxis, goods for smart fleet) are typically time-varying and thus an efficient vehicle routing strategy is extremely important. This problem is also challenging because, the planning not only needs to solve conflicts from the spatial perspective, but also needs to take into account the profits optimization in a coordinated manner in the time dimension.