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

DOI10.1002/net.20447zbMath1247.90072MaRDI 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 routing; branch-and-cut; swapping problem; precedence relationships

Mathematics Subject Classification ID

05C90: Applications of graph theory

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90B06: Transportation, logistics and supply chain management

90B10: Deterministic network models in operations research

Related Items

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