穩健節點p中心模式於緊急救災物資配送中心區位選擇之應用

A Robust Vertex p-Center Model for Locating Urgent Relief Distribution Centers

古澤民(Tze-Min Ku)

指導教授 ： 盧宗成

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2011年)

https://doi.org/10.6841/NTUT.2011.00062

摘要

緊急救災物流配送系統通常可以分為三個層級：災區外各地的物資供應來源、救災物資配送中心、災區內的臨時救災物資發放站或者小型救護站等。本研究的目的是在探討緊急救災物資配送中心之區位選擇問題，我們將此問題視為節點p中心問題，也就是從一個候選設施點集合中選取p個設施，使得這些選取的中心到最遠災區點的距離最短。在研究中，採用穩健最佳化的方法，將救災物資配送中心到災區間之運送時間的不確定性以區間資料來表示，並發展一穩健節點p中心模型，求解目標為極小化在最差狀況情境下到達所有災區物資發放站或救護站的最遠距離。由於以連續區間資料來表示運送時間的不確定性可能會導致無限多種情境，使得決定最差狀況情境變得非常困難，為解決此一難處，本研究提出一個定理能夠有效率地決定最差狀況情境。在求解方面，由於此問題為NP-Hard，本研究發展以模擬退火法為基礎的啟發式演算法，並以隨機產生的例題測試演算法的求解績效，測試結果發現此一演算法能夠在合理時間內找到非常近似最佳解。此外，本研究也探討資料不確定的程度對於相關績效指標的影響。

關鍵字

緊急救災物流 ； 穩健最佳化 ； 中心問題 ； 模擬退火法

並列摘要

Urgent relief distribution centers (URDCs) play a key role in emergency logistics systems established to respond to quick onset, natural disasters. This paper presents a robust vertex p-center model for locating URDCs on a set of given candidate sites, as well as allocating relief stations in affected areas to those URDCs. Particularly addressed in the models are uncertain travel times that are represented using intervals, instead of probability distributions. The objective is to locate p URDCs so as to minimize the worst-case loss in objective value. A key problem property that can facilitate the determination of the worst-case scenario, among an infinite number of possible scenarios, is analyzed. Since the problem is NP-hard, a simulated annealing (SA)-based heuristic was developed, to find robust solutions. Numerical results show that the proposed heuristic is effective and efficient in obtaining robust solutions of interest. In addition, we examined the impact of the degree of data uncertainty on the selected performance measures.

並列關鍵字

Emergency logistics ； Robust optimization ； P-center problem ； Simulated annealing

參考文獻

[7] B. Balcik and B. M. Beamon, "Facility location in humanitarian relief," International Journal of Logistics:search and Application, vol. 11, no. 2, 2008, pp. 101-121.

[4] A. Ben-tal and A. Nemirovsi, "Robust convex optimization," Math Operations Research, vol.23, 1998, pp. 769-805.

[5] A. Ben-tal and A. Nemirovsi, "Robust solution of linear programming problems contaminate with uncertain data," Math Programming, vol. 88, 2000, pp. 411-424.

[6] A. L. Soyster, "Convex programming with set-inclusive constraints and applications to inexact linear programming," Operations Research, vol. 21, 1973, pp. 1154-1157.

[8] C. G. Rawls and M. A. Turnquist, "Pre-positioning of emergency supplies for disasrer response," Transportation Research Part B, vol. 44, 2010, pp. 521-531.