Skip to Main content Skip to Navigation
Journal articles

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

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02521846
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, March 27, 2020 - 4:21:30 PM
Last modification on : Tuesday, June 2, 2020 - 9:22:02 AM

Identifiers

Collections

Citation

Nacima Labadie, Renata Mansini, Jan Melechovský, Roberto Wolfler Calvo. The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search. European Journal of Operational Research, Elsevier, 2012, 220 (1), pp.15-27. ⟨10.1016/j.ejor.2012.01.030⟩. ⟨hal-02521846⟩

Share

Metrics

Record views

235