A Lagrangean heuristic for the capacitated concave minimum cost network flow problem

• We propose a heuristic solution technique for the capacitated concave minimum cost network flow problem based on a Lagrangean dualization of the problem. Despite its dual character the algorithm guarantees the generation of primal feasible solutions which are local optima and therefore candidates of being the global optimum. The Lagrangean dual is solved by a subgradient search procedure and provides a lower bound to the optimal value. The lower bound is, in general, stronger than the one obtained by a linear approximation of the original problem. It can be used as a judgement of the quality of the solution or in a branch and bound procedure. Computational results from randomly generated problems are presented

Ämnesord

TEKNIK OCH TEKNOLOGIER  -- Maskinteknik -- Produktionsteknik, arbetsvetenskap och ergonomi (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Mechanical Engineering -- Production Engineering, Human Work Science and Ergonomics (hsv//eng)

Nyckelord

Industrial Logistics

Industriell logistik

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)