Solving the Orienteering Problem through Branch-and-Cut

DOI10.1287/ijoc.10.2.133zbMath1034.90523OpenAlexW2140596151MaRDI QIDQ4427336

Matteo Fischetti, Juan-José Salazar-González, Paolo Toth

Publication date: 1998

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/f418160139058493ae48576cc2a2b24aecce1a54

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Methods of successive quadratic programming type (90C55)

Related Items (84)

The clustered orienteering problem ⋮ Locating median cycles in networks ⋮ Classification, models and exact algorithms for multi-compartment delivery problems ⋮ A guided local search metaheuristic for the team orienteering problem ⋮ Boosting ant colony optimization via solution prediction and machine learning ⋮ Exact algorithms for budgeted prize-collecting covering subgraph problems ⋮ The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: a branch-and-price approach ⋮ Integer programming formulations for the elementary shortest path problem ⋮ Orienteering problem: a survey of recent variants, solution approaches and applications ⋮ Heuristic algorithms for visiting the customers in a rolling schedule environment ⋮ The traveling purchaser problem, with multiple stacks and deliveries: a branch-and-cut approach ⋮ A two-stage approach to the orienteering problem with stochastic weights ⋮ Solving the orienteering problem with time windows via the pulse framework ⋮ The ring spur assignment problem: new formulation, valid inequalities and a branch-and-cut approach ⋮ Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem ⋮ Managing platelet supply through improved routing of blood collection vehicles ⋮ A hybrid variable neighborhood search for the orienteering problem with mandatory visits and exclusionary constraints ⋮ The probabilistic orienteering problem ⋮ Multi-commodity location-routing: flow intercepting formulation and branch-and-cut algorithm ⋮ An efficient evolutionary algorithm for the orienteering problem ⋮ The bi-objective insular traveling salesman problem with maritime and ground transportation costs ⋮ Hybrid dynamic programming with bounding algorithm for the multi-profit orienteering problem ⋮ Exact algorithms for the double vehicle routing problem with multiple stacks ⋮ Solving the team orienteering problem with cutting planes ⋮ Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems ⋮ Evolution-inspired local improvement algorithm solving orienteering problem ⋮ Team Orienteering with Time-Varying Profit ⋮ A hybrid adaptive large neighborhood search heuristic for the team orienteering problem ⋮ Selective routing problem with synchronization ⋮ A dynamic and probabilistic orienteering problem ⋮ Coupling ant colony systems with strong local searches ⋮ The vehicle routing problem with service level constraints ⋮ Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems ⋮ Valid inequalities for mixed-integer programmes with fixed charges on sets of variables ⋮ Design of diversified package tours for the digital travel industry: a branch-cut-and-price approach ⋮ The orienteering problem: a survey ⋮ Multiperiod integrated spare parts and tour planning for on-site maintenance activities with stochastic repair requests ⋮ Trip planning for visitors in a service system with capacity constraints ⋮ Formulations for the orienteering problem with additional constraints ⋮ Solving the team orienteering problem with nonidentical agents: A Lagrangian approach ⋮ Clustered coverage orienteering problem of unmanned surface vehicles for water sampling ⋮ A hybrid algorithm for the DNA sequencing problem ⋮ A revisited branch-and-cut algorithm for large-scale orienteering problems ⋮ Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem ⋮ The first AI4TSP competition: learning to solve stochastic routing problems ⋮ An adaptive memory matheuristic for the set orienteering problem ⋮ Adaptive solution prediction for combinatorial optimization ⋮ Hybridized evolutionary local search algorithm for the team orienteering problem with time windows ⋮ Hybrid genetic algorithm for undirected traveling salesman problems with profits ⋮ The hazardous orienteering problem ⋮ A stabilized column generation scheme for the traveling salesman subtour problem ⋮ Hybrid evolutionary search for the traveling repairman problem with profits ⋮ Robust UAV mission planning ⋮ On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms ⋮ Mixed-integer programming approaches for the time-constrained maximal covering routing problem ⋮ On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches ⋮ Decision support for flexible liner shipping ⋮ An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits ⋮ Application of fuzzy optimization to the orienteering problem ⋮ Local search inequalities ⋮ Solving the team orienteering arc routing problem with a column generation approach ⋮ A memetic algorithm for the orienteering problem with mandatory visits and exclusionary constraints ⋮ Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming ⋮ Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem ⋮ An iterative three-component heuristic for the team orienteering problem with time windows ⋮ A TABU search heuristic for the team orienteering problem ⋮ Analysis of the maximum level policy in a production-distribution system ⋮ The effective application of a new approach to the generalized orienteering problem ⋮ A path relinking approach for the team orienteering problem ⋮ Models for a Steiner ring network design problem with revenues ⋮ A hybrid metaheuristic for the prize-collecting single machine scheduling problem with sequence-dependent setup times ⋮ The clustered team orienteering problem ⋮ A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem ⋮ A two-stage vehicle routing model for large-scale bioterrorism emergencies ⋮ A Tabu search algorithm for the probabilistic orienteering problem ⋮ A branch-and-cut algorithm for the maximum covering cycle problem ⋮ The Humanitarian Pickup and Distribution Problem ⋮ Robust Optimization of a Broad Class of Heterogeneous Vehicle Routing Problems Under Demand Uncertainty ⋮ Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty ⋮ Efficiently solving the thief orienteering problem with a max-min ant colony optimization approach ⋮ The attractive traveling salesman problem ⋮ A branch-and-cut algorithm for the capacitated profitable tour problem ⋮ An effective PSO-inspired algorithm for the team orienteering problem ⋮ A fast solution method for the time-dependent orienteering problem

Uses Software

• TSPLIB

This page was built for publication: Solving the Orienteering Problem through Branch-and-Cut