簡易檢索 / 詳目顯示

回結果列表
研究生： Eki Ruskartina
Eki - Ruskartina
論文名稱： Symbiotic Organism Search (SOS) for Solving Capacitated Vehicle Routing Problem(CVRP)
Symbiotic Organism Search (SOS) for Solving Capacitated Vehicle Routing ProblemCVRP)
指導教授： 喻奉天
Vincent F. Yu
口試委員: 郭人介
Ren-Jieh Kuo
楊朝龍
Chao-Lung Yang
Budi Santosa
Budi Santosa
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2015
畢業學年度： 103
語文別： 英文
論文頁數： 54
外文關鍵詞： Symbiotic organism search, Capacitated vehicle routing problem, Metaheuristics.
相關次數： 點閱：262  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • This research introduces symbiotic organism search (SOS) for solving capacitated vehicle routing problem (CVRP). SOS is a new approach in metaheuristics fields and never been used to solve discrete problems. A sophisticated decoding method to deal with a discrete problem setting in CVRP is applied using the basic symbiotic organism search framework. The performance of the algorithm was evaluated on a set of benchmark instances and the result were compared with the basic SOS and best known solution. The computational results show that the proposed algorithm can produce good solution in reasonable computational time. These results indicated that the proposed SOS can be applied as an alternative algorithm to solve the CVRP.

    Master’s Thesis Recommendation Form…………………...…………………………ii Qualification Form by Master’s Degree Examination Committee…………………...iii ABSTRACT iv54 ACKNOWLEDGEMENT v TABLE OF CONTENTS vi LIST OF FIGURES viii LIST OF TABLES ix CHAPTER 1 INTRODUCTION 1 1.1 Background 1 1.2 Problem Statement 2 1.3 Objectives 3 1.4 Scope and Limitations 3 1.5 Organization 3 CHAPTER 2 LITERATURE REVIEW 5 2.1 Capacitated Vehicle Routing Problem 5 2.2 Metaheuristics approach for solving capacitated vehicle routing problem 6 2.3 Symbiotic Organism Search 17 CHAPTER 3 SOLUTION METHODOLOGY 20 3.1 Symbiotic Organism Search for Capacitated vehicle routing problem 20 3.2 Solution Representation 22 3.3 Movement Procedure 24 3.4 Local Search Procedure 28 CHAPTER 4 COMPUTATIONAL RESULT 32 4.1 Test Problem 32 4.2 Design of Experiment 32 4.3 Numerical Experiment 36 4.4 Comparison with BKS and PSO SR-1 38 CHAPTER 5 CONCLUSION AND RECOMMENDATION 41 5.1 Conclusion 41 5.2 Recommendation for future research 41 5.3 Contribution 41 REFERENCES 42 APPENDIX A THE 2k FACTORIAL DESIGN RESULT 45

    Ai, T. J. & V. Kachitvichyanukul (2009) Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 56, 380-387.
    Baker, B. M. & M. Ayechew (2003) A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30, 787-800.
    Berger, J. & M. Barkaoui. 2003. A hybrid genetic algorithm for the capacitated vehicle routing problem. In Genetic and Evolutionary Computation—GECCO 2003, 646-656. Springer.
    Bramel, J. & D. Simchi-Levi (1995) A location based heuristic for general routing problems. Operations research, 43, 649-660.
    Bullnheimer, B., R. F. Hartl & C. Strauss (1999) An improved ant System algorithm for thevehicle Routing Problem. Annals of operations research, 89, 319-328.
    Cheng, M.-Y. & D. Prayogo (2014) Symbiotic Organisms Search: A new metaheuristic optimization algorithm. Computers & Structures, 139, 98-112.
    Christofides, N. 1979. Combinatorial optimization. In A Wiley-Interscience Publication, Based on a series of lectures, given at the Summer School in Combinatorial Optimization, held in Sogesta, Italy, May 30th-June 11th, 1977, Chichester: Wiley, 1979, edited by Christofides, Nicos.
    Christofides, N., A. Mingozzi & P. Toth (1981) Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Mathematical programming, 20, 255-282.
    Clarke, G. u. & J. W. Wright (1964) Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12, 568-581.
    Colorni, A., M. Dorigo, V. Maniezzo & M. Trubian (1994) Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 34, 39-53.
    Dantzig, G. B. & J. H. Ramser (1959) The truck dispatching problem. Management science, 6, 80-91.
    Dorigo, M. & L. M. Gambardella (1997) Ant colonies for the travelling salesman problem. BioSystems, 43, 73-81.
    Fisher, M. L. & R. Jaikumar (1981) A generalized assignment heuristic for vehicle routing. Networks, 11, 109-124.
    Gendreau, M., A. Hertz & G. Laporte (1994) A tabu search heuristic for the vehicle routing problem. Management science, 40, 1276-1290.
    Gillett, B. E. & L. R. Miller (1974) A heuristic algorithm for the vehicle-dispatch problem. Operations research, 22, 340-349.
    Lenstra, J. K. & A. Kan (1981) Complexity of vehicle routing and scheduling problems. Networks, 11, 221-227.
    Marinakis, Y., M. Marinaki & G. Dounias (2010) A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence, 23, 463-472.
    Mazzeo, S. & I. Loiseau (2004) An Ant Colony Algorithm for the Capacitated Vehicle Routing. Electronic Notes in Discrete Mathematics, 18, 181-186.
    Mester, D. & O. Bräysy (2005) Active guided evolution strategies for large-scale vehicle routing problems with time windows. Computers & Operations Research, 32, 1593-1614.
    Mole, R. & S. Jameson (1976) A sequential route-building algorithm employing a generalised savings criterion. Operational Research Quarterly, 503-511.
    Osman, I. H. (1993) Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of operations Research, 41, 421-451.
    Robust, F., C. F. Daganzo & R. R. Souleyrette (1990) Implementing vehicle routing models. Transportation Research Part B: Methodological, 24, 263-286.
    Rochat, Y. & É. D. Taillard (1995) Probabilistic diversification and intensification in local search for vehicle routing. Journal of heuristics, 1, 147-167.
    Szeto, W. Y., Y. Wu & S. C. Ho (2011) An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215, 126-135.
    Talbi, E.-G. 2009. Metaheuristics: from design to implementation. John Wiley & Sons.
    Toth., P., Vigo, D. (Eds.), 2002. The Vehicle Routing Problem. SIAM Society for Industrial and Applied Mathematics, Philadelphia.
    Wren, A. & A. Holliday (1972) Computer scheduling of vehicles from one or more depots to a number of delivery points. Operational Research Quarterly, 333-344.
    Yu, B., Z.-Z. Yang & B. Yao (2009) An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 196, 171-176

    無法下載圖示 全文公開日期 2017/07/08 (校內網路)
    全文公開日期 本全文未授權公開 (校外網路)
    全文公開日期 本全文未授權公開 (國家圖書館：臺灣博碩士論文系統)
    QR CODE