دانلود رایگان مقاله مساله مکان پوشش حداکثر در شبکه هایی با تقاضای منطقه ای

abstract

Covering problems are well studied in the Operations Research literature under the assumption that both the set of users and the set of potential facilities are finite. In this paper, we address the following variant, which leads to a Mixed Integer Nonlinear Program (MINLP): locations of p facilities are sought along the edges of a network so that the expected demand covered is maximized, where demand is continuously distributed along the edges. This MINLP has a combinatorial part (which edges of the network are chosen to contain facilities) and a continuous global optimization part (once the edges are chosen, which are the optimal locations within such edges).

5 Conclusions

In this paper we have studied a covering location problem on networks which, contrary to those already in the literature, assumes the demand distributed along the edges of the network, which is a more realistic assumption for problems with networks representing high-density regions, such as cities. The problem is a challenging MINLP, in which combinatorial decisions (which edges of the network are to be selected to contain facilities) are coupled with continuous decisions (where to locate the facilities once the edges are chosen). A branch-and-bound algorithm has been developed for this MINLP. While some ingredients of such branch and bound are standard, the branching procedure is rather specific, since it successfully exploits the fact that the locational decisions are taken on a network. Different bounding rules are proposed and tested on different networks; it is shown that the so-called Smart strategy, which through a learning process, is identifying for each branch-andbound node the most promising branching strategy, is the most promising in terms of running times.