PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 31 | 179--190
Tytuł artykułu

Przekształcanie grafu połączeń do struktury kernel and shell i jej zastosowania w zagadnieniach transportowych

Treść / Zawartość
Warianty tytułu
A Graph of Connection to the Kernel and Shell Conversion - Applaying in Transportation Problems
Języki publikacji
PL
Abstrakty
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) przydatnymi mogą okazać się 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ć i dlatego jako przydatny model proponujemy strukturę kernel and shell oraz jej szczególny przypadek strukturę hub and spoke oraz 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 tych struktur stosujemy specjalizowany algorytm ewolucyjny (EA).(abstrakt oryginalny)
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 a-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.(original abstract)
Rocznik
Tom
31
Strony
179--190
Opis fizyczny
Twórcy
  • Instytut Badań Systemowych PAN
  • Instytut Badań Systemowych PAN
  • Instytut Badań Systemowych PAN
  • Instytut Badań Systemowych PAN
Bibliografia
  • [1]Ambroziak T. (2000) O pewnych aspektach modelowania systemów transportowych, (eng.:On some aspects of modeling transportation systems), Prace Naukowe Transport z. 44 OW PW Warszawa.
  • [2]Cichosz P. (2000) Systemy uczące się (in Polish), (eng.: Self-learning systems) WNT, Warszawa.
  • [3]Coyle J.J. ,Bardi E.J, Novack R.A. (1994) Transportation, Fourth Edition, New York: West Publishing Company, pp. 402.
  • [4]Hansen P., Mladenovic N., Urosevic D.(2004) Variable neighborhood search for the maximum clique, The Fourth International Colloquium on Graphs and Optimization (GO- IV)GO-IV International Colloquium on Graphs and Optimization No4, Loeche-les-Bains, SUISSE (20/08/2000) 2004, vol. 145, no 1 (28 ref.), pp. 117-125.
  • [5]Jacyna M. (2001) Modelowanie wielokryterialne w zastosowaniu do oceny systemów transportowych, (eng.: Multi-criteria modeling applied to transportation systems valuation), Prace Naukowe Transport, z.47 OW PW, Warszawa.
  • [6]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.
  • [7]Kulma-Mażbic B., Sęp K. (2005) Problem wyboru węzłów tranzytowych w sieci lotniczej, (eng.: The problem of selection transit nodes in an airline network), Logistic Systems Theory And Practice OW PW, pp. 341-348.
  • [8]Kulma-Mażbic B, Potrzebowski H., Stańczak J., Sęp K. (2008) Evolutionary approach to solve hub-and-spoke problem using a-cliques, Evolutionary Computation and Global Optimization, Prace naukowe PW, Warszawa, pp. 121-130.
  • [9]Leszczyński J. (1994) Modelowanie systemów i procesów transportowych, (eng.: Modelling of transportation precesses and systems) OW PW, Warszawa.
  • [10]Piasecki S. (1973) Optymalizacja systemów przewozowych, (eng.: Optymization of freight systems), WKiŁ, Warszawa.
  • [11]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, in: Advances in soft computing Springer-Verlag, Berlin-Heidelberg, pp. 386-393.
  • [12]Potrzebowski H., Stańczak J., Sęp K. (2006) Evolutionary Algorithm to Find Graph Covering Subsets Using Alpha-Cliques, Evolutionary Computation and Global Optimization, Prace naukowe PW, Warszawa, pp. 351-358.
  • [13]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ń (eng.: Heuristic and evolutionary methods of solving graph vertex cover problem using alpha-cliques and other constraints) (in Polish), Badania operacyjne i systemowe 2006, Metody i techniki, Akademicka Oficyna Wydawnicza EXIT, Warszawa.
  • [14]Potrzebowski H., Stańczak J., Sęp K. (2008) Evolutionary approach to solve hub-and-spoke problem using alpha-cliques, Evolutionary Computation and Global Optimization, Prace naukowe PW, Warszawa, pp. 121-130.
  • [15]Protasi M. (2001) Reactive local search for the maximum clique problem, Algoritmica vol. 29, no 4. pp. 610-637.
  • [16]Stanczak J. (2003) Biologically inspired methods for control of evolutionary algorithms, Control and Cybernetics, 32(2), pp. 411-433.
  • [17]Wilson R.J. (1996) Introduction to graph theory Addison Wesley Longman.
  • [18]http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171542504

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ć.