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

• Authors: J. Węgrzyn

Title variants

EN

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

Abstracts

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.

Keywords

PL

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

EN

spreadsheet; travelling salesperson problem; optimisation software; integer programming

• Publisher: Polskie Wydawnictwo Ekonomiczne
• Journal: Gospodarka Materiałowa i Logistyka
• Year: 2014
• Issue: 10
• Pages: 11-19

Dates

published

2014

Contributors

author

J. Węgrzyn

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

References

• 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).

Identifiers

Biblioteka Nauki

1377944