A branch-and-cut algorithm for the capacitated profitable tour problem

DOI10.1016/J.DISOPT.2014.08.001zbMATH Open1308.90206DBLPjournals/disopt/JepsenPSP14OpenAlexW2039810275WikidataQ58826343 ScholiaQ58826343MaRDI QIDQ2339836FDOQ2339836

Authors: Mads Kehlet Jepsen, Simon Spoorendonk, B. 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

Recommendations

• Optimal solutions for routing problems with profits
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• The capacitated team orienteering and profitable tour problems
• A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem

zbMATH Keywords

traveling salesman problemvalid inequalitiesbranch-and-cut algorithmprofitable tour problemcapacitated shortest path problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Dynamic programming (90C39)

Cites Work

• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• The vehicle routing problem
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• Title not available (Why is that?)
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• Title not available (Why is that?)
• Multistars, partial multistars and the capacitated vehicle routing problem
• The Capacitated m-Ring-Star 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
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• New route relaxation and pricing strategies for the vehicle routing problem
• Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
• Solving the Orienteering Problem through Branch-and-Cut
• Title not available (Why is that?)
• 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
• Lagrangian relaxation and enumeration for solving constrained shortest-path problems
• Projection results for vehicle routing
• Odd Minimum Cut-Sets and b-Matchings
• Strong linear programming relaxations for the orienteering problem
• An algorithm for the resource constrained shortest path problem
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• A branch and cut approach to the cardinality constrained circuit problem.
• Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem
• Chvàtal-Gomory rank-1 cuts used in a Dantzig-Wolfe decomposition of the vehicle routing problem with time windows
• The Circuit Polytope: Facets
• Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows
• Title not available (Why is that?)

Cited In (21)

• The hiking tourist problem
• Compact formulations of the Steiner traveling salesman problem and related problems
• Branch-and-check approaches for the tourist trip design problem with rich constraints
• The merchant subtour problem
• The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach
• The undirected capacitated general routing problem with profits
• Integer programming formulations for the elementary shortest path problem
• A Pricing Algorithm for the Vehicle Routing Problem with Soft Time Windows
• A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services
• On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
• The multi-vehicle profitable pickup and delivery problem
• Solving resource constrained shortest path problems with LP-based methods
• The vehicle routing problem with service level constraints
• The time-dependent capacitated profitable tour problem with time windows and precedence constraints
• A branch-and-cut algorithm for the target visitation problem
• On Accuracy of Approximation for the Resource Constrained Shortest Path Problem
• A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints
• Formulations and exact algorithms for the vehicle routing problem with time windows
• Solving the probabilistic profitable tour problem on a line
• Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies
• A note on the separation of subtour elimination constraints in elementary shortest path problems

Uses Software

• VRP

This page was built for publication: A branch-and-cut algorithm for the capacitated profitable tour problem

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