Evolutionary approach to solve hub-and-spoke problem using α-cliques

• Autorzy: Mażbic-Kulma B. , Potrzebowski H. , Stańczak J. , Sęp K.
• Konferencja: Evolutionary Computation and Global Optimization 2008 / National Conference (11 ; 2-4.06.2008 ; Szymbark, Poland)
• Języki publikacji: EN

Abstrakty

EN

The theory of transportation systems deals with models of phenomena connected with movement of goods and persons. The model of the transportation system should simulate a real system, but should also be a tool that enables 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 or in case of air transport - airports. The edges of the graph show direct connections between vertices. It can be noticed that such a graph can have many vertices as well as many edges. 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 a graph was introduced, using the hub-and-spoke structured graph of connections. This structure enables to concentrate and order the transport of goods/persons among vertices. To obtain the hub-and-spoke structure an evolutionary algorithm (EA) was applied. EA divides the connection graph into α-cliques (a generalization of the notion of a clique, which groups into sub-graphs highly connected vertices) and then in each α-clique a vertex with a maximum degree in this sub-graph and a maximal number of connections among other selected hubs is chosen. The α-clique with chosen vertex constitutes a "hub" with point-to-point connections - "spokes". This method enables reducing the number of analyzed vertices as well as arcs of the graph. Examples visualizing functioning of the described algorithms are presented later in this paper.

Słowa kluczowe

EN

transportation system; hub and spoke model; alfa-clique; evolutionary algorithm; evolutionary computation; global optimization

PL

transport; alfa-klika; algorytm ewolucyjny; obliczenia ewolucyjne; optymalizacja globalna

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2008
• Tom: z. 165
• Strony: 121--130
• Opis fizyczny: Bibliogr. 16 poz., tab., rys.

Twórcy

autor

Mażbic-Kulma B.

autor

Potrzebowski H.

autor

Stańczak J.

autor

Sęp K.

• IBS PAN, ul. Newelska 6, 01-447 Warszawa,

Bibliografia

• [1] Ambroziak T. (2000) O pewnych aspektach modelowania systemów transportowych, (eng.: Some aspects of transportation system modelling) Prace Naukowe Transport z. 44 OW PW Warszawa.
• [2] Cichosz P. (2000) Systemy uczące się (in Polish), (eng.: 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 No 4, Lóeche-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 modelling 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] Leszczyński J. (1994) Modelowanie systemów i procesów transportowych, (eng.: Modelling of transportation processes and systems) OW PW, Warszawa.
• [9] Piasecki S. (1973) Optymalizacja systemów przewozowych, (eng.: Optimization of freight systems) WKiŁ Warszawa.
• [10] 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.
• [11] 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.
• [12] 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 for 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.
• [13] Protasi M. (2001) Reactive local search for the maximum clique problem, Algoritmica vol. 29, no 4, pp. 610-637.
• [14] Stańczak J. (2003) Biologically inspired methods for control of evolutionary algorithms, Control and Cybernetics, 32(2), pp. 411-433.
• [15] Wilson R.J. (1996) Introduction to graph theory Addison Wesley Longman.
• [16] http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm