簡易檢索 / 詳目顯示

回結果列表
研究生： Rifqi Ansari
Rifqi - Ansari
論文名稱： 應用粒子群演算法與禁忌搜尋法於－階層式設施定位問題
Developing a Hybrid Particle Swarm Optimization – Tabu Search for a Hierarchical Facility Location Problem
指導教授： 歐陽超
Chao Ou-Yang
口試委員: 郭人介
Ren-Jieh Kuo
楊朝龍
Chao-Lung Yang
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2014
畢業學年度： 102
語文別： 英文
論文頁數： 85
中文關鍵詞： 分层设施选址问题 、粒子群优化算法 、混合整数线性规划 、设施选址问题
外文關鍵詞： Hierarchical Facility Location Problem, Particle Swarm Optimization, Mixed Integer Linear Programming, Facility Location Problem
相關次數： 點閱：270  下載：5 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 分层工厂选址问题（HFLP）是一个扩展版本的设施布局问题的目的是确定在更高层次的设施能有效地服务于下级的方式接收设施的位置。粒子群优化（PSO）算法已被应用到了许多古典和现实世界的问题。然而，由于PSO算法是一种随机搜索算法，它很可能会失败在运行结束时将达到全球价值时，这个问题太复杂了。本研究提出的PSO和TS的解决所谓的HPSO-TS的分层工厂选址问题（HFLP）的组合。此外，这项研究还提出确切的方法分支定界，遗传算法和经典的粒子群算法进行比较，以该算法。以符合现实世界中，本研究认为流量在网络或其他期限的车辆通行能力，并在结果车辆任务的最佳数目也需要考虑。在这项研究中，对于HFLP一个混合整数规划模型与流量限制开发。作出的决定是定位了一些设施上的一组潜在的位点，确定所述网络分配，以及对网络流量的分配的数目。我们的目标是尽量减少整体需求加权长途旅行，打开设备成本，以及流量分配成本。随机密钥为基础的解决方案，代表和解码方法，提出了实现HPSO-TS。解码方法开始通过将颗粒引入一个优先列表，然后构造为分配网络。数值计算结果表明，该算法是有效的，因为在解决此类问题的精确解相比，给人最优或接近最优的解决方案。最后，该算法用于解决XYZ公司的研究情况。

    Hierarchical facility location problem (HFLP) is an extended version of facility layout problem which aims to determine the location of facilities in a way that facilities in higher level can serve lower level efficiently. Particle swarm optimization (PSO) algorithms have been applied to a number of classical and real-world problems. However, since PSO is a stochastic search algorithm, it is likely to be failed to reach global value at the end of a run when the problem is too complicated. This study proposes a combination of PSO and TS for solving the hierarchical facility location problem (HFLP) called HPSO-TS. Moreover, this study also proposes the exact method branch and bound, genetic algorithm, and classical PSO to be compared to the proposed algorithm. To conform to the real world, this study considers the flow capacity in the networks or in other term the vehicle capacity, and in the results the optimal number of vehicle assignments also need to be considered. In this study, a mixed integer programming model for HFLP with flow capacity constraint is developed. The decisions to be made are locating a number of facilities on a set of potential sites, determining the network assignments, and number of flow assignments on the networks. The objective is to minimize the overall demand weighted distance travel, opening facilities cost, and flow assignments cost. A random key-based solution representation and decoding method is proposed for implementing HPSO-TS. The decoding method starts by transforming the particles into a priority list and then constructed as the assignment networks. Numerical results show that the proposed algorithm is effective and gives optimal or close to optimal solutions as compared with exact solutions in solving this kind of problems. Finally, the proposed algorithm is used to solve the study case of XYZ Company.

    ABSTRACT i ACKNOWLEDGEMENT ii List of Figures v List of Tables vi Chapter 1 Introduction 1 1.1. Background 1 1.2. Research Issues and Objective 5 1.3. Research Purposes 6 1.4. Research Scope 7 1.5. Organization of the Thesis 7 Chapter 2 Literature Review 9 2.1 Facility Location Problem 9 2.2 Hierarchical Facility Location Problem 10 2.3 Metaheuristic Approaches 10 2.4 Genetic Algorithms 11 2.5 Particle Swarm Optimization 12 2.6 Tabu Search 16 2.7 Published Literatures in Hierarchical Facility Location Problems 17 Chapter 3 Methodology 23 3.1 Research Framework 23 3.2 Problem Statement 23 3.3 Assumptions 24 3.4 Influence Diagram and Unit Conversion 26 3.5 Mathematical Formulation 28 3.6 Hybrid Particle Swarm Optimization – Tabu Search Framework 31 3.7 Solution Representation and Decoding Method 32 3.8 Classical PSO 35 3.9 Tabu search procedure for PSO 37 3.10 Genetic Algorithm for HFLP 38 Chapter 4 Computational Experiments 41 4.1 Parameters Setting 42 4.2 Computational Result 43 4.3 Hypothesis Test 50 4.4 Case Study of XYZ Company 51 4.5 Sensitivity Analysis 63 Chapter 5 Conclusion and Future Research 66 5.1 Conclusion 66 5.2 Future Research 67 REFERENCES 69 Appendix.1 Baseline parameters for each problem size. 73 Appendix.2 Small size problem 26 factorial design experiments. 74 Appendix.3 Medium size problem 26 factorial design experiments. 75 Appendix.4 Large size problem 26 factorial design experiments. 76 Appendix.5 Three – dimensional graph of demand against other parameters. 77

    Aardal, K. (1998). Reformulation of capacitated facility location problems: How redundant information can help. Annals of Operations Research, 82(0), 289–308.
    Ai, T. J., & Kachitvichyanukul, V. (2009a). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36(5), 1693–1702.
    Ai, T. J., & Kachitvichyanukul, V. (2009b). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 56(1), 380–387.
    Aksen, D., & Aras, N. (2012). A bilevel fixed charge location model for facilities under imminent attack. Computers & Operations Research, 39(7), 1364–1381.
    Allahverdi, A., & Al-Anzi, F. S. (2006). A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application. Computers & Operations Research, 33(4), 1056–1080.
    Arnaout, J.-P. (2011). Ant colony optimization algorithm for the Euclidean location-allocation problem with unknown number of facilities. Journal of Intelligent Manufacturing, 24(1), 45–54.
    Boffey, B., Yates, D., & Galvao, R. D. (2003). An algorithm to locate perinatal facilities in the municipality of Rio de Janeiro. Journal of the Operational Research Society, 54(1), 21–31.
    Boloori Arabani, A., & Farahani, R. Z. (2012). Facility location dynamics: An overview of classifications and applications. Computers & Industrial Engineering, 62(1), 408–420.
    Chan, Y., Mahan, J. M., Chrissis, J. W., Drake, D. A., & Wang, D. (2008). Hierarchical maximal-coverage location-allocation: Case of generalized search-and-rescue. Computers and Operations Research, 35(6), 1886–1904.
    Chardaire, P., Lutton, J.-L., & Sutter, A. (1999). Upper and lower bounds for the two-level simple plant location problem. Annals of Operations Research, 86(0), 117–140.
    Chen, A., Yang, G., & Wu, Z. (2006). Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University SCIENCE A, 7(4), 607–614.
    Chiou, C.-W., & Wu, M.-C. (2009). A GA-Tabu algorithm for scheduling in-line steppers in low-yield scenarios. Expert Systems with Applications, 36(9), 11925–11933.
    Cınar, Y., & Yaman, H. (2011). The vendor location problem. Computers & Operations Research, 38(12), 1678–1695.
    Eberhart, R. C. (Purdue S. of E. and T., & Shi, Y. (EDS E. S. G. (2001). Particle swarm optimization: developments, applications and resources. In Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546) (Vol. 1, pp. 81–86). IEEE.
    Engelbrecht, A. P. (2006). Fundamentals of Computational Swarm Intelligence. Chicester, England: John Wiley & Sons.
    Farahani, R. Z., Hekmatfar, M., Arabani, A. B., & Nikbakhsh, E. (2013). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64(4), 1096–1109.
    Farahani, R. Z., Hekmatfar, M., Fahimnia, B., & Kazemzadeh, N. (2013). Hierarchical facility location problem: Models, classifications, techniques, and applications. Computers & Industrial Engineering.
    Ghaderi, A., Jabalameli, M. S., Barzinpour, F., & Rahmaniani, R. (2011). An Efficient Hybrid Particle Swarm Optimization Algorithm for Solving the Uncapacitated Continuous Location-Allocation Problem. Networks and Spatial Economics, 12(3), 421–439.
    Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning (p. 372). Boston, MA, USA: Publisher Addison-Wesley Longman Publishing Co., Inc.
    Hinojosa, Y., Puerto, J., & Fernandez, F. R. (2000). A multiperiod two-echelon multicommodity capacitated plant location problem. European Journal of Operational Research, 123(2), 271–291.
    Holland, J. H. (1975). Adaptation in Natural and Artificial Systems (p. 211). Ann Arbor: University of Michigan Press.
    Ignacio, A. A. V., Filho, V. J. M. F., & Galvao, R. D. (2008). Lower and upper bounds for a two-level hierarchical location problem in computer networks. Computers & Operations Research, 35(6), 1982–1998.
    Jin, Y.-X., Cheng, H.-Z., Yan, J., & Zhang, L. (2007). New discrete method for particle swarm optimization and its application in transmission network expansion planning. Electric Power Systems Research, 77(3-4), 227–233.
    Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN’95 - International Conference on Neural Networks (Vol. 4, pp. 1942–1948). IEEE.
    Khakmardan, S., & Poostchi, H. (2011). Solving Traveling Salesman Problem by a Hybrid Combination of, 1501–1507.
    Khatibzadeh, A. (2011). An improved Tabu search algorithm and PSO for unit commitment problem solving. Electrical Engineering (ICEE), 19th Iranian Conference, 19(May), 1–6.
    Kochetov, Y., & Goncharov, E. (2001). Probabilistic tabu search algorithm for the multi-stage uncapacitated facility location problem. Operations Research Proceedings, 2000, 65–70.
    Lee, J. M., & Lee, Y. H. (2010). Tabu based heuristics for the generalized hierarchical covering location problem. Computers & Industrial Engineering, 58(4), 638–645.
    Li, L., Yanyou, Q., Wei, L., & Basis, A. T. (2010). Overview of Optimization Algorithms in facility Allocation Problems, (Icnc), 1143–1147.
    Mandell, M. B. (1998). Covering models for two-tiered emergency medical services systems. Location Science, 6(1-4), 355–368.
    Mantawy, A., Abdel-Magid, Y., & Selim, S. (1998). Unit commitment by tabu search. IEE Proceedings - Generation, Transmission and Distribution, 145(1), 56 – 64.
    Mitchell, M. (1996). An Introduction to Genetic Algorithms (p. 205). MA, USA: Publisher MIT Press Cambridge.
    Obreque, C., Marianov, V., & Rios, M. (2008). Optimal design of hierarchical networks with free main path extremes. Operations Research Letters, 36(3), 366–371.
    Owen, S. H., & Daskin, M. S. (1998). Strategic facility location: A review. European Journal of Operational Research, 111(3), 423–447.
    Pirkul, H., & Jayaraman, V. (1998). A multi-commodity, multi-plant, capacitated facility location problem: formulation and efficient heuristic solution. Computers & Operations Research, 25(10), 869–878.
    Ponsich, A., & Coello Coello, C. a. (2013). A hybrid Differential Evolution—Tabu Search algorithm for the solution of Job-Shop Scheduling Problems. Applied Soft Computing, 13(1), 462–474.
    Rosendo, M., & Pozo, A. (2010). A hybrid Particle Swarm Optimization algorithm for combinatorial optimization problems. IEEE Congress on Evolutionary Computation, 1–8.
    Şahin, G., & Sural, H. (2007). A review of hierarchical facility location models. Computers & Operations Research, 34(8), 2310–2331.
    Serra, D. (1996). The Coherent Covering Location Problem. Papers in Regional Science, 75(1), 79–101.
    Sevkli, M., Mamedsaidov, R., & Camci, F. (2014). A novel discrete particle swarm optimization for p-median problem. Journal of King Saud University - Engineering Sciences, 26(1), 11–19.
    Sheu, J.-B., & Lin, A. Y.-S. (2012). Hierarchical facility network planning model for global logistics network configurations. Applied Mathematical Modelling, 36(7), 3053–3066.
    Shi, Y., & Eberhart, R. (1998a). A modified particle swarm optimizer. In 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360) (pp. 69–73). IEEE.
    Shi, Y., & Eberhart, R. (1998b). A modified particle swarm optimizer. In 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360) (pp. 69–73). IEEE.
    Tcha, D., & Lee, B. (1984). A branch-and-bound algorithm for the multi-level uncapacitated facility location problem. European Journal of Operational Research, 18(1), 35–43.
    Teixeira, J. C., & Antunes, A. P. (2008). A hierarchical location model for public facility planning. European Journal of Operational Research, 185(1), 92–104.
    Tragantalerngsak, S., Holt, J., & Ro‥nnqvist, M. (1997). Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem. European Journal of Operational Research, 102(3), 611–625.
    Vernekar, A., Anandalingam, G., & Dorny, C. N. (1990). Optimization of resource location in hierarchical computer networks. Computers & Operations Research, 17(4), 375–388.
    Victoire, T., & Jeyakumar, A. (2005). Unit commitment by a tabu-search-based hybrid-optimisation technique. IEE Proceedings - Generation, Transmission and Distribution, 152(4), 563.
    Wang, Y., Zhao, Z., & Ren, R. (2007). Hybrid particle swarm optimizer with tabu strategy for global numerical optimization. 2007 IEEE Congress on Evolutionary Computation, 2310–2316.
    Wang, Z., Du, D., Gabor, A. F., & Xu, D. (2010). An approximation algorithm for the -level stochastic facility location problem. Operations Research Letters, 38(5), 386–389.
    Widener, M. J., & Horner, M. W. (2011). A hierarchical approach to modeling hurricane disaster relief goods distribution. Journal of Transport Geography, 19(4), 821–828.
    Zeinal Hamadani, A., Abouei Ardakan, M., Rezvan, T., & Honarmandian, M. M. (2013). Location-allocation problem for intra-transportation system in a big company by using meta-heuristic algorithm. Socio-Economic Planning Sciences, 47(4), 309–317.
    Zhang, J. (2006). Approximating the two-level facility location problem via a quasi-greedy approach. Mathematical Programming, 108(1), 159–176.
    Zhang, X.-F., Koshimura, M., Fujita, H., & Hasegawa, R. (2011). An efficient hybrid particle swarm optimization for the Job Shop Scheduling Problem. In 2011 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2011) (pp. 622–626). IEEE.
    Zhihua, C. (2004). A new stochastic particle swarm optimizer. In Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753) (pp. 316–319). IEEE.

    QR CODE