【作者】 杨珺；

【导师】 杨超；

【作者基本信息】 华中科技大学 ， 管理科学与工程， 2005， 博士

【摘要】 设施的选址问题是在运筹学和管理科学领域普遍存在的决策问题。设施选址问题是研究如何选择设施的数目和最优位置来为用户提供相应的服务。选址决策正确与否主要取决于选址决策后能否带来经济利益、效用、个人或社会的满足以及社会价值等。本文将着重考虑服务对象为行走在日常路线上的顾客流(交通流、顾客流、信息流和水流等)的这类服务设施的选址-截流问题。本文在国内外关于网络服务设施选址布局优化理论研究现状及发展的基础上,系统地论述了作者对网络服务设施的截流-选址问题的研究成果。第一章首先介绍选题的依据,从交通、通讯、零售和物流等方面分析了该研究的背景动机,提出本文研究的主要问题—网络设施截流-选址问题(FLPFI),最后提出本文的主要研究目标和内容。第二章本章首先从静态确定型、动态型、随机型和竞争型四个方面对传统选址问题的研究现状进行评述。在传统选址问题的基础上,介绍了本文的研究核心问题:顾客流量产生于网络道路的服务设施截流-选址问题(FLPFI)的基本模型和研究现状。最后对本文将要应用的四种启发式算法:贪婪算法、局部搜索算法、禁忌算法和蚂蚁算法的基本原理和步骤作了详细的介绍。第三章研究合作型FLPFI(CFLPFI)的三个扩展问题:设施带双重容量限制的CFLPFI 问题、带危险度瓶颈限制的CFLPFI 问题和和带时间约束的CFLPFI 问题。设施带双重容量限制的CFLPFI 问题是考虑了设立在网络的边上设施的满足建站最小服务量和最大服务容量的CFLPFI 问题,文中建立了该问题的混合整数规划模型,给出了基于贪婪的启发式算法。带危险度瓶颈限制的CFLPFI 问题是考虑了网络上路段的危险度的一个起点和多个讫点CFLPFI 问题。文中建立了该问题的整数规划模型,给出了计算复杂度是O ( m0 t 2 n 3)的多项式时间算法,并给出了具体算例。最后,本章研究了考虑需求流量(货物)的价格-时间函数的CFLPFI 问题,建立了该问题的混合整数规划模型,将该问题转化为传统的CFCLP 问题来解决。第四章研究了独立型FLPFI(IFLPFI)的两个扩展问题:两种不同设施选址的mn-IFLPFI 问题和考虑设施服务半径的IFLPFI 问题。mn-IFLPFI 问题是考虑了在市场需求细分的条件下,两种提供不同服务的设施的IFLPFI 问题,文中建立了该问题的更多还原

【Abstract】 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.更多还原