HIERARCHICAL SOLUTION OF ORDER PICKING AND CAPACITATED VEHICLE ROUTING PROBLEMS

Year 2015, Volume: 3 Issue: 1, 15 - 28, 27.04.2015

Yusuf Şahin , Abdullah Eroğlu

Abstract

The warehouses play a versatile role in the logistics management system. The objective of the warehousing function is to provide a buffer between supply and demand. In most warehouses, order picking is the major activity and involves collecting of products according to customer orders. On the other hand, it is necessary to plan the outside distribution of the orders. Determining the suitable distribution routes from one or more warehouses to a number of geographically separated customers is called vehicle routing problem in the literature. Although the order picking and vehicle routing problems are related to each other, they have been handled separately by this time. In this study, genetic algorithm based approaches which solve order picking and vehicle routing problems connected to each other in a hierarchical manner for both conventional and multiple cross aisles warehouse systems are proposed. While the groups of the orders and customers are determined using Genetic Algorithms, the routes of the vehicles are determined with the help of Savings and Nearest Neighbor Heuristics. In order to investigate the effectiveness of proposed methods, 24 well-known test problems are conducted and the obtained results are compared with previous researches. In conclusion, the improved genetic algorithm based solution approaches provided very close results to the known best results

Keywords

Order picking, Vehicle routing, Genetic Algorithm, Savings, Nearest Neighbour

SİPARİŞ TOPLAMA VE KAPASİTE KISITLI ARAÇ ROTALAMA PROBLEMLERİNİN HİYERARŞİK ÇÖZÜMÜ

Abstract

Depolar lojistik yönetim sisteminde çok yönlü bir rol oynar. Depolama fonksiyonunun amacı, talep ile tedarik arasında bir tampon sağlamaktır. Depoların birçoğunda sipariş toplama ana faaliyettir ve ürünlerin müşteri taleplerine göre depolardaki konumlarından toplanmasını içerir. Diğer taraftan, siparişlerin dış dağıtımının da planlanması gerekir. Bir veya daha fazla depodan coğrafi olarak dağılmış olan müşterilere yapılacak olan dağıtım için uygun rotanın belirlenmesi literatürde araç rotalama problemi olarak adlandırılır. Sipariş toplama ve araç rotalama problemleri birbiri ile ilişkili problemler olmasına rağmen bugüne kadar ayrı ayrı ele alınmışlardır. Bu çalışmada, sipariş toplama ve araç rotalama problemlerini hem klasik hem de çapraz geçitli depo sistemlerinde eş zamanlı olarak çözebilen genetik algoritma esaslı yöntemler önerilmektedir. Müşteri ve sipariş grupları genetik algoritma ile belirlenirken, araç rotaları tasarruf ve en yakın komşu sezgiselleri yardımıyla belirlenmiştir. Önerilen yöntemlerin etkinliğini araştırmak için bilinen 24 test problemi ile deneyler yapılmış ve sonuçları önceki çalışmalar ile karşılaştırılmıştır. Sonuç olarak, geliştirilen genetik algoritma esaslı çözüm yöntemleri bilinen en iyi çözümlere yakın çözümler sağlamıştır.

Keywords

Sipariş Toplama, Araç Rotalama, Genetik Algoritma, Tasarruf, En Yakın Komşu

References

• Alba, E., & Dorronsoro, B., 2005. The Exploration/Exploitation Tradeoff in Dynamic Cellular Genetic Algorithms. IEEE, Transactions on Evolutionary Computation, 9, 26-142.
• Altınel, İ.K., & Öncan, T., 2005. A New Enhancement of the Clarke and Wright Savings Heuristic for the Capacitated Vehicle Routing Problem. Journal of the Operational Research Society, 56 (8), 954-961.
• Augerat P., Belenguer J., Benavent E., Corbern A., Naddef D., & Rinaldi G., 1995 Computational results with a branch and cut code for the capacitated vehicle routing problem (Res. Raep. No. 949-M). Grenoble, France: Joseph Fourier Universitesi.
• Baker B.M., & Ayechew M.A., 2003. A genetic algorithm for the vehicle routing problem. Computers & Operations Research 30, 787-800.
• Bottani, E., Cecconi, M., Vignali, G., & Montanari, R., 2012. Optimisation of storage allocation in order picking operations through a genetic algorithm. International Journal of Logistics Research and Applications, 15 (2), 127-146.
• Clarke, G. & Wright, J.W., 1964. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12, 568-581.
• Coyle, J. J., Bardi, E. J., & Langley, C. J., 1996. The Management of Business Logistics. St Paul: West Publishing.
• Croes, G.A., 1958. A method for solving large scale symmetric traveling salesman problems to optimality. Operations Research, 6:791–812.
• Çetin, S., & Gencer, C., 2010. Kesin zaman Pencereli - Eş Zamanlı Dağıtım Toplamalı Araç Rotalama Problemi: Matematiksel Model. Gazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi, 25 (3): 579-585.
• Dantzig, G.B., Ramser, J.M. 1959. The truck dispatching problem. Management Science, 6, 81– 91.
• El Hassani, A.J., Bouhafs, L., Koukam, A., 2008. A Hybrid Ant Colony System Approach for the Capacitated Vehicle Routing Problem and the Capacitated Vehicle Routing Problem with Time Windows. Tonci Caric & Hrvoje Gold (Edt), Vehicle Routing Problem içinde (s. 59-70). Viyana, I-Tech Education and Publishing KG.
• Eryavuz, M., Gencer, C., 2001. Araç Rotalama Problemine Ait Bir Uygulama. Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 6 (1), 139-155.
• Gen, M., & Cheng, R., 1997, "Genetic Algorithms and Engineering Design", Amerika Birleşik Devletleri, John Wiley & Sons, Inc.
• Goldberg, D., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, Boston: MA: Addison-Wesley Professional.
• Henn, S., Koch, S., Doerner, K., Strauss, C., & Wäscher, G., 2010. Metaheuristics for the Order Batching Problem in Manual Order Picking Systems. BuR- Business Research, 3 (1), 82-105.
• Hinton, T.G:, 2010. The Vehicle Routing Problem including a range of Novel Techniques for its Solution. Yayınlanmamış Doktora Tezi. Bristol Üniversitesi, İngiltere.
• Hsu, C.M., Chen, K.Y., & Chen, M.C., 2005. Batching orders in warehouses by minimizing travel distance with genetic algorithms. Computers in Industry, 56 (2), 169-178.
• Jaszkiewicz, A., & Kominek, P., 2003. Genetic local search with distance preserving recombination operator for a vehicle routing problem. Meta- heuristics in combinatorial optimization, 151 (2), 352-364.
• Jaszkiewicz, A., Ishibuchi, H., & Zhang, Q., 2012. Multiobjective Memetic Algorithms. F. Neri, C. Cotta, P. Moscato (Edt.), Handbook of Memetic Algorithms, içinde (s. 201-217). Berlin: Springer- Verlag, Berlin Heidelberg.
• Kulak, O., Şahin, Y., & Taner, M.E., 2012. Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster- based tabu search algorithms. Flexible Services and Manufacturing Journal, 24 (1), 52-80.
• Lambert, D.M., Stock, J.R. & Ellram, L.M. 1998. Fundamentals of logistics management. Londra: McGraw-Hill.
• Laporte G., 1992. The Vehicle Routing Problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59, 345 – 358.
• Laporte, G., & Semet, F. 2002. Classical heuristics for the capacitated VRP. Toth, P., Vigo, D. (Edt.), The Vehicle Routing Problem içinde (s. 109-128). Philadelphia: SIAM.
• Mester, D., & Braysy, O., 2007. Active-guided evolution strategies for large-scale capacitated vehicle operations Research, 34 (10), 2964-2975. Computers &
• Na, B., Jun, Y., & Kim, B.I., 2011. Some extensions to the sweep algorithm. Int J Adv Manuf Tech, 56, 1057–67.
• Nazif, H., & Lee. L.S., 2012. Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling, 36, 2110-2117.
• Or, I., 1976. Travelling Salesman-Type Combinatorial Problems and Their Relaation to Logistics of Regional Blood Banking. Yayınlanmamış Doktora Tezi, Nortwestern Üniversitesi, Evanston, III.
• Pichpibula, T., & Kawtummachai R., 2012. An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem. ScienceAsia, 38, 307-318.
• Roodbergen, K.J., & De Koster, R. 2001. Routing order pickers in a warehouse with a middle aisle. European Journal of Operational Research, 133 (1), 32-43.
• Şahin, Y., & Kulak, O. 2013. Depo Operasyonlarının Planlanması İçin Genetik Algoritma Esaslı Modeller. Uluslararası Alanya İşletme Fakültesi Dergisi, 5 (3), 141-153.
• Şahin, Y., 2009. Depo Operasyonlarının Planlanması İçin Genetik Algoritma Esaslı Bir Model. Yayınlanmamış Yüksek Lisans Tezi, Pamukkale Üniversitesi Fen Bilimleri Enstitüsü, Denizli.
• Şahin, Y., Eroğlu, A., 2014, "Kapasite Kısıtlı Araç Rotalama Problemi İçin Metasezgisel Yöntemler: Bilimsel Yazın Taraması", Süleyman Demirel Üniversitesi İ.İ.B.F. Dergisi, 19 (4), 337-355.
• Toth, P., Vigo, D. 2002. An overview of vehicle routing problems. Toth, P., & Vigo, D. (Edt.), The Vehicle Routing Problem içinde (s. 1-26). Philadelphia: SIAM.
• Tsai, C.-Y., Liou, J.J.H., & Huang, T.-M. 2008. Using a multiple-GA method to solve the batch picking problem: considering travel distance and order due time. International Journal of Production Research, 46 (22), 6533-6555
• Wang, C.H. & Lu, J.Z., 2009. A hybrid genetic algorithm that optimizes capacitated vehicle routing problems. J Expert Syst. Appl.,36 (2), 2921-2936.
• Won J., & Olafsson S., 2005. Joint order batching and order International Journal Of Production Research, 43 (7), 1427-1442. warehouse operations.
• Zhang, H., & Liu, B., 2009. A New Genetic Algorithm for Order-Picking of Irregular Warehouse. International Conference on Environmental Science and Information Application Technology, 1, 121-124.