지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2011.1
- 수록면
- 183 - 191 (9page)
이용수
초록· 키워드
오류제보하기
본 논문은 하나의 도시가 여러 구역으로 분할되고, 응급환자가 발생하였을 때, 모든 구역에 대해 최대 허용 도착시간 T를 충족시키도록 응급시설을 배치하는 문제에 대한 알고리즘을 제안하였다. 이 문제는 일반적으로 다항시간으로 해를 구하는 알고리즘이 존재하지 않아 두 구역 간 소요시간이 최대허용 도착시간이내이면 1로, 그렇지 않으면 0으로 하는 정수계획법으로 변환시키고, 선형계획법 도구를 활용하여 해를 구한다. 본 논문은 최소차수 노드의 이웃 노드들 중 최대 차수 노드를 응급시설의 위치로 결정하는 집합피복 알고리즘을 적용하였다. 제안된 알고리즘을 텍사스 오스틴 시의 33개 구역에 대한 사례에 대해 $3{\leq}T{\leq}20$ (분)을 적용하고, Swain의 55개 노드 망에 대해 T=15에 대해 응급시설의 위치를 결정할 수 있는지 여부를 검증하였다. 선형계획법을 활용한 전통적인 집합피복 알고리즘은 몇 개의 T에 대해 해를 구하지 못한 반면에, 제안된 알고리즘은 18개의 모든 T에 대해 해를 구하였다.
목차
등록된 정보가 없습니다.
참고문헌 (10)
참고문헌 신청
M. S. Daskin / 1981 / A Hierarchical Objective Set Covering Model for Emergency Medical Service Deployment / Transportation Science 15(2):137~152
R. Z. Farahani / 2009 / Facility Location: Concepts, Models, Algorithms and Case Studies / Springer-Verlag Berlin Heidelberg
L Carsten / 1994 / On the Hardness of Approximating Minimization Problems / Journal of the ACM 41(5):960~981
V. Chvatal / 1979 / A Greedy Heuristic for the Set-Covering Problem / Mathematics of Operations Research 4(3):233~235
R. M. Karp / 1972 / Reducibility Among Combinatorial Problems, in Complexity of Computer Computations / Plenum :85~103
R. Z. Farahani / 2009 / Facility Location: Concepts, Models, Algorithms and Case Studies / Springer-Verlag Berlin Heidelberg
L Carsten / 1994 / On the Hardness of Approximating Minimization Problems / Journal of the ACM 41(5):960~981
V. Chvatal / 1979 / A Greedy Heuristic for the Set-Covering Problem / Mathematics of Operations Research 4(3):233~235
R. M. Karp / 1972 / Reducibility Among Combinatorial Problems, in Complexity of Computer Computations / Plenum :85~103
이 논문의 저자 정보
최근 본 자료
댓글(0)
0