Location-area partition in a cellular radio network

With an increasing population of mobile subscribers, the signalling traffic to control the subscriber mobility expands rapidly. Subscriber mobility is controlled through location registration based on the so-called location area, the basic area unit for paging which consists of a number of cells. There is a tradeoff between the two kinds of signalling traffic: paging and location updating. As location areas include a larger number of cells, the traffic volume for paging increases while that for location updating decreases. Given not only the pattern of call arrivals but also that for subscriber mobility, our problem is to minimise the total signalling traffic by optimally partitioning the whole area into location areas. We show that this problem can be transformed to the so-called clique partitioning problem (CPP). Also we demonstrate the process of implementing the algorithm for solving the CPP for real-world problems defined on the cellular network in Seoul.     

Comparative economic analysis between direct and indirect wiring in the copper-based local loop

In a copper-based local loop, a circuit pair is indirectly connected to each subscriber usually via a primary cross connection point (PCP) which acts as a buffer to absorb circuit demand fluctuations among subareas. But some telephone operators adhere to the classic practice of direct wiring based on technological preferences without taking advantage of cost-efficient flexibility points. We analyse the extra cost of maintaining the old practice of direct wiring over the popular one using flexibility points in a single PCP area. For that, the expectation of circuit shortages in subareas during a single replenishment period for the direct wiring is first obtained. Exploiting the convexity of the expectation, we then present a procedure for optimally allocating circuits among subareas, which not only serves its own purpose of circuit provisioning for the direct wiring but also precisely calculates the extra cost over the indirect case.     

A Dual-Based Add Heuristic for Uncapacitated Facility Location

This paper presents a heuristic method for solving the uncapacitated facility-location problem (UFLP), which is similar to Erlenkotter's ‘dual ascent’ procedure. The heuristic is of the ‘add’ type, which progressively selects facilities to open according to a certain criterion derived from the analysis of the linear programming dual. Computational experience with both (static) UFLPs and dynamic UFLPs reveals that the heuristic method yields solutions in most cases superior in quality to those achieved by the dual-ascent procedure, with barely noticeable additional computation time.     

A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints

This paper deals with the problem of locating at minimum total costs both plants and warehouses in a two-level distribution system where commodities are delivered from plants to customers either directly or indirectly via warehouses. Some side-constraints are imposed on the problem, which represent the adjunct relationship of some warehouses to a certain plant. Proposed is an efficient branch and bound solution procedure, employing a set of new devices for lower bounds and simplifications which are obtained by exploiting the submodularity of the objective function and the special structure of the side-constraints. Computational experiments with fifteen test problems are provided.     

A bi-objective uncapacitated facility location problem

We consider a bi-objective model for uncapacitated facility location where one objective is to maximize the net profit and the other to maximize the profitability of the investment. We first characterize the structure of the model having both a linear and a fractional objective function. In order to generate efficient solutions for the model, we develop a heuristic procedure which has computational advantages over existing methods. A numerical example is presented to illustrate the solution process and computational tests on large scale problems are also provided.