Team orienteering problem with time windows and time-dependent scores. (January 2019) - Yu, Vincent F.; Jewpanya, Parida; Lin, Shih-Wei; Redi, A.A.N. Perwira
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.