Application of selected methods of graph theory and combinatorial heuristics to minimising the number of transits nodes in an air network

• Autorzy: Mażbic-Kulma B. , Owsiński J. W. , Sęp K.

Warianty tytułu

PL

Zastosowanie wybranych metod teorii grafów i heurystyk kombinatorycznych w minimalizacji zbioru węzłów tranzytowych w sieci lotniczej

• Języki publikacji: EN

Abstrakty

EN

In the paper we present the notion of alpha-clique and some of its properties. Covering with alpha-cliques is a preprocessing method for an air network, described as a graph, in which vertices correspond to airports and edges correspond to air connections. Using the alpha-clique cover we obtain a hypergraph, in which we find the minimum transversal. The set of vertices thus obtained is the sought-for set of transits nodes, called hubs. Using the alpha-clique concept instead of proper cliques we can obtain the solution to the graph covering problem easier.

PL

W niniejszej pracy prezentujemy pojęcie alfa-kliki i pewne jej własności. Znalezienie pokrycia alfa-klikami traktujemy jako metodę preprocessingu dla sieci lotniczych opisanych jako graf, w którym węzły odpowiadają lotniskom, a krawędzie odpowiadają połączeniom lotniczym. Znajdując pokrycie alfa-klikami, uzyskujemy hipergraf, dla którego otrzymujemy minimalną transwersalę. W ten sposób uzyskujemy zbiór wierzchołków będących węzłami tranzytowymi czyli hubami. Stosując alfa-kliki zamiast odpowiednich klik, możemy uzyskać lepsze pokrycie grafu.

Słowa kluczowe

EN

hub and spoke; graph; decision support systems; clique

PL

hub and spoke; graf; DSS; systemy wspomagania decyzji; klika

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Total Logistic Management
• Rocznik: 2008
• Tom: no. 1
• Strony: 111--123
• Opis fizyczny: Bibliogr. 29 poz., rys.

Twórcy

autor

Mażbic-Kulma B.

• Systems Research Insitute, Polish Academy of Sciences, Warsaw, Poland

autor

Owsiński J. W.

• Systems Research Insitute, Polish Academy of Sciences, Warsaw, Poland

autor

Sęp K.

• Systems Research Insitute, Polish Academy of Sciences, Warsaw, Poland

Bibliografia

• Berge C. 1989. Hypergraphs, Combinatorics of Finite Sets. North-Holland.
• Chvatal V. 1979. A greedy heuristic for the set-covering problem. Mathematics and Operations Research, 4.
• Cormen Th.H., Leiserson Ch.E., Rivest R.L., Stein C. 2004. Wprowadzenie do algorytmów. WNT, Warszawa.
• Cowen L. 1998. Approximation Algorithms. Johns Hopkins University.
• Feige U. 1998. A Threshold of ln(n) for Approximating Set Cover. Journal of the ACM.
• Hansen P., Mladenovic N., Urosevic D. 2000. Variable neighborhood search for the maximum clique. The Fourth International Colloquium on Graphs and Optimisation (GO-IV), Loeche-les-Bains, Suisse (20.08.2000) 2004, Vol. 145, No. 1, pp. 117-125.
• Horner M., O'Kelly M.E. 2001. Embedding economy of scale concepts for hub network design. Journal of Transport Geography, 9(4), pp. 255-265.
• Hochbaum D.S. (Ed.) 1997. Approximation Algorithms for NP-hard Problems. PWS Publishing Company.
• Johnson D.S. 1974. Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, 9.
• Jukna S. 2001. Extremal Combinatorics, Springer-Verlag, Berlin Heidelberg.
• Kloks T., Kratsch D. 1998. Listing all minimal separators of a graph. SIAM J. COMPUT., Vol. 27, No. 3, pp. 605-613.
• Korte B., Vygen J. 2000. Combinatorial Optimization, Theory and Algorithms. Springer.
• Kułaga P., Sapiecha P., Sęp K.2005. Approximation Algorithm for the Argument Reduction Problem. Advances in soft computing. Computer recognition systems CORES'05, Springer-Verlag, Berlin.
• Kumlander D. 2007. An Approach for the Maximum Clique Finding Problem Test Tool Software Engineering. Software Engineering, SE 2007, Innsbruck, Austria.
• Lovasz L. 1975. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13.
• Mażbic-Kulma B., Sęp K. 2005. Problem wyboru węzłów tranzytowych w sieci lotniczej (The problem of selection of the transit nodes in an air network; in Polish). Materiały konferencji "Systemy logistyczne. Teoria i praktyka", Warszawa, Politechnika Warszawska, pp. 341-348.
• Mażbic-Kulma B., Sęp K. 2006. Baza wierzchołkowa w hipergrafie jako metoda przydzielania zadań (Transversal of a hypergraph as a method of assigning tasks; in Polish). Kacprzyk J., Budziński R., Badania operacyjne i systemowe 2006. Metody i techniki, Akademicka Oficyna Wydawnicza EXIT, pp. 283-290.
• Mażbic-Kulma B., Sęp K. 2007a. Minimalizacja liczby węzłów w sieci logistycznej (Minimisation of the number of nodes in a logistic network; in Polish). [in:] Bukowski L.A., Feliks J., Karkula M., Lichota A. (Eds), Rocznik 2007, Seria: Wybrane Zagadnienia Logistyki Stosowanej, Komitet Transportu PAN, Kraków, pp. 59-65.
• Mażbic-Kulma B., Sęp K. 2007b. Some approximation algorithms for minimum vertex cover in a hypergraph. [in:] Kurzyński M., Puchała E., Woźniak M., Żołnierek A. (Eds), Komputer Recognition Systems 2, Series: Advances in Soft Computing, Springer-Verlag, Berlin-Heidelberg, pp. 250-257.
• Mażbic-Kulma B., Sęp K. 2007c. Zastosowanie algorytmu SBT jako metody minimalizacji taboru w przedsiębiorstwie transportowym (Application of the SBT algorithm as a fleet minimisation method for a transport enterprise; in Polish). [in:] Dąbrowa-Bajon M., Krawczyk G., Ambroziak T., Grochowski L., Lozia Z., Manerowski J. (Eds), Transport w systemach logistycznych, Seria: Prace Naukowe — Transport, Politechnika Warszawska, Warszawa, pp. 115-125.
• Min H., Gou Z. 2004. The location of hub-seaports in the global supply chain network using a co-operative competition strategy. Integrated Supply Management, Vol. 1 No. 1, pp. 51-63.
• O'Kelly M.E 1987. A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, 32, pp. 392-404.
• O'Kelly M.E., Bryan D. 2002. Interfacility interaction in models of hubs and spoke networks. Journal of Regional Science, 42 (1), pp. 145-165.
• Potrzebowski H., Stańczak J., Sęp K. 2006a. Evolutionary Algorithm to Find Graph Covering Subsets Using a-Cliques. [in:] Arabas J. (Ed.), Evolutionary Computation and Global Optimization. Prace naukowe Politechniki Warszawskiej, pp. 351-358.
• Potrzebowski H., Stańczak J., Sęp K. 2006b. Heurystyczne i ewolucyjne metody znajdowania pokrycia grafu, korzystajace z pojęcia alfa-kliki i innych ograniczeń (Heuristic and evolutionary methods of finding graph covering, using the notion of alpha-clique and other constraints; in Polish.) [in:] Badania operacyjne i systemowe 2006. Metody i techniki, Akademicka Oficyna Wydawnicza EXIT, Warszawa, pp. 387-395.
• Potrzebowski H., Stańczak J., Sęp K. 2007. Separable decomposition of graph using alpha-cliques. [in:] Kurzyński M., Puchała E., Woźniak M., Żołnierek A. (Eds), Computer Recognition Systems 2, Series: Advances in Soft Computing, Springer-Verlag, Berlin-Heidelberg, pp. 386-393.
• Protasi M. 2001. Reactive local search for the maximum clique problem. Algoritmica Vol. 29, No. 4, pp. 610-637.
• Sapiecha P., Selvaraj H., Stańczak j., Sęp K., Luba T. 2004. A hybrid approach to a classification. Intelligent information processing and web mining, Springer-Verlag, Berlin.
• Wilson R.J. 1996. Introduction to graph theory. Addison Wesley Longman.