Properties of an α-clique approach to obtaining the hub and spoke structure in optimization of transportation systems

• Autorzy: Mazbic-Kulma B. , Owsinski J. W. , Barski A. , Sęp K. , Stańczak J.
• Języki publikacji: EN

Abstrakty

EN

The paper is devoted to the analysis of a graph transformation, pertinent for the transport and logistic systems and their planning and management. Namely, we consider, for a given graph, representing some existing transport or logistic system, its transformation to a (non-equivalent) so-called ”hub-and-spoke” structure, known from both literature and practice of transportation and logistics. This structure is supposed to bring benefits in terms of functioning and economic performance of the respective systems. The transformation into the ”hub-and-spoke” is not only non-equivalent (regarding the original graph of the system), but is also, in general, non unique. The structure sought is composed of two kinds of elements - nodes of the graph (stations, airports, havens, etc.), namely: the subgraph of hubs, which, in principle, ought to constitute a complete sub-graph (a clique), and the ”spokes”, i.e. the subsets of nodes, each of which is connected in the ultimate structure only with one of the hubs. The paper proposes a relaxation of the hub-and-spoke structure by allowing the hub subgraph not to be complete, but at least connected, with a definite ”degree of completeness” (alpha), from where the name of ”alpha-clique”. It is shown how such structures can be obtained and what are the resulting benefits for various assumptions, regarding such structures. The benefits are measured here with travel times. The desired structures are sought with an evolutionary algorithm. It is shown on an academic example how the results vary and how the conclusions, relevant for practical purposes, can be drawn from such analyses, done with the methods here presented.

Słowa kluczowe

EN

transport; transport systems; graphs; hub and spoke; evolutionary algorithm; time-wise profitability

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2018
• Tom: Vol. 47, no. 2
• Strony: 173--189
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Mazbic-Kulma B.

• Faculty of Computer Science, Warsaw School of Information Technology ul. Newelska 6, 01-447 Warsaw, Poland

autor

Owsinski J. W.

• Faculty of Computer Science, Warsaw School of Information Technology ul. Newelska 6, 01-447 Warsaw, Poland
• Systems Research Institute, Polish Academy of Sciences ul. Newelska 6, 01-447 Warsaw, Poland

autor

Barski A.

• Faculty of Computer Science, Warsaw School of Information Technology ul. Newelska 6, 01-447 Warsaw, Poland
• Systems Research Institute, Polish Academy of Sciences ul. Newelska 6, 01-447 Warsaw, Poland

autor

Sęp K.

• Faculty of Computer Science, Warsaw School of Information Technology ul. Newelska 6, 01-447 Warsaw, Poland
• Systems Research Institute, Polish Academy of Sciences ul. Newelska 6, 01-447 Warsaw, Poland

autor

Stańczak J.

• Faculty of Computer Science, Warsaw School of Information Technology ul. Newelska 6, 01-447 Warsaw, Poland
• Systems Research Institute, Polish Academy of Sciences ul. Newelska 6, 01-447 Warsaw, Poland

Bibliografia

• [1] Brunato, M., Hoos, H., Battiti, R. (2008) On effectively finding maximal quasi-cliques in graphs. In: V. Maniezzo, R. Battiti, J. Watson, (Eds.), Proc. 2nd Learning and Intelligent Optimization Workshop, LION 2, LNCS, 5313. Springer Verlag.
• [2] Campbell, J.F., O’Kelly, M. (2012) Twenty-Five Years of Hub Location Research. Transportation Science, 46(2), 153–169.
• [3] Cetiner, S., Sepil, C., Sural, H. (2010) Hubbing and routing in postal delivery systems. Annals of Operations Research, 181, 109–124.
• [4] Chen, Z.-Q., Wang, R.-L., Okazaki, K. (2008) An Efficient Genetic Algorithm Based Approach for the Minimum Graph Bisection Problem. IJCSNS Int. Journal of Computer Science and Network Security, 8, 6, 118 – 124.
• [5] Cormen, T., Leiserson C., Rivest R., Stein. C. (2009) Introduction to Algorithms. MIT. Cowen, L. (1998) Approximation Algorithms. Johns Hopkins University.
• [6] Coyle, J.J., Bardi E.J, Novack R.A. (1994) Transportation. Fourth Edition, New York: West Publishing Company.
• [7] Eghbali Zarch M., Abedzadeh M. and Setak M. (2013) Differential evolution algorithm for multi-commodity and multi-level of service hub covering location problem. International Journal of Industrial Engineering Computations, 4, 127–138.
• [8] O’Kelly, M. (1987) A quadratic integer program for the location of interacting hub facilities. European Journal of Operation Research, 32, 392-404.
• [9] O’Kelly, M., Bryan D. (2002) Interfacility interaction in models of hubs and spoke networks. Journal of Regional Science, 42(1), 145-165.
• [10] Klincewicz, J.G. (1998) Hub location in backbone/tributary network design: a review. Location Science, 6, 307-335.
• [11] Marchiori, E. (1998) A Simple Heuristic Based Genetic Algorithm for the Maximum Clique Problem. Proceedings of the 1998 ACM Symposium on Applied Computing, 366-373.
• [12] Mazbic- Kulma, B., Potrzebowski, H., Stanczak, J., Sep, K., (2008) Evolutionary approach to solve hub-and-spoke problem using α-cliques. Evolutionary Computation and Global Optimization, Prace nauk. PW, Warszawa, 121–130.
• [13] Michalewicz, Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, Berlin-Heidelberg.
• [14] Moscato, P. (1989) On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Caltech Concurrent Computation Program (Report 826).
• [15] Pattillo J., Youssef N., Butenko S. (2013) On clique relaxation models in network analysis. European Journal of Operational Research, 226, 9-18.
• [16] Potrzebowski H., Stanczak J., Sep K. (2007) Separable decomposition of graph using α-cliques. In: M. Kurzynski, E. Puchal a , M. Wozniak, A. ˙ Zolnierek, (Eds.) Computer recognition systems 2. In: Advances in Soft Computing, Springer, Berlin-Heidelberg, 386-393.
• [17] Potrzebowski, H., Stanczak, J., Sep, K. Evolutionary approach to solve hub-and-spoke problem using α-cliques. 2008. Evolutionary Computation and Global Optimization, Prace naukowe PW, Warszawa, pp. 121-130.
• [18] Seidman, S. B. (1978) A graph-theoretic generalization of the clique concept. J. Mathematical Sociology, 6, 139-154 Gordon and Breach Science Publishers, Ltd.
• [19] Stanczak, J. (2003) Biologically inspired methods for control of evolutionary algorithms. Control and Cybernetics, 32(2), 411–433.
• [20] Stanczak, J., Potrzebowski, H., Se¸p, K. (2011) Evolutionary approach to obtain graph covering by densely connected subgraphs. Control and Cybernetics, 41, 3, 80–107.
• [21] Sutton, R.S., Barto, A.G. (1998) Reinforcement Learning: An Introduction. MIT Press.
• [22] Talbi, E.-G, Bessiere, P. (1991) A parallel genetic algorithm for the graph partitioning problem. Proceedings of the 5th International Conference on Supercomputing, ACM. NY. 312–320.
• [23] Wilson, R.J. (1996) Introduction to Graph Theory Addison Wesley Longman.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).