最佳化之救護資源動態配置與配置點匹配

Optimal dynamic allocation and location matching for emergency medical resource

張力權(Li-Quan Chang)

指導教授 ： 林慧珍

淡江大學/工學院/資訊工程學系碩士班/碩士(2017年)

https://doi.org/10.6846/TKU.2017.00751

摘要

早期救護車配置相關研究大都是以解決「集合涵蓋問題」（Set covering problems, SCO）[4]為主，尋求可以涵蓋最多需求量的配置策略。配置方式大都考慮單位區域人口數或過去的救護案件量或預測的救護案件量，救護車配置地點大都是限制在某些特定地點，比如新北市救護車只配置在消防分隊內。這樣的配置限制，對於離消防分隊較遠的地點無法得到有效的救護服務，配置結果比較無法達到公平的資源分布。
　　本研究有兩部分, 第一部分旨在提出一個救護車動態配置，即每一固定時段根據需求分布重新計算配置之方法，而且任何一點都是可能的配置位置，而非只限制在消防分隊內。提出的配置方法除了讓救護車的涵蓋範圍能達到最大化，還期望每個需求點得到的救護服務能最平均。此部分我們假設需求分布已事先預測出來。第二部分旨在提出一個能讓救護車在兩個連續時段的配置位置能迅速移動的方法，也就是對兩個連續時段的兩組配置位置做匹配，使得新舊時段匹配點距離和能最小化。如此所有救護車從一個時段的配置位置移動至下一個時段的配置位置之總移動距離，可期望達到最小化。

關鍵字

動態配置 ； 基因演算法 ； 貪婪搜尋演算法

並列摘要

Most early research on ambulance allocation focus on the solutions to the Set COvering problems (SCO) [4], seeking an allocation strategy that achieves the maximal coverage of demand. The allocation strategies are generally based on the population density distribution, the historical demand distribution, or a predicted demand distribution. In most related research or real cases, candidate locations for ambulance allocation sites are restricted to certain locations. For example, the ambulances owned by the New Taipei City government can be deployed in the fire branches only. However, this restriction might cause unfair distribution of resources, namely, some demand points gain much more ambulance service than others.
The paper will consist of two parts: ambulance allocation and matching between two sets of allocation locations. For the first part, we focus on dynamic allocation or regular periodical allocation, considering all points as candidate allocation locations rather than merely the fire stations. We use a genetic algorithm to find the best allocation based on the criterion of fairness and according to the predicted demand distribution, which is assumed being available. For the second part, the best matching between two sets of allocation locations for two consecutive periods is searched, so that ambulances can efficiently move from one period to the next period. That is, we tend to a match between two sets of locations so that the total displacement of ambulances is minimized.

並列關鍵字

Dynamic allocation ； Genetic algorithm ； Greedy search algorithm

參考文獻

[1] 黃國平、吳青翰. 緊急醫療救護系統資源配置及績效評估之模擬研究－以台南市為例. 台灣衛誌, 26(3), pp. 184-195, 2007.

[2] Aickelin, U., “An indirect genetic algorithm for set covering problems,” Journal of the Operational Research Society, vol. 53, pp. 1118–1126, 2002.

[3] Alessandrini, E., Sajani, S. Z., Scotto, F., Miglio, R., Marchesi, S., and Lauriola, P., “Emergency ambulance dispatches and apparent temperature: a time series. analysis in Emilia-Romagna,” Italy. Environ Res, vol. 111, pp. 1192–1200, 2011.

[4] Aytug, H. and Saydam, C., “Solving large-scale maximum expected covering location problems by genetic algorithms: a comparative study,” European Journal of Operational Research, vol. 141, pp. 480–494, 2002.

[5] Beraldi, P. and Bruni, M.- E., “A probabilistic model applied to emergency service vehicle location,” European Journal of Operational Research, vol. 196, pp. 323–331, 2009.