The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search - Université de technologie de Troyes Accéder directement au contenu
Article Dans Une Revue European Journal of Operational Research Année : 2012

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

Résumé

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.

Dates et versions

hal-02521846 , version 1 (27-03-2020)

Identifiants

Citer

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, 2012, 220 (1), pp.15-27. ⟨10.1016/j.ejor.2012.01.030⟩. ⟨hal-02521846⟩
60 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More