Evolutionary approach to find kernel and shell structure of a connection graph

• Autorzy: Mażbic-Kulma B. , Potrzebowski H. , 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 instances: hub-and-spoke and α-clique structured graphs of connections. These structures enable to concentrate and order the transport of goods/persons among vertices. To obtain these desired structures an evolutionary algorithm (EA) was applied. This method enables to reduce the number of analyzed vertices as well as arcs/edges of the graph.

PL

Reguły gospodarki rynkowej i coraz ostrzejsza konkurencja zmuszają przedsiębiorstwa do poszukiwania sposobów obniżenia kosztów działalnosci gospodarczej. Konieczność redukcji kosztów dotyczy m.in. gospodarki transportowej. Znaczenie optymalizacji rozwiązań w sferze transportu w aspekcie kosztowym jest szczegolnie istotne, jeżeli weźmie się pod uwagę znaczny udział kosztów transportu w kosztach logistycznych przedsiebiorstwa. Oczywisty staje się fakt, iż nie jest możliwe funkcjonowanie firm działających na współczesnych globalnych rynkach bez transportu. Zdecydowana większość przedsiębiorstw znajduje się w pewnej odległości od swoich źrodeł zaopatrzenia, co sprawia, że są one zależne od transportu łączącego źrodlo zaopatrzenia z miejscem konsumpcji. Specjalizacja pracy, masowa konsumpcja i ekonomia skali produkcji powodują, że miejsca wytwarzania produktów nie pokrywają się z miejscem, gdzie zgłaszany jest na nie popyt. Stąd też transport staje się niezbędnym narzędziem łączącym nabywców i sprzedawców. W niniejszym artykule przedstawiono narzędzie wspomagające modelowanie systemu transportowego. Jak wiadomo, dokładny model systemu transportowego przedsiębiorstwa trudno jest analizować czy też optymalizować jego działanie. Dlatego jako model sieci transportowej proponujemy strukturę kernel and shell i jej szczególne przypadki: strukturę hub and spoke oraz strukturę α-klikową. Struktury te umożliwiają koncentrację i zarządzanie transportem pomiędzy węzłami. W celu uzyskania tych struktur z wejściowego grafu połączeń stosujemy opracowane przez nas specjalizowane algorytmy ewolucyjne (EA).

Słowa kluczowe

EN

logistic network; kernel and shell; clique; evolutionary algorithm

PL

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

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Total Logistic Management
• Rocznik: 2009
• Tom: no. 2
• Strony: 37--50
• Opis fizyczny: Bibliogr. [18] poz., rys., tab.

Twórcy

autor

Mażbic-Kulma B.

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

autor

Potrzebowski H.

• 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 Transport, z. 44,OWPW,Warszawa.
• Cichosz P. 2000. Systemy uczące się (Self-learning systems). WNT, Warszawa (in Polish).
• Coyle J.J., Bardi E.J., Novack R.A. 1994. Transportation (4th Edition).West Publishing Company, New York, pp. 402.
• 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). Prace Naukowe Transport, z. 47, OW PW, Warszawa.
• 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.
• 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, pp. 341–348.
• Kulma-Mażbic B., Potrzebowski H., Stańczak J., Sęp K. 2008. Evolutionary approach to solve huband- spoke problem using α-cliques. Evolutionary Computation and Global Optimization, Prace Naukowe PW, Warszawa, pp. 121–130.
• Leszczyński J. 1994. Modelowanie systemów i procesów transportowych (Modelling of transportation precesses and systems). OWPW, Warszawa.
• 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, Evolutionary Computation and Global Optimization. Prace Naukowe PW, 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 (in Polish).
• Potrzebowski H., Stańczak J., Sęp K. 2008. Evolutionary approach to solve hub-and-spoke problem using α-cliques. Evolutionary Computation and Global Optimization, PraceNaukowe PW, 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.
• BHOSLIB: Benchmarks with Hidden Optimum Solutions for Graph Problems. http://www.nlsde. buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm (accessed November, 2009