Solution of a Large-Scale Traveling-Salesman Problem

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

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)

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

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