A probabilistic model applied to emergency service vehicle location

This paper is concerned with the formulation and the solution of a probabilistic model for determining the optimal location of facilities in congested emergency systems. The inherent uncertainty which characterizes the decision process is handled by a new stochastic programming paradigm which embeds the probabilistic constraints within the traditional two-stage framework. The resulting model drops simplifying assumptions on servers independence allowing at the same time to handle the spatial dependence of demand calls. An exact solution method and different tailored heuristics are presented to efficiently solve the problem. Computational experience is reported with application to various networks.     

Facility location models for planning a transatlantic communications network

This paper presents two facility location models for the problem of determining how to optimally serve the requirements for communication circuits between the United States and various European and Middle Eastern countries. Given a projection of future requirements, the problem is to plan for the economic growth of a communications network to satisfy these requirements. Both satellite and submarine cable facilities may be used. The objective is to find an optimal placement of cables (type, location, and timing) and the routing of individual circuits between demand points (over both satellites and cables) such that the total discounted cost over a T-period horizon is minimized. This problem is cast as a multiperiod, capacitated facility location problem. Two mathematical models differing in their provisions for network reliability are presented. Solution approaches are outlined and compared by means of computational experience. Use of the models both in planning the growth of the network and in the economic evaluation of different cable technologies is also discussed.     

Optimal location of interconnected facilities on tree networks subject to distance constraints

Optimal location of interconnected facilities on tree networks is considered in the case when some of the nodes of the network contain existing facilities. The distances between the facilities must satisfy maximum constraints. Polynomial algorithms for the solution of this problem are proposed.     

Solving a minimum-power covering problem with overlap constraint for cellular network design

We consider a type of covering problem in cellular networks. Given the locations of base stations, the problem amounts to determining cell coverage at minimum cost in terms of the power usage. Overlap between adjacent cells is required in order to support handover. The problem we consider is NP-hard. We present integer linear models and study the strengths of their continuous relaxations. Preprocessing is used to reduce problem size and tighten the models. Moreover, we design a tabu search algorithm for finding near-optimal solutions effectively and time-efficiently. We report computational results for both synthesized instances and networks originating from real planning scenarios. The results show that one of the integer models leads to tight bounds, and the tabu search algorithm generates high-quality solutions for large instances in short computing time.     

Layouts for mobility management in wireless ATM networks

In this paper, we present a new model that combines quality of service and mobility aspects in wireless ATM networks. Namely, besides the hop count and load parameters of the basic ATM layouts, we introduce a new notion of distance that estimates the time needed to reconstruct the virtual channel of a wireless user when he moves through the network. Quality of service guarantee dictates that the rerouting phase must be imperceptible, that is, the maximum distance between two virtual channels must be maintained as low as possible. Therefore, a natural combinatorial problem arises in which suitable trade-offs must be determined between the different performance measures. We first show that establishing the existence of a layout with maximum hop count h, load l and distance d is NP-complete, even in the very restricted case h=2, l=1 and d=1. We then provide optimal layout constructions for basic interconnection networks, such as chains and rings.     

A co-opetitive framework for the hub location problems in transportation networks

In this paper, we present the first model of co-opetition for a Hub Location Problem between two logistics service provider (LSPs) companies where the mother company is the owner of infrastructure. The LSPs would like to cooperate with each other by establishing joint edges with limited capacities connecting their service networks. Such services are in form of pendulum services (a direct service between two points) between nodes of different networks. Additional market can be generated as a result of joining the two networks. At the same time, a competition is taking place between the two operators to increase their share from the additional market generated. In order to solve this problem, we propose a matheuristic approach combining a local search algorithm and a Lagrangian relaxation-based approach. In our matheuristic algorithm, the neighbourhood solutions are evaluated using a Lagrangian relaxation-based approach. Numerical results of applying the proposed algorithm on a real case study of the problem are presented.     

A Fuzzy Logic Approach to Buffer Management in ATM Networks

A fuzzy buffer controller is developed to minimize cell loss in ATM switches. The proposed fuzzy controller sequences cells in buffers based upon the corresponding priority class, end-to-end delay parameter and congestion status. Cells are then scheduled and/or discarded according to their sequenced positions.     

Developing effective meta-heuristics for a probabilistic location model via experimental design

This article employs a statistical experimental design to guide and evaluate the development of four meta-heuristics applied to a probabilistic location model. The meta-heuristics evaluated include evolutionary algorithm, tabu search, simulated annealing, and a hybridized hill-climbing algorithm. Comparative results are analyzed using ANOVA. Our findings show that all four implementations produce high quality solutions. In particular, it was found that on average tabu search and simulated annealing find their best solutions in the least amount of time, with relatively small variability. This is especially important for large-size problems when dynamic redeployment is required.     

The least element property of center location on tree networks with applications to distance and precedence constrained problems

In the classicalp-center location model on a network there is a set of customers, and the primary objective is to selectp service centers that will minimize the maximum distance of a customer to a closest center. Suppose that thep centers receive their supplies from an existing central depot on the network, e.g. a warehouse. Thus, a secondary objective is to locate the centers that optimize the primary objective as close as possible to the central depot. We consider tree networks and twop-center models. We show that the set of optimal solutions to the primary objective has a semilattice structure with respect to some natural ordering. Using this property we prove that there is ap-center solution to the primary objective that simultaneously minimizes every secondary objective function which is monotone nondecreasing in the distances of thep centers from the existing central depot.Restricting the location models to a rooted path network (real line) we prove that the above results hold for the respective classicalp-median problems as well.     

A multiobjective fuzzy bandwidth partitioning model for self-sizing networks

The ability to cope with dynamic bandwidth demands is a special feature for Quality of Service provisioning in networks carrying bandwidth hungry applications. This paper introduces a novel approach based on multiobjective fuzzy optimization for dynamic bandwidth allocation. This new approach deals with uncertain bandwidth demands more efficiently than approaches based on Classical Optimization Theory and yet supports Quality of Service commitments.     

A primal-dual approximation algorithm for stochastic facility location problem with service installation costs

We consider the stochastic version of the facility location problem with service installation costs. Using the primal-dual technique, we obtain a 7-approximation algorithm.     

A new model for gas flow in pipe networks

We introduce a new model for gas dynamics in pipe networks by asymptotic analysis. The model is derived from the isothermal Euler equations. We present the derivation of the model as well as numerical results illustrating the validity and its properties. We compare the new model with existing models from the mathematical and engineering literature. We further give numerical results on a sample network. Copyright © 2009 John Wiley & Sons, Ltd.     

Sequential sampling schemes and other statistical techniques in quality of service business surveys

While there is a general consensus in the business community regarding the importance of quality service surveys in improving the company's business results, relatively little attention was devoted to the theoretical aspects of data analysis and modelling which can increase substantially the effectiveness of those surveys. Using the data from a real‐life project, we present here the developments and improvements achieved in the three stages that ultimately yield the conclusions from the survey: the analysis of the historical data, the design of the sampling method for the current survey and the development of specific indices for differentiating among the units of the financial institution. The statistical techniques fitted to historical data helped both in assessing the relative contributions of the various aspects of service, the overall perceived quality of service, as well as in providing the theoretical grounds for reducing the size of the questionnaire and thus increasing the reliability of the received replies. The sequential sampling scheme designed for this survey was particularly suitable to address the managements concerns. Finally, the classes of quality service based on the quality indices developed in the project contributed substantially to the ability of the management to rank and reward differentially the branches of the financial institution. Copyright © 2002 John Wiley & Sons, Ltd.     

A novel mechanism for provisioning of high-level quality of service information in grid environments

Grids, like other heterogeneous systems, have reached the level of maturity where they are addressing the Quality of Service (QoS) provision aspect as a fundamental part of their architecture. However, due to the multi-layer nature of these environments, the QoS characteristics of the infrastructure are revealed to the service-consumer through a complex procedure, in which each layer maps its own QoS parameters to another. Most of these approaches are starting the delegation of QoS information from the service provider’s side, resulting in delivering low-level terms to the service consumer. In this paper, we define the architecture of a mechanism that is able to provide application-oriented and user-specific QoS information in the internal layers of the Grid middleware. This way, it enables the service consumer and especially the end-user to express his business perspectives through the service level agreement life cycle. We also demonstrate the operation of this mechanism and evaluate its performance using a specific Grid scenario.     

Control of multi-node mobile communications networks with time-varying channels via stability methods

Consider a communications network consisting of mobiles and random external data processes, each destined to a particular destination. Each mobile can serve as a node in the multi-hop path from source to destination. At each mobile the data is queued according to the source destination pair. The quality of the connecting channels are randomly varying. Time is divided into small scheduling intervals. At the beginning of each interval, the channels are estimated and this information is used for the decisions concerning allocation of transmission power and/or time, bandwidth, and perhaps antennas, in a queue and channel-state dependent way. Under a natural (and “almost” necessary) “average flow” condition, stochastic stability methods are used to develop scheduling policies that assure stability. The policies are readily implementable and allow a range of tradeoffs between current rates and queue lengths, under very weak conditions. Because of the non-Markovian nature of the problem, we use the perturbed Stochastic Liapunov function method. The choice of Liapunov function allows a choice of the effective performance criteria. All essential factors are incorporated into a “mean rate” function, so that the results cover many different systems. Extensions concerning acknowledgments, multicasting, non-unique routes, and others are given to illustrate the versatility of the method, and a useful method for getting the a priori routes is discussed.     

Throughput limits from the asymptotic profile of cyclic networks with state-dependent service rates

We consider networks where at each node there is a single exponential server with a service rate which is a non-decreasing function of the queue length. The asymptotic profile of a sequence of networks consists of the set of persistent service rates, the limiting customer-to-node ratio, and the limiting service-rate measure. For a sequence of cyclic networks whose asymptotic profile exists, we compute upper and lower bounds for the limit points of the sequence of throughputs as functions of the limiting customer-to-node ratio. We then find conditions under which the limiting throughput exists and is expressible in terms of the asymptotic profile. Under these conditions, we determine the limiting queue-length distributions for persistent service rates. In the absence of these conditions, the limiting throughput need not exist, even for increasing sequences of cyclic networks.      

Developing a step-by-step effectiveness assessment model for customer-oriented service organizations

Effectiveness involves more than simple efficiency, which is limited to the production process assessment of peer operational units. Effectiveness incorporates variables that are both controllable (i.e. efficiency) and non-controllable (i.e. perceived quality) by the operational units. It is a fundamental driver for the success of either a for-profit or a non-for-profit unit in a competitive environment that is customer/citizen- and goal-oriented. Additionally, with respect to the short-run production constraints, i.e. the resources available and controllable by the operational units, and the legal status, we go beyond the traditional effectiveness assessment techniques by developing a Modified or “rational” Quality-driven-Efficiency-adjusted Data Envelopment Analysis (MQE-DEA) model. This particular model provides in the short run a feasible effectiveness attainment path for every disqualified unit in order to meet high-perceived quality and high-efficiency standards. By applying the MQE-DEA model a new production equilibrium is determined, which is different from the equilibrium suggested by the mainstream microeconomic theory, in that it takes into account not only the need for operational efficiency but also the customer-driven market dynamics.     

A cross-monotonic cost sharing method for the facility location game with service installation costs

In this paper,we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type.     

Application of a location model to fire stations in Rotterdam

This report is an outgrowth of a research project carried out by the Operations Research Group of Twente University of Technology in cooperation with the Department Fire-Brigade Affairs (Home Office) and the Rotterdam Fire Department. The objectives of the project were to determine the minimal number of fire stations, their locations and the number of first attendance pumpers, so that each point in town can be reached within a prescribed attendance time with sufficient equipment.A road network approach was used for determining the set of possible location areas for fire stations followed by a set-covering approach for calculating the minimal number of stations. The hard points to tackle were the construction of robust networks, the determination of the possible location areas and the calculation of all the alternative locations of a minimal number of fire stations.A simulation was carried out to test whether the solutions given by the network approach were realistic.