Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 23 | nr 2 | 91--105
Tytuł artykułu

The Kernel and Shell Structure as a Tool for Improving the Graph of Transportation Connections

Treść / Zawartość
Warianty tytułu
Języki publikacji
A model of a transportation system is expected to be useful in simulations of a real system to solve given transportation tasks. A connection graph is routinely used to describe a transportation system. Vertices can be train stations, bus stops, airports etc. The edges show direct connections between vertices. A direct approach can be difficult and computational problems can arise in attempts to organize or optimize such a transportation system. Therefore, a method for aggregating such graphs was introduced, using a general kernel and shell structure and its particular instances: α-clique structured graphs of connections and a hub and spoke transformation of the source graph. These structures enable the concentration and ordering of transport between vertices and reduction of the analyzed graph. To obtain the desired structures, several versions of a specialized evolutionary algorithm were developed and applied. (original abstract)
Opis fizyczny
  • Warsaw School of Information Technology
  • Polish Academy of Sciences, Warszawa
  • Polish Academy of Sciences
  • Polish Academy of Sciences
  • [1] CHEN Z.-Q., WANG R.-L., OKAZAKI K., An Efficient Genetic Algorithm Based Approach for the Minimum Graph Bisection Problem, IJCSNS International Journal of Computer Science and Network Security, 2008, 8 (6), 118-124.
  • [2] CORMEN T.H., LEISERSON CH.E., RIVEST R.L., STEIN C., Introduction to Algorithms, 3rd Ed., MIT, Cambridge, Mass., USA, 2009.
  • [3] O'KELLY M.E., A quadratic integer program for the location of interacting hub facilities, European Journal of Operational Research, 1987, 32, 392-404.
  • [4] O'KELLY M.E., BRYAN D., Interfacility interaction in models of hubs and spoke networks, Journal of Regional Science, 2002, 42 (1), 145-165.
  • [5] MARCHIORI E., A Simple Heuristic Based Genetic Algorithm for the Maximum Clique Problem, Proceedings of the 1998 ACM Symposium on Applied Computing, 1998, ACM, 366-373.
  • [6] MAŻBIC-KULMA B., POTRZEBOWSKI H., STAŃCZAK J., SĘP K., Evolutionary approach to solve huband-spoke problem using α-cliques, [in:] Evolutionary Computation and Global Optimization, Prace Naukowe PW, Elektronika, Warsaw 2008, 165, 121-130.
  • [7] MAŻBIC-KULMA B., POTRZEBOWSKI H., STAŃCZAK J., SĘP K., Evolutionary approach to find kernel and shell structure of a connection graph, TLM AGH, Cracow 2009, 37-50.
  • [8] MIN H., GOU Z., The location of hub-seaports in the global supply chain network using a cooperative competition strategy, Integrated Supply Management, 2004, 1 (1), 51-63.
  • [9] POTRZEBOWSKI H., STAŃCZAK J., SĘP K., Evolutionary algorithm to find graph covering subsets using α-cliques, [in:] Evolutionary Computation and Global Optimization, J. Arabas (Ed.), Prace Naukowe PW, Konferencje, Warsaw 2006, 351-358.
  • [10] POTRZEBOWSKI H., STAŃCZAK J., SĘP K., Heurystyczne i ewolucyjne metody znajdowania pokrycia grafu, korzystające z pojęcia alfa-kliki i innych ograniczeń. Badania operacyjne i systemowe 2006. Metody i techniki, Akademicka Oficyna Wydawnicza EXIT, Warsaw 2006.
  • [11] POTRZEBOWSKI H., STAŃCZAK J., SĘP K., Separable decomposition of graph using alpha-cliques, [in:] Computer recognition systems 2. Advances in soft computing, M. Kurzyński, E. Puchała, M. Woźniak, A. Żołnierek (Eds.), Springer-Verlag, Berlin 2007, 386-393.
  • [12] POTRZEBOWSKI H., STAŃCZAK J., SĘP K., Evolutionary approach to solve hub-and-spoke problem using α-cliques, Evolutionary Computation and Global Optimization, Prace Naukowe PW, Warsaw 2008, 165, 121-130.
  • [13] STAŃCZAK J., POTRZEBOWSKI H., SĘP K., Evolutionary approach to obtain graph covering by densely connected subgraphs, Control and Cybernetics, 2011, 41 (3), 80-107.
  • [14] TALBI E.-G., BESSIERE P., A parallel genetic algorithm for the graph partitioning problem, Proceedings of the 5th International Conference on Supercomputing, ACM, New York 1991, 312-320.
  • [15] WILSON R.J., Introduction to Graph Theory, Longman, Harlow 1996.
  • [16] YU T.L., GOLDBERG D.E., YASSINE A., YASSINE C.A., Genetic algorithm design inspired by organizational theory, Genetic and Evolutionary Computation Conference, Chicago, Illinois, USA, Springer-Verlag, Lecture Notes in Computer Science, Heidelberg 2003.
Typ dokumentu
Identyfikator YADDA

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.