研究改良式粒子群最佳化於物流管理中具接駁式轉運之車輛運途問題

簡易檢索 / 詳目顯示

回結果列表

研究生：	何書瑋 Shu-Wei He
論文名稱：	研究改良式粒子群最佳化於物流管理中具接駁式轉運之車輛運途問題 On the Study of Improved Particle Swarm Optimization to Solve the Vehicle Routing Problem with Cross-Docking in Logistics Management
指導教授：	羅士哲 Shih-Che Lo
口試委員:	王孔政 Kung-Jeng Wang 蔡鴻旭 Hung-Hsu Tsai
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業管理系 Department of Industrial Management
論文出版年：	2010
畢業學年度：	98
語文別：	英文
論文頁數：	58
中文關鍵詞：	接駁式轉運、物流運籌、粒子群優化、車輛運途、掃描法
外文關鍵詞：	Cross-docking, Logistics, Particle swarm optimization, Vehicle routing problem, Sweep method
相關次數：	點閱：528 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

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

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 novel algorithm, called sPSO, is proposed in thesis to solve the combinatorial optimal solution of the vehicle routing problem with Cross-docking. The sPSO method is based on the Particle Swarm Optimization (PSO) algorithm combined with the sweep method to quickly generate a near optimum solution. Comparisons are made between the sPSO method and the Genetic Algorithm (GA) over the experiments of various VRP pickup and delivery benchmark problems to validate the performance of the sPSO algorithm. Experiment results show that the sPSO algorithm was able to discover new solutions than the GA for all 60 benchmarks problems. Also, the computational results show that the sPSO algorithm is robust, converge fast and competitive with overall improvement of 39.30% over the GA.

摘要	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	4
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)	11
2.4.1	The Basis of PSO	11
2.4.2	GA and PSO	13
CHAPTER 3 PROBLEM FORMULATION AND PARTICLE SWARM OPTIMIZATION	15
3.1	Problem Proposition	15
3.1.1	General VRP	15
3.1.2	VRP with Cross-docking System	17
3.2	Particle Swarm Optimization	21
3.2.1	Continuous PSO	21
3.2.2	Discrete PSO (DPSO)	24
CHAPTER 4 THE PROPOSED PSO METHOD	27
4.1	Methodology	27
4.2	PSO Procedure	29
CHAPTER 5 COMPUTATIONAL EXPERIMENTS	34
5.1	Preliminary Test	34
5.2	Computational Results	35
CHAPTER 6 CONCLUSIONS AND FUTURE RESEARCH	40
6.1	Conclusions	40
6.2	Further Research	41
REFERENCES	42
Appendix A. The solution of the sPSO algorithm for Instance 1P1.	47
Appendix B. The Best Routing Plan of the sPSO algorithm for Instance 1P1.	48
Appendix C. The solution of the sPSO algorithm for Instance 2P1.	49
Appendix D. The Best Routing Plan of the sPSO algorithm for Instance 2P1.	50
Appendix E. The solution of the sPSO algorithm for Instance 3P1.	51
Appendix F. The Best Routing Plan of the sPSO algorithm for Instance 3P1.	52
Appendix G. The solution of the sPSO algorithm for Instance 55P1.	53
Appendix H. The Best Routing Plan of the sPSO algorithm for Instance 56P1.	54
Appendix I. The solution of the sPSO algorithm for Instance 56P1.	55
Appendix J. The Best Routing Plan of the sPSO algorithm for Instance 56P1.	56
Appendix K. The solution of the sPSO algorithm for Instance 57P1.	57
Appendix L. The Best Routing Plan of the sPSO algorithm for Instance 57P1.	58

                                

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.
Apte, U. M. and Viswanathan S., 2000. Effective cross docking for improving distribution efficiencies. International Journal of Logistics Research and Applications, 3, 291-302.
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.
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, 345-358.
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.
Loporte, G., Nobert, Y., and Desrochers, M., 1985. 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.
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.
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.
Marinakis, Y. and Marinaki, M., 2010. A hybrid genetic-Particle Swarm Optimization Algorithm for the vehicle routing problem. Expert Systems with Applications 37, 1446-1455.
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.
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., 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, 401-411.

簡易檢索 / 詳目顯示

相關論文