We map certain combinatorial aspects of the p-median problem and explore their effects on the efficacy of a common (1-opt) interchange heuristic and of heuristic concentration (HC) for the problem's solution. Although the problem's combinatorial characteristics exist in abstract space, its data exist in two-dimensional space and are therefore mappable. By simultaneously analysing the problem's patterns in geographic space and its combinatorial characteristics in abstract space, we provide new insight into what demand node configurations cause problems for the interchange heuristic and how HC overcomes these problems. Location-allocation (LA) models simultaneously locate facilities and allocate demand points to them. They have extensive applications in both the public and private sectors (Rosing, Hodgson, JORBEL: Belgian Journal of Operations Research and Statistics 36 (1997) 75). The p-median, which minimizes the average demand-facility distance is the most widely used LA model. The p-median model is np hard and its data sets are frequently extremely large, requiring heuristic solutions. As the size of the data sets grows, the quality of solutions from the most commonly used heuristic, that of Tietz and Bart (Operations Research 16 (1968) 955) deteriorate (Rosing, Environment and Planning 24 (1997) 59). HC (Rosing, ReVelle, European Journal of Operational Research 97 (1997) 75), a method concentrates and builds upon the good elements of suboptimal heuristic solutions, has been shown to produce excellent solutions for large data sets (Rosing, ReVelle, Rolland, Schilling, Current, European Journal of Operational Research 104 (1998) 93). The purpose of this paper is to demonstrate how and why HC improves upon the results of a 1-opt interchange heuristic. The method used is a node examination of good solutions and their geography.

, ,
doi.org/10.1016/S0305-0548(01)00033-8, hdl.handle.net/1765/71518
Computers & Operations Research
Tinbergen Institute

Rosing, K., & Hodgson, M. J. (2002). Heuristic concentration for the p-median: An example demonstrating how and why it works. Computers & Operations Research, 29(10), 1317–1330. doi:10.1016/S0305-0548(01)00033-8