無容量限制下之動態需求設施區位問題研究

On the Use of Genetic Algorithms to Solve the Dynamic Location Problem

紅名鴻(Ming Hong Hong)

指導教授 ： 丁慶榮

元智大學/工程學院/工業工程與管理學系/碩士(2002年)

摘要

對於國營企業或是私人企業而言，設施區位的選擇將是策略規劃的重要考量因素之一，而設施區位的選擇往往需受限於不同的空間資源支配，也隨著消費人口的變動、市場型態的轉移以及環境因素的改變，企業必須經常針對現有設施之區位進行評估，以決定是否進行設施產能的擴充或設施區位的更換（relocation），進而滿足顧客需求。
設施區位問題乃是針對提供服務活動的設施，尋求如何配置於最適位置，以使得所求目標最佳化。本研究所考慮的動態性設施區位問題，包含有時間、區位決策的考量，同時，顧客點需求是屬於動態性需求，會隨時間而有所改變，並加入有設施的建置成本、設施的年使用成本以及需求點與設施點之間的運送成本等成本因素考量，並以基因演算法之菁英政策進行求解，而本研究所採用的基因演算法之菁英政策加入記錄與取代兩部分，並採用同時性的演化方式，同時針對位置、時間兩決策變數進行求解。
本研究首先針對OR-Library中無容量限制的倉庫問題進行測試，此類型的區位問題是屬於本研究範疇中的一種特例，在12組測試題中，本研究所使用的基因演算法之菁英政策都能找到最佳解。最後，本研究也針對動態性需求的區位問題，隨機產生線性需求與混合性需求的測試題目，在設施建置數目給定的情形下，都可以得到最佳解或趨近最佳解結果。在參數分析方面，設施建置成本愈高，最佳設施區位數愈小；而在給定設施建置數目下，年使用成本的增加或是單位運輸成本的減少，都將使得設施的建置時間延後。

關鍵字

動態需求 ； 設施區位問題 ； 基因演算法 ； 建置成本 ； 年使用成本 ； 無容量限制

並列摘要

Location decision arises in a variety of both public and private sector problems. Many facility location problems determine where to locate an initial number of facilities at the beginning of the planning horizon and all facilities remain open throughout. These problems recognize that demand may change over time and attempt to account for the effects of these changes in the initial set of locations. However, future demand often is not known with certainty and has been approximated by a deterministic surrogate. In this research, we try to optimize a plan that opens facilities at specific times and locations in response to changes in demand over time.
We consider the dynamic location problem where, given an initial number of facilities, one must locate these facilities at optimal times and locations over the planning horizon, such that the objective function including facility construction cost, transportation cost, and facility annual usage charge is minimized. We develop a mathematical model and a genetic algorithm (GA) incorporating the elitism strategy to analyzing such problems. Two decision variables, location and opening time (where and when) of those facilities, are optimized simultaneously.
We evaluate our proposed algorithm with two different problem sets: uncapacitated warehouse location problems in the OR-library and randomly generated problems. The former problem set that optimizes facility locations with given “static” demand at the beginning of the planning horizon is a special case for our model (no time decision). Our algorithm finds all the optimal solutions. Since no test problems for the dynamic location problem that we try to solve, we randomly generate six problem sets with different combinations of planning horizon and candidate sites to illustrate the interacting effects among critical parameters in the model. For the six problem sets, the proposed algorithms find most of the optimal solutions. Our results show that the number of facilities decreases as the construction cost increases. Given an initial number of facilities, we will defer the facility construction when unit transportation cost decreases or annual facility usage cost increases.

並列關鍵字

Dynamic Location Problem ； Genetic Algorithm ； Time Decision ； Construction Cost ； Annual Usage Cost

參考文獻

33.樓邦儒，「台北市消防隊多目標區位模式之研究」，中國文化大學地學研究所地理組，碩士論文，1995。

25.曾國雄、林楨家，「淡海新市鎮消防隊佈設區位之研究-TOPSIS多目標規劃法之應用」，都市與計劃，第24卷，第1期，第81-98頁，1997。

47.Dai, Z., and T. Y. Cheung, “ A New Heuristic Approach for the P-median Problems,” Journal of the Operational Research Society, Vol. 48, No. 9, pp. 950-960, 1997.

38.Beasley, J.E., “A Note on Solving Large P-median Problems,” European Journal of Operational Research, Vol. 21, pp. 270-273, 1985.

39.Beasley, J.E., “OR-Library：Distributing Test Problems by Electronic Mail,” Journal of the Operation Research Society, Vol. 41, pp.1069-1072, 1990.