Zastosowanie algorytmu SBT jako metody minimalizacji taboru w przedsiębiorstwie transportowym

• Autorzy: Mażbic-Kulma B. , Sęp K.

Warianty tytułu

EN

The application of SBT algorithm as a method of minimizing transportation stock in transport company

• Języki publikacji: PL

Abstrakty

PL

Rozważając problemy kombinatoryczne, zwłaszcza pod kątem praktycznego zastosowania należy wziąć pod uwagę złożoność algorytmów. W niniejszej pracy omówiono algorytm dokładny backtrackingowy, a także przedstawiono algorytmy aproksymacyjne: Lovasza-Johnsona-Chvatala oraz SBT (suboptymalnej drogi w drzewie bactrackingowym) i jego modyfikacje. Przeprowadzono analizę porównawczą zaprezentowanych algorytmów oraz przedstawiono praktyczne ich zastosowanie.

EN

Considering combinatorial problems, especially the practical use, the algorithm complexity should be taken into account. In this paper author describes Precise Backtracking Algorithm, Lovdsza-Johnsona-Chvatala Approximational Algorithm and Algorithm SBT (Sub-optimal Track in Backtracking tree) with it's modifications. Presented algorithms were comparatively analyzed and the practical implementation was shown.

Słowa kluczowe

PL

przedsiębiorstwo transportowe; minimalizacja taboru; kombinatoryka; system logistyczny

EN

transportation company; minimization of road stock; theory of combinations

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Transport
• Rocznik: 2007
• Tom: z. 60
• Strony: 115--125
• Opis fizyczny: Bibliogr. 22 poz., rys., tab., wykr.

Twórcy

autor

Mażbic-Kulma B.

autor

Sęp K.

• Polska Akademia Nauk Instytut Badań Systemowych ul. Newelska 6, 01-447 Warszawa

Bibliografia

• [1] G. Aussiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi Complexity and Approximation Springer 1999
• [2] B. Ballobas Combinatorics, Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability Cambridge University Press 1986
• [3] C. Berge Hypergraphs, Combinatorics of Finite Sets North-Holland 1989
• [4] B. Berger, J. Rompel Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry Journal of Computer and System Sciences 49 1994
• [5] J. Blot, W. Hemandez de la Vega, V. Th. Paschos, R. Saad Average case analysis of greedy algorithms for optimisation problems on set problems Theoretical Computer Science 147 1995
• [6] J. Błażewicz Złożoność obliczeniowa problemów kombinatorycznych WNT 1988
• [7] Hoong Chuin LAU, Kien Ming NG, Xiaotao WU Transport Logistics Planning with Service-Level Constraints The Logistics Institute - Asia Pacific National University of Singapore, 119260
• [8] V. Chvatal A greedy heuristic for the set-covering problem Mathematics and Operations Research 4 1979
• [9] L. Cowen Approximation algorithms Hopkins University 1998
• [10] Ding-Zhu Du, Ker-i Ko Theory of computional complexity Wiley 2000
• [11] U. Feige A Threshold of ln(n) for Approximating Set Cover Journal of the ACM 1998
• [12] O. Goldschmitd, D.S. Hochbaum, G. Yu A modified greedy heuristic for the set covering problem with improved worst case bound IPL vol. 48 1993
• [13] D. S. Hochbaum (Ed.) Approximation Algorithms for NP-hard Problems PWS Publishing Company 1997
• [14] D. S. Johnson Approximation Algorithms for Combinatorial Problems Journal of Computer and System Sciences 9 1974
• [15] B. Korte, J. Vygen Combinatorial optimization, theory and algorithms Springer 2000
• [16] Mażbic-Kulma B., Sęp K.: Algorytm znajdowania minimalnej transwersali w grafie jako narzędzie wspomagające planowanie działalności przedsiębiorstwa transportowego. LOGISTYKA, No. 6, 2006, ss. 1-7, 22 poz. bibl.
• [17] P. Kulaga, P.Sapiecha, K.Sgp Approximation Algorithm for the Argument Reduction Problem Advances in soft computing Springer Verlag Berlin 2005
• [18] L. Lovasz On the ratio of optimal integral and fractional covers Discrete Mathematics 13 1975
• [19] C. Lund, M. Yannakakis On the Hardness of Approximating Minimization Problems Journal of the ACM 1994
• [20] P. Slavik A Tight Analysis of the Greedy Algorithm for Set Cover STOC'96 USA 1996
• [21] V. Vazirani Approximation Algorithms Lecture Notes Georgia Institute of Technology 1997 [22] D. Williamson Lecture Notes on Approximation Algorithms IBM Research Report RC 21409 02 17 1999.