現在位置首頁 > 博碩士論文 > 詳目
論文中文名稱:最佳化模型及演算法解決設施選址問題 [以論文名稱查詢館藏系統]
論文英文名稱:Optimization models and solution algorithms for facility location problems [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:管理學院管理博士班
畢業學年度:105
畢業學期:第二學期
出版年度:106
中文姓名:朱恒興
英文姓名:Heng-Hsing Chu
研究生學號:98749004
學位類別:博士
語文別:英文
口試日期:2017/04/25
論文頁數:72
指導教授中文名:吳建文
口試委員中文名:李炯三;吳建文;翁頌舜;陳育威;王永寧
中文關鍵詞:階層式選址倉儲設施選址快速迭代區域搜尋演算法
英文關鍵詞:Hierarchical locationWarehouse locationFast iterated local search algorithm
論文中文摘要:設施選址規劃問題是一個相當重要且被廣為應用與發展的組合最佳化問題。所發展出的相關數學模型,可透過啟發式演算法求得最佳解,並進行最佳化成果分析。在現代化工業發展環境中,妥適的規劃倉儲與零售店設施位址,將可有效推進物流供應的執行效能,與提升企業經營的整體效益。近年來,隨著賣場型倉儲設施設置日益普及,透過將既有設施位址進行最佳化分析,以解決應急救援物資的供應問題,是相當重要且值得探討的議題。此外,在高密度發展的都市環境裡,往往亦面臨到發展空間有限的實際問題,使得大型倉儲設施無法完整設置於同一位址,而必須區分成不同性質與功能的倉儲設施於不同位址設置,透過協同供應模式,滿足零售店需求。因此,在本研究中,我們提出了預置動員倉儲設施部署規劃、設施分置選址覆蓋與階層式多個不同性質的選址規劃問題進行探討,除提出相關數學模型與演算法求得最佳解外,並結合實際案例進行實務研究分析。結果顯示,透過相關應用與所發展出的演算法除可大幅提升最佳解計算效能外,其實際案例分析成果,將對於企業在商業策略制定上有著顯著的實務貢獻。
論文英文摘要:The facility location problem is a significant important combinatorial optimization problem that has a broad application and development. The models of facility location problem can be defined differently in its objective function, constraints, solution space and several other decision factors. In the modern industrial development environment, planning warehouses and retailer locations properly may effectively promote an enterprise’s operational efficiency, and enhances the effectiveness of logistics and supply chain implementation. In many real life situations, with the popularization of the compound hypermarket and depot in recent years (combined with warehouses with retailers), the applications of facilities location planning issue are very important and worth to be discussed. In addition, the limited space of the urban environment may lead to practical problems in locating a large warehouses facility in a single location, and may need to be partitioned and placed at different locations with synergy patterns to fulfill the orders from retailers. Therefore, this study we propose to discuss the positioned mobilization warehouse deployment problem, facility partition location covering problem (FPLCP), hierarchical multiple-distinct facilities location problems (HMDFLP) and its applications related to warehouse and retailer facility location aspect, and put forward solving algorithms for these problems. The experimental and practical application results show that it has significant improvement in effectiveness and has a significant contribution in a realistic location environment to promote industry development.
論文目次:摘 要 i
ABSTRACT ii
Table of Contents iv
List of Tabless vi
List of Figures viii
Chapter 1 Introduction 1
Chapter 2 Literature review 3
2.1 Warehouse location 3
2.2 Single sourcing 4
2.3 Maximal covering location problem 6
2.4 P-median 6
2.5 P-dispersion 8
2.6 Hierarchical location 8
Chapter 3 The pre-positioned mobilization warehouse deployment problem 10
3.1 Problem description 10
3.2 Formulation 12
3.3 Heuristic algorithm 14
3.4 Experiment and analysis 16
3.5 Discussions 21
Chapter 4 The Facility Partition Location Covering Problem 23
4.1 Problem description 23
4.2 Formulation 23
4.3 Description of FIM 25
4.4 Proposed approach 26
4.5 Experimental and analysis 28
4.6 Discussions 32
Chapter 5 The hierarchical multiple-distinct facilities location problems 34
5.1 Problem description 34
5.2 Formulation 36
5.3 Heuristic algorithm 38
5.4 Experiment and analysis 41
5.5 Testing in realistic instances 45
5.6 Discussions 58
5.7 Strength and limitation 59
Chapter 6 Conclusions and contribution 60
6.1 Conclusions 60
6.2 Academic contribution 61
6.3 Practical contribution 62
Reference 64
論文參考文獻:[1] Arabani, A. B., & Farahani, R. Z. (2012). Facility location dynamics: An overview of classifications and applications. Computers & Industrial Engineering, 62(1), 408-420.
[2] Jena, S. D., Cordeau, J. F., & Gendron, B. (2016). Solving a dynamic facility location problem with partial closing and reopening. Computers & Operations Research, 67, 143-154.
[3] Farahani, R. Z., SteadieSeifi, M., & Asgari, N. (2010). Multiple criteria facility location problems: A survey. Applied Mathematical Modelling, 34(7), 1689-1709.
[4] Farahani, R. Z., Asgari, N., Heidari, N., Hosseininia, M., & Goh, M. (2012). Covering problems in facility location: A review. Computers & Industrial Engineering, 62(1), 368-407.
[5] Church, R., & Velle, C. R. (1974). The maximal covering location problem. Papers in regional science, 32(1), 101-118.
[6] Cao, B., & Uebe, G. (1993). An algorithm for solving capacitated multicommodity p-median transportation problems. Journal of the Operational Research Society, 259-269.
[7] Elloumi, S., Labbé, M., & Pochet, Y. (2004). A new formulation and resolution method for the p-center problem. INFORMS Journal on Computing, 16(1), 84-94.
[8] Moon, I. D., & Chaudhry, S. S. (1984). An analysis of network location problems with distance constraints. Management Science, 30(3), 290-307.
[9] Farahani, R. Z., Hekmatfar, M., Fahimnia, B., & Kazemzadeh, N. (2014). Hierarchical facility location problem: Models, classifications, techniques, and applications. Computers & Industrial Engineering, 68, 104-117.
[10] Perl, J., & Daskin, M. S. (1985). A warehouse location-routing problem. Transportation Research Part B: Methodological, 19(5), 381-396.
[11] Cokelez, S., & Burns, J. R. (1989). Distribution systems—warehouse location and capacity. Omega, 17(1), 45-51.
[12] Lee, W. I., Shih, B. Y., & Chen, C. Y. (2012). A hybrid artificial intelligence sales‐forecasting system in the convenience store industry. Human Factors and Ergonomics in Manufacturing & Service Industries, 22(3), 188-196.
[13] Kallrath, J. (2002). Planning and scheduling in the process industry. OR spectrum, 24(3), 219-250.
[14] Kallrath, J. (2005). Solving planning and design problems in the process industry using mixed integer and global optimization. Annals of Operations Research, 140(1), 339-373.
[15] Lin, C. K. Y. (2009). Stochastic single-source capacitated facility location model with service level requirements. International Journal of Production Economics, 117(2), 439-451.
[16] Tragantalerngsak, S., Holt, J., & Ro, M. (1997). Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem. European Journal of Operational Research, 102(3), 611-625.
[17] Elmaghraby, W. J. (2000). Supply contract competition and sourcing policies. Manufacturing & Service Operations Management, 2(4), 350-371.
[18] Sayyady, F., Tutunchi, G. K., & Fathi, Y. (2015). P-median and p-dispersion problems: A bi-criteria analysis. Computers & Operations Research, 61, 46-55.
[19] Hansen, P. H., Hegedahl, B., Hjortkjaer, S., & Obel, B. (1994). A heuristic solution to the warehouse location-routing problem. European Journal of Operational Research, 76(1), 111-127.
[20] Kalfakakou, R., Katsavounis, S., & Tsouros, K. (2003). Minimum number of warehouses for storing simultaneously compatible products. International Journal of Production Economics, 81, 559-564.
[21] Hsieh, L. F., & Tsai, L. (2006). The optimum design of a warehouse system on order picking efficiency. The International journal of advanced manufacturing technology, 28(5-6), 626-637.
[22] Drezner, Z., Scott, C., & Song, J. S. (2003). The central warehouse location problem revisited. IMA Journal of Management Mathematics, 14(4), 321-336.
[23] Michel, L., & Van Hentenryck, P. (2004). A simple tabu search for warehouse location. European Journal of Operational Research, 157(3), 576-591.
[24] Köchel, P., & Thiem, S. (2011). Search for good policies in a single-warehouse, multi-retailer system by particle swarm optimisation. International Journal of Production Economics, 133(1), 319-325.
[25] Yaobao, Z., Ping, H., & Shu, Y. (2013). An improved particle swarm optimization for the automobile spare part warehouse location problem. Mathematical Problems in Engineering, 2013, 1-6.
[26] Rath, S., & Gutjahr, W. J. (2014). A math-heuristic for the warehouse location–routing problem in disaster relief. Computers & Operations Research, 42, 25-39.
[27] Sharma, R. R. K., & Agarwal, P. (2014). Approaches to solve MID_CPLP problem: Theoretical framework and empirical investigation. American Journal of Operations Research, 4(03), 142-154.
[28] Alavidoost, M. H., Tarimoradi, M., & Zarandi, M. F. (2015). Bi-objective mixed-integer nonlinear programming for multi-commodity tri-echelon supply chain networks. Journal of Intelligent Manufacturing, 1-18.
[29] Wutthisirisart, P., Sir, M. Y., & Noble, J. S. (2015). The two-warehouse material location selection problem. International Journal of Production Economics, 170, 780-789.
[30] Sharma, R. R. K., Tyagi, P., Kumar, V., & Jha, A. (2015). Developing strong and hybrid formulation for the single stage single period multi commodity warehouse location problem: Theoretical framework and empirical investigation. American Journal of Operations Research, 5(03), 112-128.
[31] Yu, H., Zeng, A. Z., & Zhao, L. (2009). Single or dual sourcing: decision-making in the presence of supply chain disruption risks. Omega, 37(4), 788-800.
[32] Costantino, N., & Pellegrino, R. (2010). Choosing between single and multiple sourcing based on supplier default risk: A real options approach. Journal of Purchasing and Supply Management, 16(1), 27-40.
[33] Meena, P. L., Sarmah, S. P., & Sarkar, A. (2011). Sourcing decisions under risks of catastrophic event disruptions. Transportation research part E: logistics and transportation review, 47(6), 1058-1074.
[34] Guastaroba, G., & Speranza, M. G. (2014). A heuristic for BILP problems: the single source capacitated facility location problem. European Journal of Operational Research, 238(2), 438-450.
[35] Zarandi, M. F., Davari, S., & Sisakht, S. H. (2011). The large scale maximal covering location problem. Scientia Iranica, 18(6), 1564-1570.
[36] Berman, O., & Krass, D. (2002). The generalized maximal covering location problem. Computers & Operations Research, 29(6), 563-581.
[37] Serra, D., & Marianov, V. (2004). New trends in public facility location modeling. UPF Economics and Business Working Paper, (755).
[38] Erdemir, E. T., Batta, R., Rogerson, P. A., Blatt, A., & Flanigan, M. (2010). Joint ground and air emergency medical services coverage models: A greedy heuristic solution approach. European Journal of Operational Research, 207(2), 736-749.
[39] Galvão, R. D., & ReVelle, C. (1996). A Lagrangean heuristic for the maximal covering location problem. European Journal of Operational Research, 88(1), 114-123.
[40] Senne, E. L. F., Pereira, M. A., & Lorena, L. A. N. (2010). A decomposition heuristic for the maximal covering location problem. Advances in Operations Research, 2010.
[41] ReVelle, C., Scholssberg, M., & Williams, J. (2008). Solving the maximal covering location problem with heuristic concentration. Computers & Operations Research, 35(2), 427-435.
[42] Otto, B., & Boysen, N. (2014). A dynamic programming based heuristic for locating stops in public transportation networks. Computers & Industrial Engineering, 78, 163-174.
[43] Segura, E., Benítez, R. B. C., Lozano, A., & Flores, I. (2014). Optimization of Milk Distribution for Maximum Demand Coverage in Chihuahua, Mexico. Procedia-Social and Behavioral Sciences, 160, 519-528.
[44] Farahani, R. Z., Hassani, A., Mousavi, S. M., & Baygi, M. B. (2014). A hybrid artificial bee colony for disruption in a hierarchical maximal covering location problem. Computers & Industrial Engineering, 75, 129-141.
[45] Pereira, M. A., Coelho, L. C., Lorena, L. A., & De Souza, L. C. (2015). A hybrid method for the probabilistic maximal covering location–allocation problem. Computers & Operations Research, 57, 51-59.
[46] He, Z., Fan, B., Cheng, T. C. E., Wang, S. Y., & Tan, C. H. (2016). A mean-shift algorithm for large-scale planar maximal covering location problems. European Journal of Operational Research, 250(1), 65-76.
[47] Mladenović, N., Brimberg, J., Hansen, P., & Moreno-Pérez, J. A. (2007). The p-median problem: A survey of metaheuristic approaches. European Journal of Operational Research, 179(3), 927-939.
[48] Jayaraman, V., & Pirkul, H. (2001). Planning and coordination of production and distribution facilities for multiple commodities. European journal of operational research, 133(2), 394-408.
[49] Tang, H., Cheng, T. C. E., & Ng, C. T. (2009). Finite dominating sets for the multi-facility ordered median problem in networks and algorithmic applications. Computers & Industrial Engineering, 57(3), 707-712.
[50] Kalcsics, J. (2011). The multi-facility median problem with pos/neg weights on general graphs. Computers & Operations Research, 38(3), 674-682.
[51] Brimberg, J., & Drezner, Z. (2013). A new heuristic for solving the p-median problem in the plane. Computers & Operations Research, 40(1), 427-437.
[52] Kalcsics, J., Nickel, S., Pozo, M. A., Puerto, J., & Rodríguez-Chía, A. M. (2014). The multicriteria p-facility median location problem on networks. European Journal of Operational Research, 235(3), 484-493.
[53] An, Y., Zeng, B., Zhang, Y., & Zhao, L. (2014). Reliable p-median facility location problem: two-stage robust models and algorithms. Transportation Research Part B: Methodological, 64, 54-72.
[54] Gueye, S., & Menezes, M. B. (2015). General asymptotic and submodular results for the Median Problem with Unreliable Facilities. Operations Research Letters, 43(5), 519-521.
[55] Albareda-Sambola, M., Hinojosa, Y., & Puerto, J. (2015). The reliable p-median problem with at-facility service. European Journal of Operational Research, 245(3), 656-666.
[56] Drezner, Z., Brimberg, J., Mladenović, N., & Salhi, S. (2015). New heuristic algorithms for solving the planar p-median problem. Computers & Operations Research, 62, 296-304.
[57] Blanco, V., Puerto, J., & Ben-Ali, S. E. H. (2016). Continuous multifacility ordered median location problems. European Journal of Operational Research, 250(1), 56-64.
[58] Resende, M. G., Martí, R., Gallego, M., & Duarte, A. (2010). GRASP and path relinking for the max–min diversity problem. Computers & Operations Research, 37(3), 498-508.
[59] Ravi, S. S., Rosenkrantz, D. J., & Tayi, G. K. (1994). Heuristic and special case algorithms for dispersion problems. Operations Research, 42(2), 299-310.
[60] Pisinger, D. (2006). Upper bounds and exact algorithms for p-dispersion problems. Computers & operations research, 33(5), 1380-1398.
[61] Sayyady, F., & Fathi, Y. (2016). An integer programming approach for solving the p-dispersion problem. European Journal of Operational Research, 253(1): 216-225.
[62] Gao, L. L., & Robinson, E. P. (1992). A dual‐based optimization procedure for the two‐echelon uncapacitated facility location problem. Naval Research Logistics, 39(2), 191-212.
[63] Barros, A. I., & Labbé, M. (1994). A general model for the uncapacitated facility and depot location problem. Location science, 2, 173-191.
[64] Hinojosa, Y., Puerto, J., & Fernández, F. R. (2000). A multiperiod two-echelon multicommodity capacitated plant location problem. European Journal of Operational Research, 123(2), 271-291.
[65] Huang, H. C., & Li, R. (2008). A k-product uncapacitated facility location problem. European Journal of Operational Research, 185(2), 552-562.
[66] Nezhad, A. M., Manzour, H., & Salhi, S. (2013). Lagrangian relaxation heuristics for the uncapacitated single-source multi-product facility location problem. International Journal of Production Economics, 145(2), 713-723.
[67] Aksen, D., Akca, S. Ş., & Aras, N. (2014). A bilevel partial interdiction problem with capacitated facilities and demand outsourcing. Computers & Operations Research, 41, 346-358.
[68] Aliakbarian, N., Dehghanian, F., & Salari, M. (2015). A bi-level programming model for protection of hierarchical facilities. Computers & Operations Research, 64: 210-224.
[69] Pettit, S. J., & Beresford, A. K. (2005). Emergency relief logistics: an evaluation of military, non-military and composite response models. International Journal of Logistics: Research and Applications, 8(4), 313-331.
[70] Roh S., Beresford A.K.C., Pettit S.J., (2008). Humanitarian aid logistics: response depot networks. In: Proceedings of the 20th NOFOMA Conference, Helsinki, Finland.
[71] Tatham, P., & Altay, N. (2013). On humanitarian logistics education and training. Journal of Humanitarian Logistics and Supply Chain Management, 3(2), 1–3.
[72] Balcik, B., & Beamon, B. M. (2008). Facility location in humanitarian relief. International Journal of Logistics, 11(2), 101-121.
[73] Roh, S., Pettit, S., Harris, I., & Beresford, A. (2015). The pre-positioning of warehouses at regional and local levels for a humanitarian relief organisation. International Journal of Production Economics, 170, 616-628.
[74] Tomasini, R. M., & Van Wassenhove, L. N. (2004). Pan-American health organizations humanitarian supply management system: de-politicization of the humanitarian supply chain by creating accountability. Journal of public procurement, 4(3), 437.
[75] Balcik, B., Beamon, B. M., Krejci, C. C., Muramatsu, K. M., & Ramirez, M. (2010). Coordination in humanitarian relief chains: Practices, challenges and opportunities. International Journal of Production Economics, 126(1), 22-34.
[76] Ballou, R. H. (1984). DISPLAN: a multiproduct plant/warehouse location model with nonlinear inventory costs. Journal of Operations Management, 5(1), 75-90.
[77] Özcan, T., Çelebi, N., & Esnaf, Ş. (2011). Comparative analysis of multi-criteria decision making methodologies and implementation of a warehouse location selection problem. Expert Systems with Applications, 38(8), 9773-9779.
[78] Lourenço, H. R., Martin, O. C., & Stützle, T. (2010). Iterated local search: Framework and applications. In Handbook of Metaheuristics (pp. 363-397). Springer US.
[79] Burdick, D., Calimlim, M., Flannick, J., Gehrke, J., & Yiu, T. (2005). Mafia: A maximal frequent itemset algorithm. IEEE transactions on knowledge and data engineering, 17(11), 1490-1504.
[80] IBM Inc. 2011. IBM ILOG CPLEX optimization studio getting started with CPLEX. Retrieved from http://cedric.cnam.fr/~lamberta/MPRO/ECMA/doc/Interface.pdf on March 01, 2016.
[81] Jin, R., & Agrawal, G. (2001, April). An efficient implementation of apriori association mining on cluster of smps. In Proceedings of the workshop on High Performance Data Mining, held with IPDPS 2001.
[82] Han, J., Pei, J., & Kamber, M. (2011). Data mining: concepts and techniques. Elsevier.
[83] Agarwal, R. C., Aggarwal, C. C., & Prasad, V. V. V. (2000, August). Depth first generation of long patterns. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 108-118).
[84] Mac Queen, J. (1967, June). Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability 1(14) 281-297.
[85] Schrage, L. (1990). Lindo an optimization modeling system/book and Macintosh disk. Course Technology Press. Retrieved from http://www.lindo.com/index.php?option=com_content&view=article&id=34&Itemid=15 on July 01, 2016.
[86] Feo, T. A., Venkatraman, K., & Bard, J. F. (1991). A GRASP for a difficult single machine scheduling problem. Computers & Operations Research, 18(8): 635-643.
[87] Bautista, J., & Pereira, J. (2007). A GRASP algorithm to solve the unicost set covering problem. Computers & Operations Research, 34(10): 162-3
論文全文使用權限:同意授權於2022-05-05起公開