한정된 응급시설의 최적위치 문제

다국어 초록 (Multilingual Abstract)

This paper proposes an EMS algorithm designed to determine the optimal locations for Emergency Medical Service centers that both satisfy the maximum ambulance response time T in case of emergency and cover the largest possible number of residents given a limited number of emergency medical services p in a city divided into different zones. This methodology generally applies integer programming whereby cases are categorized into 1 if the distance between two zones is within the response time and 0 if not and subsequently employs linear programming to obtain the optimal solution. In this paper, where p=1, the algorithm determines a node with maximum coverage. In cases where p≥2, the algorithm selects top 5 nodes with maximum coverage. Based on inclusion-exclusion method, this selection entails repeatedly selecting a node with the maximum coverage when nodes with lower numbers are deleted. Among these 5 selected nodes, the algorithm selects a single node set with the greatest coverage and thereby as the optimal EMS location. The proposed algorithm has proven to accurately and expeditiously obtain the optimal solutions for 12-node network, 21-node network, and Swain's 55-node network.

참고문헌 (Reference)

1 K. J. Devlin, "The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time" Basic Books 2002

2 R. Church, "The Maximal Covering Location Problem" 32 (32): 101-118, 1974

3 D. Serra, "Surviving in a Competitive Spatial Market: The Threshold Capture Model" 39 (39): 637-650, 1999

4 L Carsten, "On the Hardness of Approximating Minimization Problems" 41 (41): 960-981, 1994

5 L. Dawei, "Model and Algorithms for Emergency Service Facility Location Problem" IEEE Computer Science 15-19, 2009

6 "List of NP-complete Problems" Wikipedia Foundation Inc

7 R. J. Vanderbei, "Linear Programming: Foundations and Extensions" Springer Verlag 114 : 2008

8 R. Z. Farahani, "Facility Location: Concepts, Models, Algorithms and Case Studies" Springer-Verlag Berlin Heidelberg 2009

9 R. M. Karp, "Complexity of Computer Computations, In Complexity of Computer Computations" Plenum 85-103, 1972

10 J. E. Storbeck, "A Simple Trade-off Model for Maximal and Multiple Coverage" 20 (20): 220-230, 1988

11 M. S. Daskin, "A Hierarchical Objective Set Covering Model for Emergency Medical Service Vehicle Deployment" 15 (15): 137-152, 1981

12 V. Chvatal, "A Greedy Heuristic for the Set- Covering Problem" 4 (4): 233-235, 1979