A branch-cut-and-price algorithm for the traveling salesperson problem with hotel selection. (November 2020)

• Record Type: Journal Article
• Authors: Barbosa, Luiz Henrique; Uchoa, Eduardo
• Is Part Of: Computers & operations research. Volume 123(2020)
• Publication Date: 2020-11
• Subjects: Column generation -- Cut separation -- Routing; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.104986
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: An algorithm for Traveling Salesperson Problem with Hotel selection is proposed. It adapts advanced features found in recent exact algorithms for vehicle routing. Subset row cuts and 2-path cuts are effectively used. Experiments show that many instances from the literature can now be solved. A new set of 240 benchmark instances is proposed. Abstract: The Traveling Salesperson Problem with Hotel Selection (TSPHS) is a realistic extension of the classic Traveling Salesperson Problem recently introduced to the literature. In the TSPHS, there is a time limit that restricts the visits that can be performed in a single day. Therefore, several days may be necessary to visit all clients. The salesperson has to spend the night in one of the available hotels. Previous works focus mainly on metaheuristics and on MIP formulations. This work presents a sophisticated exact algorithm for the TSPHS, a Branch-Cut-and-Price (BCP) algorithm that includes and adapts several features found in state-of-the-art algorithms for vehicle routing. In that algorithm, columns correspond to possible salesperson day trips; subtour elimination cuts, 2-path cuts, and limited-memory subset row cuts are separated. Computational results show that many medium-sized instances, having up to 75 clients and 20 hotels, can be solved to optimality, as well as some larger instances from the literature, with up to 225 clients.