簡易檢索 / 詳目顯示

回結果列表
研究生： 莊英林
Ying-Lin Chuang
論文名稱： 研究兩階段人工免疫系統演算法於物流管理中具接駁式轉運之車輛運途問題
On the Study of Two-stage Artificial Immune System to Solve the Vehicle Routing Problem with Cross-Docking in Logistics Management
指導教授： 羅士哲
Shih-Che Lo
口試委員: 蔡鴻旭
Hung-Hsu Tsai
楊朝龍
Chao-Lung Yang
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2012
畢業學年度： 100
語文別： 英文
論文頁數： 71
中文關鍵詞： 接駁式轉運 、物流運籌 、人工免疫系統演算法 、車輛運途 、掃描法
外文關鍵詞： Cross-docking; Logistics; Artificial immune syst
相關次數： 點閱：243  下載：4 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 企業在現今激烈的競爭環境下想要增加獲利，除了提高銷售量及降低生產成本外，另一方面就是提升物流的效率。因此，企業必須提供有效率的物流運籌網路來因應快速的顧客回應需求，而導入接駁式轉運中心(cross-docking, CD)的物流運籌網路，被視為是減少存貨和快速回應顧客多樣需求的好方法。接駁式轉運中心與車輛途程問題(vehicle routing problem, VRP)結合後，最主要的概念就是讓車隊於取貨(pickup)及送貨(delivery)的過程中同時抵達，避免轉運中心有存貨產生，並且最小化車輛路徑距離，達到最低運輸成本與快速回應的目標。
    本研究提出以人工免疫系統演算法(artificial immune systems, AIS)結合掃描法(sweep method)的啟發式演算法(sAIS)。對具有接駁式轉運中心的車輛途程問題(VRPCD)快速提出一個近似最佳解，主要目標在於滿足所有限制條件下，達到總成本（運輸及營運）的最小化。為了驗證所提出的啟發式演算法的效能，將本研究所提的方法與基因演算法(genetic algorithm, GA)做比較，求解60組車輛取貨與交貨運途的標竿問題，實驗結果發現在每一組標竿問題中，本研究所提出的啟發式演算法都能找出比基因演算法更好的最佳成本解，總平均成本改善率達 7.26%。相較於基因演算法，我們所提出的啟發式演算法呈現出具有相當穩健且有效搜尋全局最佳解的能力，且能更快收斂到近似最佳解。

    All 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, cross-docking (CD) system in the supply chain is considered a good method to reduce inventory and improve responsiveness to various customer demands. This thesis focuses on the vehicle routing problem with cross-docking (VRPCD) aiming at synchronizing the shipments in both pickup and delivery processes concurrently. The collective effort of VRPCD is to reduce handling cost, inventory cost and transport cost to fulfill the distribution services.
    A two-stage algorithm based on the artificial immune systems (AIS) combined with the sweep method, called sAIS, is proposed in this thesis to find the combinatorial optimum solution of the vehicle routing problem with cross-docking. Since the complexity of the problem is NP-hard, the proposed meta-heuristic method can quickly generate a near optimum solution. Comparisons are made between the proposed method and the genetic algorithm (GA) over the experiments of various VRP pickup and delivery benchmark problems to validate the performance of the sAIS approach. Experiment results show that the sAIS algorithm was able to discover new optimum solutions than the GA for all 60 benchmarks problems. Also, the computational results show that the proposed algorithm is robust, converge fast to near optimal solution and competitive with overall improvement of 7.26% over the GA method.

    摘要 i ABSTRACT ii ACKNOWLEDGMENTS iii CHAPTER 1 INTRODUCTION 1 1.1 Research Motivation 1 1.2 Objectives 3 1.3 Research Structure 4 CHAPTER 2 LITERATURE REVIEW 6 2.1 Logistics Management 6 2.2 Cross-docking System 7 2.3 Vehicle Routing Problem 8 2.4 Artificial Immune Systems 13 2.4.1 Introduction of Artificial Immune Systems 14 2.4.2 Features of artificial immune systems 15 2.4.3 Basic component of artificial immune systems 15 2.4.4 Mechanism of the artificial immune systems 16 2.4.5 Techniques of Selection 19 2.4.6 Applications of Artificial Immune Systems 25 2.4.7 The GA and the AIS 26 CHAPTER 3 PROBLEM FORMULATION AND THE AIS ALGORITHM 28 3.1 Problem Proposition 28 3.1.1 General VRP 28 3.1.2 The VRP with Cross-docking System 30 3.2 The Sweep Method 34 3.3 The sAIS Algorithm 37 3.3.1 Basic components of the sAIS 37 3.3.2 Mechanism of the proposed algorithm 38 CHAPTER 4 COMPUTATIONAL EXPERIMENTS 42 4.1 Preliminary Test 42 4.2 Computational Results 44 CHAPTER 5 CONCLUSIONS AND FUTURE RESEARCH 50 5.1 Conclusions 50 5.2 Further Research 51 REFERENCES 52 Appendix A. The solution of the sAIS algorithm for Instance 6P1. 60 Appendix B. The Best Routing Plan of the sAIS algorithm for Instance 6P1. 61 Appendix C. The solution of the sAIS algorithm for Instance 9P1. 62 Appendix D. The Best Routing Plan of the sAIS algorithm for Instance 9P1. 63 Appendix E. The solution of the sAIS algorithm for Instance 18P1. 64 Appendix F. The Best Routing Plan of the sAIS algorithm for Instance 18P1. 65 Appendix G. The solution of the sAIS algorithm for Instance 43P1. 66 Appendix H. The Best Routing Plan of the sAIS algorithm for Instance 43P1. 67 Appendix I. The solution of the sAIS algorithm for Instance 53P1. 68 Appendix J. The Best Routing Plan of the sAIS algorithm for Instance 53P1. 69 Appendix K. The solution of the sAIS algorithm for Instance 54P1. 70 Appendix L. The Best Routing Plan of the sAIS algorithm for Instance 54P1. 71

    Ai, T.J. and 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. and Kachitvichyanukul, V., 2009b. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem, Computers & Industrial Engineering, 56(1), 380-387.
    Apte, U.M. and Viswanathan, S., 2000. Effective cross docking for improving distribution efficiencies. International Journal of Logistics Research and Applications, 3, 291-302.
    Ayara﹐M., Timmis﹐J., De Lemos, R., and Forrest, S., 2005. Immunising automated teller machines, Lecture Notes in Computer Science, 3627, 404-417.
    Baker, B.M. and Ayechew, M.A., 2003. A genetic algorithm for the vehicle routing problem, Computers & Operations Research, 30 (5), 787-800.
    Balinski, M. and Quandt, R., 1964. On an integer program for a delivery problem, Operations Research, 12(2), 300-304.
    Bell, J.E. and McMullen, P.R., 2004. Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics, 18 (1), 41-48.
    Bianchessi, N., and Righini, G. 2007. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery, Computers & Operations Research, 34(2), 578-594.
    Boloori Arabani, A.R., Fatemi Ghomi, S.M.T., and Zandieh, M., 2011. Meta-heuristics implementation for scheduling of trucks in a cross-docking system with temporary storage, Expert Systems with Applications, 38(3), 1964-1979.
    Campelo﹐F., Guimaraes, F.G., Igarashi, H., Ramirez, J.A. and Noguchi, S., 2006. A modified immune network algorithm for multimodal electromagnetic problems, IEEE Transactions on Magnetics, 42(4), 1111-1114.
    Çatay, B. 2010. A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery, Expert System with Applications, 37(10), 6809-6817.
    Chen, A.L., Yang, G.K., and Wu, Z.M., 2006. Effective hybrid optimization algorithm for capacitated vehicle routing problem, Journal of Shanghai Jiaotong University (Science), 11E(1) , 50-55.
    Chen, P., Huang, H., and Dong, X., 2007. An ant colony system based heuristic algorithm for the vehicle routing problem with simultaneous delivery and pickup, 2nd IEEE Conference on Industrial Electronics and Applications, 136-141.
    Chow, H. K.H., Choy, K.L., Lee, W.B., Chan, F.T.S., 2005. Design of a knowledge-based logistics strategy system, Expert Systems with Applications, 29, 272-290.
    Christofides, N. and Eilon, S. 1969. An algorithm for the vehicle dispatching problem, Operational Research Quarterly, 20,309-318.
    Christopher, M., 1985. Logistics and Supply chain management: strategies for reducing cost and improving customer service, Pitman Publishing, Singapore.
    Chun, J.S., Kim, M.K., Jung, H.K., and Hong, S.K., 1997. Shape optimization of electromagnetic devices using immune algorithm, IEEE Transactions on Mangetics, 33(2), 1876-1879.
    Cutello, V. and Nicosia, G., 2002. An immunological approach to combinatorial optimization problems, Lecture Notes in Computer Science, 2527, 361-370.
    Dantzig, G.B. and Ramser, J.H., 1959. The truck dispatching problem, Management Science, 6(1), 80-91.
    de Castro, L.N., Timmis, J.I. 2003. Artificial immune systems as a novel soft computing paradigm, Soft Computing, 7(8), 526-544.
    de Castro, L.N. and Von Zuben﹐F.J., 2001. aiNet: An artificial immune network for data analysis. data mining: a heuristic approach.
    de Castro, L.N. and Von Zuben, F.J. , 2002. Learning and optimization using the clonal selection principle, IEEE Transaction on Evolutionary Computation, 239-251.
    Dethloff, J., 2001. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR Spectrum, 23(1), 79-96.
    D'Souza, C., Omkar, S.N., and Senthilnath, J., 2012. Pickup and delivery problem using metaheuristics techniques, Expert Systems with Applications, 39(1), 328-334.
    Eilon, S., Watson-Grandy C.D.T., and Christofides, N., 1971. Distribution management: Mathematical modelling and practical analysis, Griffin, London.
    Engin,O. and Döyen, A., 2004. A new approach to solve hybrid flow shop scheduling problems by artificial immune system, Future Generation Computer Systems 20 (6 SPEC. ISS.), 1083-1095.
    Farmer, J.D., Packard, N.H., and Perelson, A.S.﹐1986. The immune system, adaption, and machine learning, Proceedings of the 5th Annual International Conference, 22, 187-204.
    Forrest, S., Perelson, A.S., Allen, L., and Cherukuri, R., 1994. Self-nonself discrimination in a computer, IEEE Symposium on Research in Security and Privacy, Oakland CA, 202-212.
    Freschi, F. and Repetto, M. 2005. Multiobjective optimisation by a modified artificial immune system, Lecture Notes in Computer Science, 3627, 248-261.
    Freschi, F. and Repetto, M., 2006. Comparison of artificial immune systems and genetic algorithms in electrical engineering optimization, COMPEL: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering, 25(4), 792-811.
    Gendreau, M., Hertz A., and Laporte G., 1994. A Tabu search heuristic for the vehicle routing problem, Management Science, 40(10), 1276-1290.
    Hart, E. and Timmis, J. , 2008. Application areas of AIS: The past, the present and the future, Applied Soft Computing, 8(1),191-201.
    Hong, C. and Liu, C., 2009. A two-stage hybrid heuristic for vehical routing problem with pickups and deliveries, 2009 International Conference on Information Management, Innovation Management and Industrial Engineering, 1,92-97.
    Hunt J.E. and Cooke, D.E., 1996. Learning using an artificial immune system, Journal of Network and Computer Applications, 19(2), 189-212.
    Hunt, J., Timmis, J., Cooke, D., Neal, M., and King, C., 1999. Jisys: Development of an artificial immune system for real world applications, Springer-Verlag ,157-186.
    Jerne, N.K., 1974 . Towards a network theory of the immune system, Annual Immunology, 125c, 373-389.
    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.
    Kreng, V. B. and Chen, F. T. (2008). The benefits of a cross-docking delivery strategy: a supply chain collaboration approach, Production Planning & Control, 19(3), 229-241.
    Lai, M. and Cao, E., 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.
    LaLonde, B.J. and Zinszer, P.H., 1976. Customer service: Meaning and measurement, national council of physical distribution management, USA.
    Laporte, G., 1992. The vehicle routing problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59(3), 345-358.
    Laporte, G., 2009. Fifty years of vehicle routing, Transportation Science, 43(4), 408-416.
    Laporte, G. and Nobert, Y., 1987. Exact algorithms for the vehicle routing problem, Annals of Discrete Mathematics, 31, 147-184.
    Laporte, G. and Osman, I.H., 1995. Routing problems: A bibliography, Annals of Operations Research, 61, 227-262.
    Laporte, G., Nobert, Y., and Desrochers, M., 1984. Optimal routing under capacity and distance restrictions, Operations Research, 33(5), 1050-1073.
    Lee, Y.H., Jung, J.W., and Lee, K.M., 2006. Vehicle routing scheduling for cross-docking in the supply chain, Computers & Industrial Engineering, 51(2), 247-256.
    Li, J., Wang, M.G., Tang, L.X., and Song, J.H., 2001. Special kind of vehicle routing problem, Journal of Northeastern University (Natural Science), 22(3), 245-248.
    Li, Y. and Liu, Y., 2010. Research on vehicle routing problem based on immune genetic algorithm, 2010 Information Engineering and Computer Science (ICIECS), 1-4.
    Liao, C.J., Tjandradjaja, E. and Chung, T.P., 2012. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem, Applied Soft Computing, 12(6), 1755–1764.
    Liao, C.J., Lin, Y.M., and Shin, S.C., 2010. Vehicle routing with cross-docking in the supply chain, Expert Systems with Applications, 37(10), 6868-6873.
    Liu, C.S. and Tang, Q.J., 2010. A hybrid heuristics for vehicle routing problem with simultaneous pickup and delivery service, 2010 International Conference on Logistics Systems and Intelligent Management, 1422-1426.
    Liu, F., Wang, Q., and Gao, X., 2006. Survey of artificial immune system, Systems and Control in Aerospace and Astronautics, 2006. ISSCAA 2006. 1st International Symposium, 985-989.
    Montane, F.A. T.and Galvao, R.D., 2006. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Computers & Operations Research, 33(3), 595-619.
    Meade, L., Sarkis, J., 1988. Strategic analysis of logistics and supply chain management systems using the analytical network process, Transportation Research Part E: Logistics and Transportation Review, 34(3), 201-215.
    Mosheiov, G., 1998. Vehicle routing with pick-up and delivery: Tour partitioning heuristics, Computers & Industrial Engineering, 34(3), 669-684.
    Ojha, U. Chow M. Y., 2010. An analysis of artificial immune system and genetic algorithm in urban path planning, IECON 2010 - 36th Annual Conference on IEEE Industrial Electronics Society, 1064-1069.
    Osman, I.H., 1993. Metastrategy simulated annealing and Tabu search algorithms for the vehicle routing problem, Annals of Operations Research, 41(4), 421-451.
    Parham, P., 2005. The immune system, Garland science publishing, second edition, USA.
    Rohrer, M., 1995. Simulation and cross docking, Proceeding of the 1995 Winter Simulation Conference, 846-849.
    Salhi, S. and Nagy, G., 1999. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the Operational Research Society, 50(10), 1034-1042.
    Shi, G. and Jing, Y., 2009. Research of improved immune clonal algorithms and its applications, IEEE International Conference on Computational Intelligence for Measurement Systems and Applications, 2009 (CIMSA '09), 212-215.
    Shi, G., Jing, Y.W., and Ma, J., 2009. A new immune clonal algorithm and its applications to CVRP, Dongbei Daxue Xuebao/Journal of Northeastern University, 30(10), 1373-1376.
    Stalk, G., Evans, P., and Shulman, L.E., 1992. Competing on capabilities: The new rules of corporate strategy, Harvard Business Review, 70, 57-69.
    Taillard, E., 1993. Parallel iterative search methods for vehicle routing problems, Networks, 23(8), 661-673.
    Tasan, A.S. and Gen, M., 2010. A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries, 40th International Conference on Computers & Industrial Engineering, 1-5.
    Taylor, D.W. and Corne, D.W., 2003. An investigation of the negative selection algorithm for fault detection in refrigeration systems, Lecture Notes in Computer Science, 2787, 34-45.
    Timmis, J. and Edmonds, C., 2004. A comment on Opt-AiNET: An immune network algorithm for optimisation. Lecture Notes in Computer Science, 3102, 308-317.
    Timmis, J. and Neal, M., 2001. A resource limited artificial immune system for data analysis, Knowledge-Based Systems, 14(3-4), 121-130.
    Toth, P. and Vigo, D., 2001. The vehicle routing problem. Monographs on discrete mathematics and applications, PA: SIAM, Philadelphia.
    Wang, I.C., 2010. The application of third party logistics to implement the Just-In-Time system with minimum cost under a global environment, Expert Systems with Applications, 37(3), 2117-2123.
    Wang, Z.W. and Wang, Z.G., 2009. A novel two-phase heuristic method for vehicle routing problem with backhauls, Computers & Mathematics with Applications, 57(11-12), 1923-1928.
    Wei, R., Zhang, T., and Tang, H., 2011. An improved particle swarm optimization algorithm for vehicle routing problem with simultaneous pickup and delivery, Communications in Computer and Information Science, 105(7), 430-436.
    Zachariadis, E.E., Tarantilis, C.D., and Kiranoudis, C.T., 2009. An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries, European Journal of Operational Research, 202(2), 401-411.
    Zachariadis, E.E. and Kiranoudis, C.T., 2010. A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries, Expert Systems with Applications, 38(3), 2717-2726,.
    Zhang, L.X. and Niu, H.M., 2009. An algorithm for vehicle routing problem with soft time windows using tabu search, Critical Issues in Transportation Systems Planning, Development, and Management, 3257-3262.
    Zhang, X., Ma, T., and Han, X., 2007. Optimizing fixed shelf order-picking for AS/RS based on immune particle swarm optimization algorithm. Proceedings of the IEEE International Conference on Automation and Logistics, 8, 2824-2829.
    Zhu Y., Gao S., Dai H., Li F., and Tang Z., 2007. Improved clonal algorithm and its application to traveling salesman problem, International Journal of Computer Science and Network Security(IJCSNS), 7(8), 109-113.

    QR CODE