Team orienteering problem with time windows and time-dependent scores. (January 2019)

• Record Type: Journal Article
• Authors: Yu, Vincent F.; Jewpanya, Parida; Lin, Shih-Wei; Redi, A.A.N. Perwira
• Is Part Of: Computers & industrial engineering. Volume 127(2019)
• Page Start: 213
• Page End: 224
• Publication Date: 2019-01
• Subjects: Metaheuristics -- Logistics -- Team orienteering problem -- Time window -- Artificial bee colony -- Time-dependent score; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.11.044
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The team orienteering problem with time windows and time-dependent scores (TOPTW-TDS) is studied. A mathematical programming model for TOPTW-TDS is introduced. A hybrid artificial bee colony (HABC) algorithm is proposed for solving TOPTW-TDS. Computational study shows that the proposed HABC algorithm effectively solves TOPTW-TDS. Abstract: This study investigates the team orienteering problem with time windows and time-dependent scores (TOPTW-TDS), which is a new variant of the well-known team orienteering problem with time windows (TOPTW). TOPTW-TDS builds a set of paths to maximize the collected scores. The score of visiting an attraction is different depending on the time of visit. A mathematical formulation is proposed for this new problem. Since the problem is NP-hard, a hybrid artificial bee colony (HABC) algorithm is proposed to find the optimal solutions for small instances and near-optimal solutions for larger instances. Three datasets (small, medium and large) are generated with 168 TOPTW-TDS instances. Computational results reveal that the proposed HABC algorithm can generate high-quality TOPTW-TDS solutions. The proposed HABC obtains the optimal solution of each small TOPTW-TDS instance. For medium and large TOPTW-TDS instances, HABC results are comparable with the SA results. Additionally, results from solving TOPTW benchmark instances indicate that the proposed HABC compares well with the state-of-the-art algorithms for TOPTW.