Facility Location Problems About Flow Interception In Network

Facility location problem is the pervasive decision problem in the field of management science. This problem is to decide to choose the optimal location strategy to serve the customers in the network. The location strategy lies on its economic profit, personal or social satisfaction and social value. This article focuses on the Facility Location Problem about Flow Interception (FLPFI), which analyze the location of facilities capturing by-passing customer flows (traffic flows, data flows and water flows etc). Therefore, this thesis presents and discusses my research and application fruit of facility location problem about flow interception based on the theory of this field. Firstly, the article introduces the reasons of choosing this topic, analysis background and motivation from several fields such as transportation, communication, retail trade and logistics. It proposes the main problem —Facility Location Problem about Flow Interception (FLPFI), then introduces the research route and structure of the paper. Secondly, the article summarizes the theories on traditional facility location problem, which is organized into four categories: deterministic models, dynamic models, stochastic models and competitive models. Based on traditional location problem, it introduces the basic model of FLPFI and research background. Then four heuristic algorithms: Greedy, neighborhood search, Tabu search and Ant system are presented in detail. Thirdly, three extended Cooperative-FLPFI problem are studied. The CFLPFI with double service capacities considers the minimum capacity for guarantee profit and the maximum service capacity. The mixed-integral model and heuristic based on greedy algorithm are proposed. The CFLPFI with risk bottleneck limitation with one origin and multi-destinations is considered with objection of minimizing the total cost for setting up facilities as well as an additional security cost. This paper formulates this integral model of this problem and proposes the polynomial algorithm based on the post-order traversal substitute algorithm. The CFLPFI with travel time constraints considers the commodity price –time function. It can be tansformed to Capacitated Fixed Charge Facility Location Problem by virtual network. Fourthly, two extended Independent-FLPFI problem are studied. The mn—IFLPFI that is to determine the locations of type A facilities and type B facilities on the network in order that the sum of the intercepted flows are maximum. The mn-IFLPFI as a binary integer program is formulated and heuristic algorithm is presented. Then, this paper proposes the IFLPFI with service radius. Hence, a hybrid IFLPFI-MCLM with dedicated-trip demand service radius D and by-passing flow demand service radius d is proposed. A heuristic greedy algorithm as well as several variants of an ascent search and of a tabu search is developed to solve the example network. Fifthly, the stochastic FLPFI models are proposed. The FLPFI with intercepted probability we posed is a new problem to determine the minimum cost and locations of survey station on the network in order that the intercepted probability of O ? D pair is αat least. A binary integer programming formulation for this problem is constructed. Heuristic greedy algorithm and the results of computational experiments are presented. Then, the FLPFI models with uncertain demand in several scenarios are proposed, corresponding to the MAXMIN and REGRET approaches respectively. A heuristic method based on Teitz and Bart substitution algorithm is developed. Computational experiments are described and compared with the results using the branch and bound. Sixthly, we introduce the gravity model with random functions, which reflect the customers'choice behavior. It concerns four effective factors: captured market, consumptions, distance between demand and facility and facility attractiveness. This paper studies competitive models of FLPFI from three facts: regional limitation, chance limitation with random demands and linear bounded expenditures that is proportional to total utility of same path. Ant systems and greedy algorithm are developed. The experiment results given show the advantages of the above algorithm. Finally, this article concludes the main content, innovated points and presents a prospect on further studies.