Multiobjective orienteering problem with time windows: An ant colony optimization algorithm

Yu Han Chen, Wei Ju Sun, Tsung-Che Chiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

The orienteering problem with time windows (OPTW) deals with the problem about selecting a set of points of interest and then determining the route to visit them under the time window constraints. In the classical OPTW each candidate point of interest is associated with a profit value, and the objective is to maximize the total profit. In this study, we extend the problem and allow each point to have multiple profit values, which could reflect different aspects of consideration. We propose an ant colony optimization (ACO) algorithm to solve the multiobjective OPTW (MOOPTW) with the goal of finding the set of Pareto optimal solutions. To our best knowledge, this is the first study to address the MOOPTW with comprehensive numerical experiments. Our algorithm is a decomposition-based one, which decomposes the multiobjective optimization problem into single-objective sub-problems. Pheromone matrices are associated with sub-problems. We also incorporate path-relinking and propose several strategies. We apply our algorithm to solve 76 public benchmark instances and offer the list of non-dominated solutions to facilitate performance comparison in future researches.

Original languageEnglish
Title of host publicationTAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages128-135
Number of pages8
ISBN (Electronic)9781467396066
DOIs
Publication statusPublished - 2016 Feb 12
EventConference on Technologies and Applications of Artificial Intelligence, TAAI 2015 - Tainan, Taiwan
Duration: 2015 Nov 202015 Nov 22

Publication series

NameTAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence

Other

OtherConference on Technologies and Applications of Artificial Intelligence, TAAI 2015
CountryTaiwan
CityTainan
Period15/11/2015/11/22

    Fingerprint

Keywords

  • Pareto optimal
  • ant colony optimization
  • multiobjective
  • orienteering problem
  • time window

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Science Applications

Cite this

Chen, Y. H., Sun, W. J., & Chiang, T-C. (2016). Multiobjective orienteering problem with time windows: An ant colony optimization algorithm. In TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence (pp. 128-135). [7407130] (TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/TAAI.2015.7407130