Search: onr:"swepub:oai:DiVA.org:liu-36277" >
A stabilized column...
-
Westerlund, Andreas,1974-Linköpings universitet,Matematiska institutionen,Tekniska högskolan
(author)
A stabilized column generation scheme for the traveling salesman subtour problem
- Article/chapterEnglish2006
Publisher, publication year, extent ...
-
Elsevier BV,2006
-
printrdacarrier
Numbers
-
LIBRIS-ID:oai:DiVA.org:liu-36277
-
https://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-36277URI
-
https://doi.org/10.1016/j.dam.2005.04.012DOI
Supplementary language notes
-
Language:English
-
Summary in:English
Part of subdatabase
Classification
-
Subject category:ref swepub-contenttype
-
Subject category:art swepub-publicationtype
Notes
-
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.
Subject headings and genre
Added entries (persons, corporate bodies, meetings, titles ...)
-
Göthe-Lundgren, Maud,1952-Linköpings universitet,Matematiska institutionen,Tekniska högskolan(Swepub:liu)maugo23
(author)
-
Larsson, Torbjörn,1957-Linköpings universitet,Matematiska institutionen,Tekniska högskolan(Swepub:liu)torla64
(author)
-
Linköpings universitetMatematiska institutionen
(creator_code:org_t)
Related titles
-
In:Discrete Applied Mathematics: Elsevier BV154:15, s. 2212-22380166-218X1872-6771
Internet link
Find in a library
To the university's database