Associate Professor Tsung-Che Chiang

Department of Computer Science and Information Engineering
National Taiwan Normal University

Tel: +886-2-77346692    Fax: +886-2-29322378    Email

Yu-Han Chen, Wei-Ju Sun, and Tsung-Che Chiang, Multiobjective orienteering problem with time windows: An ant colony optimization algorithm, Proc. of Conference on Technologies and Applications of Artificial Intelligence (TAAI), Tainan, Taiwan, November, 2015.

Full text: Unedited version

Download instances and solutions (Problem instances are obtained from The Orienteering Problem: Test Instances.)

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.