Efficient incrementing heuristics for generalized p-location problems

This paper studies effective solving techniques for large p-location problems, in which generalized disutility is applied to incorporate stochastic behavior of real service system. The concept of generalized disutility follows the idea that the nearest located service center may be temporarily unavailable at the moment of currently arisen demand and the demand is serviced from a more distant service center with given probability. The more complex approach to the real p-location asks for enormous computational time of exact solving tools and thus evokes the question whether the faster heuristics can compete with the exact approaches in accuracy of results obtained. To answer the question, two heuristics were proposed for the studied problem. The first of them is a common swap local search with the best-admissible strategy and the second is based on the path-relinking method. The both heuristics make use of so called uniformly deployed sets used for preliminary mapping of the feasible solutions to accelerate the performance of the heuristics. As uniformly deployed set construction can be done in two modes, the paper is also focused on finding the most effective combination of the mode and heuristic. A real case study was performed with seven road networks with number of nodes varying from 250 to 660. In addition, ten different families of uniformly deployed sets were generated for each network and mode. The results of the case study confirm that the suggested approaches are able to produce the solutions of the same quality as the exact approaches. Furthermore, the study indicates drawbacks, which can be met in connection with usage of specific combinations of heuristic and the mode of uniformly deployed set construction.