The traveling salesman problem on a graph and some related integer polyhedra

No abstract is available for this paper.

• Publication year

  1985

• Venue

  Mathematical programming

• Publication date

  1985-09-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/BF01582008
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Steiner trees, partial 2-trees, and minimum IFI networks

  1983cited by this paper
• Halin graphs and the travelling salesman problem

  1983cited by this paper
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem

  1983cited by this paper
• Linear-time computability of combinatorial problems on series-parallel graphs

  1982cited by this paper
• On the Relationship between the Biconnectivity Augmentation and Traveling Salesman Problems

  1982cited by this paper
• On the symmetric travelling salesman problem II

  1979cited by this paper
• On the symmetric travelling salesman problem I: Inequalities

  1979cited by this paper
• On the symmetric travelling salesman problem II: Lifting theorems and facets

  1979cited by this paper
• Graph Theory with Applications

  1978cited by this paper
• Facets of I-matching polyhedra

  1974cited by this paper
• Matroids and the greedy algorithm

  1971cited by this paper

• The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-zero Components

  2025cites this paper
• Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds

  2025cites this paper
• GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets

  2025cites this paper
• A literature review and bibliometric analysis of 50 years of optimization approaches applied to the order batching problem

  2025cites this paper
• Steiner Traveling Salesman Problem with Time Windows and Pickup-Delivery: integrating classical and quantum optimization

  2025cites this paper
• Steiner Traveling Salesman Problem with Quantum Annealing

  2025cites this paper
• The single picker routing problem with scattered storage: modeling and evaluation of routing and storage policies

  2024cites this paper
• A Branch-and-Cut algorithm for the multiple Steiner TSP with order constraints

  2024cites this paper
• Playing hide and seek: tackling in-store picking operations while improving customer experience

  2023cites this paper
• Theoretical and computational analysis of a new formulation for the Rural Postman Problem and the General Routing Problem

  2023cites this paper
• Learning efficient in-store picking strategies to reduce customer encounters in omnichannel retail

  2023cites this paper
• Upgrading edges in the Graphical TSP

  2023cites this paper
• A Comparison of Three Popular Routing Policies for Lift-truck Order Picking

  2023cites this paper
• A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem

  2022cites this paper
• On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations

  2022cites this paper
• A Criteria-Based Approach to the Traveling Salesman Problem A Criteria-Based Approach to the Traveling Salesman Problem (TSP)

  2022cites this paper
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization

  2022cites this paper
• An asymptotically tight online algorithm for m-Steiner Traveling Salesman Problem

  2022cites this paper
• A capacitated multi-vehicle covering tour problem on a road network and its application to waste collection

  2022cites this paper
• An integrated assignment, routing, and speed model for roadway mobility and transportation with environmental, efficiency, and service goals

  2022influential citation
• Improved formulations of the joint order batching and picker routing problem

  2022cites this paper
• Box-total dual integrality and edge-connectivity

  2022cites this paper
• A comprehensive review of batching problems in low-level picker-to-parts systems with order due dates: Main gaps, trade-offs, and prospects for future research

  2022cites this paper
• Improving a constructive heuristic for the general routing problem

  2022influential citation
• Bypassing the surface embedding: approximation schemes for network design in minor-free graphs

  2022cites this paper
• Vehicle routing on road networks: How good is Euclidean approximation?

  2021influential citation
• A partitioning column approach for solving LED sorter manipulator path planning problems

  2021cites this paper
• Topology-Constrained Network Design

  2021cites this paper
• The Steiner bi-objective shortest path problem

  2021cites this paper
• The Graphical Traveling Salesperson Problem has no Integer Programming Formulation in the Original Space

  2021influential citation
• Optimizing Web Surfing Pathways for the Overloaded Polyhedral insights from the travelling salesman problem of operations research

  2020cites this paper
• Complexity of Branch-and-Bound and Cutting Planes in Mixed-Integer Optimization — II

  2020cites this paper
• On the Multiple Steiner Traveling Salesman Problem with Order Constraints

  2020cites this paper
• Combinatorial Optimization: 6th International Symposium, ISCO 2020, Montreal, QC, Canada, May 4–6, 2020, Revised Selected Papers

  2020cites this paper
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

  2020influential citation
• The Multiple Steiner TSP with order constraints: complexity and optimization algorithms

  2020cites this paper
• An efficient and general approach for the joint order batching and picker routing problem

  2020cites this paper
• On the Distance-Constrained Close Enough Arc Routing Problem

  2020cites this paper
• Split Demand One-to-One Pickup and Delivery Problems With the Shortest-Path Transport Along Real-Life Paths

  2020cites this paper
• On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

  2020cites this paper
• Complexity of cutting planes and branch-and-bound in mixed-integer optimization

  2020cites this paper
• The node weight dependent traveling salesperson problem: approximation algorithms and randomized search heuristics

  2020cites this paper
• On k-edge-connected Polyhedra: Box-TDIness in Series-Parallel Graphs

  2020cites this paper
• Multi-start heuristic approaches for one-to-one pickup and delivery problems with shortest-path transport along real-life paths

  2020cites this paper
• The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP

  2020cites this paper
• Online routing and scheduling of search-and-rescue teams

  2020cites this paper
• A new integer programming formulation of the graphical traveling salesman problem

  2020cites this paper
• Retail facility layout considering shopper path

  2020cites this paper
• A layered compact formulation for the Multiple Steiner TSP with Order constraints

  2019cites this paper
• New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs

  2019cites this paper
• Software Approaches to Optimize Energy Consumption for a Team of Distributed Autonomous Mobile Robots

  2019cites this paper
• Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains

  2019cites this paper
• The multi-objective Steiner pollution-routing problem on congested urban road networks

  2019cites this paper
• A discrete cross aisle design model for order-picking warehouses

  2019cites this paper
• Ju n 20 19 A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem *

  2019cites this paper
• Formulating and solving the integrated batching, routing, and picker scheduling problem in a real-life spare parts warehouse

  2019cites this paper
• The Steiner Traveling Salesman Problem and its extensions

  2019cites this paper
• Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows

  2019cites this paper
• New Applications of the Nearest-Neighbor Chain Algorithm

  2019cites this paper
• Vehicle routing problems with road‐network information: State of the art

  2018cites this paper
• Integrated Route, Charging and Activity Planning for Whole Day Mobility with Electric Vehicles

  2018cites this paper
• A PTAS for subset TSP in minor-free graphs

  2018cites this paper
• Order picking in parallel-aisle warehouses with multiple blocks: complexity and a graph theory-based heuristic

  2018influential citation
• Single Vehicle's Package Delivery Strategy with Online Traffic Congestion of Certain Delay Time

  2018cites this paper
• A note on computational aspects of the Steiner traveling salesman problem

  2018cites this paper
• A GRASP heuristic using path-relinking and restarts for the Steiner traveling salesman problem

  2017cites this paper
• Exact algorithms for the order picking problem

  2017cites this paper
• ILP formulation of the degree-constrained minimum spanning hierarchy problem

  2017influential citation
• A dual local search framework for combinatorial optimization problems with TSP application

  2017cites this paper
• - 01 Tight Lower Bound for the Sparse Travelling Salesman Problem

  2017cites this paper
• Empirical analysis for the VRPTW with a multigraph representation for the road network

  2017cites this paper
• Exact algorithms for the picking problem

  2017cites this paper
• Learning Combinatorial Optimization Algorithms over Graphs

  2017cites this paper
• The Survivable Network Design Problems with High Node-Connectivity Constraints : Polyhedra and Algorithms. (Conception de réseaux fiables avec fortes contraintes de sommet-connexité : Étude polyédrale et Algorithmes)

  2017cites this paper
• Optimally solving the joint order batching and picker routing problem

  2017cites this paper
• The survivable k-node-connected network design problem: Valid inequalities and Branch-and-Cut

  2017cites this paper
• On matrices with the Edmonds-Johnson property arising from bidirected graphs

  2017cites this paper
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem

  2017cites this paper
• Modelling and Solving the Joint Order Batching and Picker Routing Problem in Inventories

  2016cites this paper
• A GRASP with restarts heuristic for the Steiner traveling salesman problem

  2016cites this paper
• Routing Optimization Under Uncertainty

  2016cites this paper
• Robust and Survivable Network Design Considering Uncertain Node and Link Failures

  2016cites this paper
• Robustness of Mission Plans for Unmanned Aircraft.

  2016cites this paper
• The Steiner traveling salesman problem with online advanced edge blockages

  2016cites this paper
• Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs

  2016cites this paper
• An algorithm for dynamic order-picking in warehouse operations

  2016influential citation
• Removing and Adding Edges for the Traveling Salesman Problem

  2016cites this paper
• The split-demand one-commodity pickup-and-delivery travelling salesman problem

  2016influential citation
• Circuit and bond polytopes on series-parallel graphs

  2015cites this paper
• Designing Networks with Good Equilibria under Uncertainty

  2015cites this paper
• Universal Network Cost-Sharing Design

  2015cites this paper
• Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal

  2015cites this paper
• Cut Dominants and Forbidden Minors

  2015cites this paper
• The Steiner travelling salesman problem with correlated costs

  2015cites this paper
• Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms

  2015cites this paper
• Optimization of Cable Cycles: A Trade-off between Reliability and Cost

  2015cites this paper
• An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic Graphs

  2014influential citation
• Recherche à voisinage variable pour des problèmes de routage avec ou sans gestion de stock

  2014cites this paper
• Graph-TSP from Steiner Cycles

  2014cites this paper
• Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs

  2014cites this paper