The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search

Nacima Labadie, Renata Mansini, Jan Melechovský and Roberto Wolfler Calvo

European Journal of Operational Research, 2012, vol. 220, issue 1, 15-27

Abstract: The Team Orienteering Problem (TOP) is a known NP-hard problem that typically arises in vehicle routing and production scheduling contexts. In this paper we introduce a new solution method to solve the TOP with hard Time Window constraints (TOPTW). We propose a Variable Neighborhood Search (VNS) procedure based on the idea of exploring, most of the time, granular instead of complete neighborhoods in order to improve the algorithm’s efficiency without loosing effectiveness. The method provides a general way to deal with granularity for those routing problems based on profits and complicated by time constraints. Extensive computational results are reported on standard benchmark instances. Performance of the proposed algorithm is compared to optimal solution values, when available, or to best known solution values obtained by state-of-the-art algorithms. The method comes out to be, on average, quite effective allowing to improve the best know values for 25 test instances.

Keywords: Team Orienteering Problem; Time windows; Variable Neighborhood Search; LP-based granularity (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (29)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221712000653
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:220:y:2012:i:1:p:15-27

DOI: 10.1016/j.ejor.2012.01.030

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().