簡易檢索 / 詳目顯示

回結果列表
研究生： 王景昱
Ching-Yu Wang
論文名稱： 應用粒子群最佳化於供應鏈中具接駁式轉運之車輛運途問題研究
Apply Particle Swarm Optimization to Solve the Vehicle Routing Problem with Cross-Docking in the Supply Chain
指導教授： 羅士哲
Shih-Che Lo
口試委員: 郭伯勳
Po-Hsun Kuo
蔡鴻旭
Hung-Hsu Tsai
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2009
畢業學年度： 97
語文別： 英文
論文頁數： 48
中文關鍵詞： 接駁式轉運 、物流運籌 、粒子群優化 、供應鏈管理 、車輛運途
外文關鍵詞： Cross-docking, Logistics, Particle swarm optimization, Supply chain management, Vehicle routing problem
相關次數： 點閱：529  下載：9 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 導入接駁式轉運中心(Cross-Docking, CD)的物流運籌網路可以賦予企業協同整合供應鏈上游供應商和下游零售商間貨物流通的能力。整體規劃的目標在於同步化運輸車隊於取貨(Pickup)及送貨(Delivery)過程中的抵達時程和運/卸載貨物量，使得在轉運中心中避免存貨處置成本的產生。因此，最佳化的車輛運途規劃(Vehicle Routing Problem, VRP)在此運籌模型中顯得相對關鍵，尤其當最佳化的車輛排程與調度可以建構出最低運輸成本的配送路線，去滿足所有顧客的已知需求。本研究提出了基於粒子群優化(Particle Swarm Optimization, PSO)概念的啟發式演算法來求解於供應鏈中導入接駁式轉運中心的車輛運途(VRPCD)最佳化問題。主要目標在於求算最佳化的車輛路徑規劃與排程組合，在滿足定義條件下達到總成本(運輸及營運)的最小化。為了驗證所提出粒子群演算法的效能，本研究比較了最鄰近搜索法(Nearest Neighbor, NN)與基因遺傳演算法(Genetic Algorithm, GA)的優化績效。在60組車輛排程取貨與交貨的問題實驗中，結果顯示我們所提出的粒子群最佳化法呈現出具有相當穩健且有效搜尋全局最佳解的能力，相較於最鄰近搜索法和基因遺傳演算法，本研究提出的粒子群優化演算法相對的提高4.37% 和0.97%的平均總成本改善率。另外，在此60組標竿問題驗證中，本研究設計的粒子群優化法相較於基因演算法在其中的55組題目中找出了更好的最佳成本解。

    The design of logistics network with the implementation of Cross-docking (CD) allows freight companies to collaboratively integrate the physical flow of goods between upstream suppliers and downstream retailers in the supply chain. The collective effort aims at synchronizing the shipments in both pickup and delivery processes concurrently so that to avoid the handling and inventory cost being generated. Accordingly, the optimal vehicle routing schedule is imperative in order to produce a routing plan with minimum transport cost fulfilling the distribution services. In this paper, a heuristic algorithm based on the Particle Swarm Optimization (PSO) is developed and applied to solve the combinatorial optimal solution of the vehicle routing problem with Cross-docking (VRPCD) in the supply chain. To validate the performance of the proposed PSO algorithm, comparisons are drawn with the Nearest Neighbor (NN) search and the Genetic Algorithm (GA) over the experimentation of a number of VRP pickup and delivery benchmark problems. The computational results showed the proposed PSO is robustly competitive with average improvements of 4.37% and 0.97% over the NN search and the GA algorithm, respectively, on the criterion of average solution quality. In addition, the proposed algorithm was able to discover new best-solution than the GA in a set of 55 instances out of the 60 benchmarks applied.

    摘要 i ABSTRACT ii ACKNOWLEDGMENTS iii CONTENTS iv FIGURES vi TABLES vii CHAPTER 1 INTRODUCTION 1 1.1 Research Motivation 1 1.2 Objective 3 1.3 Research Structure 3 CHAPTER 2 LITERATURE REVIEW 5 2.1 Logistics Management 5 2.2 Cross-docking System 6 2.3 Vehicle Routing Problem 7 2.4 Particle Swarm Optimization (PSO) 10 2.4.1 The Basis of PSO 10 2.4.2 GA and PSO 13 CHAPTER 3 PROBLEM FORMULATION AND PARTICLE SWARM OPTIMIZATION 14 3.1 Problem Proposition 14 3.1.1 General VRP 14 3.1.2 VRP with Cross-docking System 16 3.2 Particle Swarm Optimization 19 3.2.1 Continuous PSO 19 3.2.2 Discrete PSO (DPSO) 23 CHAPTER 4 PROPOSED PSO HEURISTICS 25 4.1 Methodology 25 4.2 PSO Procedure 27 CHAPTER 5 COMPUTATIONAL EXPERIMENTS 31 5.1 Preliminary Test 31 5.2 Computational Results 32 CHAPTER 6 CONCLUSIONS AND FUTURE RESEARCH 36 6.1 Conclusions 36 6.2 Further Research 37 REFERENCES 39 Appendix A. The Best Solution of the Proposed PSO Heuristics for Instance 16P1. 43 Appendix B. The Best Routing Plan for Instance 16P1. 44 Appendix C. The Best Solution of the Proposed PSO Heuristics for Instance 17P1. 45 Appendix D. The Best Routing Plan for Instance 17P1. 46 Appendix E. The Best Solution of the Proposed PSO Heuristics for Instance 18P1. 47 Appendix F. The Best Routing Plan for Instance 18P1. 48

    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.
    Baker, B.M. and Ayechew, M.A., 2003. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30 (5), 787-800.
    Baker, B.M. and Sheasby, J., 1999. Extensions to the generalized assignment heuristic for vehicle routing. European Journal of Operational Research, 119 (1), 147-157.
    Bell, J.E. and McMullen, P.R., 2004. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18 (1), 41-48.
    Clerc, M., 2000. Discrete Particle Swarm Optimization Illustrated by the Traveling Salesman Problem.
    Dantzig, G.B. and Ramser, J.H., 1959. The Truck Dispatching Problem. Management Science, 6 (1), 80-91.
    Dethloff, J., 2001. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up. OR Spectrum, 23 (1), 79-96.
    Eberhart, R.C. and Kennedy, J., 1995. A New Optimizer Using Particle Swarm Theory. Proc. Sixth International Symposium on Micro Machine and Human Science. IEEE Service Center, Piscataway, NJ, 39-43.
    Eberhart, R.C. and Shi, Y., 1998. Comparison between Genetic algorithms and Particle Swarm Optimization. 1998 Annual Conference on Evolutionary Programming. 611-616.
    Gendreau M., Hertz A., and Laporte G., 1994. A Tabu search heuristic for the vehicle routing problem. Management Science, 40 (10), 1276-1290.
    Hu, X., Shi, Y., and Eberhart, R.C., 2004. Recent Advances in Particles Swarm. Proceedings of IEEE congress on evolutionary computation, 1, 90-97.
    Kennedy, J. and Eberhart, R.C., 1995. Particle Swarm Optimization, Proc. IEEE International Conference on Neural Networks. IEEE Service Center, Piscataway, NJ, 4, 1942-1948.
    Kennedy, J., 1997a. The Particle Swarm: Social Adaption of Knowledge, Proc. IEEE International Conference on Evolutionary Computation. IEEE Service Center, Piscataway, NJ, 303-308.
    Kennedy, J. and Eberhart, R.C., 1997b. A discrete binary version of the particle swarm algorithm. Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics. Piscataway, NJ, 4104-4109.
    Kennedy, J., Eberhart, R.C., and Shi, Y., 2001. Swarm Intelligence. San Francisco, CA: Morgan Kaufmann.
    Laporte, G., 1992. The Vehicle Routing Problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59, 345-358.
    Loporte, G., Nobert, Y., and Desrochers, M., 1985. Optimal Routing under Capacity and Distance Restrictions. Operations Research, 3 (5), 1050-1073.
    Laporte, G. and Nobert, Y., 1987. Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics, 31, 147-184.
    Loporte, 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.
    Liao, C.J., Tseng, C.T., and Luarn, P., 2007. A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research, 34 (10), 3099-3111.
    Mosheiov, G., 1998. Vehicle Routing With Pick-up and Delivery: Tour Partitioning Heuristics. Computers & Industrial Engineering, 34 (3), 669-684.
    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.
    Salman, A., Ahmad, I., and Al-Madani, S., 2002. Particle swarm optimization for task assignment problem. Microprocessors and Microsystems, 26 (8), 363-371.
    Shi, Y. and Eberhart, R.C., 1998a. A Modified Particle Swarm Optimizer. Proceedings of the IEEE Congress on Evolutionary Computation, 69-73.
    Shi, Y. and Eberhart, R.C., 1998b. Parameter Selection in Particle Swarm Optimization. 1998 Annual Conference on Evolutionary Programming, 591-600.
    Song, S.H. and Sung, C.S., 2003. Integrated service network design for a cross-docking supply chain network. Journal of the Operational Research Society, 54, 1283-1295.
    Stalk, G., Evans, P., and Shulman, L.E., 1992. Competing on Capabilities: The New Rules of Corporate Strategy. Harvard Business Review, 1992, 70, 57-69.
    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.
    Tang, 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.
    Taillard, E., 1993. Parallel iterative search methods for vehicle routing problems. Networks, 23 (8), 661-673.
    Tasgetiren, M.F., Liang, Y.C., Sevkli, M., and Gencyilmaz, G., 2007. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research, 177 (3), 1930-1947.
    Tseng, C.T. and Liao, C.J., 2008. A discrete particle swarm optimization for lot-streaming flowshop scheduling problem. European Journal of Operational Research, 191 (2), 360-373.
    Toth, P. and Vigo, D., 2001. The vehicle routing problem. Monographs on Discrete Mathematics and Applications. Philadelphia, PA: SIAM.

    QR CODE