A stabilized column generation scheme for the traveling salesman subtour problem

DOI10.1016/j.dam.2005.04.012zbMath1111.90097OpenAlexW1998874971MaRDI QIDQ2433808

Torbjörn Larsson, Maud Göthe-Lundgren, Andreas Westerlund

Publication date: 30 October 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.04.012

zbMATH Keywords

prize collecting traveling salesman problemstabilized column generation1-tree problem with one degree-constrainttraveling salesman subtour problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items (9)

Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation ⋮ Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ The packing while traveling problem ⋮ Attractive orienteering problem with proximity and timing interactions ⋮ Genetic algorithm for combinatorial path planning: the subtour problem ⋮ A note on relatives to the Held and Karp 1-tree problem ⋮ Chebyshev center based column generation ⋮ An exact approach to extend network lifetime in a general class of wireless sensor networks ⋮ A Time-Indexed Generalized Vehicle Routing Model and Stabilized Column Generation for Military Aircraft Mission Planning

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• The selective travelling salesman problem
• A polyhedral approach to edge coloring
• On symmetric subtour problems
• A Lagrangian heuristic for the Prize Collecting Travelling Salesman Problem
• Minimum directed 1-subtree relaxation for score orienteering problem
• Stabilized column generation
• Strong linear programming relaxations for the orienteering problem
• A TSSP+1 decomposition strategy for the vehicle routing problem
• An exact algorithm for IP column generation
• The merchant subtour problem
• The vehicle routing-allocation problem: A unifying framework
• A technical review of column generation in integer programming
• A parallel implementation of the TSSP+1 decomposition for the capacity-constrained vehicle routing problem
• On the nucleolus of the basic vehicle routing game
• A note on relatives to the Held and Karp 1-tree problem
• Lagrangian duality applied to the vehicle routing problem with time windows
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Generalized Subtour Elimination Constraints and Connectivity Constraints
• On Some Generalizations of the Travelling-Salesman Problem
• The orienteering problem
• An SST-based algorithm for the steiner problem in graphs
• AN ALGORITHM FOR SINGLE CONSTRAINT MAXIMUM COLLECTION PROBLEM
• The prize collecting traveling salesman problem
• An Insert/Delete Heuristic for the Travelling Salesman Subset-Tour Problem with One Additional Constraint
• An Optimal Algorithm for the Orienteering Tour Problem
• The B<scp>oxstep</scp> Method for Large-Scale Optimization
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• A Polynomial Algorithm for the Degree-Constrained Minimum K-Tree Problem
• The Circuit Polytope: Facets
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• Solving the Orienteering Problem through Branch-and-Cut
• The prize collecting traveling salesman problem: II. Polyhedral results
• The Traveling-Salesman Problem and Minimum Spanning Trees
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem

This page was built for publication: A stabilized column generation scheme for the traveling salesman subtour problem