A revisited branch-and-cut algorithm for large-scale orienteering problems

DOI10.1016/J.EJOR.2023.07.034MaRDI QIDQ6087525zbMATH OpenOpenAlexFDO

Authors Gorka Kobeaga, Jairo Rojas-Delgado, María Merino, José A. Lozano

Publication date 15 November 2023

Published in European Journal of Operational Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2011.02743

zbMATH Keywords

branch-and-cutlarge problemsorienteering problemrouting

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Abstract: The orienteering problem is a route optimization problem which consists in finding a simple cycle that maximizes the total collected profit subject to a maximum distance limitation. In the last few decades, the occurrence of this problem in real-life applications has boosted the development of many heuristic algorithms to solve it. However, during the same period, not much research has been devoted to the field of exact algorithms for the orienteering problem. The aim of this work is to develop an exact method which is able to obtain optimality certification in a wider set of instances than with previous methods, or to improve the lower and upper bounds in its disability. We propose a revisited version of the branch-and-cut algorithm for the orienteering problem which includes new contributions in the separation algorithms of inequalities stemming from the cycle problem, in the separation loop, in the variables pricing, and in the calculation of the lower and upper bounds of the problem. Our proposal is compared to three state-of-the-art algorithms on 258 benchmark instances with up to 7397 nodes. The computational experiments show the relevance of the designed components where 18 new optima, 76 new best-known solutions and 85 new upper-bound values were obtained.

Cites work

• A Branch-and-Cut Algorithm for Solving the Team Orienteering Problem
• A branch-and-cut algorithm for the orienteering arc routing problem
• A branch-and-cut algorithm for the team orienteering problem
• An efficient evolutionary algorithm for the orienteering problem
• An exact algorithm for team orienteering problems
• An Optimal Algorithm for the Orienteering Tour Problem
• Boosting ant colony optimization via solution prediction and machine learning
• Complexity and approximation for traveling salesman problems with profits
• Cut tree algorithms: An experimental study
• Facets of the knapsack polytope
• scientific article; zbMATH DE number 1769325 (Why is no real title available?)
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
• On the symmetric travelling salesman problem: A computational study
• Orienteering problem: a survey of recent variants, solution approaches and applications
• Solution of large-scale symmetric travelling salesman problems
• Solving the Orienteering Problem through Branch-and-Cut
• Solving the team orienteering arc routing problem with a column generation approach
• Strong linear programming relaxations for the orienteering problem
• The Circuit Polytope: Facets
• The orienteering problem
• The orienteering problem: a survey
• The prize collecting traveling salesman problem
• The probabilistic orienteering problem
• The selective travelling salesman problem
• The team orienteering problem: formulations and branch-cut and price

This page was built for publication: A revisited branch-and-cut algorithm for large-scale orienteering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087525)