A Branch-and-Price Approach for the Team Orienteering Problem with Time Windows
SCIE
SCOPUS
- Title
- A Branch-and-Price Approach for the Team Orienteering Problem with Time Windows
- Authors
- Hyunchul Tae; Kim, BI
- Date Issued
- 2015-04
- Publisher
- The International Journal of Industrial Engineering
- Abstract
- Given a set of vertices, each of which has its own prize and time window, the team orienteering problem with time windows (TOPTW) is a problem of finding a set of vehicle routes with the maximum total prize that satisfies vehicle time limit and vertex time window constraints. Many heuristic algorithms have solved the TOPTW; to our knowledge, however, no exact algorithm that can solve this problem optimally has yet been identified. This study proposes an exact algorithm based on the branch-and-price approach to solve the TOPTW. This algorithm can find optimal solutions for many TOPTW benchmark instances. We also apply the proposed algorithm to the team orienteering problem (TOP), which is a time window constraint relaxed version of the TOPTW. Unlike the TOPTW, a couple of exact algorithms have solved the TOP. The proposed algorithm can find more number of optimal solutions to TOP benchmark instances.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/27109
- ISSN
- 1943-670X
- Article Type
- Article
- Citation
- INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING-THEORY APPLICATIONS AND PRACTICE, vol. 22, no. 2, page. 243 - 251, 2015-04
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.