On the distribution approach to location problems

While making location decisions, the distribution of travel distances among the service recipients (clients) is an important issue. It is usually tackled with the minimax (center) or the minisum (median) solution concepts. Both concepts minimize only simple scalar characteristics of the distribution: the maximal distance and the average distance, respectively. In this paper, all the distances for the individual clients are considered as a set of multiple uniform criteria to be minimized. This results in a multiple criteria model taking into account the entire distribution of distances. Our analysis of the multiple criteria problem focuses on the symmetrically efficient solutions which comply with minimization of distances as well as with impartial consideration of the clients. Various solution concepts generating symmetrically efficient location patterns are analyzed. Finally, the reference distribution approach is developed as an interactive technique which enables us to identify a satisfactory symmetrically efficient location pattern by evolving a reference (target) distribution of distances.     

Hub location for time definite transportation

Time definite motor carriers provide very reliable scheduled truck transportation service between specified terminals. They provide service competitive with airfreight carriers over continental-scale distances at a much lower cost. This paper provides time definite models for multiple allocation p-hub median problems and hub arc location problems. Service levels are imposed by limiting the maximum travel distance via the hub network for each origin–destination pair. Computational results are presented to demonstrate the effects of the time definite service levels on practical network design for truck transportation in North America.     

The p-median problem in a changing network: the case of Barcelona

In this paper a p-median-like model is formulated to address the issue of locating new facilities when there is uncertainty in demand, travel times or distance. Given several possible scenarios, the planner would like to choose a set of locations that will perform as well as possible over all future scenarios. This paper presents a discrete location model formulation to address this p-median problem under uncertainty. The model is applied to the location of fire stations in Barcelona.     

A minisum model with forbidden regions for locating a semi-desirable facility in the plane

Most facilities in today's technological society may be classified as semi-desirable. That is, the facility provides a benefit or service to society, while adversely affecting the quality of life or social values in a number of possible ways. The paper proposes a location model for a new semi-desirable facility that accounts for the service costs by a standard minisum objective with arbitrary travel distance function. The social costs are imputed by specifying around each demand point or population center a convex forbidden region, also defined by an arbitrary distance metric, in which the new facility may not be located. A general solution algorithm is suggested, and the methodology is applied to circular forbidden regions and special travel distance functions.     

Deployment of field hospitals in mass casualty incidents

We propose an analysis framework to determine the location and size of emergency service facilities to be established after a disaster to cope with the demand surge. We utilize a multi-period mixed integer programming (MIP) model that simultaneously optimizes capacity allocation and casualty transportation decisions in order to provide emergency transportation and medical care services to the largest number of casualties in shortest time. The objectives are to minimize the total travel and waiting time of casualties over the search-and-rescue period and the total cost of establishing new facilities. The model minimizes a weighted sum of these objectives subject to the availability of vehicles and service capacity at existing and new facilities in each period. We provide a detailed case study of a large-scale emergency due to an expected earthquake in Istanbul to demonstrate the two-level solution approach. Service requests over time and travel times are generated with respect to regional vulnerabilities and road network conditions. Solutions and sensitivity analysis reveal the resource needs and service performance to guide preparedness strategies.     

A continuous analysis framework for the solution of location–allocation problems with dense demand

Location–allocation problems arise in several contexts, including supply chain and data mining. In its most common interpretation, the basic problem consists of optimally locating facilities and allocating customers to facilities so as to minimize the total cost. The standard approach to solving location–allocation problems is to model alternative location sites and customers as discrete entities. Many problem instances in practice involve dense demand data and uncertainties about the cost and locations of the potential sites. The use of discrete models is often inappropriate in such cases. This paper presents an alternative methodology where the market demand is modeled as a continuous density function and the resulting formulation is solved by means of calculus techniques. The methodology prioritizes the allocation decisions rather than location decisions, which is the common practice in the location literature. The solution algorithm proposed in this framework is a local search heuristic (steepest-descent algorithm) and is applicable to problems where the allocation decisions are in the form of polygons, e.g., with Euclidean distances. Extensive computational experiments confirm the efficiency of the proposed methodology.     

The vendor location problem

The vendor location problem is the problem of locating a given number of vendors and determining the number of vehicles and the service zones necessary for each vendor to achieve at least a given profit. We consider two versions of the problem with different objectives: maximizing the total profit and maximizing the demand covered. The demand and profit generated by a demand point are functions of the distance to the vendor. We propose integer programming models for both versions of the vendor location problem. We then prove that both are strongly NP-hard and we derive several families of valid inequalities to strengthen our formulations. We report the outcomes of a computational study where we investigate the effect of valid inequalities in reducing the duality gaps and the solution times for the vendor location problem.     

An approximation manpower planning model for after-sales field service support

Manpower planning is a key part of after-sales field service support with a service guarantee. Accurate field travel distance approximation presents a good opportunity to lower the manpower level. By explicitly considering the uncertainties, a state-dependent travel distance approximation model is presented and used to find the optimized manpower solution. A simulation model is developed to study the relationship between staffing level, travel distance, and percentage of customers serviced on time. Numerical results show that the proposed travel distance approximation model performs much better than the classical “square root law” and other models in the literature.     

Probabilistic single obnoxious facility location with fixed budget

This paper investigates probabilistic single obnoxious facility location with fixed budget which is defined as locating the facility to maximize the probability that the minimum weighted distance from the facility to all non-expropriated demand nodes exceeds a given threshold and the maximum weighted distance from the facility to all expropriated demand nodes does not exceed another given value, where demand weights are random variables with general continuous probability distributions. Properties of the optimal solutions are identified and heuristic solution procedures are presented, especially under the condition of some specific probability distributions. The general problem we propose also leads to some known problems such as maximin, quantile location problems.     

Locating an n-server facility in a stochastic environment

We consider a demand-responsive service system in which n mobile units (servers) are garaged at one facility. Service demands arrive in time as a homogenous Poisson process, but are located over the service region according to an arbitrary probability law. Given a random service demand, either (1) a mobile unit is dispatched to the demand's location to provide on-scene service or (2) the demand is lost (i.e. it is handled by some back-up system). The resultant queueing system is an M/G/n loss system operating in steady state. The objective is to locate the garage facility so that the average cost of response is minimized, where the cost of response is a weighted sum of mean travel time to a random serviced demand and the cost of a lost demand, the weights being the respective probabilities of occurrence. We show that the optimum facility location reduces to Hakimi's well-known minisum location.     

基于SimpliciTI协议的无线传感器网络设计

针对GPRS、ZigBee、WiFi等国际标准无线传感器网络通信协议价格高、对硬件要求高等问题,提出采用适用于小型射频网络的低功耗SimpliciTI协议设计无线传感器网络的方案。首先介绍了SimpliciTI协议的基本原理;然后给出了一种采用CC2500射频收发芯片和MSP430超低功耗微处理器芯片的无线传感器节点的电路设计方案,并介绍了基于SimpliciTI协议的无线传感器网络的组网及通信过程;最后介绍了基于距离的无线传感器网络定位算法,并针对常用的多边定位算法误差较大的问题,提出了一种改进的定位算法,即通过实际距离和估算距离的误差平方最小化来计算节点坐标的误差修正值,并采用二维双曲线算法修正未知节点的初始定位坐标,从而提高定位精度。     

城市潜力地段共享停车位资源需求预测仿真

当前停车位资源需求预测方法对城市潜力地段停车位资源分布均匀性差,导致共享停车位资源需求预测误差较大、可信度较低等问题。针对上述问题提出一种基于灰色算法的共享停车位资源需求预测方法,计算共享停车时间转变参数、出行吸引参数、区位因子参数和出行方式调节参数。利用灰度灰色算法构建非畸形模型,将参数结果代入最小二乘法中获取指标矩阵,利用该矩阵计算拟合值,得到城市潜力地段共享停车位资源需求的预测结果。实验结果证明,所提方法能够提高共享停车位资源需求预测准确率,保证了方法的可信度。     

基于模糊模式识别的车辆定位地图匹配算法

针对传感器给出的车辆定位信息的不确定性,提出了基于模糊模式识别技术获得匹配道路的算法。给出的算法不需要车辆行驶的速度、方向参数,利用车辆定位轨迹与电子地图道路网之间的相似性,结合车辆实际行驶情况,得出定位点到候选道路之间的距离、相邻采样时刻定位点连线与候选道路之间的夹角、候选道路与历史匹配道路连通性的隶属函数,按照最大隶属原则选择匹配道路。通过实验验证,表明该算法具有可靠性,适用面广,能有效地提高车辆定位的精度。     

Moments and error expressions in polynomial minimum mean square estimatior

The mathematical complexity of the minimum mean square estimators made inevitable the consideration of suboptimal solutions, such as the linear minimum mean square (m.m.s.) estimators. The compromise between performance and complexity can be, in general, less serious if the estimator that will substitute the optimum one is polynomial. If the minimum mean square estimator happens to be equal to a polynomial one, the polynomial substitution does not involve any compromise with respect to performance. Balakrishnan found a necessary and sufficient condition satisfied by the joint characteristic functions of observations and variable to be estimated, so that the m.m.s. estimate is a polynomial. The equivalent moment relationships in this case were found in the present paper. A matrix expression of the error difference from two different m.m.s. polynomial estimators was also found. This form involves much fewer calculations than required for finding separately the two errors.     

出租车数据的城市道路网路段通行时间估计方法

城市路段通行时间估计能够更好地运营和管理城市交通。针对包含起点-终点位置,行程时间和距离信息的GPS行程数据,提出了一种城市道路网短时通行时间的估计模型。首先将城市道路网按照交叉路口分解为多个路段,并基于k-最短路径搜索方法分析司机行进路线。然后针对每一个路段,提出了双车道通行时间多项式关联关系模型,既能提升道路网通行时间精细度,又能避免因训练数据不足导致的路网通行时间过拟合问题。最后以最小化行程期望时间和实际行程时间之间的均方误差为优化目标,拟合道路网通行时间。在纽约出租车数据集上的实验结果表明,所提模型及方法相对于传统单车道估计方法能够更准确地估计城市道路网路段的通行时间。     

Supply facility and input/output point locations in the presence of barriers

This paper studies a facility location model in which two-dimensional Euclidean space represents the layout of a shop floor. The demand is generated by fixed rectangular-shaped user sites and served by a single supply facility. It is assumed that (i) communication between the supply point and a demand facility occurs at an input/output (I/O) point on the demand facility itself, (ii) the facilities themselves pose barriers to travel and (iii) distance measurement is as per the L₁-metric. The objective is to determine optimal locations of the supply facility as well as I/O points on the demand facilities, in order to minimize total transportation costs. Several, increasingly more complex, versions of the model are formulated and polynomial time algorithms are developed to find the optimal locations in each case.Scope and purposeIn a facility layout setting, often a new central supply facility such as a parts supply center or tool crib needs to be located to serve the existing demand facilities (e.g., workstations or maintenance areas). The demand facilities are physical entities that occupy space, that cannot be traveled through, and that receive material from the central facility, through a perimeter I/O (input/output or drop-off/pick-up) point. This paper addresses the joint problem of locating the central facility and determining the I/O point on each demand facility to minimize the total material transportation cost. Different versions of this problem are considered. The solution methods draw from and extend results of location theory for a class of restricted location problems. For practitioners, simple results and polynomial time algorithms are developed for solving these facility (re) design problems.     

The gravity multiple server location problem

Models for locating facilities and service providers to serve a set of demand points are proposed. The number of facilities is unknown, however, there is a given number of servers to be distributed among the facilities. Each facility acts as an M/M/k queuing system. The objective function is the minimization of the combined travel time and the waiting time at the facility for all customers. The distribution of demand among the facilities is governed by the gravity rule. Two models are proposed: a stationary one and an interactive one. In the stationary model it is assumed that customers do not consider the waiting time at the facility in their facility selection decision. In the interactive model we assume that customers know the expected waiting time at the facility and consider it in their facility selection decision. The interactive model is more complicated because the allocation of the demand among the facilities depends on the demand itself. The models are analyzed and three heuristic solution algorithms are proposed. The algorithms were tested on a set of problems with up to 1000 demand points and 20 servers.     

The rectilinear distance minisum problem with minimum distance constraints:

This paper describes a mathematical model for locating a single facility on a continuous plane, which considers transportation (or service) costs between the facility and a set of demand points as well as social costs arising from the undesirable characteristics of the facility. The transportation costs are given by a standard minisum objective function, while the social costs appear implicitly in the form of lower bound constraints on the distances between the facility and the demand points. The model is analyzed under the assumption that distances are measured by the rectilinear norm, and an efficient branch-and-bound algorithm is derived to solve this case.     

The Capacitated p-facility Location Problem on the Real Line

The problem we address involves locating p new facilities to service a set of customers or fixed points on the real line such that a measure of total cost will be minimized. A basic form of this problem was investigated by Love (1976), who observed that the fixed points must be allocated in sequence to the new facilities in an optimal solution, and thus, the problem can be solved by a dynamic programming algorithm. Since then, other forms of the model have been investigated; however, in all cases it is assumed that the new facilities have unlimited capacity so that customer flows are always allocated to the nearest facility. The objective of this paper is to analyze the effect of capacity constraints on the optimal locations of the new facilities. A general fixed-cost function is also included to account for practical considerations such as zoning regulations, and to permit the facilities to be located anywhere on the line instead of only at the fixed vertices. A dynamic programming method is formulated to solve the problem when the variable cost components are increasing convex functions of travel distance. The problem is shown to be NP-hard under more general cost structures.     

Locating a semi-obnoxious facility with expropriation

This paper considers the problem of locating semi-obnoxious facilities assuming that “too close” demand nodes can be expropriated by the developer at a given price. The objective is to maximize the minimum weighted distance from the facility to the non-expropriated demand nodes given a limited budget while taking into account the fact that customers do not want to be too far away from the facility. Two models of this problem on a network are presented. One is to minimize the difference between the maximum and the minimum weighted distances. The other one is to maximize the minimum weighted distance subject to an upper bound constraint on the maximum weighted distance. The dominating sets are determined and efficient algorithms are presented.