A Spatio-Temporal Representation for the Orienteering Problem
with Time-Varying Profits

arXiv:1611.08037v2 [cs.AI] 2 Jul 2017

Zhibei Ma, Kai Yin, Lantao Liu, Gaurav S. Sukhatme
Abstract— 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 arbitrary 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 of inherent nonlinearity and difficult to solve by
existing methods. 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.

I. I NTRODUCTION
The rapid progress of smart vehicle technologies allows 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 a 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) [11]. 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 or topology with stationary
cost metrics) [17], [12], 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 growth rate of goods at
different factories may be nonidentical: larger factories
Z. Ma, L. Liu and G.S. Sukhatme are with the Department of Computer
Science at the University of Southern California, Los Angeles, CA 90089,
USA. {zhibeima, lantao.liu, gaurav}@usc.edu. K.
Yin is with HomeAway, Inc., yinkai1000@gmail.com.

Fig. 1. An autonomous vehicle needs to route through depots with timevarying profits (loads). The goal is to maximize overall collected profits
within given limited time. The task can be persistent.

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.
• 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 timevarying (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” [5] that navigate the
robots to acquire data from those most information-rich
spots which best help estimate the environment.
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 will show 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.
II. R ELATED W ORKS
The routing problems have been well studied in many
research domains including operations research, theoretical
computer science, and transportation systems [3], [4], [7].
Typical routing problems involve incorporation of constraints
expressed from the nature of the target problems, which
also narrow the space of searching for solutions [19]. We
are interested in a variant of routing problems called the
orienteering problems (OPs) [11], [22]. An OP considers
both travel cost (e.g., travel time) and scores 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
scores within a given period is maximized. The OPs integrate

characteristics of both knapsack problems (KPs) [15] and
travelling salesman problems (TSPs) [19], and OPs are NPhard 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 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 [22], [12] 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 [13], [16]. 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 [6], [21], [24].
Although in general OPs have been well researched, the
time-dependent OPs (TOPs) have received relatively less
attention comparing with other variants [10], [12]. 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 [18], [9], [8], [23]. Very rarely we could find the works
that discuss about time-varying scores of OPs. One work that
share certain similarity with this proposed problem is [2],
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 [2], 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.
III. P ROBLEM D ESCRIPTION AND F ORMULATION
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 states and
properties of the network such as congestion and capacity,
we assume that the travel time τij between two vertices vi
and vj is time-invariant for simplicity∗ . We associate each
∗ It is relatively straightforward to incorporate time-dependent travel times
in our proposed model described in the following section.

vertex vi with a time-varying value, called profit, which is
denoted by fi (t) ≥ 0 at time t ≥ 0. Here fi (·) is of arbitrary
nonlinear function form. We assume that function fi (·) is
known or can be predicted or approximated.
Suppose that the agent (vehicle) starting from a dummy
node v0 at time 0 travels across a subset of vertices on the
graph G. When the agent visits vertex vi at time ti , it will
collect the profit fi (ti ). The remaining profit at the vertex
vi right after the agent leaves becomes 0 and accumulates
again. Additionally, the profit at v0 is assumed to be 0, i.e.,
f0 (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 xij = 1 if the agent travels from vi to vj , and 0
otherwise. Let t0 = 0. We also introduce extra variables ui
with u0 = 0 to eliminate the subtours. Then the problem in
this study can be formulated as the following mixed-integer
program.
max
xij

n
X
i=1
n
X
j=1
n
X

fi (ti ) ·
x0j =
xik =

i=0

tj 6 T ·

X

j
n
X
i=1
n
X

j=0
n
X

xji ,

(1)

xi0 = 1,

(2)

xkj 6 1,

xij ,

∀k 6= 0,

∀j,

(3)
(4)

i=0

ti + xij (τij + T ) 6 T + tj ,
1 6 ui 6 n,

ui − uj + 1 6 n(1 − xij ),
xij ∈ {0, 1},

∀i, j,

∀i 6= 0,

(5)
(6)

∀i 6= 0, j 6= 0,

∀i, j.

(7)
(8)

Eq. (1) is to maximize the total collected profits. Constraint (2) guarantees that the path starts and ends at dummy
node v0 . Note that our setup allows a path to end at any
node by discarding the inward edge. 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 ti along the path. Constraints (6) and (7), so called
Miller-Tucker-Zemlin (MTZ) formulation in the traveling
sales problem[19], are used to prevent subtours.
IV. A S PATIO -T EMPORAL R EPRESENTATION
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 [20], [22], or
decouples the constraints into master-subproblem modules
such as column generation [2], or use certain heuristics
such as center-of-gravity heuristic [11]. In contrast, we

(a)
(b)
(c)
(d)
Fig. 2. Illustrations of spatio-temporal representation. (a) Graph G = (V, E) constructed on a x-y plane. Numbers on vertices are the vertex IDs, and
numbers on edges denote required travel time costs; (b) Spatio-temporal graph of (a). In this example each vertex has 5 time units along the (z-axis);
(c)(d) Another example with 7 vertices and 8 time windows.

desire to develop a framework starting from a constraintincluded 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 spatio-temporal 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 = nij ∆t
and T = nT ∆t , where nij and nT 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 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 time-varying.
In other words, the profits 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
profits are maximized. It is worth mentioning that, the spatiotempral 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 uni-directional 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) [18]. This allows us to conveniently
develop our own routing algorithm built on many existing
efficient DAG algorithms.
More formally, the spatio-temporal representation is a
vertex-weighted DAG, denoted by G0 = (V 0 , E 0 , W 0 ), where

V 0 = V × T , T = {0, ∆t , ..., nT ∆t }; eijus is a directed
0
0
edge from vertex viu
= (vi , u) to vjs
= (vj , s), and
0
eijus ∈ G if and only if the edge e(vi , vj ) ∈ E in G and
0
0
∈ W 0 for vertex viu
τij = ns ∆t − nu ∆t ; the weight wiu
0
has value wiu = fi (u). Keep in mind that u = nu ∆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 spatiotemporal representation G0 shown in Fig. 2(b), there are 18
0
0
0
vertices v0,0
, v0,1
, ..., v2,5
, each vertex in the original graph G
is duplicated at the discrete time in T = {0, 1, 2, 3, 4, 5}. If
0
0
τ01 = 3 and τ21 = 5, then vertex v0,0
is directed to v1,3
and
0
0
v2,0
is directed to v1,5
. In this example, we have 9 directed
edges in total.
With graph G = (V, E) and given time limit T , the spatiotemporal graph G0 = (V 0 , E 0 , W 0 ) can be constructed by
Alg. 1. Assume there are n vertices in G, the time complexity
of Alg. 1 is O(n2 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 G0 , so the space complexity is
O(nT /∆t ) .
Algorithm 1: SpatioTemporalGraph (G, T, v0 , ∆t )
Input:
1: Graph G = (V, E), time limit T , start vertex v0 , time
interval ∆t
Output:
2: for each vertex vi in graph G do
3:
for each t in time period [0, T ], time step is ∆t do
0
4:
vit
.id = i
0
0
5:
vit
.weight = fi (t), put wit
into the weight set W 0
0
6:
vit
.position = vi .position
0
7:
vit
.prof it = fi (t)
0
8:
vit
.sum = −∞
0
9:
vit
.parent = −1
10:
for each vi ’s neighbor vj do
11:
if t + τij is equal to t0 AND t0 <= T then
12:
put edge eijtt0 into the edge set E 0
0
0
13:
push vjt
0 into vector vit0 .successors
0
14:
update indegree of vit .
0
15:
put vit
into the vertex set V 0
0
16: set the v0,0 .sum to 0
17: return graph G0 = (V 0 , E 0 , W 0 )
0
Note: fi (t) is the time-varying profit function of vertex vi at time t. v0,0
is

the start vertex in G0 , and .sum is used to store accumulated profit from prior
traversal along a path. The label .parent points to the predecessor vertex.

V. ROUTING A LGORITHM
An important advantage of the spatio-temporal graph lies
in that, the time related constraints have been incorporated
into this 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
0
equivalent to finding a path P from
P vertex v00,0 = (v0 , 0) to
0
0
vks on G where s ≤ T such that (v0 u)∈P wiu is maximum.
i
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
accumulating 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 two concerns that are related
to applications into account.
• 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.
A. 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 euv
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 [14] to sort our spatial-temporal graph G0 , with main
steps shown 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 G0 .
0
For each vertex vit
, there will be at most n−1 directed edges.
0
Therefore |E | = O(n2 T /∆t ), and the time complexity of
Alg. 2 is O(|V 0 | + |E 0 |) = O(n2 T /∆t ).
Algorithm 2: TopologicalSort (G0 )
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

L: an empty list that will contain the sorted elements
S: a set of all nodes with no incoming edges
while S is not empty do
remove a vertex v from S
add v to the end of L
for each successor u of v do
deg − (u) = deg − (u) − 1
if deg − (u) equals to 0 then
insert u into S
return L (a topologically sorted order)

Note: G0 is a DAG, the indegree of v is denoted as deg − (v).

B. 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:
l[w] = l[v] + τvw , if l[v] + τvw > l[w],

(9)

where l[w] is the largest distance from start vertex to w, we
utilize an update function:
w.sum = v.sum+w.prof it, if v.sum+w.prof it > w.sum.
(10)
The computation of the maximal profit path is described
in Alg. 3. Briefly, the topologically sorted vertices V 0 of
the spatio-temporal graph G0 are used as an input. Then
vertices from different stages form dynamic programming
subproblems and they are updated with accumulated profits
0
0
recursively, starting from v0,0
. Here we use vit
.path to store
vertices along the path from start v00 to vi0 (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
0
routes from v0,0
to it. Since the graph G0 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) vi ∈ G, one simply needs to enumerate
0
all states vij
∈ G0 , ∀j of vertex vi 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(n2 T /∆t ) due to its two for loops.
Algorithm 3: M aximalP rof itP ath(L)
vit .sum = 0, i = 0, t = 0
0
for each vertex vit
in topologically sorted order L do
0
0
for each vertex vjt
0 in vit .successors do
0
if vertex vj is not in the vit
.path then
0
0
0
if vit
.sum + vjt
0 .prof it > vjt0 .sum then
0
0
0
vjt0 .sum = vit .sum + vjt0 .prof it
0
0
update the vjt
0 .parent to vit
0
0
vjt0 .path = vit .path + vj
0
for each vertex vit
in G0 do
find the maximal sum
retrieve a path P by backtracking from end to start
12: return P

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Note: The label .path is a vector that stores all visited vertices from start to vi

C. 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 n2 T /∆t , and
the space complexity is n2 T /∆t as well.
Algorithm 4: Time-Varying OP
Input:
1: 2D graph G = (V, E), start vertex v0 , time limit T , time
interval ∆t
Output:
2: construct a spatio-temporal graph
G0 = SpatioT emporalGraph(G, T, v0 , ∆t )
3: L = T opologicalSort(G0 )
4: path = M aximalP rof itP ath(L)
5: return path

Our algorithm 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 possibly reaching
at 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 algorithm produces near-optimal
solutions.
D. Discussion: Effects of Discretization
The time interval ∆t plays a critical role in our framework
as the total profits are actually evaluated at travel time steps

equal to multiple ∆t . Yet it may be impractical to select
a small enough 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 fi (t) satisfies the following
Lipschitz condition:
|fi (t) − fi (s)| ≤ K|t − s|, ∀t, s ∈ [0, T ], ∀i ∈ {0, ..., n},
(11)
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 0 .
Then we have the result as follows.
Proposition 1: Under the condition (11), we have the
upper bound for the difference in two objective values:
|z − z 0 | ≤ [n(n + 1)/2] · K · ∆t .
(12)
proof: Let P be the optimal path in the graph G for the
problem (1)-(8) and let P 0 be the optimal path in the
proposed spatio-temporal DAG G0 . By the construction of
G0 , P must correspond to a path P̃ in the graph G0 . Let z̃
be the total profits (i.e. the value of objective (1) on this path)
for the path P̃ . 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̃| ≤ [n(n + 1)/2]K∆t .
As P 0 rather than P̃ is the optimal path in G0 , we have
z̃ ≤ z 0 . By combining these results, we should have z − z 0 ≤
[n(n + 1)/2]K∆t . Conversely, by construction any feasible
path on the graph G0 must correspond to a feasible path on G.
Using similar arguments, we have z 0 −z ≤ [n(n+1)/2]K∆t .
Therefore, the result (12) holds. It is worthwhile noting that
the constraint that the path in G or G0 contains no subtours
is critical to the result (12).
VI. R ESULTS
We conducted numerical evaluations to validate the proposed algorithm. We compared our algorithm 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.
A. 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(a) 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(a) we

(a)
(b)
Fig. 3. (a) Route feature of orienteering. ∆t is 1, vertex number is 200,
T is 200 and the start vertex is at (-49,0); (b) Route behavior under timevarying profit function, ∆t is 1, vertex number is 200, T is 200. The start
vertex v0 is at (-49,0). In all of our experimental graphs, the size of a vertex
represents the weight, which is proportional to its profit.

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.
B. 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. 3(b). The profits are the same if the vertices are in
the same region, but different if not. For example, in region
0
I, the profit function for each vit
is
(
5wi
if t 6 T /2
fi (t)I =
0
if t > T /2
where wi is the weight of vertex vi in graph G. (Keep in
0
mind that, wi is different from wit
which is time-varying.
Here the weight wi refers to a fixed parameter for profit
function.) Similarly, the profit functions in regions II, III and
IV are
(
10wi
if t 6 T /2
fi (t)II =
0
if t > T /2
(
0
if t 6 T /2
fi (t)III =
5wi
if t > T /2
(
0
if t 6 T /2
fi (t)IV =
10wi
if t > T /2
Figure 3(b) 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
indicates that our algorithm is sensitive to the time-varying
profit functions.
C. Comparison with Optimal Solution
We compare the result of our algorithm 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. 4. We can see
that the results of our algorithm are very close to those of
the optimal solutions, for all the three functions.
Figure 5 shows a group of paths produced from our
algorithm and the optimal solution. We use a linear profit
fi (t) = wi t/T for this example. In many cases, our algorithm get the same results as those of the optimal solution,
as shown in Fig. 5(a) and Fig. 5(b). Sometimes the paths are
different, such as Fig. 5(c) and Fig. 5(d), but the collected
profits are quite similar (in this example, ours obtains 183.5
whereas the optimal is 185.0). Fig. 5(e) and Fig. 5(f) show
another example.
D. Comparison with Classic OP Algorithm
We also compared our algorithm with the classic OP
algorithms. We implemented a well-known heuristic called
center-of-gravity [11], and tested with both time-invariant
and time-variant profits. Fig. 6 demonstrates the differences
between the results of our approach and those of the OP.
Fig. 7 show statistics of numerical evaluations with 200
vertices. We can see that, our algorithm outperforms the
OP for both the time-invariant and time-varying profits.
Particularly, the difference margin is larger for the timevarying profits. Actually, the classic OP cannot handle timevarying 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. 7(c), from which we
can observe that, in practice our algorithm costs less time
than that of the OP using the center-of-gravity heuristic.
E. Path Quality under Different Time Intervals
Time interval ∆t determines time discretization resolution,
and therefore affacts the optimality as well. Table I 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 algorithm.
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.
F. Demonstration with New York Taxi Data
We demonstrate that the proposed algorithm can be used
for (autonomous) taxi routing. Fig. 8 shows real data of
taxi calls in New York city. The data is obtained from
NYC Taxi and Limousine Commission [1]. We use the kmeans clustering algorithm to cluster the whole New York
taxi calls into 50 local regions, as shown in Fig. 9(a). The
clustering centers are shown in Fig. 9(b). We assume that
each pick-up and the subsequent drop-off occur in the same
local region, and each pick-up and drop-off is counted as

(a) f (t) = wi t/T
(b) f (t) = −wi (t2 +tT +T 2 )/T 2
(c) f (t) = wi log(t + 1)
Fig. 4. Profit statistics on (a) Linear function; (b) Quadratic function; (c) Logarithmic function.

(a)
(b)
(c)
(d)
(e)
(f)
Fig. 5. Examples with linear profit functions. The paths in red are from our algorithm while the paths in green are found with brute-force search. (a)(b)
Our algorithm obtains optimal solution 281; (c)(d) Our solution is 183.5 whereas the optimal solution is 185.0; (e)(f) Our solution is 186.6 whereas the
optimal solution is 195.1.

(a)
(b)
(c)
(d)
Fig. 6. Path comparisons. The paths in red are computed from our algorithm while the paths in green are from the classic OPs using the center-of-gravity
heuristic. (a)(b) Time-invariant profits fi (t) = wi ; (c)(d) Time-varying profits fi (t) = wi t/T
TABLE I
S TATISTICS OF SOLUTION QUALITY WITH VARIOUS TIME INTERVALS ∆t
Intervals

(a)

(b)

0.1

0.5

1

2

5

10

50

541.1

530.3

529.2

522.1

515.1

498.3

100

788.2

783.4

767.9

735.6

727.5

619.2

150

950.2

919.0

909.7

892.9

823.0

686.8

200

1129.5

1117.6

1107.1

1094.3

935.5

696.0

Note: T = 150, graph within [−50, 50] × [−50, 50] on x-y plane,
profit fi (t) = wi t/T. 50,100,150 and 200 are the numbers of
vertices.

(c)
Fig. 7.
(a) Performance on time-invariant profits fi (t) = wi ; (b)
Performance on time-varying profits fi (t) = wi t/T ; (c) Statistics of
practical running time.

other taxis too). Therefore, this problem can be formulated as
an orienteering problem with time-varying profits, where we
need to treat those clustered regions as super routing depots
that offer different profits at different times of a day. Fig. 11
demonstrates a result generated from running our algorithm,
from which we can observe that the taxi is routed across
those regions with the most taxi calls, even though we set
the starting point at a distant location with sparse requests.

a completion of one service. Then a taxi driver aims at
maximizing the profit by providing more services during a
fixed period. In each region, we calculate the total number
of taxi calls in every predefined time unit (e.g., minute). An
example is shown in Fig. 10. We regard the total number
of taxi calls in a region as a time-varying profit, and more
calls indicate higher chance of getting profits (note, there are

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 timevariations into the fundamental planning process. Specifically, we first construct a deterministic spatio-temporal

VII. C ONCLUSION AND F UTURE W ORK

Fig. 8.

Data of taxi calls in New York city

Fig. 11. The taxi routing path generated from our algorithm. The big
square is the starting location.

(a)
(b)
Fig. 9. (a) Taxi calls are clustered through k-means; (b) Clustering centers
represent high-level routing depots.

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 algorithm with numerical
evaluations and the results show that our framework produces
near-optimal solutions in a very efficient way.
R EFERENCES
[1] NYC Taxi and Limousine Commission. http://www.nyc.gov/
html/tlc/html/about/trip_record_data.shtml. Accessed: 2017-02-25.
[2] H. M. Afsar and N. Labadie. Team orienteering problem with
decreasing profits. Electronic Notes in Discrete Mathematics, 41:285–
293, 2013.
[3] R. Bellman. On a routing problem. Quarterly of applied mathematics,
pages 87–90, 1958.
[4] M. Bellmore and G. L. Nemhauser. The Traveling Salesman Problem:
A Survey. Operations Research, 16(3):538–558, May 1968.
[5] J. Binney, A. Krause, and G. S. Sukhatme. Optimizing waypoints for
monitoring spatiotemporal phenomena. The International Journal of
Robotics Research, 32(8):873–888, 2013.
[6] I.-M. Chao, B. L. Golden, and E. A. Wasil. The team orienteering
problem. European journal of operational research, 88(3):464–474,
1996.
[7] N. Christofides. The vehicle routing problem. Revue française
d’automatique, d’informatique et de recherche opérationnelle.
Recherche opérationnelle, 10(1):55–70, 1976.

(a)
(b)
Fig. 10. For a particular region (region 1 in this example), the number of
taxi calls is varying as time elapses. (a) Time unit is minute; (b) Time unit
is hour.

[8] H. C. B. de Oliveira and G. C. Vasconcelos. A hybrid search
method for the vehicle routing problem with time windows. Annals
of Operations Research, 180(1):125–144, 2010.
[9] F. V. Fomin and A. Lingas. Approximation algorithms for timedependent orienteering. Information Processing Letters, 83(2):57–62,
2002.
[10] A. Garcia, O. Arbelaitz, P. Vansteenwegen, W. Souffriau, and M. T.
Linaza. Hybrid approach for the public transportation time dependent
orienteering problem with time windows. In International Conference
on Hybrid Artificial Intelligence Systems, pages 151–158, 2010.
[11] B. L. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval
research logistics, 34(3):307–318, 1987.
[12] A. Gunawan, H. C. Lau, and P. Vansteenwegen. Orienteering problem:
A survey of recent variants, solution approaches and applications.
European Journal of Operational Research, 2016.
[13] G. Gutiérrez-Jarpa, G. Desaulniers, G. Laporte, and V. Marianov.
A branch-and-price algorithm for the vehicle routing problem with
deliveries, selective pickups and time windows. European Journal of
Operational Research, 206(2):341–349, 2010.
[14] A. B. Kahn. Topological sorting of large networks. Commun. ACM,
5(11):558–562, Nov. 1962.
[15] H. Kellerer, U. Pferschy, and D. Pisinger. Introduction to NPCompleteness of knapsack problems. Springer, 2004.
[16] M. Keshtkaran, K. Ziarati, A. Bettinelli, and D. Vigo. Enhanced exact
solution methods for the team orienteering problem. International
Journal of Production Research, 54(2):591–601, 2016.
[17] G. Laporte. The traveling salesman problem: An overview of exact and
approximate algorithms. European Journal of Operational Research,
59(2):231–247, 1992.
[18] M. Mahmoudi and X. Zhou. Finding optimal solutions for vehicle
routing problem with pickup and delivery services with time windows:
A dynamic programming approach based on state–space–time network
representations. Transportation Research Part B: Methodological,
89:19–42, 2016.
[19] C. E. Miller, A. W. Tucker, and R. A. Zemlin. Integer programming
formulation of traveling salesman problems. Journal of the ACM
(JACM), 7(4):326–329, 1960.
[20] G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial
Optimization. Wiley-Interscience, New York, NY, USA, 1988.
[21] H. Tang and E. Miller-Hooks. A tabu search heuristic for the team
orienteering problem. Computers & Operations Research, 32(6):1379–
1407, 2005.
[22] P. Vansteenwegen, W. Souffriau, and D. Van Oudheusden. The
orienteering problem: A survey. European Journal of Operational
Research, 209(1):1–10, 2011.
[23] C. Verbeeck, K. Sörensen, E.-H. Aghezzaf, and P. Vansteenwegen.
A fast solution method for the time-dependent orienteering problem.
European Journal of Operational Research, 236(2):419–432, 2014.
[24] T. Vidal, N. Maculan, L. S. Ochi, and P. H. Vaz Penna. Large
neighborhoods with implicit customer selection for vehicle routing
problems with profits. Transportation Science, 50(2):720–734, 2015.

