Using injection points in reformulation local search for solving continuous location problems
DOI:
https://doi.org/10.2298/YJOR160517018BKeywords:
Continuous Location, Weber problem, Formulation space search, Reformulation descent, Variable neighbourhood searchAbstract
Reformulation local search (RLS) has been recently proposed as a new approach for solving continuous location problems. The main idea, although not new, is to exploit the relation between the continuous model and its discrete counterpart. The RLS switches between the continuous model and a discrete relaxation in order to expand the search. In each iteration new points obtained in the continuous phase are added to the discrete formulation. Thus, the two formulations become equivalent in a limiting sense. In this paper we introduce the idea of adding 'injection points' in the discrete phase of RLS in order to escape a current local solution. Preliminary results are obtained on benchmark data sets for the multi-source Weber problem that support further investigation of the RLS framework.References
I. Bongartz, P.H. Calamai, and A.R. Conn, A projection method for LP norm location-allocation problems, Mathematical Programming, 66 (1994) 283–312.
J. Brimberg, Z. Drezner, N. Mladenovic, and S. Salhi, A new local search for continuous location problems, European Journal of Operational Research, 232 (2014) 256–265.
J. Brimberg, P. Hansen, and N. Mladenovic, Attraction probabilities in variable neighbourhood search, 4OR: Quarterly Journal of Operations Research, 8 (2010) 181–194.
J. Brimberg, P. Hansen, N. Mladenovic, and S. Salhi, A survey of solution methods for the continuous location-allocation problem, International Journal of Operations Research, 5 (2008) 1–12.
J. Brimberg, P. Hansen, N. Mladenovic, and E.D. Taillard, Improvement and comparison of heuristics for solving the uncapacitated multisource Weber problem, Operations Research, 48 (3) (2000) 444–460.
J. Brimberg and J. Hodgson, Heuristics for Location Models, in Foundations of Location Analysis (eds.) H.A. Eiselt, Vladimir Marianov, Springer, Berlin, 2011, 335–355.
L. Cooper, Location-allocation problem, Operations Research, 11 (1963) 331–343.
L. Cooper, Heuristics methods for location-allocation problems, SIAM Review, 6 (1964) 37–53.
Z. Drezner, J. Brimberg, N. Mladenovic, and S. Salhi, New local searches for solving the multi-source Weber problem, Annals of Operations Research, 246 (2016) 181–203.
S. Eilon, C.D.T. Watson-Gandy, and N. Christodes, Distribution Management, Hafner, New York, 1971.
D. Erlenkotter, A dual-based procedure for uncapacitated facility location, Operations Research, 26 (1978) 992–1009.
P. Hansen, N. Mladenovic, and E. Taillard, Heuristic solution of the multisource Weber problem as a p-median problem, Operations Research Letters, 22 (1998) 55–62.
R.F. Love, J.G. Morris, and G.O. Wesolowsky, Facilities Location: Models and Methods, North-Holland, New York, 1988.
M. Megiddo and K.J. Supowit, On the complexity of some common geometric location problems, SIAM Journal on Computing, 13 (1984) 182–196.
N. Mladenovic, J. Brimberg, P. Hansen, and J.A. Moreno-Perez, The p-median problem: A survey of metaheuristic approaches, European Journal of Operational Research, 179 (2007) 927–939.
G. Reinelt, TSLIB—a travelling salesman library, ORSA Journal on Computing, 3 (1991) 376–384.
S. Salhi and M.D.H. Gamal, An algorithm-based approach for the uncapacitated continuous location-allocation problem, Annals of Operations Research, 123 (2003) 203–222.
S. Salhi and R.J. Petch, A GA based heuristic for the vehicle routing problem with multiple trips, Journal of Mathematical Modelling and Algorithms, 6 (2007) 591–613.
A.J. Scott, Combinatorial Programming, Spatial Analysis and Planning, Methuen, London, 1971.
E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum, Tohoku Mathematical Journal, 43 (1937) 355–386.
Downloads
Published
Issue
Section
License
Copyright (c) 2017 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
