The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search |
| |
Authors: | Nacima Labadie Renata Mansini Jan Melechovský Roberto Wolfler Calvo |
| |
Institution: | 1. University of Brescia, Department of Information Engineering, Italy;2. University of Technology of Troyes, ICD-LOSI, France;3. LIPN (UMR 7030), 99, av. Jean-Baptiste Cement, 93430 Villetaneuse, France;4. University of Economics, Prague, Department of Econometrics, Czech Republic |
| |
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 |
本文献已被 ScienceDirect 等数据库收录! |
|