簡易檢索 / 詳目顯示

回結果列表
研究生： Ferani Eva Zulvia
Ferani - Eva Zulvia
論文名稱： 混合粒子群最佳化與基因演算法於具模糊需求之容量限制車輛途程問題之求解-以垃圾收集系統為例
A Hybrid Particle Swarm Optimization with Genetic Algorithm for Solving Capacitated Vehicle Routing Problem with Fuzzy Demand – A Case Study on Garbage Collection System
指導教授： 郭人介
Ren-Jieh Kuo
口試委員: 喻奉天
Vincent F. Yu
許鉅秉
Jiuh-Biing Sheu
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2010
畢業學年度： 98
語文別： 英文
論文頁數： 134
中文關鍵詞： Hybrid PSO and GA 、CVRP 、fuzzy demand
外文關鍵詞： Hybrid PSO and GA, CVRP, fuzzy demand
相關次數： 點閱：201  下載：11 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • This research proposes a Hybrid Particle Swarm Optimization (PSO) with Genetic Algorithm (GA) for solving Capacitated Vehicle Routing Problem (CVRP) and CVRP with Fuzzy Demand (CVRPFD). The CVRPFD is developed using Change Constraint Program model with credibility measurement. The proposed method uses the idea of particle’s best solution and social’s best solution in PSO algorithm, followed by combining it with crossover and mutation of GA. This method also modifies the particle’s coding to ensure particle always can generate feasible solution. The proposed method is evaluated by using nine benchmark data sets for CVRP and garbage collection system data for CVRPFD. The results indicate that the proposed Hybrid PSO with GA has promising performance for solving CVRP and CVRPFD. It not only can obtain better solutions, but also only requires small number of particles and iterations.

    This research proposes a Hybrid Particle Swarm Optimization (PSO) with Genetic Algorithm (GA) for solving Capacitated Vehicle Routing Problem (CVRP) and CVRP with Fuzzy Demand (CVRPFD). The CVRPFD is developed using Change Constraint Program model with credibility measurement. The proposed method uses the idea of particle’s best solution and social’s best solution in PSO algorithm, followed by combining it with crossover and mutation of GA. This method also modifies the particle’s coding to ensure particle always can generate feasible solution. The proposed method is evaluated by using nine benchmark data sets for CVRP and garbage collection system data for CVRPFD. The results indicate that the proposed Hybrid PSO with GA has promising performance for solving CVRP and CVRPFD. It not only can obtain better solutions, but also only requires small number of particles and iterations.

    ABSTRACT i ACKNOWLEDGEMENT ii CONTENTS iii LIST OF FIGURES vi LIST OF TABLES vii Chapter 1 INTRODUCTION 1 1.1. Research Background 1 1.2. Research Objectives 2 1.3. Research Scopes and Constraints 2 1.4. Research Framework 3 Chapter 2 LITERATURE STUDY 5 2.1. Vehicle Routing Problem (VRP) 5 2.1.1 Definition of Capacitated Vehicle Routing Problem (CVRP) 6 2.1.2 Dynamic Vehicle Routing Problem (VRP) 8 2.2. VRP Methods 9 2.2.1. Exact Method 9 2.2.2. Heuristics Method 10 2.2.3. Meta-Heuristics Method 12 2.3. Genetic Algorithm (GA) 15 2.4. Particle Swarm Optimization (PSO) to Solve CVRP 16 2.4.1. Basic Concept and Original Algorithm of PSO 16 2.4.2. Discrete Binary PSO 18 2.5. Fuzzy Sets Theory 18 2.5.1. Basic Concept of Fuzzy Sets 18 2.5.2. Fuzzification 21 2.5.3. Fuzzy Comparison 21 Chapter 3 RESEARCH METHODOLOGY 24 3.1. Problem Determination 25 3.2. CVRP Model Development 26 3.3. Hybrid PSO with GA for CVRP Development 28 3.4. PSO, GA and Hybrid PSO with GA for CVRPFD Development 31 3.4.1. PSO for CVRPFD 33 3.4.2. GA for CVRPFD 34 3.4.3. Hybrid PSO with GA for CVRPFD 35 Chapter 4 COMPUTATIONAL RESULTS FOR SOLVING CVRP 38 4.1. Experimental Setup 38 4.2. Computational Result 42 4.3. Statistical Test 45 4.4. Comparing with Other Hybrid Methods 46 Chapter 5 COMPUTATIONAL RESULT AND ANALYSIS OF APPLYING PSO, GA AND HYBRID PSO WITH GA FOR SOLVING CVRPFD 48 5.1. Data 48 5.2. Experimental Setup 49 5.3. Computational Result 50 5.4. Investigate Mean Differences 54 5.5. Application in Real Case 55 5.6. Sensitivity Analysis 59 5.6.1. Sensitivity Analysis of Dispatcher Preference Index 59 5.6.2. Sensitivity Analysis of Vehicle Capacity 60 Chapter 6 CONCLUSION AND FUTHER RESEARCH 62 6.1. Conclusion 62 6.2. Contributions 62 6.3. Future Research 63 REFERENCES 64 Appendix I PSEUDOCODE 68 Appendix II GENERAL FACTORIAL DESIGN OF DETERMINING TUNING PARAMETERS FOR SOLVING CVRP 72 Appendix III COMPUTATIONAL RESULT OF CVRP SOLUTION 81 Appendix IV STATISTICAL TEST RESULT OF CVRP 88 Appendix V RESULTS OF HYBRID PSO WITH GA FOR SOLVING OTHER BENCHMARK DATA SETS 91 Appendix VI GENERAL FACTORIAL DESIGN OF DETERMINING TUNING PARAMETERS FOR SOLVING CVRPFD 92 Appendix VII COMPUTATIONAL RESULTS OF CVRPFD 106 Appendix VIII STATISTICAL TEST RESULT OF CVRPFD 116 Appendix IX CUMPUTATIONAL RESULT AND STATISTICAL TEST RESULT FOR ANALYSIS SENSITIVITY OF DISPATCHER PREFERENCE INDEX 121 Appendix X COMPUTATIONAL RESULT FOR ANALYSIS SENSITIVITY OF VEHICLE CAPACITY 127

    Aarts, E.L.H. and H.M.M.T. Eikelder. (2002). “Simulated annealing”. In P. M. Pardalos and M.G.C. Resende (Eds), Handbook of Applied Optimization. New York: Oxford University Press.

    Ai, T.J. and V. Kachitvichyanukul. (2009). “A particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery”. Computers and Operations Research, 36( 5), 1693-1702.

    Bramel and S. Levi. (2002). “Set-covering-based algorithm for capacitated VRP”. In P. Toth and D. Vigo (Eds). The Vehicle Routing Problem. Bologna: Society for Industrial and applied mathematics.

    Beasley, J.E., a. Lucena, and M.P. Aragao. (2002). “The vehicle routing problem”. In P. M. Pardalos and M.G.C. Resende (Eds). Handbook of Applied Optimization. New York: Oxford University Press.

    Chen, C.T. (1998). “A fuzzy approach to select the location of the distribution center”. Fuzzy Sets and System,118(1), 65-73.

    Chen, A., Yang G., and Wu Z. (2006). “Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem”. Journal of Zhejiang University – Science A, 7(4), 607-614.

    Dantzig, G., R Fulkerson and S. Johnson. (1954). “Solution of a large-scale travelling salesman problems”. Journal of The Operations Research Society of America, 2(4), 393-410.

    Dantzig, G.B. and J.H. Ramser. (1959). “The truck dispatching problem”. Management Science, 6(1), 80-91.

    Engelbrecht, A.P. (2007). Computational Intelligence, an Introduction. Second Edition. Chichester: John Wiley & Sons Ltd.

    Eksioglu, B., A.V. Vural, and A. Reisman. (2009). “Survey the vehicle routing problem: a taxonomic review”. Computers and Industrial Engineering, 57(4), 1472-1483.

    Erbao, C. and L. Mingyong. (2009).“A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demand”. Journal of Computational and Applied Mathematics, 231(1), 302-310.

    Fukuyama, H. (2008). “Fundamentals of Particle Swarm Optimization Techniques”. In K.Y. Lee and M.A. El-sharkawi (Eds). Modern Heuristics Optimization Techniques. New jersey: John Wiley & sons, Inc.

    Goncalves, G., T. Hsu and J. Xu. (2009). “Vehicle routing problem with time windows and fuzzy demand: an approach based on the possibility theory”. International Journal of Advance Operations Management, 1(4), 312-320.

    Gendreau, M., G. Laporte, and J-Y. Potvin. (2002). “Metaheuristics for capacitated VRP”. In P. Toth and D. Vigo (Eds). The Vehicle Routing Problem. Bologna: Society for Industrial and applied mathematics.

    Hanshar, F.T. and Ombuki-Berman B.M. (2007). “Dynamic vehicle routing using genetic algorithms”. Applied Intelligence, 27(1), 89-99.

    Kennedy, J. and R.C. Eberhart. (1995). “Particle swarm optimization”. Proceeding of International conference of Neural Networks, Washington, USA, Nov, 27th – Des, 1st, 1995.

    Kennedy, J. and R.C. Eberhart. (1997). “A discrete binary version of the particle swarm optimization”. Proceeding IEEE International conference of System, Man, and Cybernetics and Simulation, Orlando, FL, USA, October, 12th – 15th, 1997.

    Kuo, R.J., Y. Chiu, and Y.J. Lin. (2004). “Integration of fuzzy theory and ant algorithm for vehicle routing problem with time window”. Proceeding of Annual Conference of the North American Fuzzy Information Processing Society, Alberta, Canada, June, 27th – 30th, 2004.

    Laporte, G. and F. Semet. (2002). “Classical heuristics for the capacitated VRP”. In P. Toth and D. Vigo (Eds). The Vehicle Routing Problem. Bologna: Society for Industrial and applied mathematics.

    Lee, E. (2002). “Branch-and-bound methods”. In P. M. Pardalos and M.G.C. Resende (Eds). Handbook of Applied Optimization. New York: Oxford University Press.

    Liu, B. (2006). “A survey of credibility theory”. Fuzzy Optimization and Decision Making, 5(4), 387-408.

    Liu, B., L. Wang and Y.H. Jin. (2008). “An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers”. Computers and Operations Research, 35(9), 2791-2806.

    Malekly, H., B. Haddadi, and R.T. Moghadam. (2009). “A fuzzy random vehicle routing problem: the case of Iran”. Proceedings of International Conference of Computer and Industrial Engineering, Troyes, July, 6th-9th, 2009.

    Marcovi, H., I. Cavar and T. Caric. (2005). “Using data mining to forecast uncertain demands in stochastic vehicle routing problem”. European Journal of Operation Research, 196(2), 509-515.

    Marinakis, Y. and M. Marinaki. (2010). “A hybrid genetic-particle swarm optimization algorithm for the vehicle routing problem”. Expert System with Application, 37(2), 1446-1455.

    Moghadam, B.F. and S.M. Seyedhosseini. (2010). “A particle swarm approach to solve Vehicle routing problem with uncertain demand: a drug distribution case study”. International Journal of Industrial and Engineering Computations, 1, 55-64.

    Montemanni, R., R.M. Gambardella, A.E. Rizzolli, and A.V. Donati. (2005). “Ant colony system for a dynamic vehicle routing problem”. Journal of Combinatorial Optimization, 10(4), 327-343.

    Psaraftis, H.N. (1988). “Dynamic vehicle routing: status and prospect”. Annals of Operations Research, 61(1), 143-164.

    Pang, W., K. Wang, C. Zhou, and L. Dong. (2004). “Fuzzy discrete particle swarm optimization for solving travelling salesman problem”. Proceedings of the Fourth International Conference on Computer and Information Technology, Wuhan, China, September, 14th-16th, 2004.

    Powell, W.B., P. Jaillet, and A. Odoni. (1995). “Stochastic and dynamic networks and routing”. Handbooks in Operational Research and Management Science. Amsterdam: Elsevier.

    Rardin, R.L. (2000). Optimization in Operations Research. New Jersey: John Wiley & sons, Inc.

    Sarker, R.A. and C.S. Newton. (2008). “Optimization Modeling”. A Practical Approach. New York: Taylor & Francis Group.

    Shao, Z.J., S.P. Gao, and S.S. Wang. (2009). “A hybrid particle swarm optimization algorithm for vehicle routing problem with stochastic travel time”. In Fuzzy Information and Engineering. Heidelberg: Springer Berlin.

    Shin, Y.C. and C. Xu. (2009). Automation and Control Engineering Series, Intelligent System: Modeling, Optimization and Control. New York: CRC Press.

    Shi, Y. and R.C. Eberhart. (1998). “Parameter selection in particle swarm optimization”. IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, may 4th-9th, 1998.

    Talbi, E. (2009). Metaheuristicss from Design to Implementation. New jersey: John Wiley & sons, Inc.

    Teodorovic, D. and G. Pavkovickm. (1996). “The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertainty”. Fuzzy Sets and System, 82(3), 307-317.

    Tilman, F. (1969). “The multiple terminal delivery problem with probabilistic demands”. Transportation Science, 3(3), 192-204.

    Toth, P. and D. Vigo. (2002a). “An overview of vehicle routing problem”. In P. Toth and D. Vigo (Eds). The Vehicle Routing Problem. Philadelphia: Society for Industrial and applied mathematics.

    Toth, P. and D. Vigo. (2002b). “Models, relaxations, and exact approaches for the capacitated vehicle routing problem”. Discrete Applied Mathematics, 123(1), 487-512.

    Vigo, D. (1996). “A heuristics algorithm for asymmetric capacitated vehicle routing problem”. European Journal of Operational Research, 89(1), 108-126.

    Warnes, B and M. Drawe. (2003). “Capacitated vehicle routing problem with fuzzy demand”. In J.L. Verdegay (Eds). Fuzzy Sets Based Heuristic for Optimization. New York: Springer.

    Waters, C.D.J. (1989). “Vehicle-scheduling problems with uncertainty and omitted customers”. Journal of the Operations Research Society, 40(12), 1099-1108.

    Zadeh, L.A. (1965). “Fuzzy sets”. Information and Control, 8(3), 338-353.

    Zheng, Y. and B. Liu, 2006, “Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm”. Applied Mathematics and Computation, 176(2), 673-683.

    QR CODE