Title

應用蟻群最佳化演算法求解越庫作業系統的車輛途程與卡車排序問題

Translated Titles

Simultaneous Vehicle Routing and Truck Sequencing Problem in Cross-Docking Systems with Ant Colony Optimization

DOI

10.6838/YZU.2013.00373

Authors

鄭廷棟

Key Words

越庫作業系統 ; 車輛途程問題 ; 卡車排序問題 ; 蟻群最佳化演算法 ; Cross-Docking ; Vehicle Routing Problem ; Truck Sequencing ; Ant Colony Optimization

PublicationName

元智大學工業工程與管理學系學位論文

Volume or Term/Year and Month of Publication

2013年

Academic Degree Category

碩士

Advisor

丁慶榮

Content Language

繁體中文

Chinese Abstract

如今全球貿易蓬勃發展,各大企業在成本的考量下,不少業者委外第三方物流倉儲及運送,在這繁複的貿易網路圖中,物流中心即為其中繼點,負責轉運、倉儲、資訊交流等重要功能。傳統的物流中心有四大主要功能:接收、倉儲、訂單揀貨和運輸,其中倉儲與員工揀貨是成本最高的。越庫作業系統 (Cross-Docking, CD) 為一種供應鏈管理中物流中心策略處理貨物的方法,貨品由物流中心接收後經由訂單資訊的整合,直接將貨物整合並送往出貨,目的在減少倉儲與人工揀貨之成本。本研究考量物流中心之成本,應用越庫作業系統,整合車輛途程問題 (Vehicle Routing Problem, VRP) 與卡車排序問題 (Truck Sequencing),目標為物流中心營運時間與總運輸時間最小化。首先建構混合整數規劃數學模型,由於此問題屬於NP-Hard問題,因此使用蟻群最佳化演算法 (Ant Colony Optimization, ACO) ,分別使用兩方法求解:方法一、使用兩階段求解,先找出最佳車輛途程後將車內貨品數量給予第二階段求解最佳卡車排序,方法二、應用同步處理的方式,每次迭代產生之菁英VRPCD螞蟻就建立一較優虛擬卡車序列螞蟻,並以此加強費洛蒙濃度,以兩問題總成本更新費洛蒙。使用Gurobi最佳化軟體驗證本研究之數學模型,得到之最佳解可以測試ACO之誤差;由於此兩問題合併在過去尚未有學者探討,故本研究參考文獻例題產生方式,產生30題測試例題。本研究應用兩種ACO程序,得到之結果顯示30題測試例題總平均而言ACO2得到較好的最小成本為9682.3確實改善了ACO1的結果,而30題中有25題得到的結果是優於ACO1的,並且經過敏感度分析,將ACO1的卡車排序部分使用Gurobi測試最佳解,結果證實本研究卡車排序部分皆找到最佳解,並且於ACO2中由於VRPCD部分影響較深,故測試了VRPCD多次的處理情形,結果顯示VRPCD處理10次後得到的結果相較原始的處理1次來的降低許多,故未來將持續探討如何將VRPCD部分深入測試,預期未來能夠改善使得更接近最佳解。

English Abstract

Nowadays, the global trade booming, the freights are passed in and out the distribution centers and between companies frequently. For cost considerations, many companies outsource transportation and warehousing activities to the third-part logistics providers. In this complex logistics network, the cross-dock center is the point where the trucks are responsible for pickup and delivery and transfer between inbound and outbound traffic. The traditional warehouse has four major functions: receiving, warehousing, order picking and transport, which warehousing and staff picking are cost-intensive activities. Cross-docking is a logistics strategy in which freight is unloaded from inbound vehicles and (almost) directly loaded into outbound vehicles, with little or no storage in between. This strategy aims to reduce the cost of warehousing and order picking. This study considers a cross-docking system which combines the vehicle routing problem with cross-docking (VRPCD) for both inbound and outbound operations and truck sequencing problem (Truck Sequencing) at docks. The objective is to minimize the logistics center operation costs and transportation costs. Both VRP and sequencing problems are NP-hard problem. We first formulated the integrated problem with a mixed integer programming model. Since the integrated problem is a NP-hard problem, only small size instance can be solved with optimization software within reasonable computational time. We propose two ant colony optimization (ACO) algorithms to solve the problem. The first algorithm (ACO1) solves the VRP and sequencing problem by two independent ant colonies sequentially, in which the sequencing problem solved based on the results of the VRP. The second algorithm (ACO2) solves both problems simultaneously and iteratively by sharing the information between two ant colonies. In this study, the Gurobi optimization software is used to validate the mathematical model and tested for small size instances. Since there are no test instances for this integrated problem, we generate 30 test problems. The results show that ACO2 can obtain the optimal solutions in small size instances. ACO2 can provide better solutions in 25 out of the 30 test problems than ACO1. Through sensitivity analysis, we also found that the truck sequencing problem is easier to get the optimal solution than the VRPCD. We believe the proposed ACO algorithms can be used for practical use for the cross-docking system. In the future, we could consider multiple dock operations at the cross-dock for a more complex system.

Topic Category 工程學院 > 工業工程與管理學系
工程學 > 工程學總論
社會科學 > 管理學
Reference
  1. 3. 羅敏華,「蟻群最佳化演算法於載重限制之車輛途程問題的研究」,元智大學工業工程與管理學系碩士學位論文,2003。
    連結:
  2. 4. Alpan, G., Ladier, A. L., Larbi, R. and Penz, B., “Heuristic solutions for transshipment problems in a multiple door cross docking warehouse”, Computers & Industrial Engineering, Vol. 61, No. 2, pp. 402-408, 2011.
    連結:
  3. 5. Apte, U. M. and Viswanathan, S, “Effective cross docking for improving distribution efficiencies”, International Journal of Logistics, Vol. 3, No. 3, pp. 291-302, 2000.
    連結:
  4. 7. Arabani, A. R. B., Ghomi, S. M. T. F. and Zandieh, M. “A multi-criteria cross-docking Sequencing with just-in-time approach”, The International Journal of Advanced Manufacturing Technology, Vol. 49, No. 5-8, pp. 741-756, 2010.
    連結:
  5. 8. Boloori Arabani, A. R., Fatemi Ghomi, S. M. T. and Zandieh, M., “Meta-heuristics implementation for Sequencing of trucks in a cross-docking system with temporary storage”, Expert Systems with Applications, Vol. 38, No. 3, pp. 1964-1979, 2011a.
    連結:
  6. 9. Boloori Arabani, A., Zandieh, M. and Ghomi, S. M. T., “Multi-objective genetic-based algorithms for a cross-docking Sequencing problem”, Applied Soft Computing, Vol. 11, No. 8, pp. 4954-4970, 2011b.
    連結:
  7. 10. Boysen, N. and Fliedner, M., “Cross dock Sequencing: classification, literature review and research agenda” Omega, Vol. 38, No. 6, pp. 413-422., 2010.
    連結:
  8. 11. Boysen, N., Fliedner, M. and Scholl, A., “Sequencing inbound and outbound trucks at cross docking terminals”, OR Spectrum, Vol. 32, No. 1, pp. 135-161, 2008.
    連結:
  9. 12. Boysen, N., “Truck Sequencing at zero-inventory cross docking terminals”, Computers & Operations Research, Vol. 37, No. 1, pp. 32-41, 2010.
    連結:
  10. 13. Bullnheimer, B., Hartl, R. F. and Strauss, C., “Applying the ant system to the vehicle routing problem”, Meta-Heuristics, pp. 285-296, Springer US, 1999.
    連結:
  11. 16. Dethloff, J., “Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up”, OR Spectrum, Vol. 23, No. 1, pp 79-96, 2001.
    連結:
  12. 19. Dorigo, M. and Gambardella, L. M., “Ant colonies for the travelling salesman problem”, BioSystems, Vol. 43, No. 2, pp. 73-81, 1997.
    連結:
  13. 20. Forouharfard, S. and Zandieh, M., “An imperialist competitive algorithm to schedule of receiving and shipping trucks in cross-docking systems”, International Journal of Advanced Manufacturing Technology, Vol. 51, No. 9-12, pp. 1179-1193, 2010.
    連結:
  14. 21. Hoff, A., Gribkovskaia, I., Laporte, G. and L#westeur057#kketangen, A., “Lasso solution strategies for the vehicle routing problem with pickups and deliveries”, European Journal of Operational Research, Vol. 192, No. 3, pp. 755-766, 2009.
    連結:
  15. 22. Hu, Z. M., Zhao, Y. and Choi, T. M., “Vehicle routing problem for fashion supply chains with cross-docking”, Mathematical Problems in Engineering, Vol. 2013, No. 10, pp. 1-10, 2013.
    連結:
  16. 23. Jayaraman, V. and Ross, A., “A simulated annealing methodology to distribution network design and management”, European Journal of Operational Research, Vol. 144, No. 3, pp. 629-645, 2003.
    連結:
  17. 25. Kinnear, E., “Is there any magic in cross-docking?”, Supply Chain Management: An International Journal, Vol. 2, No. 2, pp. 49-52, 1997.
    連結:
  18. 26. Lee, Y. H., Jung, J. W. and Lee, K. M., “Vehicle routing Sequencing for cross-docking in the supply chain”, Computers & Industrial Engineering, Vol. 51, No. 2, pp. 247-256, 2006.
    連結:
  19. 27. Liao, C. J., Lin, Y. and Shih, S. C., “Vehicle routing with cross-docking in the supply chain”, Expert Systems with Applications, Vol. 37, No. 10, pp. 6868-6873, 2010.
    連結:
  20. 28. Liao, T. W., Egbelu, P. J. and Chang, P. C., “Two hybrid differential evolution algorithms for optimal inbound and outbound truck sequencing in cross docking operations”, Applied Soft Computing, Vol. 12, No. 11, pp. 3683-3697, 2012.
    連結:
  21. 29. Liao, T. W., Egbelu, P. J. and Chang, P. C., “Simultaneous dock assignment and sequencing of inbound trucks under a fixed outbound truck schedule in multi-door cross docking operations”, International Journal of Production Economics, Vol. 141, No. 1, pp. 212-229, 2013.
    連結:
  22. 30. Mosheiov, G., “Vehicle routing with pick-up and delivery:Tour-partitioning heuristics”, Computers & Industrial Engineering, Vol. 34, No. 3, pp. 669-684, 1998.
    連結:
  23. 34. Santos, F. A., Mateus, G. R. and Salles da Cunha, A., “A branch-and-price algorithm for a vehicle routing problem with cross-docking”, Electronic Notes in Discrete Mathematics, Vol. 37, pp. 249-254, 2011a.
    連結:
  24. 35. Santos, F. A., Mateus, G. R. and Da Cunha, A. S., “A novel column generation algorithm for the vehicle routing problem with cross-docking”, Lecture Notes in Computer Science, Vol. 6701, pp. 412-425, 2011b.
    連結:
  25. 36. Sung, C. S. and Song, S. H., “Integrated service network design for a cross-docking supply chain network”, Journal of the Operational Research Society, Vol. 54, No. 12, pp. 1283-1295, 2003.
    連結:
  26. 37. Tang, F.A. and Galv#westeur036#o, R.D., “Vehicle routing problems with simultaneous pick-up and delivery service”, Journal of the Operational Research Society of India (OPSEARCH), Vol. 38, No. 1, pp. 19–33, 2002.
    連結:
  27. 38. Tang, F.A. and Galv#westeur036#o, R.D., “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service”, Computers & Operations Research, Vol. 33, No. 3, pp. 595-619, 2006.
    連結:
  28. 40. Vahdani, B. and Zandieh, M., “Sequencing trucks in cross-docking systems: Robust meta-heuristics”, Computers & Industrial Engineering, Vol. 58, No. 1, pp. 12-24, 2010.
    連結:
  29. 41. Van Belle, J., Valckenaers, P. and Cattrysse, D., “Cross-docking: State of the art”, Omega, Vol. 40, No. 6, pp. 827-846, 2012.
    連結:
  30. 42. Wasner, M. and Z#westeur037#phel, G., “An integrated multi-depot hub-location vehicle routing model for network planning of parcel service”, Computers & Operations Research, Vol. 90, No. 3, pp. 403–419, 2004.
    連結:
  31. 45. Yu, W. and Egbelu, P. J., “Sequencing of inbound and outbound trucks in cross docking systems with temporary storage”, European Journal of Operational Research, Vol. 184, No. 1, pp. 377-396, 2008.
    連結:
  32. 1. 王景昱,「應用粒子群最佳化於供應鏈中具接駁式轉運之車輛運途問題研究」,國立臺灣科技大學工業管理系碩士學位論文,2009。
  33. 2. 郭紋伶,「越庫作業系統之時窗車輛指派問題」,國立臺灣科技大學工業管理系碩士學位論文,2010。
  34. 6. Apte, U. M. and Viswanathan, S, “Strategic and technological innovations in supply chain managemen”, International Journal of Manufacturing Technology and Management, Vol. 4, No. 3-4, pp. 264-282, 2004.
  35. 14. Daneshzand, F., Logistics Operations and Management: Concepts and Models, Elsevier, London, pp. 127-153, 2011.
  36. 15. Davoudpour, H., Hooshangi-Tabrizi, P. and Hoseinpour, P., “A genetic algorithm for truck Sequencing in cross docking systems”, Journal of American Science, Vol. 8, No. 2, pp.96-99, 2012.
  37. 17. Doerner, K., Gronalt, M., Hartl, R. F., Reimann, M., Strauss, C. and Stummer, M., “SavingsAnts for the vehicle routing problem”, Applications of Evolutionary Computing (Editors: Cagnoni, S., Gottlieb, J., Hart, E., Middendorf, M. and Raidl, G. R.), Springer Berlin Heidelberg, Lecture Notes in Computer Science Vol. 2279, pp.11-20, 2002.
  38. 18. Dorigo, M., “Optimization, learning and natural algorithms”, Ph. D. Thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992.
  39. 24. Kawamura, H., Yamamoto, M., Mitamura, T., Suzuki, K. and Ohuchi, A., “Cooperative search based on pheromone communication for vehicle routing problems”, The Institute of Electronics, Information and communication Engineers (IEICE), Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E81-A, No. 6, pp. 1089-1096, 1998.
  40. 31. Reimann, M., Stummer, M. and Doerner, K., “A savings based ant system for the vehicle routing problem”, Proceedings of the Genetic and Evolutionary Computation Conference, Vol. 31, pp. 1317-13261, Morgan Kaufmann Publishers Inc., 2002.
  41. 32. Rodriguez Lopez, A. G., “Dock Assignment and Truck Sequencing at Cross-docking Terminals”, Master thesis, Yuan Ze University, 2011.
  42. 33. Rohrer, M., “Simulation and cross-docking”, Proceedings of the 27th conference on winter simulation, pp. 846-849, 1995.
  43. 39. Toth, P. and Vigo, D., “The vehicle routing problem,” SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, pp. 1-26, 2002.
  44. 43. Wen, M., Larsen, J., Clausen, J., Cordeau, J. F. and Laporte, G., “Vehicle routing with cross-docking”, Journal of the Operational Research Society, Vol. 60, No. 12, pp. 1708-1718, 2008.
  45. 44. Yu, W., “Operational strategies for cross docking systems”, Ph. D. Thesis., Iowa State University, Ames Iowa, 2002.