A cutting-plane algorithm for the Steiner team orienteering problem. (September 2019)

• Record Type: Journal Article
• Authors: Assunção, Lucas; Mateus, Geraldo Robson
• Is Part Of: Computers & industrial engineering. Volume 135(2019)
• Page Start: 922
• Page End: 939
• Publication Date: 2019-09
• Subjects: Vehicle routing -- Orienteering problems -- Cutting-plane; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.06.051
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Introducing the Steiner team orienteering problem, a generalization of capacitated routing problems with profit collection. A new commodity-based compact formulation is proposed for the problem. Introduction of a new class of valid inequalities, namely "conflict cuts". A cutting-plane algorithm to solve the general problem and a specific case of it is proposed. Abstract: The Team Orienteering Problem (TOP) is an NP-hard routing problem in which a fleet of identical vehicles aims at collecting rewards (prizes) available at given locations, while satisfying restrictions on the travel times. In TOP, each location can be visited by at most one vehicle, and the goal is to maximize the total sum of rewards collected by the vehicles within a given time limit. In this paper, we propose a generalization of TOP, namely the Steiner Team Orienteering Problem (STOP). In STOP, we provide, additionally, a subset of mandatory locations. In this sense, STOP also aims at maximizing the total sum of rewards collected within the time limit, but, now, every mandatory location must be visited. In this work, we propose a new commodity-based formulation for STOP and use it within a cutting-plane scheme. The algorithm benefits from the compactness and strength of the proposed formulation and works by separating three families of inequalities, which consist of some general connectivity constraints, classical lifted cover inequalities based on dual bounds and a class of conflict cuts. To our knowledge, the last class of inequalities is also introduced in this work. A state-of-the-art branch-and-cut algorithm from the literature of TOP is adapted to STOP and used as baseline to evaluate the performance of the cutting-plane. Extensive computational experiments show the competitiveness of the new algorithm while solving several STOP and TOP instances. In particular, it is able to solve, in total, 15 more TOP instances than any other previous exact algorithm and finds eight new optimality certificates. With respect to the new STOP instances introduced in this work, our algorithm solves 30 more instances than the baseline.