Model and Algorithm for Time-Dependent Team Orienteering Problem - Advanced Research on Computer Education, Simulation and Modeling - page 1

Model and Algorithm for Time-Dependent Team
Orienteering Problem
Jin Li
College of Computer Science & Information Engineering,
Zhejiang Gongshang University, Hangzhou, P.R. China
Jinli @mail.zjgsu.edu.cn
Abstract. In the team orienteering problem (TOP) a set of locations is given,
each with a score. The goal is to determine a fixed number of routes, limited in
length, that visit some locations and maximize the sum of the collected scores.
The team orienteering problem is often used as a starting point for modeling
many combinatorial optimization problems. This paper studies the time-
dependent team orienteering problem considering the travel cost varying with
time and visiting time constraints. After a mixed integer programming model is
proposed, a novel optimal dynamic labeling algorithm is designed based on the
idea of network planning and dynamic programming. Finally, a numerical ex-
ample is presented to show the validity and feasibility of this algorithm.
Keywords: Team orienteering problem; time-dependent network; travel time;
optimal algorithm.
1 Introduction
In the orienteering problem (OP) a set of n locations i is given, each with a score
s i .The starting point (location1) and the end point (location n ) are fixed. The time t ij
needed to travel from location i to j be known for all location pairs. A given T limits
the time to visit locations. The goal of the OP is to determine a single route, limited
by T , in order to maximize the total collected score. Each location can be visited at
most once. The Team Orienteering Problem (TOP) is an OP that maximizes that total
collected score of m routes, each limited to T . The team orienteering problem (TOP)
first appeared in Butt and Cavalier [1] under the name of the Multiple Tour Maximum
Collection Problem. The term TOP, first introduced in Chao et al. [2], comes from a
sporting activity: team orienteering. A team consists of several members who all be-
gin at the same starting point. Each member tries to collect as many reward points as
possible within a certain time before reaching the finishing point. Available points can
be awarded only once. Chao et al. [2] also created a set of instances, used nowadays
as standard benchmark instances for the TOP.
The TOP is an extension to multiple-vehicle of the orienteering problem (OP), also
known as the selective traveling salesman problem (STSP). The TOP is also a gener-
alization of vehicle routing problems (VRPs) where only a subset of customers can be