Finding structure kernel and shell with predetermined cardinality of kernel set, using evolutionary algorithm

• Autorzy: Mażbic-Kulma B. , Stańczak J. , Sęp K.

Warianty tytułu

PL

Zastosowanie metod ewolucyjnych do wyznaczania struktur kernel and shell w grafie połączeń

• Języki publikacji: EN

Abstrakty

EN

The theory of logistic transportation systems deals with models of phenomena connected with movement of goods and persons. The developed model of the transportation system is expected to simulate a real system, but also should help us to solve given transportation tasks. In order to describe transportation system (rail, bus or air), as a routine a connection graph would be used. Vertices of the graph can be train stations, bus stops etc. The edges show direct connections between vertices. Its direct application can be difficult and computational problems can occur while one would try to organize or optimize such a transportation system. Therefore, a method of aggregation of such graph was introduced, using the general kernel and shell structure and its particular instance the α-clique structured graphs of connections. In the present approach, we use a predetermined number of communication hubs with the possibility of direct determining which nodes should become hubs or selecting them by the solving method. This structure allows to concentrate and order the transport of goods/persons among vertices and enables to reduce the number of analyzed vertices as well as arcs/edges of the graph. To obtain the desired structure, an evolutionary algorithm (EA) was applied.

PL

Teoria logistycznych systemów transportowych zajmuje się zagadnieniem połączeń w przewozach ludzi i towarów. Od modelu systemu transportowego oczekuje się symulowania rzeczywistego systemu w celu rozwiązywania problemów transportowych. Do opisania systemów transportowych (kolejowych, drogowych czy lotniczych) przydatne mogą się okazać grafy. Wierzchołki grafu mogą odpowiadać węzłom logistycznym, takim jak: stacje kolejowe, przystanki autobusowe, lotniska itd., a krawędzie - bezpośrednim połączeniom pomiędzy węzłami. Dokładny model trudno byłoby analizować lub optymalizować, dlatego jako przydatny model proponujemy strukturę kernel and shell oraz jej szczególny przypadek - strukturę α-klikową jako graf odwzorowujący strukturę połączeń. Struktury te umożliwiają koncentrację i zarządzanie transportem pomiędzy węzłami. W celu uzyskania tej struktury stosujemy specjalizowany algorytm ewolucyjny (EA).

Słowa kluczowe

EN

kernel and shell; clique; logistic network; evolutionary algorithm

PL

kernel and shell; klika; sieć logistyczna; algorytm ewolucyjny

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Total Logistic Management
• Rocznik: 2010
• Tom: no. 3
• Strony: 53--64
• Opis fizyczny: Bibliogr. [19] poz., rys., tab.

Twórcy

autor

Mażbic-Kulma B.

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

autor

Stańczak J.

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

autor

Sęp K.

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

Bibliografia

• Ambroziak T. 2000. O pewnych aspektach modelowania systemów transportowych [On some aspects of modeling transportation systems]. Prace Naukowe Politechniki Warszawskiej. Transport, z. 44, OW PW,Warszawa, pp. 29–56.
• BHOSLIB: Benchmarks with Hidden Optimum Solutions for Graph Problems. http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm (accessed: November, 2009).
• Cichosz P. 2000. Systemy uczące się [Self-learning systems]. WNT, Warszawa.
• Coyle J.J., Bardi E.J., Novack R.A. 1994. Transportation. 4th Edition. West Publishing Company, New York.
• Hansen P., Mladenovic N., Urosevic D. 2004. Variable neighborhood search for the maximum clique. Discrete Applied Mathematics, Vol. 145, No. 1, pp. 117–125.
• Jacyna M. 2001. Modelowanie wielokryterialne w zastosowaniu do oceny systemów transportowych [Multi-criteria modeling applied to transportation systems valuation]. PraceNaukowe Politechniki Warszawskiej. Transport, z. 47, OWPW, Warszawa, pp. 3–139.
• 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.
• Leszczyński J. 1994. Modelowanie systemów i procesów transportowych [Modelling of transportation precesses and systems]. OWPW, Warszawa.
• Mażbic-Kulma B., Potrzebowski H., Stańczak J., Sęp K. 2008. Evolutionary approach to solve hub-and-spoke problem using α-cliques. Evolutionary Computation and Global Optimization, Prace Naukowe Politechniki Warszawskiej. Elektronika, z. 165, OW PW, Warszawa, pp. 121–130.
• Mażbic-Kulma B., Potrzebowski H., Stańczak J., Sęp K. 2008. Evolutionary approach to find kernel and shell structure of a connection graph. Total Logistic Management, Vol. 2, AGH University of Science and Technology Press, Cracow, pp. 37–50.
• Kulma-Mażbic B., Sęp K. 2005. Problem wyboru węzłów tranzytowych w sieci lotniczej [The problem of selection transit nodes in an airline network]. Logistic Systems Theory and Practice, OW PW,Warszawa, pp. 341–348.
• Piasecki S. 1973. Optymalizacja systemów przewozowych [Optimization of freight systems]. WKiŁ, Warszawa.
• 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, Advances in soft computing, Springer Verlag, Berlin – Heidelberg, pp. 386–393.
• Potrzebowski H., Stańczak J., Sęp K. 2006. Evolutionary Algorithm to Find Graph Covering Subsets Using α-Cliques. [in:] Evolutionary Computation and Global Optimization, Prace Naukowe Politechniki Warszawskiej. Elektronika, OWPW, Warszawa, pp. 351–358.
• Potrzebowski H., Stańczak J., Sęp K. 2006. Heurystyczne i ewolucyjne metody znajdowania pokrycia grafu, korzystające z pojęcia alfa-kliki i innych ograniczeń. [Heuristic and evolutionary methods of solving graph vertex cover problem using alpha-cliques and other constraints]. [in:] Badania operacyjne i systemowe. Metody i techniki, Akademicka Oficyna Wydawnicza EXIT, Warszawa.
• Potrzebowski H., Stańczak J., Sęp K. 2008. Evolutionary approach to solve hub-and-spoke problem using α-cliques. [in:] Evolutionary Computation and Global Optimization, Prace Naukowe Politechniki Warszawskiej. Elektronika, OWPW, Warszawa, pp. 121–130.
• Protasi M. 2001. Reactive local search for the maximum clique problem. Algoritmica, Vol. 29, No. 4, pp. 610–637.
• Stańczak J. 2003. Biologically inspired methods for control of evolutionary algorithms. Control and Cybernetics, Vol. 329, No. 2, pp. 411–433.
• Wilson R.J. 1996. Introduction to graph theory. AddisonWesley, Longman.