A stabilized column generation scheme for the traveling salesman subtour problem

Westerlund, Andreas,1974-Linköpings universitet,Matematiska institutionen,Tekniska högskolan (författare)

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.

Göthe-Lundgren, Maud,1952-Linköpings universitet,Matematiska institutionen,Tekniska högskolan(Swepub:liu)maugo23 (författare)
Larsson, Torbjörn,1957-Linköpings universitet,Matematiska institutionen,Tekniska högskolan(Swepub:liu)torla64 (författare)
Linköpings universitetMatematiska institutionen (creator_code:org_t)

Ingår i:Discrete Applied Mathematics: Elsevier BV154:15, s. 2212-22380166-218X1872-6771

Av författaren/redakt...: Westerlund, Andr ...; Göthe-Lundgren, ...; Larsson, Torbjör ...

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.