Content area
Full Text
Abstract
This paper deals with the problem of designing the public service systems with an exact optimization core. Designing the public service system represents NP-hard problem consisting of solution to the p-median location problem. Erlenkotter designed one of the most effective algorithm for solving the uncapacitated facility location problem. Erlenkotter approach is based on the branch and bound method, theory of duality and using dual solution to obtaining the lower and upper bound of solution. we present two approaches to solving the p-median location problem with using Erlenkotter approach. Semi-exact iterative approach is based on the transformation of the p-median location problem to the uncapacitated facility location problem by Lagrangean relaxation of the p-median condition. Generalized exact approach is based on the generalization of Erlenkotter approach to the solving the p-median location problem. The proposed approaches are compared in terms of demands on the computational time and accuracy of the obtained solution.
Categories and Subject Descriptors
G.1.6 [Optimization]: Integer Programming
Keywords
Public service system design, location problem, Erlenkotter approach, Lagrangean relaxation, branch and bound method, generalized exact approach, semi-exact iterative approach, compositional approach.
(ProQuest: ... denotes formulae omitted.)
1. Introduction
In real situations, we find various service systems, which have become part of our lives. Service system can be divided into private and public service systems.The servise system design consists of a set of customers and a set of candidates to the facility location. Private service systems is based on the maximal profit of system owner. Main goal of private servise system is minimizing costs to requirements of the customers with some profit. The public service system structure is formed by the deployment of limited number of service centers and the associated objective is to minimize social costs, which are often proportional to distances from serviced customers to the nearest source of provided service.The service is available for all customers. Designing a public service system, including medical emergency system, fire-brigade deployment, public administration system and many others, can often bring along some overall combinatorial problems concerning the system structure. The public system design can evaluate the quality solutions using different criteria. The system criterium gives minimizing the sum of the costs associated with the establishment of centers and customer servicing. Minimax criterion gives position...