Team orienteering problem with time windows and time-dependent scores

Vincent F. Yu, Parida Jewpanya, Shih Wei Lin*, A. A.N.Perwira Redi

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

43 Scopus citations

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.

Original languageEnglish
Pages (from-to)213-224
Number of pages12
JournalComputers and Industrial Engineering
Volume127
DOIs
StatePublished - 01 2019
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2018 Elsevier Ltd

Keywords

  • Artificial bee colony
  • Logistics
  • Metaheuristics
  • Team orienteering problem
  • Time window
  • Time-dependent score

Fingerprint

Dive into the research topics of 'Team orienteering problem with time windows and time-dependent scores'. Together they form a unique fingerprint.

Cite this