Coupling Feasibility Pump and Large Neighborhood Search to solve the Steiner team orienteering problem
From MaRDI portal
Publication:6357616
DOI10.1016/J.COR.2020.105175arXiv2101.01530MaRDI QIDQ6357616FDOQ6357616
Authors: Lucas Assunção, Geraldo Robson Mateus 
Publication date: 26 December 2020
Abstract: The Steiner Team Orienteering Problem (STOP) is defined on a digraph in which arcs are associated with traverse times, and whose vertices are labeled as either mandatory or profitable, being the latter provided with rewards (profits). Given a homogeneous fleet of vehicles M, the goal is to find up to m = |M| disjoint routes (from an origin vertex to a destination one) that maximize the total sum of rewards collected while satisfying a given limit on the route's duration. Naturally, all mandatory vertices must be visited. In this work, we show that solely finding a feasible solution for STOP is NP-hard and propose a Large Neighborhood Search (LNS) heuristic for the problem. The algorithm is provided with initial solutions obtained by means of the matheuristic framework known as Feasibility Pump (FP). In our implementation, FP uses as backbone a commodity-based formulation reinforced by three classes of valid inequalities. To our knowledge, two of them are also introduced in this work. The LNS heuristic itself combines classical local searches from the literature of routing problems with a long-term memory component based on Path Relinking. We use the primal bounds provided by a state-of-the-art cutting-plane algorithm from the literature to evaluate the quality of the solutions obtained by the heuristic. Computational experiments show the efficiency and effectiveness of the proposed heuristic in solving a benchmark of 387 instances. Overall, the heuristic solutions imply an average percentage gap of only 0.54% when compared to the bounds of the cutting-plane baseline. In particular, the heuristic reaches the best previously known bounds on 382 of the 387 instances. Additionally, in 21 of these cases, our heuristic is even able to improve over the best known bounds.
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Transportation, logistics and supply chain management (90B06)
This page was built for publication: Coupling Feasibility Pump and Large Neighborhood Search to solve the Steiner team orienteering problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6357616)
