Rozwiązywanie problemu komiwojażera za pomocą LP/Quadratic Solver z Analytic Solver Platform v12.5

• Autorzy: Węgrzyn J.

Warianty tytułu

EN

Solving the travelling salesman problem using LP/Quadratic Solver from the Analytic Solver Platform V12.5

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono wyniki rozwiązań przykładów Problemu Komiwojażera (TSP). Uzyskano je za pomocą LP/Quadratic Solver wchodzącego w skład Analytic Solver Platform v12.5. LP/Quadratic Solver zaprojektowany do rozwiązywania problemów LP/MIP pozwala na rozwiązanie TSP w postaci modelu programowania całkowitoliczbowego. Rozwiązania uzyskano w oparciu: o wprowadzony do Excela 2010 model problemu przydziału z warunkami ograniczającymi Millera, Tuckera i Zemlina eliminującymi podcykle. Przedstawiono czasy rozwiązań symetrycznych i asymetrycznych przykładów TSP z TSPLIB o małych rozmiarach, ograniczonych przez maksymalną liczbę zmiennych całkowitoliczbowych w LP/Quadratic Solver.

EN

The solutions of results of Traveling Salesperson Problem (TSP) samples are presented in this article. Their were received using LP/Quadratic Solver included in Analytic Solver Platform V12.5. LP/Quadratic Solver designed for solutions of LP/MIP problems allow to solve TSP as integer programming model. Solutions were received based on Assignment Problem with Miller, Tucker, Zemlin subtour eliminating constraints model introduced to Excel 2010. Solved times of symmetric and asymmetric TSP samples from TSPLIB with small size of problems, limited by max integer variables of LP/Quadratic Solver are presented.

Słowa kluczowe

PL

arkusz kalkulacyjny; problem komiwojażera; oprogramowanie optymalizacyjne; programowanie całkowitoliczbowe

EN

spreadsheet; travelling salesperson problem; optimisation software; integer programming

• Wydawca: Polskie Wydawnictwo Ekonomiczne SA
• Czasopismo: Gospodarka Materiałowa i Logistyka
• Rocznik: 2014
• Tom: nr 10
• Strony: 11--19
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Węgrzyn J.

• Politechnika Śląska, Wydział Inżynierii Materiałowej i Metalurgii, Katedra Inżynierii Produkcji

Bibliografia

• Applegate, D.L., Bixby, R.E., Chvátal, V. and Cook, W.J. (2007). The traveling salesman problem: a computational study. NJ, USA: Princeton University Press.
• Baker, K.R. (2011). Solving sequencing problems in spreadsheets. Int. J. Planning and Scheduling, 1(1/2), 3-18.
• Changbing, J. (2010). A Reliable Solver of Euclidean Traveling Salesman Problems with Microsoft Excel Addin Tools for Smallsize System. Journal of Software, 5(7), 761-768.
• Chaudhuri, A., De K. (2010). A study of Traveling Salesman Problem Using Fuzzy Self Organizing Map. In: D. Davendra (edited) Traveling Salesman Problem, Theory and Applications. InTech 2010; http: //www. intechopen. com (2013-04-15).
• Dantzig, G., Fulkerson, R., Johnson, S. (1954). Solution of a Large-Scale Traveling-Salesman Problem. Reviewed work(s): Source: Journal of the Operations Research Society of America, 2(4), 393-410. Published by: INFORMS Stable URL: http: //www.stor.org/sta-ble/166695 (Accessed: 11/04/2012 17: 52).
• Gutin, G., Punnen, A.P. (edited). (2004). The Traveling Salesman Problem And Its Variations. Kluwer Academic Publishers.
• Langevin, A., Suomis, F. (1990). Classification of Travelling Salesman Problem formulations. Operations Research Letters, (9), 127-132.
• Miller, C.E., Tucker, A.W., Zemlin, R A (1960). Integer Programming Formulation of Traveling Salesman Problems. Journal of ACM, (7), 326-329.
• Orman, A.J. and Williams, H.P. (2004). A survey of different integer programming formulations of the travelling salesman problem. LSE Research Online, March 09 2004 Revised July 2005; http://eprints.lse.ac.Uk/9349/l/WP67_A_Survey_ofJDifferentFormulationsoftheT-SPJuly20051LSEROVERSION.pdf (2013-04-25).
• Pataki, G. (2003). Teaching integer programming formulations using the traveling salesman problem. SIAM Review, 45 (1), 116-123.
• Patterson, M.C., Harmel, B. (2005). Solving the Traveling Salesman Problems using Premium Solver Platform Software. International Journal of Management, 22 (4), 532-541.
• Rasmussen R. (2011a). TSP in Spreadsheets — a Guided Tour. 2011. International Review of Economic Education, 10 (1), 94-116; http://www.economicsnetwork.ac.uk/iree/vlOnl/rasmussen.pdf (2012-08-30).
• Rasmussen R. (2011b). TSP inspreadsheets —A fast and flexible tool. Omega 39 (2011) pages 51-63; http://www.elsevier.com/locate/omega (2013-04-04).
• Sysło M., Deo N., Kowalik J. (1999). Algorytmy optymalizacji dyskretnej. Warszawa: PWN.
• Węgrzyn J. (2013). Rozwiązywanie problemu komiwojażera za pomocą Metody Ewolucyjnej z Excela 2010. Gospodarka Materiałowa i Logistyka, (12), 11-17.
• Frontline Systems Inc. (2013). Frontline Solvers User Guide version 12.5 For Use With Excel 2003-2013.
• http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (2013-01-29).
• http://www.solver.com/analytic-solver-platform (2013-02-15).
• http://www.tsp.gatech.edu/concorde/ (2013-04-04).