TSP with Multiple Time-Windows and Selective Cities - Computational Logistics - page 158

TSP with Multiple Time-Windows
and Selective Cities
Marta Mesquita 1 , Alberto Murta 2 , Ana Paias 3 , and Laura Wise 2
1 CIO and ISA, UTL,Tapada da Ajuda, 1349-017 Lisboa, Portugal
[e-mail]
2 IPMA, Portuguese Institute of the Sea and Atmosphere, Av.Brasılia, 1449-006
Lisboa, Portugal
{ amurta,lwise } @ipma.pt
3 CIO and DEIO, Faculdade de Ciencias, Universidade de Lisboa, C6, Piso 4,
1749-016 Lisboa, Portugal
[e-mail]
Abstract. We address a special TSP in which the set of cities is
partitioned into two subsets: mandatory cities and selective cities. All
mandatory cities should be visited once within one of the corresponding
predefined multiple time windows. A subset of the selective cities, whose
cardinality depends on the tour completion time, should be visited within
one of the associated multiple time windows. The objective is to plan a
tour, not exceeding a predefined number of days, that minimizes a linear
combination of the total traveled distance as well as the total waiting
time. We present a mixed integer linear programming (MILP) model
for the problem and propose a heuristic approach to solve it. Computa-
tional experiments address two real world problems that arise in different
practical contexts.
Keywords: Traveling salesman problem, multiple time windows, mixed
integer linear programming, branch-and-bound, heuristics.
1 Introduction
This paper addresses a special case of the traveling salesman problem, namely
the traveling salesman problem with selective cities and multiple time windows
(TSPSNTW), motivated by two real world applications. A traveling salesman
must plan a tour, not exceeding a maximum number of days, to visit a set of
clients spread over a set of cities, with known geographic locations. There are
two types of cities: mandatory cities and selective cities. For mandatory cities
the visit is compulsory and must be scheduled according to the availability of
the corresponding clients. Therefore, a duration time for the visit and one time
window for each day of the planning horizon are associated with each mandatory
city. After a mandatory city visit is completed, the salesman proceeds to the next
one or must be forced to rest. Selective cities represent potential locations to rest
or refueling. According to a predefined periodicity a visit to one selective city