簡易檢索 / 詳目顯示

回結果列表
研究生： 王詠賢
Yung-Hsien Wang
論文名稱： 研究改良式帝國主義競爭演算法於物流管理中具容量限制之車輛運途問題
On the Study of Improved Imperialist Competitive Algorithm to Solve the Capacitated Vehicle Routing Problem in Logistics Management
指導教授： 羅士哲
Shih-Che Lo
口試委員: 蔡鴻旭
Hung-Hsu Tsai
楊朝龍
Chao-Lung Yang
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2013
畢業學年度： 101
語文別： 英文
論文頁數： 74
中文關鍵詞： 精實物流運籌 、帝國主義競爭演算法 、車輛運途 、掃描法
外文關鍵詞： Lean logistics, Imperialist competitive algorithm, Vehicle routing problem, Sweep method
相關次數： 點閱：269  下載：8 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 企業在現今激烈的競爭環境下想要增加獲利，除了提高銷售量及降低生產成本外，另一方面就是提升物流的效率。因此，企業必須提供有效率的物流運籌網路來因應快速的顧客回應需求，而導入精實物流的概念被視為是減少車子的派遣進而降低公司的固定成本的新思維。精實概念與車輛途程問題結合後，最主要的貢獻就是有效減少車子數，並且最小化車輛路徑距離，減少運輸時間的浪費。
    本研究提出基植於帝國主義競爭演算法結合掃描法的改良式帝國主義競爭演算法（IICA），對具有容量限制的車輛途程問題快速提出一個近似最佳解，主要目標在於滿足所有限制條件下，達到總成本（運輸及營運）的最小化。為了驗證所提出IICA演算法的效能，本研究與基因演算法做比較，求解60組不同車輛容量下運途的標竿問題，在每一組標竿問題中，本研究的IICA演算法都能找出比基因演算法更好的最佳成本解，總平均成本改善率達到7.78%。相較於基因演算法，我們所提出的IICA演算法呈現出具有相當穩健且有效搜尋全局最佳解的能力，且能更快收斂到較佳的解。

    Enterprises want to make profits in the extremely competitive environment. In addition to expanding sales and reducing manufacturing cost, the efficiency of logistics management is also considered as the additional source of profit. Increasing efficiency of logistics becomes critical in the supply chain due to customer’s quick response requirements. Therefore, lean logistics is considered a new thinking to decrease the number of the dispatched vehicles and reduce the fixed cost of the company. This thesis focuses on the vehicle routing problem with lean principles aiming at finding the shortest routes by using the minimum number of vehicles and shortest travel distance.
    A novel algorithm, called the Improved Imperialist Competitive Algorithm (IICA), is proposed in thesis to solve the combinatorial optimal solution for the Capacitated Vehicle Routing Problem. The IICA method is based on the new developed Imperialist Competitive Algorithm combined with the sweep method to quickly generate a near optimum solution. Comparisons are made between the IICA method and the Genetic Algorithm (GA) over the experiments of different capacitated benchmark problems to validate the performance of the IICA. Experiment results show that the IICA was able to discover new solutions than the GA for all 60 benchmarks problems. Also, the computational results show that the IICA is robust, converge fast and competitive with overall improvement of 7.78% over the GA.

    摘要 ABSTRACT ACKKNOWLEDGEMENTS CONTENTS FIGURES TABLES CHAPTER 1 INTRODUCTION 1.1 Research Motivation 1.2 Objectives 1.3 Research Structure CHAPTER 2 LITERATURE REVIEW 2.1 Logistics Management 2.2 Vehicle Routing Problem 2.2.1 VRP Problems with Various Constraints 2.2.2 Different Methods for the VRP Problems 2.3 The GA and the AIS 2.3.1 Genetic Algorithms 2.3.2 Artificial Immune System 2.4 Imperialist Competitive Algorithm (ICA) 2.4.1 The Basis of Imperialist Competitive Algorithm 2.4.2 The GA and the ICA CHAPTER 3 PROBLEM FORMULATION AND IMPERIALIST COMPETITIVE ALGORITHM 3.1 Problem Proposition 3.2 The Sweep Method 3.3 The General ICA Procedure 3.3.1 Solution Representations 3.3.2 Power Evaluation 3.3.3 Generating Initial Empires 3.3.4 Moving the Colonies of an Empire toward the Imperialist 3.3.5 Exchange Position of the Imperialist and Colony 3.3.6 Total Power of an Empire 3.3.7 Imperialistic Competition 3.3.8 Eliminating the Powerless Empires 3.3.9 Convergence 3.4 The Proposed IICA for the CVRP 3.4.1 Solution Representations 3.4.2 Assimilation CHAPTER 4 COMPUTATIONAL EXPERIMENTS 4.1 Preliminary Test 4.2 Computational Results 4.3 Summary CHAPTER 5 COCLUSIONS AND FUTURE RESEARCH 5.1 Conclusions 5.2 Future Research REFERENCES Appendix A. Comparisons between the IICA and the GA in different capacities. Appendix B. Comparisons between the IICA and the GA in the large capacity. Appendix C. The results of the IICA for instance 5G3. Appendix D. The results of the IICA for instance 19G3. Appendix E. The results of the IICA for instance 23G3. Appendix F. The results of the IICA for instance 60G3.

    Aguilar-Escobar, V. G., & Garrido-Vega, P. (2013). Lean logistics management in healthcare: A case study. Revista de Calidad Asistencial, 28(1), 42-49.
    Ai, T. J., & Kachitvichyanukul, V. (2009). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 56(1), 380-387
    Anbuudayasankar, S. P., Ganesh, K., Lenny Koh, S.C., & Ducq, Y. (2012). Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls. Expert Systems with Applications, 39(3), 2296-2305.
    Apte, U. M., & Viswanathan, S. (2002). Strategic and technological innovations in supply chain management. International Journal of Manufacturing Technology and Management, 4, 264-282.
    Atashpaz-Gargari, E., Hashemzadeh, F., & Lucas, C. (2008). Designing MIMO PIID controller using colonial competitive algorithm: Applied to distillation column process. Proceeding of IEEE CEC 2008, within IEEE WCCI 2008, Hong Kong, 1929-1934.
    Atashpaz-Gargari, E., & Lucas, C. (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress on Evolutionary Computation, 4661-4667.
    Baldacci, R., Hadjiconstantinou, E., & Mingozzi, A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations Research, 52, 723-738.
    Balinski, M., & Quandt, R. (1964). On an integer program for a delivery problem. Operations Research, 12, 300-304.
    Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem, Computers & Operations Research, 30(5), 787-800.
    Behnamian, J., & Zandieh, M. (2011). A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties. Expert Systems with Applications, 38(12), 14490-14498.
    Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1), 41-48.
    Biabangard-Oskouyi, A., Atashpaz-Gargari, E., Soltani, N., & Lucas, C. (2009). Application of imperialist competitive algorithm for materials property characterization from sharp indentation test. International Journal of Engineering Simulation, 10(1).
    Cai, X., Chen, J., Xiao, Y., Xu, X., & Yu, G. (2013). Fresh-product supply chain management with logistics outsourcing. Omega, 41(4), 752-765.
    Chen, J. W., Zhang, Y. B., & Wang, G.J. (2011). A new algorithm for a fuzzy vehicle routing and scheduling problem: Imperialist competitive algorithm. Journal of Convergence Information Technology, 6(7), 303-311.
    Chen, N., & Xue, H. (2012). The study on the performance evaluation of the lean supply chain in chain retailers. Proceedings - 2012 International Conference on Computer Science and Service System, CSSS 2012, 1393-1396.
    Christofides, N., & Eilon, S. (1969) An algorithm for the vehicle dispatching problem. Operational Research Quarterly, 20, 309-318.
    Christofides, N., Mingozzi A., & Toth P. (1981a). Exact algorithms for the vehicle routing problem, based on spanning tree shortest path relaxations. Mathematical Programming, 20, 255-282.
    Christofides N., Mingozzi, A., & Toth, P. (1981b). Space state relaxation procedures for the computation of bounds to routing problems. Networks, 11, 145-164.
    Christopher, M., (1985). Logistics and supply chain management: strategies for reducing cost and improving customer service, Pitman Publishing, Singapore.
    Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568-581.
    Dantzig G. B., Fulkerson D. R., & Johnson S. M. (1954). Solution of a large-scale travelling-salesman problem. Operations Research, 2, 393-410.
    Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem, Management Science, 6(1), 80-91.
    Dasgupta, D. (1998). Artificial immune system as a multi-agent decision support system. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 4, 3816-3820.
    de Castro, L. N., & Timmis, J. (2002). Artificial Immune Systems: A New Computational Intelligence Approach. Springer, 57-58.
    Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical Computer Science, 344(2-3), 243-278.
    Dueck, G. (1993). New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104, 86-92.
    Dueck, G., & Scheurer, T. (1990). Threshold accepting: A general purpose optimization algorithm. Journal of Computational Physics, 90, 161-175.
    Eilon, S., Watson-Grandy, C. D. T., & Christofides, N. (1971). Distribution Management: Mathematical Modelling and Practical Analysis, Griffin, London.
    Ergun, O., Orlin, J. B., & Steele-Feldman, A. (2006). Creating very large-scale neighbourhoods out of smaller ones by compounding moves. Journal of Heuristics, 12, 115-140.
    Farmer, J. D., Packard, N. H., & Perelson, A. S. (1986). The immune system, adaption, and machine learning. Proceedings of the 5th Annual International Conference, 22, 187-204.
    Finke, G. A., Claus, A., & Gunn, E. (1984). A two-commodity network flow approach to the traveling salesman problem. Congressus Numerantium, 41, 167-178.
    Fisher, M., & R. Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11, 109-124.
    Forouharfard, S., & Zandieh, M. (2010). An imperialist competitive algorithm to schedule of receiving and shipping trucks in cross-docking systems. International Journal of Advanced Manufacturing Technology, 51(9-12), 1179-1193.
    Forrest, S., Perelson, A.S., Allen, L., & Cherukuri, R. (1994). Self-nonself discrimination in a computer. IEEE Symposium on Research in Security and Privacy, Oakland CA, 202-212.
    Gavish, B., & Graves, S. C. (1979). The Travelling Salesman Problem and Related Problems. Working Paper no. 7905, Graduate School of management, University of Rochester, Rochester, NY.
    Gendreau, M., Hertz, A., & Laporte, G. (1994). A Tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276-1290.
    Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle dispatch problem. Operations Research, 22, 340-349.
    Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13, 533-549.
    Haghani, A., & Jung, S. (2005). A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 32(11), 2959-2986.
    Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, MI.
    Hsieh, P. F. (2003). Basic information of warehousing and logistics industries. Taiwan Institute of Economic Research, December 16.
    Hunt, J., Timmis, J., Cooke, D., Neal, M., & King, C. (1999). Jisys: Development of an artificial immune system for real world applications, Springer-Verlag ,157-186.
    Hwang, H. S. (2002). An improved model for vehicle routing problem with time constraint based on genetic algorithm. Computers & Industrial Engineering, 42(2-4), 361-369
    Jasour, A. M., Atashpaz-Gargari, E., & Lucas, C. (2008). Vehicle fuzzy control using imperialist competitive algorithm. In Second iranian joint congress on fuzzy and intelligent systems (IFIS 2008), Tehran, Iran.
    Javadian, N., Khorshidian, H., Rezaeian, J., & Rahmani, K. (2011). Single machine preemptive scheduling by hybridized meta-heuristic approach. 2011 IEEE 3rd International Conference on Communication Software and Networks (ICCSN), 750-753.
    Jerne, N.K. (1974). Towards a network theory of the immune system. Annual Immunology, 125c, 373-389.
    Kennedy, J., & Eberhart, R. C. (1995). Particle Swarm Optimization. Proc. IEEE International Conference on Neural Networks. IEEE Service Center, Piscataway, NJ, 4, 1942-1948.
    Kephart, J. O. (1994). A biologically inspired immune system for computers. Proceedings of Artificial Life IV: The Fourth International Workshop on the Synthesis and Simulation of Living Systems, 130-139.
    Khabbazi, A., Atashpaz-Gargari, E., & Lucas, C. (2009). Imperialist competitive algorithm for minimum bit error rate beamforming. International Journal of Bio-Inspired Computation, 1(1-2), 125-133.
    Kirkpatrick, S., Gelatt Jr., C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671-680.
    Kuo, R. J., Tseng, W. L., Tien, F. C., & Warren Liao, T. (2012). Application of an artificial immune system-based fuzzy neural network to a RFID-based positioning system. Computers & Industrial Engineering, 63(4), 943-956.
    Lalonde, B. J., & Zinszer, P. H. (1976). Customer service: Meaning and measurement, National Council of Physical Distribution Management, USA.
    Laporte, G., & Nobert, Y. (1983). A branch and bound algorithm for the capacitated vehicle routing problem. Operations Research Spektrum, 5, 77-85.
    Laporte, G., Nobert, Y., & Desrochers, M. (1984). Optimal routing under capacity and distance restrictions. Operations Research, 33(5), 1050-1073.
    Laporte, G., & Nobert, Y. (1987). Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics, 31, 147-184.
    Laporte, G. (1991). The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59, 345-358.
    Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography. Annals of Operations Research, 61, 227-262.
    Laporte, G. (2009). A concise guide to the traveling salesman problem. Journal of the Operational Research Society, forthcoming.
    Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43 (4), 408-416.
    Lin, S. W., Lee, Z. J., Ying, K. C., & Lee, C. Y. (2009). Applying hybrid meta-heuristics for capacitated vehicle routing problem. Expert Systems with Applications, 36(2), 1505-1512.
    Mazzeo, S., & Loiseau, I. (2004). An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Mathematics, 18(1), 181-186.
    Mingyong, L., & Erbao, C. (2010). An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence, 23(2), 188-195.
    Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24, 1097-1100.
    Mosheiov, G. (1998). Vehicle routing with pick-up and delivery: tour partitioning heuristics, Computers & Industrial Engineering, 34(3), 669-684.
    Ochi, L. S., Vianna, D. S., Drummond L. M. A., & Victor, A. O. (1998). An evolutionary hybrid metaheuristic for solving the vehicle routing problem with heterogeneous fleet. Lecture Notes in Computer Science, 1391, 187-195.
    Osman, I.H. (1993). Metastrategy simulated annealing and Tabu search algorithms for the vehicle routing problem. Operations Research, 41, 421-451.
    Purnomo, H. D., Wee, H. M., & Praharsi, Y. (2012). Two inventory review policies on supply chain configuration problem. Computers & Industrial Engineering, 63(2), 448-455.
    Rajabioun, R., Atashpaz-Gargari, E., & Lucas, C. (2008). Colonial competitive algorithm as a tool for nash equilibrium point achievement. Lecture Notes in Computer Science, 5073, 680-695.
    Rajabioun, R., Hashemzadeh, F., Atashpaz-Gargari, E., Mesgari, B., & Rajaei Salmasi, F. (2008). Identification of a MIMO evaporator and its decentralized PID controller tuning using colonial competitive algorithm. Proceedings of the 17th World Congress, the International Federation of Automatic Control, Seoul, Korea, July 6-11, 2008, 9952-9957.
    Reimann, M., Doerner, K., & Hartl, R.F. (2004). D-Ants: Savings based ants divide and conquer the vehicle routing problem, Computers & Operations Research, 31, 563-591.
    Ropke, S., & Pisinger, D. (2006). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171, 750-775.
    Salhi, S., & Nagy, G. (1999).A cluster insertion heuristic for the single and multiple depot vehiclerouting problems with backhauls. Journal of the Operational Research Society, 50(10), 1034-1042.
    Szeto, W. Y., Wu, Y., & Ho, S. C. (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1), 126-135.
    Solakivi, T., Toyli, J., & Ojala, L. (2013). Logistics outsourcing, its motives and the level of logistics costs in manufacturing and trading companies operating in Finland. Production Planning & Control, 24(4-5), 388-398.
    Tavakkoli-Moghaddam, R., Safaei, N., & Gholipour, Y. (2006). A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 176(2), 445-454.
    Taillard, E. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23(8), 661-673.
    Thompson, P. M., & Psaraftis, H. M. (1993). Cyclic transfer algorithms for multi-vehicle routing and scheduling problems. Operations Research, 41, 935-946.
    Toth, P., & Vigo, D. (2001). The vehicle routing problem. Monographs on Discrete Mathematics and Applications, Philadelphia, PA: SIAM.
    Van Breedam, A. (2002). A parametric analysis of heuristics for the vehicle routing problem with side-constraints. European Journal of Operational Research, 137(2), 348-370.
    Wang, G. J., Zhang, Y. B., & Chen, J. W. (2011). A novel algorithm to solve the vehicle routing problem with time windows: Imperialist competitive algorithm. Advances in Information Sciences and Service Sciences, 3(5), 108-116.
    Wu, T. H., Chung, S. H., & Chang, C. C. (2010). A water flow-like algorithm for manufacturing cell formation problems. European Journal of Operational Research, 205(2), 346-360.
    Yang, F. C., & Wang, Y. P. (2007). Water flow-like algorithm for object grouping problems. Journal of the Chinese Institute of Industrial Engineers, 24(6), 475-488.
    Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2010). An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries. European Journal of Operational Research, 202(2), 401-411.
    Zhen, Y. R., Huang, J. C., Li, W. Y., Li, F. X., & Zhang, Y. (2013). The planning of the dynamic path of the 3rd party logistics center, which based on the ant colony optimization. Applied Mechanics and Materials, 253-255, 1472-1475.

    QR CODE