基于需求多元化的网络设施选址问题研究

项目名称： 基于需求多元化的网络设施选址问题研究

项目编号： No.70871044

项目类型： 面上项目

立项/批准年度： 2009

项目学科： 电工技术

项目作者： 杨超

作者单位： 华中科技大学

项目金额： 24万元

中文摘要： 本项目基于现有网络服务设施选址问题的研究现状，提出了一类考虑用户需求与服务种类多元化条件下基于成本效益均衡优化的服务设施选址问题。当前的服务设施选址模型中一般假定给定服务设施的数目或建设成本，如何确定服务设施选址或用户流路线选择，使得服务设施能够服务的用户流最大。而实际问题中由于服务设施通常具有不同的规模和等级，相应的采购和建设成本也不同，并且决策者不能事先确定服务设施的数目，这就要求将建立服务设施的类型与服务收益进行综合考虑以达到成本效益的最优均衡。所以我们提出了一个收益最大和总的建设成本最小双目标多元需求截流选址模型，具体表述如下：令网络图G(V,A)和一系列路径集合P，其中V是G(V,A)中所有节点集合，A是路径P上所有边或者弧的集合，Vp为路径p上的节点，S表示网络上可以提供的所有服务，fsp表示路径p上需求服务s的流量，rs表示s设施截得单位流量可获得的收益。问题研究目标是确定网络中的最优设施以及服务类型，使得总的收益最大，并且总的建设成本最小。我们正对此模型设计了相应的求解算法，并在该模型的基础上考虑了一些更现实的相关模型，最后，我们在理论研究的基础上进行了一系列实证研究。

中文关键词： 设施选址；多元需求；成本-收益均衡；算法

英文摘要： In this research, we studied a cost-benefit trade-off facility location problem with the consideration of the customers' multi-demand and serviece facilities' multi-type, which was based on the research status of the current facility location problem. In general, the traditonal facility location models all assumed that the number of facilities to be consturacted or the total construction cost was given in advance, and the problem is to determine the location of service facilities or the customer flows to maximize the caputred customer flows.In fact, in reality the service facility usually have different scales and ranks, and the corresponding construction costs are different. As the decision- maker cannot determine the exact facility number to be consturcted in advance, it is necessary to integrate the the facility types and service benefit to achieve optimmal cost-benefit trade-off. Therefore, we proposed a a bi-objective multi-demand FIP model of the following type: given a network graph G(V,A) and s series sets of routines P, where V is the set of nodes in G(V,A), A is the set of edges or archs in routine P, Vp is the set of nodes in routine p, S is the set of possible service that can be provided in the network, fsp denotes the flow of service s in routine p, rs denotes the benefit from captured unit flow. The goal is to find the optimal location of facilities and service type in the network to maximize the total benefit and minimize the construction cost.We studied algorithms for this problem. In addition, we discussed some more practical variation of this model under some other conditions. Furthermore, we did some empirical studies based on the above theoretical researches.

英文关键词： facility location; multi-demand; cost-benefit trade-off; algorithm