Issue: 2013/Vol.23/No.2, Pages 91-105
THE KERNEL AND SHELL STRUCTURE AS A TOOL FOR IMPROVING THE GRAPH OF TRANSPORTATION CONNECTIONS
Barbara Mażbic-Kulma
, Jan W. Owsiński, Krzysztof Sęp, Jarosław Stańczak
Cite as: B. Mażbic-Kulma, J. W. Owsiński, K. Sęp, J. Stańczak. The kernel and shell structure as a tool for improving the graph of transportation connections. Operations Research and Decisions 2013: 23(2), 91-105. DOI 10.5277/ord130208
Abstract
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.
Keywords: transport, connections graph, hub and spoke, kernel and shell, α-clique, genetic algorithm
Received: Accepted: