The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search - Archive ouverte HAL Access content directly
Journal Articles European Journal of Operational Research Year : 2012

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

(1) , (2) , (3, 1) , (4)
1
2
3
4

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.
Not file

Dates and versions

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

Identifiers

Cite

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⟩
48 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More