Sökning: id:"swepub:oai:DiVA.org:liu-36277" >
A stabilized column...
A stabilized column generation scheme for the traveling salesman subtour problem
-
- Westerlund, Andreas, 1974- (författare)
- Linköpings universitet,Matematiska institutionen,Tekniska högskolan
-
- Göthe-Lundgren, Maud, 1952- (författare)
- Linköpings universitet,Matematiska institutionen,Tekniska högskolan
-
- Larsson, Torbjörn, 1957- (författare)
- Linköpings universitet,Matematiska institutionen,Tekniska högskolan
-
(creator_code:org_t)
- Elsevier BV, 2006
- 2006
- Engelska.
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 154:15, s. 2212-2238
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.
Ämnesord
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Nyckelord
- MATHEMATICS
- MATEMATIK
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas