No label defined (Q3753824)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3991297
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3991297

      Statements

      1987
      0 references
      network flow methods
      0 references
      asymmetric traveling salesman problem
      0 references
      one commodity approach
      0 references
      strong connectedness
      0 references
      branch and bound
      0 references
      [For the entire collection see Zbl 0608.00016.] The classical approach to TSPs, based on the assignment problem as relaxation, requires an exponential number of subtour elimination constraints. However, equivalent multicommodity formulations reduce this number to the order \(O(n^ 3)\) for an n city problem. Although interesting in theory, this method does not yield a practical solution procedure. One considers therefore weaker versions, mainly one and two commodity flow problems. In this paper, we investigate the one commodity approach. An elaborate definition of supplies and demands will yield an optimal distribution graph with rich mathematical properties, such as strong connectedness and a continuing positive flow through each point as it is the case for a traveling salesman tour. The network problem will be used in form of a branch and bound method to solve asymmetric TSP's and its performance will be analyzed.
      0 references
      0 references
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references