A Hierarchical Flow Capturing Location Problem with Demand Attraction Based on Facility Size, and Its Lagrangian Relaxation Solution Method

This article presents a hierarchical flow capturing location problem (HFCLP) and proposes an effective Lagrangian heuristic solution method. The original flow capturing location problem (FCLP) aims to locate a given number of facilities on a network to maximize the total flow that can be serviced at facilities along their preplanned routes, such as daily commute to work. We extend the original model to allow a decision maker to select the size of facilities among m different size alternatives. Larger facilities are assumed to be more attractive and, therefore, can attract more customers, but they cost more to construct than smaller ones. Customers deviate from their preplanned routes to access a facility's service when the size of the facility is sufficiently large. The degree of deviation from the original path is measured by the additional distance customers have to go to access facilities, and the acceptable deviation distance becomes larger as the size of a facility increases. This article presents a new problem in which the number of facilities of each size and their locations are simultaneously determined so as to capture as much flow as possible within the total budget available for locating all facilities. We present an integer programming formulation of the problem and devise a Lagrangian relaxation solution method. The proposed algorithm is tested using road networks with 300 and 500 nodes. The results show that the method produces high-quality solutions in a fairly short time.