Solution of a Large-Scale Traveling-Salesman Problem

DOI10.1287/OPRE.2.4.393zbMath1414.90372DBLPjournals/ior/DantzigFJ54OpenAlexW2399100674WikidataQ29042541 ScholiaQ29042541MaRDI QIDQ5378639

R. Fulkerson, Selmer Johnson, George B. Dantzig

Publication date: 3 June 2019

Published in: Journal of the Operations Research Society of America (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/0fa37740fe865bcac0d9687c0e5f65131f4492c8

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Combinatorial optimization (90C27)

Related Items (only showing first 100 items - show all)

Generating subtour elimination constraints for the TSP from pure integer solutions ⋮ Discrete optimization methods to determine trajectories for Dubins' vehicles ⋮ PathOGiST: A Novel Method for Clustering Pathogen Isolates by Combining Multiple Genotyping Signals ⋮ Subadditive approaches in integer programming ⋮ Uncertain multiobjective traveling salesman problem ⋮ Mathematical formulations for a 1-full-truckload pickup-and-delivery problem ⋮ A branch and cut algorithm for the hierarchical network design problem ⋮ Length-constrained cycle partition with an application to UAV routing* ⋮ Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics ⋮ Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs ⋮ On the Skeleton of the Polytope of Pyramidal Tours ⋮ Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps ⋮ A mathematical model for supply chain management of blood banks in India ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ Decomposition theorems for square-free 2-matchings in bipartite graphs ⋮ The traveling salesman problem with job-times (\textit{TSPJ}) ⋮ Reinforcement learning for combinatorial optimization: a survey ⋮ Visual attractiveness in vehicle routing via bi-objective optimization ⋮ Edge Elimination in TSP Instances ⋮ Strategies for Generating Well Centered Tetrahedral Meshes on Industrial Geometries ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ Inductive linearization for binary quadratic programs with linear constraints ⋮ Multidistances and inequality measures on abstract sets: an axiomatic approach ⋮ “Make no little plans”: Impactful research to solve the next generation of transportation problems ⋮ Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule ⋮ The family traveling salesman problem with incompatibility constraints ⋮ The r‐interdiction selective multi‐depot vehicle routing problem ⋮ Heuristic approaches for the family traveling salesman problem ⋮ A biased random-key genetic algorithm for the two-level hub location routing problem with directed tours ⋮ A matheuristic algorithm for the pollution and energy minimization traveling salesman problems ⋮ Heuristic sequencing methods for time optimal tracking of nested, open and closed paths ⋮ The multi‐depot family traveling salesman problem and clustered variants: Mathematical formulations and branch‐&‐cut based methods ⋮ A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP ⋮ Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems ⋮ Selective arc‐ng pricing for vehicle routing ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ Tight lower bounds for the traveling salesman problem with draft limits ⋮ Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm ⋮ 0-1 mathematical programming models for flexible process planning ⋮ Small and large neighborhood search for the park-and-loop routing problem with parking selection ⋮ Adaptive solution prediction for combinatorial optimization ⋮ Multistart Branch and Bound for Large Asymmetric Distance-Constrained Vehicle Routing Problem ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes ⋮ Dual track and segmented single track bidirectional loop guidepath layout for AGV systems ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Some contributions of Ailsa H. Land to the study of the traveling salesman problem ⋮ On the generation of metric TSP instances with a large integrality gap by branch-and-cut ⋮ A conditional-logic interpretation for Miller-Tucker-Zemlin inequalities and extensions ⋮ On optimally solving sub‐tree scheduling for wireless sensor networks with partial coverage: A branch‐and‐cut algorithm ⋮ Exact separation of the rounded capacity inequalities for the capacitated vehicle routing problem ⋮ Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem ⋮ Coordinating Particle Swarm Optimization, Ant Colony Optimization and K-Opt Algorithm for Traveling Salesman Problem ⋮ A hybrid mathematical model for flying sidekick travelling salesman problem with time windows ⋮ Solving large-scale routing optimization problems with networks and only networks ⋮ The symmetric quadratic traveling salesman problem ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Cut-and-solve: An iterative search strategy for combinatorial optimization problems ⋮ The significance of deterministic empty vehicle trips in the design of a unidirectional loop flow path ⋮ A general system for heuristic minimization of convex functions over non-convex sets ⋮ A travelling salesman problem (TSP) with multiple job facilities. ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ From Single-Objective to Multi-Objective Vehicle Routing Problems: Motivations, Case Studies, and Methods ⋮ A New Formulation for the Travelling Salesman Problem ⋮ The single vehicle routing problem with deliveries and selective pickups ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ A modified subgradient algorithm for Lagrangean relaxation ⋮ Branch and cut methods for network optimization ⋮ Unnamed Item ⋮ Selection and sequencing heuristics to reduce variance in gas turbine engine nozzle assemblies ⋮ Multilocus consensus genetic maps (MCGM): Formulation, algorithms, and results ⋮ A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ On pedigree polytopes and Hamiltonian cycles ⋮ On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem ⋮ Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ Reassembling Trees for the Traveling Salesman ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ Development and implementation of algorithms for vehicle routing during a no-notice evacuation ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Transformation of integer programs to knapsack problems ⋮ The capacitated m two node survivable star problem ⋮ Low-complexity algorithms for sequencing jobs with a fixed number of job-classes ⋮ A Memetic Random Key Algorithm for the Balanced Travelling Salesman Problem ⋮ A Variable Neighborhood Search Algorithm for Cost-Balanced Travelling Salesman Problem ⋮ Unnamed Item ⋮ On Pedigree Polytopes and Hamiltonian Cycles ⋮ The minimum flow cost Hamiltonian cycle problem: a comparison of formulations ⋮ Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph ⋮ Memetic algorithm-based path generation for multiple Dubins vehicles performing remote tasks ⋮ Collection of different types of milk with multi-tank tankers under uncertainty: a real case study ⋮ Lagrangian heuristic for simultaneous subsidization and penalization: implementations on rooted travelling salesman games ⋮ New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ Modelling and solving the milk collection problem with realistic constraints ⋮ A LP-based approximation algorithm for generalized traveling salesperson path problem ⋮ Solving the max-cut problem using eigenvalues ⋮ The multiple Steiner TSP with order constraints: complexity and optimization algorithms

This page was built for publication: Solution of a Large-Scale Traveling-Salesman Problem