An adaptive ejection pool with toggle-rule diversification approach for the capacitated team orienteering problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

14 Scopus Citations
View graph of relations

Author(s)

  • Zhixing Luo
  • Brenda Cheang
  • Andrew Lim
  • Wenbin Zhu

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)673-682
Journal / PublicationEuropean Journal of Operational Research
Volume229
Issue number3
Publication statusPublished - 16 Sep 2013

Abstract

In the capacitated team orienteering problem (CTOP), we are given a set of homogeneous vehicles and a set of customers each with a service demand value and a profit value. A vehicle can get the profit of a customer by satisfying its demand, but the total demand of all customers in its route cannot exceed the vehicle capacity and the length of the route must be within a specified maximum. The problem is to design a set of routes that maximizes the total profit collected by the vehicles. In this article, we propose a new heuristic algorithm for the CTOP using the ejection pool framework with an adaptive strategy and a diversification mechanism based on toggling between two priority rules. Experimental results show that our algorithm can match or improve all the best known results on the standard CTOP benchmark instances proposed by Archetti et al. (2008). © 2013 Elsevier B.V. All rights reserved.

Research Area(s)

  • Capacitated team orienteering problem, Ejection pool, Local search, Routing