Solution of a Large-Scale Traveling-Salesman Problem
From MaRDI portal
Publication:5378639
DOI10.1287/opre.2.4.393zbMath1414.90372OpenAlexW2399100674WikidataQ29042541 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
Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Combinatorial optimization (90C27)
Related Items
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, Vehicle routing with split deliveries, The median tour and maximal covering tour problems: Formulations and heuristics, Modeling supermarket re-layout from the owner's perspective, The hierarchical network design problem, Metaheuristics for the distance constrained generalized covering traveling salesman problem, Layered graph approaches for combinatorial optimization problems, Optimization of a 532-city symmetric traveling salesman problem by branch and cut, Computational approaches for zero forcing and related problems, Tabu search performance on the symmetric travelling salesman problem, A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs, Rich vehicle routing problems: from a taxonomy to a definition, The fleet size and mix location-routing problem with time windows: formulations and a heuristic algorithm, The traveling salesman problem with time-dependent service times, A branch-and-cut framework for the consistent traveling salesman problem, Calibrating cross-training to meet demand mix variation and employee absence, Integer programming formulations for the elementary shortest path problem, A new mathematical programming formulation for the single-picker routing problem, Lower bounding procedure for the asymmetric quadratic traveling salesman problem, The hybrid electric vehicle-traveling salesman problem, Exact and heuristic procedures for the material handling circular flow path design problem, Ordered spatial sampling by means of the traveling salesman problem, Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations, Approaches for solving the container stacking problem with route distance minimization and stack rearrangement considerations, Model-based automatic neighborhood design by unsupervised learning, Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: an application to fish aggregating devices, A bi-objective model for the used oil location-routing problem, A branch-and-cut algorithm for the minimum branch vertices spanning tree problem, Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations, A variable MIP neighborhood descent algorithm for managing inventory and distribution of cash in automated Teller machines, Integer programming models and linearizations for the traveling car renter problem, Load-dependent and precedence-based models for pickup and delivery problems, A new heuristic for detecting non-Hamiltonicity in cubic graphs, Solution algorithms for synchronous flow shop problems with two dominating machines, The complexity of facets resolved, A polynomial-time solution to Papadimitriou and Steiglitz's ``traps, The pickup and delivery problem: Faces and branch-and-cut algorithm, Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope, A hybrid approach for biobjective optimization, Distance conserving reductions for nonoriented networks, General solutions to the single vehicle routing problem with pickups and deliveries, Models and exact solutions for a class of stochastic location-routing problems, On cutting-plane proofs in combinatorial optimization, A simple LP relaxation for the asymmetric traveling salesman problem, A classification of formulations for the (time-dependent) traveling salesman problem, Multi-depot vessel routing problem in a direction dependent wavefield, Heuristic and exact algorithms for a min-max selective vehicle routing problem, On the choice of step size in subgradient optimization, Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times, A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem, Classification of travelling salesman problem formulations, A comparison of lower bounds for the symmetric circulant traveling salesman problem, A bilevel programming approach to the travelling salesman problem., Hamiltonian location problems, A note on exploiting the Hamiltonian cycle problem substructure of the asymmetric traveling salesman problem, A hybrid fuzzy-optimization approach to customer grouping-based logistics distribution operations, A note on the effect of neighborhood structure in simulated annealing, An extended approach for lifting clique tree inequalities, An effective heuristic for the \(P\)-median problem with application to ambulance location, George Dantzig's contributions to integer programming, George Dantzig's impact on the theory of computation, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Combined route capacity and route length models for unit demand vehicle routing problems, An iterated local search algorithm for the time-dependent vehicle routing problem with time windows, Polarity and the complexity of the shooting experiment, The traveling salesman problem: An overview of exact and approximate algorithms, The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, Minisum and maximin aerial surveillance over disjoint rectangles, A comparative analysis of several asymmetric traveling salesman problem formulations, Three enhancements for optimization-based bound tightening, An efficient optimal solution to the coil sequencing problem in electro-galvanizing line, New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints, Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient, A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants, The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation, An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem, A diagonal completion and 2-optimal procedure for the travelling salesman problem, An ant colony system for enhanced loop-based aisle-network design, Solving the family traveling salesman problem, The indefinite period traveling salesman problem, Strong multi-commodity flow formulations for the asymmetric traveling salesman problem, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, Certification of an optimal TSP tour through 85,900 cities, An approach for solving a class of transportation scheduling problems, The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem, A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem, A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs, A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem, An empirical study of a new metaheuristic for the traveling salesman problem, A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron \& Steel Complex, Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration, A cutting-plane approach to the edge-weighted maximal clique problem, The complexity of facets (and some facets of complexity), Survey of facial results for the traveling salesman polytope, Transformation of the generalized traveling-salesman problem into the standard traveling-salesman problem, A cutting plane procedure for the travelling salesman problem on road networks, Compact formulations of the Steiner traveling salesman problem and related problems, A cutting plane method for solving harvest scheduling models with area restrictions, A two-dimensional mapping for the traveling salesman problem, Light on the infinite group relaxation. I: Foundations and taxonomy, Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem, 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, A waste collection problem with service type option, Discrete dynamical system approaches for Boolean polynomial optimization, The simultaneous semi-random model for TSP, Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics, Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies, Decomposition-based algorithms for the crew scheduling and routing problem in road restoration, A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings, A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes, A lower bound for the smallest uniquely Hamiltonian planar graph with minimum degree three, The traveling salesman problem on grids with forbidden neighborhoods, On global integer extrema of real-valued box-constrained multivariate quadratic functions, A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem, Covering and connectivity constraints in loop-based formulation of material flow network design in facility layout, Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP, An efficient and general approach for the joint order batching and picker routing problem, A note on the polytope of bipartite TSP, Formulations for the orienteering problem with additional constraints, Rejoinder on: continuous approximation models in freight distribution management, A branch-and-cut algorithm for the generalized traveling salesman problem with time windows, Decorous combinatorial lower bounds for row layout problems, Graph coloring-based approach for railway station design analysis and capacity determination, Optimization of order-picking problems by intelligent optimization algorithm, A polyhedral study of the diameter constrained minimum spanning tree problem, Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem, Crane scheduling in railway yards: an analysis of computational complexity, A branch-and-Benders-cut algorithm for the crew scheduling and routing problem in road restoration, An alternate formulation of the symmetric traveling salesman problem and its properties, The green location-routing problem, Facets from gadgets, Revisiting the Hamiltonian \(p\)-median problem: a new formulation on directed graphs and a branch-and-cut algorithm, A comparison of algorithms for finding an efficient theme park tour, Travelling salesman problem in tissue P systems with costs, A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for routing problems with time windows, Selective capacitated location-routing problem with incentive-dependent returns in designing used products collection network, Hard to solve instances of the Euclidean traveling salesman problem, Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks, Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs, A way to optimally solve a green time-dependent vehicle routing problem with time windows, Traveling worker assembly line (re)balancing problem: model, reduction techniques, and real case studies, Inventory rebalancing and vehicle routing in bike sharing systems, A penalized method for multivariate concave least squares with application to productivity analysis, Exact algorithms for the equitable traveling salesman problem, Models and linearizations for the Traveling Car Renter with passengers, The undirected \(m\)-capacitated peripatetic salesman problem, Geometric and LP-based heuristics for angular travelling salesman problems in the plane, Exact algorithms for the traveling salesman problem with draft limits, Maintaining the regular ultra passum law in data envelopment analysis, The traveling salesman problem with draft limits, A heuristic algorithm for the routing and scheduling problem with time windows: a case study of the automotive industry in Mexico, Multiperiod multi traveling salesmen problem considering time window constraints with an application to a real world case, A cutting plane method for risk-constrained traveling salesman problem with random arc costs, Exact algorithms for the order picking problem, Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints, On the integrality ratio of the subtour LP for Euclidean TSP, Polyhedral approximations of the semidefinite cone and their application, Vehicle routing with endogenous learning: application to offshore plug and abandonment campaign planning, Algorithm for directing cooperative vehicles of a vehicle routing problem for improving fault-tolerance, Designing flexible loop-based material handling AGV paths with cell-adjacency priorities: an efficient cutting-plane algorithm, A metaheuristic algorithm and structured analysis for the Line-haul Feeder vehicle routing problem with time windows, A novel list-constrained randomized VND approach in GPU for the traveling thief problem, A branch-and-cut algorithm for an assembly routing problem, A branch-and-cut algorithm for the maximum covering cycle problem, The rainbow spanning forest problem, The power of linear programming: some surprising and unexpected LPs, Improved approximations for cubic bipartite and cubic TSP, On polyhedral and second-order cone decompositions of semidefinite optimization problems, Models and algorithms for the traveling salesman problem with time-dependent service times, A solution framework for linear PDE-constrained mixed-integer problems, Galois connections for phylogenetic networks and their polytopes, The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints, An optimality cut for mixed integer linear programs, Branch-and-price for a class of nonconvex mixed-integer nonlinear programs, A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP, A branch and bound algorithm for agile earth observation satellite scheduling, Constrained spanning trees and the traveling salesman problem, Stronger \(K\)-tree relaxations for the vehicle routing problem, Strong lower bounds for the prize collecting Steiner problem in graphs, Computing in combinatorial optimization, Approximate algorithms for the travelling purchaser problem, The multicommodity traveling salesman problem with priority prizes: a mathematical model and metaheuristics, Exact approaches for the cutting path determination problem, Pickup and delivery problem with incompatibility constraints, Determination of optimal path under approach and exit constraints, The influence of problem specific neighborhood structures in metaheuristics performance, An iterative graph expansion approach for the scheduling and routing of airplanes, IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem, On the facial structure of symmetric and graphical traveling salesman polyhedra, Scheduling multi-colour print jobs with sequence-dependent setup times, Elevator dispatching problem: a mixed integer linear programming formulation and polyhedral results, Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation, Branch-and-refine for solving time-expanded MILP formulations, A branch-and-price algorithm for solving the single-hub feeder network design problem, Learning to sparsify travelling salesman problem instances
