Location of facilities on a network subject to a single‐edge failure

Networks - Tập 22 Số 3 - Trang 231-246 - 1992
H. A. Eiselt1, Michel Gendreau2, Gilbert Laporte2
1Faculty of Administration, University of New Brunswick, P.O. Box 4400, Fredericton, New Brunswick, Canada E3B 5A3
2Centre de recherche sur les transports, Université de Montréal, C.P. 6128, Succursale A, Montréal, Canada H3C 3J7

Tóm tắt

AbstractIn this work, the following location problem is analyzed. Let N = (V,E) be an undirected connected simple network, where V is the vertex set, |V| = n and E is the edge set. There is a nonnegative demand wj associated with every vertex uj. It is assumed that every edge (ui,uj) has a probability of failure pij and that failures can never occur on two edges simultaneously. The problem consists of locating p facilities on the network so that the total expected demand disconnected from the facilities is minimized. This problem occurs naturally in the fields of computer and telecommunications networks. A number of important results are proved. First, there always exists a solution in which all facilities are located at vertices. Second, the problem can always be solved optimally on the so‐called leaf‐tree associated with the network. Third, when p = 1, the problem is a 1‐median problem. When p > 1, there always exists an optimal solution for which all facilities are located at pendent vertices of the tree. Finally, when p > 2, the problem with p + 1 facilities can be solved in a greedy fashion, starting from a solution to the problem with p facilities. An exact algorithm for this problem is described. It can be executed in either O(np + |E|) time or in O(n log n + |E|) time. A numerical example is provided.

Từ khóa


Tài liệu tham khảo

Berman O., 1990, Discrete Location Theory, 503

10.1287/opre.33.4.746

Boffey T. B., 1991, Computer network design problems

10.1287/mnsc.35.6.645

10.1287/opre.38.6.1034

Carré B., 1979, Graphs and Networks

10.1016/0305-0548(86)90072-9

10.1287/mnsc.31.6.764

Drezner Z., 1985, Location of unreliable facilities

10.1287/opre.14.3.409

10.1287/trsc.5.2.212

10.1287/opre.12.3.450

10.1137/0137041

Louvaux F. V., 1986, Location Decisions: Methodology and Applications, 23

10.1016/0167-6377(85)90020-3

Mirchandani P. B., 1990, Discrete Location Theory, 55

10.1287/trsc.13.2.85

Nel L. D., 1990, Locating a broadcast facility in an unreliable network, INFOR, 28, 363

10.1016/0377-2217(89)90272-5

ReVelle C., 1989, Facility Location Analysis: Theory and Applications, 155

10.1109/26.103044

10.1016/0020-0190(74)90003-9

10.1287/trsc.17.2.168

Thông tin
Thông tin xuất bản

Networks

Tập 22 Số 3

231-246

Thông tin tác giả