Lagrangian Heuristic for Fastidious Travelling Salesman Problem

• Autorzy: Maros Poncak , Stefan Pesko
• Języki publikacji: EN

Abstrakty

EN

We presented a new integer formulation for the Fastidious Travelling Salesman Problem and Lagrangean decomposition for this formulation. We proposed an aproximation algorithm for special case of the problem in which we investigated the specific updating of the Lagrangean multipliers. With this algorithm we can obtaine a lower bound of the problem for branch and bound algorithm. We can see from computational results that the improvement of the lower bound is indispensable. The limited computational results show that formulation has promise. There is a need, therefore, for extensive computational studies. The authors are currently working on a more elaborate algorithm which will exploit the structure of the formulation. (fragment of text)

Słowa kluczowe

EN

Heuristics methods; Insurances; Mathematical modeling; Lagrange multiplier

PL

Metody heurystyczne; Ubezpieczenia; Modelowanie matematyczne; Mnożniki Lagrange'a

• Czasopismo: Scientific Publications / University of Economics in Katowice
• Rocznik: 2006
• Tom: Mathematical, econometrical and computational methods in finance and insurance
• Strony: 223--229

Twórcy

autor

Maros Poncak

• University of Zilina, Slovakia

autor

Stefan Pesko

• University of Zilina, Slovakia

Bibliografia

• Palúch S.: The Fastidious Travelling Problem (to appear).
• Pončák M.: The Fastidious Travelling Problem. Transcom 2003, University of Zilina, 5-th European Conference of Young Research and Science Workers in Transport and Telecommunication, ISBN 80-8070-079-6.
• Pončák M.: The Fastidious Assignment Problem. "Journal of Information, Control and Management System" 2004, Vol. 2, No 1.
• Millar, Harvey H.: An Alternate Formulation and Lagrangean Heuristic for the Traveling Salesperson Problem. 1999, http://citeseer.ist /millar99alternate. Html
• Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B.: The Traveling Salesman Problem. Wiley, Chichester 1985.
• Holmberg K.: A Convergence Proof for Linear Mean Value Cross Decomposition. LiTH-MAT-R, 1991.