Maxwell, Matthew S., et al. "Approximate dynamic programming for ambulance redeployment." INFORMS Journal on Computing 22.2 (2010): 266-281.
본 연구는 approximate dynamic programming 을 활용해서 앰뷸런스의 재배치 장소를 실시간으로 결정하는 문제를 푼다. 긴급 의료 서비스를 제공하는 앰뷸런스의 운행 전략을 짤때 골든타임 내에 응급 환자를 수송할 수 있는 가능성을 최대화 할 수 있도록 공차 배차 전략을 짜는 것이 본 연구의 핵심 목표이다. 이 문제를 dynamic programming 문제로 포뮬레이션 할텐데, 이때 고차원의 무수히 많은 state space를 다루기 위한 value function appoximation을 제안한다. 이를 통해 적은 개수의 파라미터로 구성된 value function을 구축할 수 있다. 이 파라미터는 시뮬레이션을 반복적으로 시행하면서 적정 값을 찾아나간다. 각 이터레이션은 두 단계로 구성된다. 첫번째 스텝에서는 현재 value function을 기반으로 cost trajectory 를 계산하고, 두번째 스텝에서는 계산된 값을 기반으로 regression 문제를 풀어 value function 값을 갱신한다. 이 과정은 마치 Markov decision process 에서 policy를 평가하고 policy를 개선해나가는 iteration 과정과도 유사하다.
본 연구가 approximate dynamic programming 을 사용함으로써 다른 방법론을 사용하는 것에 비해 얻는 장점은 다음과 같다.
-
integer programming 방법과 비교하면 시스템에서 시간의 흐름에 따라 진화해나가는 랜덤성을 모델에 반영할 수 있다.
-
비교적 간단한 최적화 문제를 풀기 때문에 실시간으로 해를 구해낼 수 있다.
-
운영자의 해석에 따라 차량을 어디로 보낼지 최종결정을 해야하는 lookup table 전략에 비해 본 연구는 완전히 자동화된 의사결정을 지원한다.
-
전통적인 dynamic programming 방식에 대비해서 문제의 규모를 현실 문제 수준으로 키울 수 있다.
-
다양한 objective function을 선택할 수 있다 (기 설정된 통행 시간 한계치를 넘지 않는 요청 건수 최대화, 전체 통행 시간 최소화 등).
-
이 방법론은 앰뷸런스 재배치의 빈도수와 도착지를 제한시킬 수 있다. 이는 현실에서는 서비스의 개선과 앰뷸런스 크루에게 가중될 업무량 사이에서 적절한 균형점을 찾아야 하기 때문이다.