O problemie komiwojażera, w którym koszty tras są zmiennymi losowymi niezależnymi

• Autorzy: Artur Owczarkowski

Warianty tytułu

On the Travelling Salesperson Problem, Where Costs between Cities Independent Random Variables

• Języki publikacji: PL

Abstrakty

W niniejszym artykule autor prezentuje wariant zagadnienia komiwojażera, w którym koszty tras są zmiennymi losowymi niezależnymi o różnych rozkładach. Proponowane ujęcie problemu jest uogólnieniem wariantu TSP z kosztami jako zmiennymi niezależnymi o identycznym rozkładzie, pozbawionym wyżej wspomnianych wad. W artykule przedstawiono model matematyczny zagadnienia oraz modyfikacje algorytmu dokładnego i wybranych algorytmów heurystycznych, służących uzyskaniu rozwiązania problemu. (fragment tekstu)

EN

This paper studies the Traveling Salesperson Problem, where costs c_ij between cities i and j are treated as independent random variables. A new formulation of this problem is derived. The author presents modified algorithms to solve the problem: an exact branch and bound algorithm and two heuristics, such as the Nearest Neighbor and the Greedy algorithm. (original abstract)

Słowa kluczowe

PL

Modele podejmowania decyzji; Modele matematyczne; Metody heurystyczne; Algorytmy; Zmienne losowe; Ryzyko

EN

Decision-making models; Mathematical models; Heuristics methods; Algorithms; Random variable; Risk

• Czasopismo: Zeszyty Naukowe / Akademia Ekonomiczna w Poznaniu
• Rocznik: 2008
• Numer: nr 104
• Strony: 118--129

Twórcy

autor

Artur Owczarkowski

• Akademia Ekonomiczna w Poznaniu

Bibliografia

• Cerf N.J., Boutet de Monvel J., Bohigas O., Martin O.C., Percus A.G., The Random Link Approximation for the Euclidean Traveling Salesman Problem, Journal de Phisique I, 1997, s. 117-136.
• Choi J., Lee J.H., Realff M.J., An Algorithmic Framework for Improving Heuristic Solutions, part II: A New Version of the Stochastic Travelling Salesman Problem. http://www.cpse.gatech.edu/reports/TSP_stoc_final.pdf.
• Dantzig G.B., Fulkerson D.R., Johnson S.M., Solution of a Large-scale Traveling-salesman Problem, Operations Research 1954, 2, s. 393-410.
• Garfinkel R.S., Nemhauser G.L., Integer programming, John Wiley & Sons, Nowy Jork 1972.
• Grabowski W., Programowanie matematyczne, PWE, Warszawa 1980.
• Jurek W., Konstrukcja i analiza portfela papierów wartościowych o zmiennym dochodzie, Wydawnictwo Akademii Ekonomicznej w Poznaniu, Poznań 2001.
• Kao E.P.C., A Preference Order Dynamic Program for a Stochastic Traveling Salesman Problem. Operations Research 26, 1978, nr 6, s. 1033-1045.
• Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B., The Traveling Salesman Problem, John Wiley & Sons, Nowy Jork 1985.
• Little J.D.C., Murty K.G., Sweeney D.W., Karel C., An Algorithm for the Traveling Salesman Problem. Operations Research 1963, 11, s. 972-989.
• Miller C.E., Tucker A.W., Zemlin R.A., Integer Programming Formulation of Traveling Salesman Problems, J. Assoc. Comput. Mach, 1960, 7, s. 326-329.
• Kasprzak T. (red.), Optymalizacja dyskretna. Zastosowania ekonomiczne, PWE, Warszawa 1984.
• Owczarkowski A., Problem komiwojażera z losowym obciążeniem tras, w: T. Trzaskalik (red.), Modelowanie preferencji a ryzyko '06, 2006, s. 255-267.
• Percus A.G., Martin O.C., The Stochastic Traveling Salesman Problem: Finite Size Sacling and the Cavity Prediction, Journal of Statistical Physics 94, 1999, nr 5/6, s. 739-758.
• Sysło M.M., Deo N., Kowalik J.S., Algorytmy optymalizacji dyskretnej z programami w języku Pascal, Wydawnictwo Naukowe PWN, Warszawa 1995.