A branch-and-cut algorithm for the preemptive swapping problem

DOI10.1002/net.20447zbMath1247.90072OpenAlexW2134465458MaRDI QIDQ2913951

Charles Bordenave, Gilbert Laporte, Michel Gendreau

Publication date: 21 September 2012

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20447

zbMATH Keywords

vehicle routingbranch-and-cutswapping problemprecedence relationships

Mathematics Subject Classification ID

Applications of graph theory (05C90) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10)

Related Items

Vehicle driven approaches for non preemptive vehicle relocation with integrated quality criterion in a vehicle sharing system, The static bicycle relocation problem with demand intervals, Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem, A branch-and-cut algorithm for solving the Non-preemptive Capacitated Swapping Problem, Bike sharing systems: solving the static rebalancing problem, The unit-capacity constrained permutation problem, Preemptive stacker crane problem: extending tree-based properties and construction heuristics, Heuristics for the mixed swapping problem

Uses Software

• Concorde
• CVRPSEP
• CVRPSP

Cites Work

• Unnamed Item
• A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery
• Heuristics for the mixed swapping problem
• An inexact algorithm for the sequential ordering problem
• Multistars, partial multistars and the capacitated vehicle routing problem
• A branch \& cut algorithm for the asymmetric traveling salesman problem with precedence constraints
• Efficient separation routines for the symmetric traveling salesman problem. I: General tools and comb separation
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• The precedence-constrained asymmetric traveling salesman polytope
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• On the symmetric travelling salesman problem I: Inequalities
• The preemptive swapping problem on a tree
• Integer Programming Formulation of Traveling Salesman Problems
• A new approach to the maximum-flow problem
• The swapping problem
• The Swapping Problem on a Line
• A branch‐and‐cut algorithm for the nonpreemptive swapping problem
• The one‐commodity pickup‐and‐delivery traveling salesman problem: Inequalities and algorithms
• Edmonds polytopes and weakly hamiltonian graphs