Multi-depot multiple TSP: a polyhedral study and computational results

DOI10.1007/s10479-011-1024-yzbMath1272.90065OpenAlexW2119235896MaRDI QIDQ367624

Mohammad Hasan, M. Dambrine, H. S. Yoon

Publication date: 16 September 2013

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-011-1024-y

zbMATH Keywords

polyhedral studyBranch-and-Cutmultiple depot traveling salesman problem

Mathematics Subject Classification ID

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

Related Items

Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm, The multiple Steiner TSP with order constraints: complexity and optimization algorithms, Compact formulations for multi-depot routing problems: theoretical and computational comparisons, Modeling and optimization of multiple traveling salesmen problems: an evolution strategy approach, A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem, The multi‐depot family traveling salesman problem and clustered variants: Mathematical formulations and branch‐&‐cut based methods, Node based compact formulations for the Hamiltonian p‐median problem, Revisiting the Hamiltonian \(p\)-median problem: a new formulation on directed graphs and a branch-and-cut algorithm, Multiple depot ring star problem: a polyhedral study and an exact algorithm, Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm

Uses Software

• TSPLIB
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• A Branch-and-Cut method for the Capacitated Location-Routing Problem
• Facet identification for the symmetric traveling salesman polytope
• A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
• Transformation of multidepot multisalesmen problem to the standard travelling salesman problem
• The traveling salesman problem and its variations
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• Hamiltonian path and symmetric travelling salesman polytopes
• A cutting plane algorithm for minimum perfect 2-matchings
• A unified exact method for solving different classes of vehicle routing problems
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• Integer linear programming formulations of multiple salesman problems and its variations
• On the symmetric travelling salesman problem I: Inequalities
• A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem
• Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems
• TSPLIB—A Traveling Salesman Problem Library
• A tabu search heuristic for periodic and multi-depot vehicle routing problems
• A branch-and-cut algorithm for the plant-cycle location problem
• Edmonds polytopes and weakly hamiltonian graphs