Loading...
Please wait, while we are loading the content...
Similar Documents
O Problema De Localização De Concentradores Em Árvores: Um Procedimento Para Acelerar Um Algoritmo Baseado Em Decomposição De Benders
| Content Provider | Semantic Scholar |
|---|---|
| Author | Noronha, Thiago F. Santos, Andréa C. |
| Copyright Year | 2015 |
| Abstract | Given a directed complete graph G = (N,E), where N is the set of nodes and E is the set of arcs. Let Wij ∈ R be the flow demand of node i ∈ N to node j ∈ N , cij be the cost of routing every flow unit in an arc (i, j) ∈ E and p be a positive integer. The Tree of Hubs Location Problem consists in selecting a set of P ⊂ N with p nodes, called of Hubs, and connect them by means of a tree. In addition, each node N\P is set to a single node belonging to P in such a way that there is a single path among any pair of nodes i, j ∈ G and the total cost to route all the demands Wij is minimized. The routing cost for every flow unit passing though Hubs receives a discount α given by cij × α . The state-of-the-art of algorithms for this problem is able to solve instances with up to 100 nodes in a high computational time, using a Benders decomposition. This is due to the fact that O(|N |2) subproblems have to be solved at each iteration. In this study, an ad-hoc algorithm to solve O(|N |2) subproblems is proposed. Thus, the computational time of the Benders decomposition algorithm for THLP is speed up. Preliminary results indicate that about 28% of running time is saved. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://cdsid.org.br/sbpo2015/wp-content/uploads/2015/08/142870.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
