Keywords: resource allocation, optimization, clustering, complex networks, granular computing, systems approach.

Most problems in engineering imply resource allocation at least from an economic perspective. Amongst a wide range of applications, this paper deals with the specific problem of allocating resources to satisfy a physically distributed demand; such a problem includes the installation and operation of facilities to supply goods and, or services. In this sense, there is a high dependence on the available infrastructure systems, e.g. transportation networks.

Complex systems, such as infrastructure networks, consist of many nonlinearly related components, making conceptual and computational tasks very difficult. Commonly, optimization problems on such networks lead to NP complexity and become intractable using exact methods. The proposed strategy is based on a systems thinking [1] approach that seeks to unravel the network's structure and properties by successively decomposing it into subsystems in the form of a hierarchy. This approach includes a granular view of infrastructure networks, the use of clustering algorithms to decompose networks [2] and optimization methods to perform a hierarchy-based resource allocation process.

Granular computing [3] is based on the fact that humans perceive the world in several levels of abstraction and all knowledge-related functions are performed accordingly. Granular computing is included as a conceptual framework to work with multi-level units representing infrastructure networks.

Clustering is an unsupervised learning method that deals with pattern recognition [4]. In the case of networks, clustering algorithms seek to find the best way in which the network is divided into k sub-networks. Successive clustering methods are applied to infrastructure networks in order to obtain hierarchical representations of them.

The objective of this paper is to explore and apply computational tools to support the granular approach to the stated resource allocation problem. Particularly, a novel formulation for resource allocation is presented, which includes constraints that result from the hierarchical decomposition of the infrastructure network and whose objective function is expressed in terms of granules (i.e. clusters) rather than actual network nodes.

The results include a significant reduction of the execution time of the optimization problem and a network that responds to network intrinsic structure (e.g. connectivity). The latter is due to the fact that the formulated objective function reduces the number of variables, whereas the additional constraints reduce the search space (i.e. feasible region), based on the multi-level clustering.

1

P.B. Checkland, "Systems thinking, systems practice", John Wiley and Sons, Chichester, UK, 1981.

2

C. Gómez, M. Sánchez-Silva, L. Dueñas Osorio, D. Rosowsky, "Hierarchical infrastructure network representation methods for risk-based decision-making ", Structure and Infrastructure Engineering: Maintenance, Management, Life-Cycle Design and Performance, 2011. doi:10.1080/15732479.2010.546415

3

Yiyu Yao, "Granular computing: Past, present and future", IEEE International Conference on Granular Computing, GrC 2008, 80-85, 2008. doi:10.1109/GRC.2008.4664800

4

M. Filippone, F. Camastra, F. Masulli, S. Rovetta, "A survey of kernel and spectral methods for clustering", Pattern recognition, Jan 2008. doi:10.1016/j.patcog.2007.05.018

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £70 +P&P)