مدل برنامه ریزی سطح دو جهته و الگوریتم ژنتیک ترکیبی برای مشکل رهگیری جریان همراه با انتخاب مشتری

This paper investigates how to optimize the facility location strategy such as to maximize the intercepted customer flow, while accounting for “flow-by” customers’ path choice behaviors and their travel cost limitation. A bi-level programming static model is constructed for this problem. An heuristic based on a greedy search is designed to solve it. Consequently, we proposed a chance constrained bi-level model with stochastic flow and fuzzy trip cost threshold level. For solving this uncertain model more efficiently, we integrate the simplex method, genetic algorithm, stochastic simulation and fuzzy simulation to design a hybrid intelligent algorithm. Some examples are generated randomly to illustrate the performance and the effectiveness of the proposed algorithms.

Traditional location–allocation models, such as the maximal covering location model (MCLM) and the pp-median model, aim to locate network facilities to optimally serve demand expressed as weights at nodes [1], [2], [3] and [4]. Nowadays, many customers purchase services as part of routine pre-planned trips, i.e., the daily commute to and from home and the workplace, instead of making a special-purpose trip to obtain a service. Such facilities include convenience stores, gas stations, ATM machines, drugstores, laundries and restaurants. Thus, as the purchasing behavior changes, there are cases where demand in a network is now expressed as flows, rather than nodes. To solve these types of facility locations in a network where demand is not expressed at nodes, but is exerted by traffic flowing between origins and destinations, Hodgson [5] and Berman [6] presents the flow interception problem (FIP) and developed a heuristic greedy algorithm to solve the FIP. The basic problem of FIP [5] and [6] is to locate mm facilities to intercept as much flow as possible from a given set of pre-existing flows on the network. It assumes the “interception” occurs if a flow passes through at least one facility. The focus is on maximizing the total consumption of the service by “flow-by” customers traveling on preplanned paths (e.g. daily commute). Based on the basic FIP,they also published a series of studies for a class of FIP [7], [8] and [9]. During the last two decades, uncertainty theory has experienced spectacular growth and is a hotspot in location science. The present papers recognize uncertainty in the demand or population at the nodes of the network or the different travel time between the nodes, which depend on the time of the day or day of the week. Uncertainty theory has been considered in the traditional location models (PP-median, center problem, set-covering problem) [10], [11], [12] and [13]. In these FIP modes above, “flow-by” customers which are static only travel on preplanned paths. Nowadays some probabilistic models of locating flow-capturing facilities are investigated [14], [15] and [16]. In the probabilistic models, pre-planned paths are not known and only information on the fractions of customers traveling from any node to any adjacent node(transition probabilities) and the initial distribution of customers among nodes is available.Then the theory of Markov decision processes is applied for the analysis [14]. According to the relationship between customers and facilities, J. Yang categorizes the flow interception problem into three types: cooperative FIP, independent FIP and opposite FIP [17]. In independent FIP, for facility managers, the objective function is to maximize the intercepted “flow-by” customers; but from the “flow-by” customers perspective, they are concerned with two factors for choosing the paths from their origin to their destination. On one hand, they desire to obtain services from facilities on their trip. On the other hand, the expected trip cost (travel time) cannot be above the threshold level that they can bear. This problem can be described within a game theoretic framework as leader–follower or Stackelberg game [18]. Thus, a bi-level model for this problem is formulated in this paper. Due to the NP-hardness of bi-level programming problem [19], a number of authors proposed various exact algorithms for solving it [20], [21] and [22]. As for researches on computational methods using meta-heuristics for bi-level programming problem, Liu designed a genetic algorithm for solving a Stackelber–Nash equilibrium of nonlinear multilevel programming with multiple followers in which there might be information exchange among the followers [23]. Gendreau, Marcotte and Savard proposed an adaptive search method related to the Tabu Search meta-heuristic to solve the linear bi-level programming problem [24]. Li, Tian and Min developed a new algorithm framework based on particle swarm optimization for solving general bi-level programming problem, which combines two variants of PSO to solve the upper-level and lower-level programming problems interactively and cooperatively [25]. Takeshi and Hideki formulated defensive location problem as bi-level zero-one programming problems and proposed an algorithm based upon tabu search methods [26]. In this paper, we investigate how to optimize the facility location strategy such as to maximize the intercepted customer flow, while accounting for “flow-by” customers’ path choice behaviors and their travel cost limitation. The purpose of this paper is to develop a bi-level model for this problem and to design meta-heuristic algorithms to solve it. The rest of the paper is organized as follows. In Section 2, the problem and symbols used are introduced. And we construct a bi-level programming static model for this problem. A heuristic based on a greedy search is designed to solve this model in Section 3. In Section 4, we suppose customers of OD pairs be stochastic variables. And the customers in general choose their paths in order to obtain service as conveniently as possible, while satisfying the trip cost threshold level which is a fuzzy variable. Thus,on the basis of credibility measure, a bi-level chance constrained model for FIP is developed. For solving this model more efficiently, we integrate the simplex method, genetic algorithm, stochastic simulation and fuzzy simulation to design a powerful hybrid intelligent algorithm in Section 5. Finally, Section 6 provides some numerical examples generated randomly to illustrate the performance and the effectiveness of the proposed algorithm.

In this paper, the facility location problem with customers’ path choice is presented. We need to located mm facilities in order to maximize the intercepted customers, while accounting for “flow-by” customers’ preferences and their travel cost threshold. This problem is defined as a bi-level programming static model. Consequently, a heuristic based on a greedy search is designed to solve it. Due to the co-existence of randomness and fuzziness in the real world, we propose a chance constrained bi-level model with stochastic flow and fuzzy trip cost threshold level. For solving this bi-level uncertain model more efficiently, the simplex method, genetic algorithm, stochastic simulation and fuzzy simulation are integrated to design a hybrid intelligent algorithm. Some numerical examples are generated randomly to illustrate the performance and the effectiveness of the proposed algorithms. This modeling work focuses on game theory between the network planner and users. Future research should expand the model frame work to capacitated facilities, set-up cost of facilities and expected losses of users.