Solving the Orienteering Problem with Time Windows via the Pulse Framework. (February 2015)

• Record Type: Journal Article
• Authors: Duque, Daniel; Lozano, Leonardo; Medaglia, Andrés L.
• Is Part Of: Computers & operations research. Volume 54(2015)
• Page Start: 168
• Page End: 176
• Publication Date: 2015-02
• Subjects: Routing -- Shortest path problems with side constraints -- Traveling salesman problem with profits -- Vehicle routing problem with time windows; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2014.08.019
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The Orienteering Problem with Time Windows (OPTW) is the problem of finding a path that maximizes the profit available at the nodes in a time-constrained network. The OPTW has multiple applications in transportation, telecommunications, and scheduling. First, we extend an exact method for shortest path problems with side constraints into a general-purpose framework for hard shortest path variants. Then, using this framework, we develop a new method for the OPTW that incorporates problem-specific knowledge. Our method outperforms the state-of-the-art algorithm on instances derived from benchmark datasets from the literature achieving speedups of up to 266 times and is able to find optimal solutions to large-scale problems with up to 562 nodes in short computational times.