带约束多设施选址分配模型与基于变分不等式的启发式算法  

A variational inequality heuristic algorithm for a constrained multi-source location-allocation model

作　　者：蒋建林[1] 程坤[1] 

机构地区：[1]南京航空航天大学理学院,江苏南京210016

出　　处：《江苏师范大学学报（自然科学版）》2014年第1期47-52,共6页Journal of Jiangsu Normal University：Natural Science Edition

基　　金：国家自然科学基金资助项目(11101211);江苏省自然科学基金资助项目(BK2011719);第46批留学回国人员科研启动基金资助项目;中央高校基本科研业务费专项资金资助项目(NZ2012306)

摘　　要：设施选址问题在生活、物流、军事中有着非常广泛的应用.主要考虑设施有约束限制以及设施间存在相互运输的情形,提出一个约束多设施选址模型.目标是在平面上的约束区域内选择多个设施,使得这些设施到各个需求点以及各个设施间的距离和最小.提出了基于变分不等式方法的交替选址-分配启发式算法解决此模型:在分配步,采用最近中心再分配算法将顾客分配给设施;在选址步,先将子问题转化为等价的变分不等式问题,再用投影收缩方法求解相应的变分不等式问题.分析了问题及算法的一些性质,并给出了数值试验,证明了算法的有效性.Facility location problems have practical applications in various fields such as life,supply chain manage-ment,and military.In this paper,a constrained multi-source model is built,considering the locational constraints on facilities and the transportation costs between facilities.The objective is to locate new facilities in some constrain-ed areas such that the sum of the distances between facilities and customers and the distance between these facilities is minimized.Based on variational inequality,an alternative location-allocation heuristic algorithm is proposed to solve this constrained location model.In the allocation phase,all customers are allocated to facilities by the nearest center reclassification algorithm,and in the location phase,the subproblem is transformed into an equivalent linear variational inequality（LVI）problem.Then a projection-contraction method is adopted to solve this LVI problem. Several properties about the proposed model and algorithm are analyzed,and some preliminary numerical results are reported which verifies the effectiveness of this algorithm.

关 键 词：设施选址 交替选址 分配 最近中心再分配 变分不等式 

分 类 号：O221[理学—运筹学与控制论] U116[理学—数学]