The set covering problem is to find the minimum cardinality set of locations to site the facilities which cover all of the demand points in the network. In this classical problem, it is assumed that the potential facility locations and the demand points are limited to the set of vertices. Although this problem has some applications, there are some covering problems in which the facilities can be located along the edges and the demand exists on the edges, too. For instance, in the public service environment the demand (population) is distributed along the streets. In addition, in many applications (like bus stops), the facilities are not limited to be located at the vertices (intersections), rather they are allowed to be located along the edges (streets). For the first time, this paper develops a novel integer programming formulation for the set covering problem wherein the demand and facility locations lie continuously along the edges. In order to find good solutions in a reasonable time, a matheuristic algorithm is developed which iteratively adds dummy vertices along the edges and solves a simpler problem which does not allow non-nodal facility locations. Finally, a Benders decomposition reformulation of the problem is developed and the lower bounds generated by the Benders algorithm are used to evaluate the quality of the heuristic solutions. Numerical results show that the Benders lower bounds are tight and the matheuristic algorithm generates good quality solutions in short time.

This article presents a broad review of Hub location problem (HLP), and its applications. The goal of this article is to provide a review on the newest and most recent publications on Hub location and its application in real world practices since 2013. While, there are some articles which reviewed hub location problem literature but some models were not covered in those articles. In this paper, we try to include capacitated models. We survey advances in analysis and modeling of the hub location problem including its variants and solution algorithm of HLPs. We emphasize the most applicable areas for Marine Transpiration. We show that first, majority of the articles consider network domain, while there are some articles which execute HLP in discrete and continuous domain. Also, the capacitated case attracts more attention in recent years. Finally, the contribution of any type of HLP in the literature is shown schematically.