This thesis focuses on an operational scheduling problem in a home healthcare system in which nurses visit patients regularly for relatively minor healthcare services. Intervals between the visits may differ for different patients and each patient must be assigned to only one nurse. On each day in the planning horizon (24 working days), nurses must visit the patients assigned to them on that day, and then return to the hospital. For the problem with the objective of minimizing total travelling distances of the nurses over the planning horizon, we develop a two-phase heuristic algorithm, in which nurses are assigned to the patients and then the visiting schedules of the nurses are determined. To evaluate performance of the proposed algorithm, we perform computational experiments on a number of problem instances that are randomly generated. Results of the tests show that the proposed algorithm gives near optimal solutions in a reasonable time.
본 논문은 가정간호 시스템에서 환자에 대한 간호사 할당 및 간호사의 환자 방문 일정 계획에 관한 문제를 다루고 있다. 환자들에 대한 방문 간격은 환자들의 질환 수준에 따라 다르며, 각 환자들은 오직 한 명의 간호사에 할당되어 치료를 받을 수 있다. 간호사는 병원에서 출발하여study period동안 각각의 날짜마다 할당된 환자들을 모두 방문한 후 다시 병원으로 돌아와야 한다. 본 논문의 목적은 study period동안 간호사들의 환자 방문 이동 시간을 최소화시키는 경로를 찾는 것이다. 그리고 본 문제는 Periodic Vehicle Routing Problem(주기적 차량 경로문제, PVRP)과 유사하나, 환자의 방문 간격이 일정하게 정해져 있기 때문에 기존 PVRP문제를 확장시킨 형태이다. 또한 일반적으로 PVRP 문제가 NP-hard로 알려져 있으므로 본 문제 또한 NP-hard 문제임을 알 수 있다. 이 문제의 복잡성 때문에 기존의 다른 PVRP연구에서는 주로 meta-heuristic 기법을 사용하여 최소 이동시간을 가지는 경로를 구하였다. 그러나 본 논문에서는 간호사를 환자에 먼저 할당한 후, 간호사의 환자 일정 방문 계획을 구하는 두 단계로 나누어 접근하였다. 제안된 휴리스틱의 성능 평가를 위해 실제 가정 간호 시스템의 조건을 반영하여 임의로 생성한 다양한 데이터들로 실험을 수행하였다. 그 결과, 빠른 시간 내에 좋은 해를 주는 것으로 나타났다.