簡易檢索 / 詳目顯示

回結果列表
研究生： 陳偉剛
Wei-kang Chen
論文名稱： 一個三階段蟻群最佳化演算法於物流管理中具回程取貨與接駁式轉運之車輛運途問題
A Three-stage Ant Colony Optimization to Solve the Vehicle Routing Problem with Backhaul and Cross-docking in Logistics Management
指導教授： 羅士哲
Shih-Che Lo
口試委員: 蔡鴻旭
Hung-Hsu Tsai
楊朝龍
Chao-Lung Yang
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2012
畢業學年度： 100
語文別： 英文
論文頁數： 80
中文關鍵詞： 接駁式轉運 、物流管理 、蟻群最佳化 、車輛運途 、掃描法 、支持向量機
外文關鍵詞： Cross-docking, Logistics management, Ant colony optimization, Vehicle routing problem, Sweep method, Support vector machine
相關次數： 點閱：316  下載：6 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 企業在現今激烈的競爭環境下想要增加獲利，除了提高銷售量及降低生產成本外，另一方面就是提升物流的效率。因此，企業必須提供有效率的物流運籌網路來因應快速的顧客回應需求，而導入接駁式轉運中心(Cross-docking, CD)的物流運籌網路，被視為是減少存貨和快速回應顧客多樣需求的好方法。考慮接駁式轉運與回程取貨之車輛途程問題(Vehicle Routing Problem with Backhaul, VRPB)結合後，最主要的概念就是讓車隊於取貨(Pickup)、送貨兼併處理回收及退貨(Delivery with Backhaul)、送回供應商(Go-back) 的過程中同時抵達，避免轉運中心有存貨產生，並且最小化車輛路徑距離，達到最低運輸成本與快速回應的目標。
    本研究提出以蟻群演算法(Ant Colony Optimization Algorithm, ACO)結合掃描法 (Sweep method) 與支持向量機(Support Vector Machine)的啟發式演算法，稱為ssACO演算法，對具有回程取貨與接駁式轉運之車輛途程問題(VRPBCD)快速提出一個近似最佳解，主要目標在於滿足所有限制條件下，達到總成本(運輸及營運)的最小化。為了驗證所提出的ssACO演算法的效能，本研究與基因演算法(Genetic Algorithm, GA)做比較，改良60組車輛取貨與交貨運途的標竿問題為VRPBCD問題，在每一組標竿問題中，本研究所提出的ssACO演算法都能找出比基因演算法更好的最佳成本解，總平均成本改善率達到7.81%。相較於基因演算法，我們所提出的ssACO演算法呈現出具有相當穩健且有效搜尋全局最佳解的能力，且能更快收斂到較佳的解。

    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 profits. 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 Backhaul and Cross-docking system (VRPBCD) aiming at synchronizing the shipments in pickup, delivery with backhaul and go-back processes concurrently. The collective effort of VRPBCD is to reduce handling cost, inventory cost and transport cost to fulfill the distribution services.
    A three-stage algorithm, called ssACO, based on the Ant Colony Optimization (ACO) algorithm is proposed in this thesis to solve the combinatorial optimal solution of the vehicle routing problem with Backhaul and Cross-docking. The ssACO method is based on the Ant Colony Optimization algorithm combined with the sweep method and support vector machine (SVM) to quickly generate a near optimal solution. Comparisons are made between the proposed method and the Genetic Algorithm (GA) over the experiments of various VRPBCD problems, modified from VRP pickup and delivery benchmark problems, to validate the performance of the proposed algorithm. Experiment results show that the ssACO algorithm was able to find out new solutions than the GA for all 60 benchmarks problems. Also, the results show that the ssACO algorithm is robust, converge fast and competitive with overall improvement of 7.81% over the GA.

    CONTENTS 摘要 i ABSTRACT ii ACKNOWLEDGMENTS iii FIGURES vi TABLES vii 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 with Backhaul 9 2.4 Ant Colony Optimization (ACO) 16 2.4.1 The Basis of ACO 16 2.4.2 GA and ACO 21 CHAPTER 3 PROBLEM FORMULATION AND ANT COLONY OPTIMIZATION 23 3.1 Problem Proposition 23 3.1.1 Vehicle routing problem with backhaul (VRPB) 23 3.1.2 VRPB with Cross-docking System 25 3.2 Sweep Method 29 3.3 Support Vector Machine (SVM) 32 3.4 Ant Colony Optimization (ACO) 37 3.4.1 Construction of the Routes 37 3.4.2 Pheromone Updating 39 3.4.3 The Framework of the ssACO 40 CHAPTER 4 COMPUTATIONAL EXPERIMENTS 43 4.1 Preliminary Test 43 4.2 Computational Results 46 CHAPTER 5 CONCLUSIONS AND FUTURE RESEARCH 58 5.1 Conclusions 58 5.2 Further Research 59 REFERENCES 60 Appendix A. The solution of the ssACO for Instance 4P1. 69 Appendix B. The Best Routing Plan of the ssACO algorithm for Instance 4P1. 70 Appendix C. The solution of the ssACO algorithm for Instance 12P1. 71 Appendix D. The Best Routing Plan of the ssACO algorithm for Instance 12P1. 72 Appendix E. The solution of the ssACO algorithm for Instance 27P1. 73 Appendix F. The Best Routing Plan of the ssACO algorithm for Instance 27P1. 74 Appendix G. The solution of the ssACO algorithm for Instance 31P1. 75 Appendix H. The Best Routing Plan of the ssACO algorithm for Instance 31P1. 76 Appendix I. The solution of the ssACO algorithm for Instance 43P1. 77 Appendix J. The Best Routing Plan of the ssACO algorithm for Instance 43P1. 78 Appendix K. The solution of the ssACO algorithm for Instance 59P1. 79 Appendix L. The Best Routing Plan of the ssACO algorithm for Instance 59P1. 80

    Achuthan, N.R. and Caccetta, L., 1991. Integer linear programming formulation for a vehicle routing problem, European Journal of Operational Research, 52(1), 86-89.
    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.
    Allen, J., 2001. Cross docking: Is it right for you? Canadian Transportation Logistics, 104, 22-25.
    Apte, U.M. and Viswanathan, S., 2000. Effective cross docking for improving distribution efficiencies, International Journal of Logistics Research and Applications, 3, 291-302.
    Apte, U.M. and Viswanathan, S., 2002. Strategic and technological innovations in supply chain management, International Journal of Manufacturing Technology and Management, 4, 264–282.
    Baker, B.M. and Ayechew, M.A., 2003. A genetic algorithm for the vehicle routing problem, Computers & Operations Research, 30(5), 787-800.
    Baldacci, R., Christofides, N., and Mingozzi, A., 2008. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Mathematical Programming Series A, 115(2), 351-385.
    Beckers, R., Deneubourg, J.L., and Goss, S., 1992, Trails and U-turns in the selection of the shortest path by the ant Lasius niger, Journal of Theoretical Biology, 159(4), 397-415.
    Bell, J.E. and McMullen, P.R., 2004. Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics, 18(1), 41-48.
    Bersini, H., Oury, C., and Dorigo, M., 1995, Hybridization of genetic algorithms, Technical Report. No. IRIDIA 95-22, IRIDIA, Universite´ Libre de Bruxelles, Belgium.
    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.
    Brandao, J., 2004. A tabu search algorithm for the open vehicle routing problem, European Journal of Operational Research, 157, 552-564.
    Breedam, A.V., 1995. Improvement heuristics for the vehicle routing problem based on simulated annealing, European Journal of Operational Research, 86, 480-490.
    Bowersox, D.J. and Closs, D.J., 1996. Logistics Management, McGraw-Hill.
    Bullnheimer, B., Hartl, R.F. and Strauss, C., 1999. An improved ant system for the vehicle routing problem, Annals of Operations Research, 89, 319-328.
    Casco, D., Golden, B., and Wasil, E., 1988. Vehicle routing with backhauls: Models, algorithms and case studies, in: Golden, A., and Assad, A. (Eds.), vehicle routing: methods and studies, Elsevier Science Publishers, Amsterdam, 127-147.
    Catay, B., 2006. An ant colony optimization approach for the capacitated vehicle routing problem with simultaneous delivery and pick-up, Proceedings of the EWGT Joint Conferences, 275-282.
    Çatay, B. 2010. A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery, Expert System with Applications, 37, 6809-6817.
    Chang, C.C. and Lin, C.J., 2011. LIBSVM: A library for support vector machines, ACM Transactions on Intelligent Systems and Technology, 2:27:1--27:27.
    Chen, G.H., 2005. The application of ant memory system on traveling salesman problems, master’s thesis, Feng Chia University.
    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.
    Christopher, M., 1985. Logistics and supply chain management: strategies for reducing cost and improving customer service, Pitman Publishing, Singapore.
    Cordeau, J.F. and Maischberger, M., 2012. A paralle literated tabu search heuristic for vehicle routing problems, Computers & Operations Research, 39, 2033-2050.
    Dantzig, G.B. and Ramser, J.H., 1959. The truck dispatching problem, Management Science, 6(1), 80-91.
    Deif, I. and Bodin, L., 1984. Extension of the Clarke and Wright algorithm for solving the vehicle routing with backhauling, in: Kidder, A. (Ed.), Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management, Babson Park, 75-96.
    Dethloff, J., 2001. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR Spectrum, 23(1), 79-96.
    Doerner, K., Gronalt, M., Hartl, R.F., Reimann, M., Strauss, C., and Stummer, M., 2002. SavingsAnts for the vehicle routing problem, POM-02/02, Department of Production and Operations Management, University of Vienna, Austria.
    Doerner, K., Hartl, R.F., and Reimann M., 2004, D-Ants: Savings based ants divide and conquer the vehicle routing problem, Computers & Operations Research, 31, 63-591.
    Dorigo, M. and Gambardella, L.M., 1997a. Ant colonies for the travelling salesman problem, BioSystems, 43, 73-81.
    Dorigo, M. and Gambardella, L.M., 1997b. Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 26(1), 29-41.
    Dror, M. and Trudeau, P., 1990. Split delivery routing, Naval Research Logistics, 37(3), 383-402.
    Forger, G., 1995. UPS starts world’s premiere cross-docking operation, Modern Materials Handling, 36-38.
    Gendreau, M., Hertz A., and Laporte G., 1994. A Tabu search heuristic for the vehicle routing problem, Management Science, 40(10), 1276-1290.
    Goetschalckx, M. and Jacobs-Blecha, C., 1989. The vehicle routing problem with backhauls, European Journal of Operational Research, 42(1), 39-51.
    Goss, S., Aron, S., Deneubourg, J.L., and Pasteels, J.M., 1989. Self-organized shortcuts in the argentine ant, Naturwis-senschaften, 76, 579-581.
    Gumus, M. and Bookbinder, J.H., 2004. Cross-docking and its implications in location-distribution systems, Journal of Business Logistics, 25, 199-229.
    Golden, B., Baker, E., Alfaro, J., and Schaffer, J., 1985. The vehicle routing problem with backhauling: Two approaches, in: Hammesfahr, R., (Ed.), Proceedings of the Twenty-first Annual Meeting of S.E. TIMS, 90-92.
    Halse, K., 1992. Modelling and solving complex vehicle routing problems, PHD thesis, The Technical University of Denmark.
    Holldobler, B. and Wilson, E.O., 1990. The ants, Springer-Verlag, Berlin.
    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.
    Hsieh, P.-f., 2003. Basic information of warehousing and logistics industries, Taiwan Institute of Economic Research, December 16.
    Karaoglan, L., Altiparmak, F., Kara, I., and Dengiz, B., 2012. The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach, Omega, 40, 465-477
    Lai, J.T., 2010. The application of the ant memory system on the vehicle routing problems, master’s thesis, Feng Chia University.
    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, 188-195.
    Lalonde, B.J. and Zinszer, P.H., 1976. Customer service: Meaning and measurement, National Council of Physical Distribution Management, USA.
    Laporte, G., Nobert, Y., and Desrochers, M., 1984. Optimal routing under capacity and distance restrictions. Operations Research, 33(5), 1050-1073.
    Laporte, G. and 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. and Osman, I.H., 1995. Routing problems: A bibliography, Annals of Operations Research, 61, 227-262.
    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, S.H. and Tien, P., 2008. An ant colony optimization on open vehicle routing problem. Systems Engineering Theory and Practice, 28(6), 81-93.
    Lin, F.-T., Kao, C.-Y., and Hsu, C.-C., 1993, Applying the genetic approach to simulated annealing in solving some NP-hard problems, IEEE Transactions on Systems, Man and Cybernetics, 23(6), 1752-1767.
    Lin, Y.J., 2003. Integration of fuzzy theory and ant algorithm for vehicle routing problem with time window, master’s thesis, National Taipei University of Science and Technology.
    Lin, T.H., 2006. An ant colony system for solving the truck and trailer routing problem, master’s thesis, National Kaohsiung First University of Science and Technology.
    Liu, B., Tang, J., and Yu, Y., 2010. A sweep-heuristic algorithm combined with partition of time and district for large-scale vehicle routing and scheduling problem of pickup and delivery of customers to airport, Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, art. no.5645314, 285-290.
    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.
    Lu, S.C., 2005. To solve the vehicle routing problem with time dependent road network, master’s thesis, National Kaohsiung First University of Science and Technology.
    Lo, M.H., 2003. A new ant colony algorithm to vehicle routing problem under capacity and distance constraints, master’s thesis, Yuan Ze University.
    Luton, D., 2003. Keep it moving: A cross-docking primer, Materials Management and Distribution, 48, 29-30.
    Martinovic, G., Aleksi, I., and Baumgartner, A., 2008. Single-commodity vehicle routing problem with pickup and delivery service, Mathematical Problems in Engineering, art. no. 697981.
    Mazzeo, S. and Loiseau, I., 2004. An ant colony algorithm for the capacitated vehicle routing, Electronic Notes in Discrete Mathematics, 18, 181-186.
    Meihua, W., Xuhong, T., Chang, S., and Wu, S.H., 2011. Hybrid ant colony optimization algorithm for two echelon vehicle routing problem, Procedia Engineering, 15, 3361-3365.
    Naddef, D. and Rinaldi, G., 2002. Branch-and-cut algorithms for the capacitated VRP, in: Toth, P., Vigo, D. (Eds.), the vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, 9, 53-81.
    Min, H., 1989. The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transportation Research, 23(5), 377-386.
    Montemanni, R., Gambardella, L.M., Rizzoli, A.E., and Donati, A.V., 2002. An algorithm for the relative robust shortest path problem with interval data, Istituto Dalle Molle di Studi sull'Intelligenza Artificiale.
    Mosheiov, G., 1998. Vehicle routing with pick-up and delivery: Tour partitioning heuristics, Computers & Industrial Engineering, 34(3), 669-684.
    Osman, I.H., 1993. Metastrategy simulated annealing and Tabu search algorithms for the vehicle routing problem, Operations Research, 41, 421-451.
    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 the single and multiple depot vehicle routing problems with backhauls, Journal of the Operational Research Society, 50(10), 1034-1042.
    Silva, C.A., Faria, J.M., Abrantes, P., Sousa, J.M.C., Surico, M., and Naso, D., 2005. Concrete delivery using a combination of GA and ACO, Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, art. no.1583394, 7633-7638.
    Slats, P.A., Bhola, B., Evers, J.J.M., and Dijkhuizen, G., 1995. Logistics chain modeling, European Journal of Operational Research, 87, 1-20.
    Stalk, G., Evans, P., and Shulman, L.E., 1992. Competing on capabilities: The new rules of corporate strategy, Harvard Business Review, 70, 57-69.
    Stutzle1, T., 2000. Max-min ant system, Computers & Operations Research, 16(8), 889-914.
    Song, K. and Chen, F., 2007. Scheduling cross docking logistics optimization problem with multiple inbound vehicles and one outbound vehicle, Proceedings of IEEE International Conference on Automation and Logistics, 3089-3094.
    Sung, C.S. and Song, S.H., 2003. Integrated service network design for a cross-docking supply chain network, Journal of the Operational Research Society, 54(12), 1283-1295.
    Taillard, E., 1993. Parallel iterative search methods for vehicle routing problems, Networks, 23(8), 661-673.
    Tang Montane, F.A. 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.
    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 and Industrial Engineering, 1-5.
    Toth, P. and Vigo, D., 2001. The vehicle routing problem, Monographs on Discrete Mathematics and Applications. Philadelphia, PA: SIAM.
    Vapnik, V., 1995. Support-vector networks, Machine Learning, 20(3), 273-297.
    Wade, A.C. and Salhi, S., 2002. An investigation into a new class of vehicle routing problem with backhauls, Omega, 30, 479-487.
    Wang, Z.W. and Wang, Z.G., 2008. A novel two-phase heuristic method for vehicle routing problem with backhauls, Computers and Mathematics with Applications, 57, 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.
    Witt, C. E., 1998. Crossdocking: Concepts demand choice, Material Handling Engineering 53(7), 44-49.
    Wren, A., 1971. Computers in transport planning and operation, Ian Allan, London.
    Yu W. and Egbelu P.J., 2006. Scheduling of inbound and outbound trucks in cross docking system with temporary storage, European Journal of Operational Research, 177, 377-396.
    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, 401-411.
    Zachariadis, E.E. and Kiranoudis, C.T., 2011. 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, 358, 3257-3262.
    Zhang,Y. and Wu, L., 2012. A novel genetic ant colony algorithm, Journal of Convergence Information Technology, 7(1), 268-274.

    QR CODE