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

DOI10.1016/J.DISOPT.2014.08.001MaRDI QIDQ2339836zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3728302 (Why is no real title available?)
• scientific article; zbMATH DE number 1234739 (Why is no real title available?)
• scientific article; zbMATH DE number 1312984 (Why is no real title available?)
• scientific article; zbMATH DE number 1769325 (Why is no real title available?)
• A branch and cut approach to the cardinality constrained circuit problem.
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• An algorithm for the resource constrained shortest path problem
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts
• Chvàtal-Gomory rank-1 cuts used in a Dantzig-Wolfe decomposition of the vehicle routing problem with time windows
• Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Facet identification for the symmetric traveling salesman polytope
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• Lagrangian relaxation and enumeration for solving constrained shortest-path problems
• Multistars, partial multistars and the capacitated vehicle routing problem
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• New route relaxation and pricing strategies for the vehicle routing problem
• Odd Minimum Cut-Sets and b-Matchings
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• Projection results for vehicle routing
• Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem
• Solving the Orienteering Problem through Branch-and-Cut
• Strong linear programming relaxations for the orienteering problem
• Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• The Capacitated m-Ring-Star Problem
• The Circuit Polytope: Facets
• The selective travelling salesman problem
• The vehicle routing problem
• Vehicle routing problem with elementary shortest path based column generation

Cited in

(21)

• A note on the separation of subtour elimination constraints in elementary shortest path problems
• The merchant subtour problem
• The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach
• Solving resource constrained shortest path problems with LP-based methods
• The multi-vehicle profitable pickup and delivery problem
• The hiking tourist 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
• The undirected capacitated general routing problem with profits
• Formulations and exact algorithms for the vehicle routing problem with time windows
• Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies
• The vehicle routing problem with service level constraints
• The time-dependent capacitated profitable tour problem with time windows and precedence constraints
• Compact formulations of the Steiner traveling salesman problem and related problems
• On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
• Solving the probabilistic profitable tour problem on a line
• Integer programming formulations for the elementary shortest path problem
• A branch-and-cut algorithm for the target visitation problem
• Branch-and-check approaches for the tourist trip design problem with rich constraints
• 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

Describes a project that uses

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)