研究兩階段禁忌搜尋法於物流管理中具接駁式轉運之車輛運途問題

簡易檢索 / 詳目顯示

回結果列表

研究生：	王朝慶 Chao-ching Wang
論文名稱：	研究兩階段禁忌搜尋法於物流管理中具接駁式轉運之車輛運途問題 On the Study of Two-stage Tabu Search to Solve the Vehicle Routing Problem with Cross-Docking in Logistics Management
指導教授：	羅士哲 Shih-che Lo
口試委員:	王福琨 Fu-kwun Wang 蔡鴻旭 Hung-hsu Tsai
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業管理系 Department of Industrial Management
論文出版年：	2011
畢業學年度：	99
語文別：	英文
論文頁數：	74
中文關鍵詞：	接駁式轉運、物流運籌、禁忌搜尋法、車輛運途、k-means群集分析法
外文關鍵詞：	Cross-docking, Logistic, Tabu search algorithm, Vehicle routing problem, k-means algorithm
相關次數：	點閱：490 下載：4
分享至:	分享至facebook 分享至twitter

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

上一筆

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

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 Tabu Search algorithm is proposed in this thesis to solve the combinatorial optimal solution of the vehicle routing problem with Cross-docking. The Tabu Search algorithm combined with the k-means method to 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 proposed algorithm. Experiment results show that the proposed algorithm was able to discover new solutions than the GA for all 60 benchmarks problems. Also, the computational results show that the proposed algorithm is robust, converge fast and competitive with overall improvement of 11.16% over the GA.

摘要 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 8
2.4	Tabu Search (TS) 13
2.4.1	The Basis of Tabu Search 13
2.4.2	GA and TS 20
CHAPTER 3 PROBLEM FORMULATION AND TABU SEARCH ALGORITHM 22
3.1	Problem Proposition 22
3.1.1	General VRP 22
3.1.2	VRP with Cross-docking System 24
3.2	K-means Method 28
3.3	Tabu Search Algorithm 34
3.3.1	Types of Memory 34
3.3.2	Basis components of Tabu Search 35
3.3.3	Main elements of Tabu Search 36
CHAPTER 4 COMPUTATIONAL EXPERIMENTS 40
4.1	Preliminary Test 40
4.2	Computational Results 41
CHAPTER 5 CONCLUSIONS AND FUTURE RESEARCH 47
5.1	Conclusions 47
5.2	Further Research 48
REFERENCES 49
Appendix A. The solution of the Tabu Search algorithm for Instance 4P1. 55
Appendix B. The Best Routing Plan of the Tabu Search algorithm for Instance 4P1. 56
Appendix C. The solution of the Tabu Search algorithm for Instance 7P1. 57
Appendix D. The Best Routing Plan of the Tabu Search algorithm for Instance 7P1. 58
Appendix E. The solution of the Tabu Search algorithm for Instance 10P1. 59
Appendix F. The Best Routing Plan of the Tabu Search algorithm for Instance 10P1. 60
Appendix G. The solution of the Tabu Search algorithm for Instance 52P1. 61
Appendix H. The Best Routing Plan of the Tabu Search algorithm for Instance 52P1. 62
Appendix I. The solution of the Tabu Search algorithm for Instance 53P1. 63
Appendix J. The Best Routing Plan of the Tabu Search algorithm for Instance 53P1. 64
Appendix K. The solution of the Tabu Search algorithm for Instance 54P1. 65
Appendix L. The Best Routing Plan of the Tabu Search algorithm for Instance 54P1. 66

                                

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.
Alander, J. 1992. On Optimal Population Size of Genetic Algorithm. CompEuro’92. Computer Systems and Software Engineering, Proceedings, 65-70.
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.
Barichard, V. and Hao, J.K., 2003. Genetic Tabu Search for the Multi-Objective Knapsack Problem. Tsinghua Science and Technology, 8 (1), 8-13.
Barbarosoglu, G. and Ozgur, D., 1999. A Tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 26, 255-270.
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 and operations Research, 34(2), 578-594.
Ç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.
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.
Christodides, N., Mingozze, A., and Toth, P., 1979. Contributions to the quadratic assignment problem. European Journal of Operational Research, 4(4), 243-247.
Cordeau, J.F. and Laporte, G., 2002. Tabu Search Heuristics for the Vehicle Routing Problem. Les Cahiers du GERAD, G-2002-15.
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.
Duncan, T., 1995. Experiment in the use of Neighbourhood Search techniques for Vehicle Routing. Artificial Intelligence Applications Institute, University of Edinburgh.
Gendreau, M., Hertz A., and Laporte G., 1994. A Tabu search heuristic for the vehicle routing problem. Management Science, 40 (10), 1276-1290.
Glover, F., 1986. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research, 13( 5), 533-549.
Glover, F., 1989a. Tabu Search - Part I. ORSA Journal on Computing, 1( 3), 190-206.
Glover, F., 1989b. Tabu Search-Part II. Operations Research Society of America, 2(1), 4-32.
Glover, F., 1990. Tabu Search: A Tutorial. Interfaces, 20, 74-94.
Glover, F. and Laguna, M., 1997. Tabu Search. Kluwer Academic Publishers, Boston.
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.
Huang, F. and Liu, C.S., 2010a. An Improved Tabu Search for Open Vehicle Routing Problem. 2010 International Conference on Management and Service Science (MASS), 1-4.
Huang, F. and Liu, C.S., 2010b. A hybrid Tabu Search for Open Vehicle Routing Problem. 2010 International Conference on Computer and Communication Technologies in Agriculture Engineering,132-134.
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., 1991. 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., 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., Song, J.H., 2001. Special Kind of Vehicle Routing Problem. Journal of Northeastern University (Natural Science), 22 (3), 245-248.
Liao, C.J., Lin, Y.M., 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.
MacQueen, J., 1967. Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281-297.
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.
Prins, C., 2004. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31, 1985-2002.
Ralambondrainy, H., 1995. A conceptual version of the K-means algorithm. Pattern Recognition Letters, 16, 1147-1157.
Renaud, J., Laporte, G., and Boctor, F.F., 1996. A Tabu Search Heuristic for the Multi-depot Vehicle Routing Problem. Computers Operations Research, 23(3), 229-235.
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.
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.
Stalk, G., Evans, P., and Shulman, L.E., 1992. Competing on Capabilities: The New Rules of Corporate Strategy. Harvard Business Review, 70, 57-69.
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.
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.
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.
Taillard, E., 1993. Parallel iterative search methods for vehicle routing problems. Networks, 23(8), 661-673.
Toth, P. and Vigo, D., 2001. The vehicle routing problem. Monographs on Discrete Mathematics and Applications. Philadelphia, PA: SIAM.
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.
Willard, J.A.G., 1989. Vehicle routing using r-optimal tabu search. MSc. Dissertation. The management school, Imperial College.
Xu, D.G., Xiao, R.B., and Wang, S.X., 2008. An Improved Tabu Search for the Split Delivery VRP. Proceedings of 2008 IEEE International on IT in Medicine and Education, 945-948.
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., 2010. A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications. 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.

簡易檢索 / 詳目顯示

相關論文