Two-level Network Design With Intermediate Facilities: An Application To Electrical Distribution Systems

We consider the two-level network design problem with intermediate facilities. This problem consists of designing a minimum cost network respecting some requirements, usually described in terms of the network topology or in terms of a desired flow of commodities between source and destination vertices. Each selected link must receive one of two types of edge facilities and the connection of different edge facilities requires a costly and capacitated vertex facility. We propose a hybrid decomposition approach which heuristically obtains tentative solutions for the vertex facilities number and location and use these solutions to limit the computational burden of a branch-and-cut algorithm. We test our method on instances of the power system secondary distribution network design problem. The results show that the method is efficient both in terms of solution quality and computational times. © 2010 Elsevier Ltd.

Gavish, B., Topological design of telecommunications networks-local access design methods (1991) Annals of Operations Research, 33, pp. 17-71

Mateus, G.R., Cruz, F.R.B., Luna, H.P.L., An algorithm for hierarchical network design (1994) Location Science, 2, pp. 149-164

Gouveia, L., Lopes, M.J., Using generalized capacitated trees for designing the topology of local access networks (1997) Telecommunications Systems, 7, pp. 315-337

de Jongh, A., Gendreau, M., Labbe, M., Finding disjoint routes in telecommunications networks with two technologies (1999) Operations Research, 47, pp. 81-92

Patterson, R.A., Rolland, E., Hybrid fiber coaxial network design (2002) Operations Research, 50, pp. 538-551

Yaman, H., Carello, G., Solving the hub location problem with modular link capacities (2005) Computers & Operations Research, 32, pp. 3227-3245

Pirkul, H., Narasinham, S., Locating concentrators for primary and secondary coverage in a computer communication network (1988) IEEE Transactions on Communications, 36, pp. 450-458

Pióro, M., Medhi, D., (2004) Routing, flow and capacity design in communication and computer networks, , Morgan Kaufmann, San Francisco

Ignacio, A.A.V., Ferreira Filho, V.J., Galvão, R.D., Lower and upper bounds for a two-level hierarchical location problem in computer networks (2008) Computers & Operations Research, 35, pp. 1982-1998

Fleischmann, M., Bloemhof-Ruwaard, J.M., Dekker, R., van der Laan, E., van Nunen, J.A.E.E., Wassenhove, L.N.V., Quantitative models for reverse logistics: a review (1997) European Journal of Operational Research, 103, pp. 1-17

Srivastava, S.K., Network design for reverse logistics (2008) Omega, 36, pp. 535-548

Gupta, R., Pirkul, H., Hybrid fiber co-axial CATV network design with variable capacity optical network units (2000) European Journal of Operational Research, 123, pp. 73-85

Gouveia, L., Janssen, E., Designing reliable tree networks with two cable technologies (1998) European Journal of Operational Research, 105, pp. 552-568

Lee, K., Park, K., Park, S., Design of capacitated networks with tree configurations (1996) Telecommunications Systems, 6, pp. 1-19

Balakrishnan, A., Magnanti, T.L., Mirchandani, P., Modeling and heuristic worst-case performance analysis of the two-level network design problem (1994) Management Science, 40, pp. 846-867

Daskin, M.S., (1995) Network and discrete location: models, algorithms, and applications, , Wiley, New York

Sahin, G., Süral, H., A survey of hierarchical facility location models (2007) Computers & Operations Research, 34, pp. 2310-2331

Toth, P., Vigo, D., The granular tabu search and its application to the vehicle-routing problem (2003) INFORMS Journal on Computing, 15, pp. 333-346

Carneiro, M.S., França, P.M., Silveira, P.D., Long-range planning of power distribution systems secondary networks (1996) Computers & Electrical Engineering, 22, pp. 179-191

Aoki, K., Nara, K., Satoh, T., Kitagawa, M., Yamanaka, K., New approximate optimization method for distribution system planning (1990) IEEE Transactions on Power Systems, 5, pp. 126-132

Diaz-Dorado, E., Miguez, E., Cidras, J., Design of large rural low-voltage networks using dynamic programming optimization (2001) IEEE Transactions on Power Systems, 16 (4), pp. 898-903

Diaz-Dorado, E., Pidre, J., Garcia, E., Planning of large rural low-voltage networks using evolution strategies (2003) IEEE Transactions on Power Systems, 18 (4), pp. 1594-1600

Cossi, A.M., Romero, R., Mantovani, J.R.S., Planning of secondary distribution circuits through evolutionary algorithms (2005) IEEE Transactions on Power Delivery, 20, pp. 205-213

Senne, E.L.F., Lorena, L.A.N., Lagrangean/surrogate heuristics for p-median problems (2000) Computing tools for modeling, optimization and simulation: interfaces in computer science and operations research, pp. 115-30. , Dordrecht: Kluwer;

Fisher, M.L., The Lagrangian relaxation method for solving integer programing problems (2004) Management Science, 50, pp. 1861-1871

Aneja, Y.P., An integer linear programming approach to Steiner problems in graphs (1980) Networks, 10, pp. 167-178

Subjects

Show full item record