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
0.8241750597953796
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