Development of a Lagrangian Heuristic for Solving Regional Coverage Problem (지역포괄 시설물 입지선정 문제를 위한 라그란지안 해법 연구)

Jong-Geun Kim (김종근)

Development of a Lagrangian Heuristic for Solving Regional Coverage Problem

Journal of the Korean Cartographic Association
Abbr : JKCA
2013, 13(1), pp.143-153
Publisher : The Korean Cartographic Association
Research Area : Social Science > Geography > Geography in general > Cartography

Jong-Geun Kim ¹

¹서울대학교

Accredited

ABSTRACT

Incorporation of efficient solution methods into a GIS environment has the potential of providing insights into the importance of spatial representation in location modeling. Heuristic algorithms based on lagrangian relaxation have solid theoretic grounds and the quality of the solutions is guaranteed to be within bounds. This paper focuses on solving the LSCP that optimizes the locations of a minimum number of facilities that can cover all the demands. The structure and characteristics of LSCP were analyzed to develop a lagrangian heuristic, which was implemented into a GIS environment. Tests on the real world data suggest that the developed system provides high-quality solutions efficiently.

KEYWORDS

Lagrangian relaxation, Location modeling, Heuristics, GIS, Spatial representation

Citation status

* References for papers published after 2023 are currently being built.

[journal] 김명진 / 2012 / A Heuristic Approach with New Contiguity Checking Method to Congressional Redistricting / 한국지도학회지 / 한국지도학회 12(3) : 81~94

[journal] 김영훈 / 2009 / Applying a p-median algorithm to zone design problems / 한국지도학회지 / 한국지도학회 9(2) : 73~80

[journal] 이건학 / 2012 / Coverage Analysis and Optimal Location Modeling for Establishing a Wi-Fi based U-campus / 한국지도학회지 / 한국지도학회 12(2) : 47~58

[journal] Balas, E. / 1980 / Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study / Combinatorial Optimization 12 : 37~60

[journal] Beasley, J. E. / 1987 / An algorithm for set covering problem / European Journal of Operational Research 31(1) : 85~93

[book] Beasley, J. E. / 1993 / Lagrangian relaxation, In Modern Heuristic Techniques for Combinatorial Problems / Blackwell Scientific Publications : 243~303

[journal] Caprara, A. / 1999 / A heuristic method for the set covering problem / Operations Research 47(5) : 730~743

[journal] Church, R.L. / 1974 / The maximal covering location problem / Papers of Regional Science 32(1) : 101~118

[journal] Current, J.R. / 1990 / Analysis of errors due to demand data aggregation in the set covering and maximal covering location problems / Geographical Analysis 22(2) : 116~126

[book] Daskin, M.S. / 1995 / Network and Discrete Location: Models, Algorithms, and Applications / John Wiley and Sons

[journal] Edmonds, J. / 1962 / Covers and packings in a family of sets / Bulletin of the American Mathematical Society 68 : 494~499

[journal] Fisher, M. L. / 1985 / An applications oriented guide to lagrangian relaxation / Interfaces 15(2) : 10~21

[journal] Fisher, M. L. / 2004 / The lagrangian relaxation method for solving integer programming problems / Management Science 50(12) : 1861~1871

[book] Garfinkel, R.S. / 1972 / Integer Programming / John Wiley and Sons

[journal] Haddadi, S. / 1997 / Simple lagrangian heuristic for the set covering problem / European Journal of Operational Research 97(1) : 200~204

[journal] Held, M. / 1974 / Validation of subgradient optimization / Mathematical Programming 6(1) : 62~88

[journal] Murray, A. T. / 2008 / Regional service coverage modeling / Computers & Operations Research 35(2) : 339~355

[journal] RcVelle, C. / 1976 / Applications of the location set covering problem / Geographical Analysis 8(1) : 65~76

[journal] Shilling, D. A. / 1980 / Some models for fire protection locational decisions / European Journal of Operational Research 5(1) : 1~7

[journal] Toregas, C. / 1971 / The location of emergency service facilities / Operations Research 19(5) : 1363~1373

[journal] Toregas, C. / 1973 / Binary logic solutions to a class of location problem / Geographical Analysis 5(2) : 145~155

KJCKorea
Journal Central

Journal of the Korean Cartographic Association 2023 KCI Impact Factor : 1.34