Multicriteria Semi-Obnoxious Network Location Problems (MSNLP) with Sum and Center Objectives

Locating a facility is often modeled as either the maxisum or the minisum problem, reflecting whether the facility is undesirable (obnoxious) or desirable. But many facilities are both desirable and undesirable at the same time, e.g., an airport. This can be modeled as a multicriteria network location problem, where some of the sum-objectives are maximized (push effect) and some of the sum-objectives are minimized (pull effect).We present a polynomial time algorithm for this model along with some basic theoretical results, and generalize the results also to incorporate maximin and minimax objectives. In fact, the method works for any piecewise linear objective functions. Finally, we present some computational results.     

区间图上可带负权的2-中位选址问题

本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的$p-$中位选址问题($p\geq 2$)可分为两类：即 MWD 和 WMD 模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为$O(n^2)$的多项式时间算法.     

半讨厌型设施选址问题的模型与算法

研究了结合网络和平面模型的半讨厌型设施的选址问题.半讨厌型设施结合了讨厌型设施与喜爱型设施的性质,一方面由于这些设施对人们带来很多副作用,人们想要远离他们以避免遭到污染,但同时人们又希望距离设施不要过远,因此建立0-1整数模型,在保证所有人使用该设施的距离不超过既定距离的基础上,使污染范围最小.由于该问题是NP困难问题,本为给出了启发式算法,通过算例进行了比较分析,证明了算法的有效性.     

Efficient Location for a Semi-Obnoxious Facility

This paper deals with a location model for the placement of a semi-obnoxious facility in a continuous plane with the twin objectives of maximizing the distance to the nearest inhabitant and minimizing the sum of distances to all the users (or the distance to the farthest user) in a unified manner. For special cases, this formulation includes (1) elliptic maximin and rectangular minisum criteria problem, and (2) rectangular maximin and minimax criteria problem. Polynomial-time algorithms for finding the efficient set and the tradeoff curve are presented.