A branch-and-cut algorithm for the capacitated profitable tour problem
From MaRDI portal
Publication:2339836
DOI10.1016/j.disopt.2014.08.001zbMath1308.90206OpenAlexW2039810275WikidataQ58826343 ScholiaQ58826343MaRDI QIDQ2339836
Simon Spoorendonk, Mads Kehlet Jepsen, Björn Petersen, David Pisinger
Publication date: 9 April 2015
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2014.08.001
branch-and-cut algorithmtraveling salesman problemvalid inequalitiesprofitable tour problemcapacitated shortest path problem
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Dynamic programming (90C39)
Related Items (15)
The multi-vehicle profitable pickup and delivery problem ⋮ Integer programming formulations for the elementary shortest path problem ⋮ Solving resource constrained shortest path problems with LP-based methods ⋮ The vehicle routing problem with service level constraints ⋮ Solving the probabilistic profitable tour problem on a line ⋮ A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services ⋮ Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms ⋮ The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach ⋮ A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints ⋮ A Pricing Algorithm for the Vehicle Routing Problem with Soft Time Windows ⋮ On Accuracy of Approximation for the Resource Constrained Shortest Path Problem ⋮ Compact formulations of the Steiner traveling salesman problem and related problems ⋮ A note on the separation of subtour elimination constraints in elementary shortest path problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The selective travelling salesman problem
- Facet identification for the symmetric traveling salesman polytope
- An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts
- Strong linear programming relaxations for the orienteering problem
- Multistars, partial multistars and the capacitated vehicle routing problem
- Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
- Vehicle routing problem with elementary shortest path based column generation
- Projection results for vehicle routing
- Accelerated label setting algorithms for the elementary resource constrained shortest path problem
- The Vehicle Routing Problem
- New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem
- Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
- Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem
- The Capacitated m-Ring-Star Problem
- Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
- New dynamic programming algorithms for the resource constrained elementary shortest path problem
- Lagrangian relaxation and enumeration for solving constrained shortest-path problems
- Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows
- An algorithm for the resource constrained shortest path problem
- Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
- Odd Minimum Cut-Sets and b-Matchings
- The Circuit Polytope: Facets
- Solving the Orienteering Problem through Branch-and-Cut
- Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
- An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
- On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
- A branch and cut approach to the cardinality constrained circuit problem.
- Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows
This page was built for publication: A branch-and-cut algorithm for the capacitated profitable tour problem
