Information Technology Reference
In-Depth Information
must occur. Consequently, the number of selective cities to be included in the
tour depends on its completion time. Time windows defining the available rest
and refueling periods are associated with each selective city. The objective is
to design a tour, starting and ending at the home city, that minimizes a linear
combination of the total traveled distance (time) as well as the total waiting
time to start the visits.
Two practical applications of this problem are referred to in this paper. The
first application arises in the design of survey trips for a research vessel to esti-
mate the abundance of fish species. Sampling operations are made at predefined
locations along the Portuguese coast. The vessel route starts and ends at the
port of Lisbon and should include some regular visits to a port. The second
application consists of designing the route of a sales representative that needs to
visit his clients spread all over Portugal. Client visits are scheduled from Monday
to Friday and the sales representative returns home for the weekend.
There are several well known variants of the TSP in which not all clients
need to be visited (see [1] for a survey on TSP variants). In the Generalized
TSP (GTSP), cities are partitioned into clusters and the objective is to find the
minimum cost circuit visiting at least one city of each cluster. If we consider that
each mandatory city defines a cluster and all the selective cities are included in
an additional cluster then the TSPSNTW can be seen as variant of the GTSP
with time windows and additional constraints where each 'mandatory' cluster
is visited once and the 'selective' cluster is visited more than once according to
a predefined periodicity. In the Orienteering Problem each node has associated
a non-negative weight. The objective is to find a path, whose total traveled
time does not exceed a given threshold value, visiting the subset of cities that
maximizes the total weight. When the starting and final locations of the path are
the same, the problem looks for a circuit and is usually called Selective TSP. In
[2] the authors developed different classes of valid inequalities and used a branch-
and-cut algorithm to solve a Selective TSP that includes a subset of compulsory
cities. If the goal is to find
P
paths (circuits), each limited in time by a predefined
threshold value, the problem is known as the Team Orienteering Problem (see
[9] for a recent survey on the Orienteering Problem). Problem TSPSNTW has
some similarities with extensions of the aforementioned problems that include
time windows. Heuristic algorithms to solve the (Team) Orienteering Problem
with time windows have recently been proposed by [8,7,4]. In particular, in [7] the
authors propose a VNS procedure to solve a multi-period orienteering problem
with multiple time windows where mandatory clients should be visited exactly
once and potential customers can be visited at most once.
The outline of this paper is as follows. Section 2 describes the underlying
problem as a traveling salesman problem with special nodes, time windows and
additional constraints and presents a mathematical programming formulation.
Section 3 is devoted to the solution methodology. In Section 4, two real life
applications are described and computational results for different scenarios are
reported and discussed. Finally, some conclusions are drawn in Section 5.
