Classification of travelling salesman problem formulations

DOI10.1016/0167-6377(90)90052-7zbMATH Open0697.90057OpenAlexW2001994662MaRDI QIDQ911990FDOQ911990

Jacques Desrosiers, André Langevin, François Soumis

Publication date: 1990

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(90)90052-7

Recommendations

• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• [[:Publication:3475129|Title not available (Why is that?)]]
• A comparative analysis of several asymmetric traveling salesman problem formulations
• [[:Publication:3217891|Title not available (Why is that?)]]
• A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows

zbMATH Keywords

commodity flow formulationlinear programming relaxationsTraveling Salesman

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Integer programming (90C10)

Cites Work

• Integer Programming Formulation of Traveling Salesman Problems
• A New Formulation for the Travelling Salesman Problem
• An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• The traveling-salesman problem and minimum spanning trees: Part II
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (30)

• Formulations and valid inequalities for the heterogeneous vehicle routing problem
• Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the asymmetric traveling salesman problem
• Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation
• Covering and connectivity constraints in loop-based formulation of material flow network design in facility layout
• A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows
• A comparative analysis of several asymmetric traveling salesman problem formulations
• A classification of formulations for the (time-dependent) traveling salesman problem
• Title not available (Why is that?)
• The traveling salesman problem: An overview of exact and approximate algorithms
• Vehicle routing with endogenous learning: application to offshore plug and abandonment campaign planning
• An efficient genetic algorithm for the traveling salesman problem with precedence constraints
• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints
• A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem
• The traveling salesman problem with time-dependent service times
• Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• Routing problems: A bibliography
• The arc-item-load and related formulations for the cumulative vehicle routing problem
• Natural and extended formulations for the time-dependent traveling salesman problem
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
• Integer programming formulations for the \(k\)-in-a-tree problem in graphs
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• On symmetric subtour problems
• Combined route capacity and route length models for unit demand vehicle routing problems
• Topological design of a two-level network with ring-star configuration
• Survey of facial results for the traveling salesman polytope
• Hop-indexed circuit-based formulations for the traveling salesman problem
• Projection results for vehicle routing
• A bilevel programming approach to the travelling salesman problem.

This page was built for publication: Classification of travelling salesman problem formulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911990)