The joint order batching and vehicle routing problem with time window

Yıl 2024, Cilt: 39 Sayı: 4, 2223 - 2238, 20.05.2024

Esra Boz , Nil Aras

https://doi.org/10.17341/gazimmfd.1144003

Öz

During the Covid-19 pandemic, online shopping spread widely, and its quality is later improved and made permanent. Before it is enabled, online shopping is a very expensive and challenging process for businesses to manage, especially since customers can set a time window for their products. Customers may lose business and incur expenditures if the products they requested are not timely and of the appropriate quality supplied to them. Due to this, it is crucial to handle this difficult process well, and for this to happen, both in- and out-of-warehouse procedures must be carried out simultaneously. Order batching, a branch of the order picking process inside the warehouse, and vehicle routing, a distribution problem outside the warehouse, are these processes. The Combined Order Batching and Vehicle Routing Problem arises if these two procedures are considered as being integrated. The linked problem becomes the Integrated Order Batching and Vehicle Routing Problem with Time Window (OB_VRP_TW) when the time component is added. This study categorized and analyzed papers in the literature for OB_VRP_TW and created a novel mixed integer nonlinear programming model. Since just a part of the small data set can be handled by packet encoding programs and this developed model is linearized under specific circumstances, a metaheuristic search algorithm called the genetic algorithm is offered to solve that problem. The test data of the sub-problems were searched for, and the test data for the problem were added to the literature by combining the test data in the literature and some data of a company whose problems were applied, as there were no test data for the current problem in the relevant area.

Anahtar Kelimeler

Genetic algorithm, Order batching, Time window vehicle routing problem, Order picking problem

Proje Numarası

20DRP060

Bütünleşik sipariş gruplama ve zaman pencereli araç rotalama problemi

Öz

Online alışveriş, Covid-19 pandemi döneminde oldukça yaygınlaşmış ve sonrasında ise kalitesi arttırılarak kalıcı hale getirilmiştir. Online alışveriş süreci, özellikle müşterilerin, siparişlerinin ulaştırılması için zaman penceresi belirttiği hali ile, şirketler için etkin bir hale getirilene kadar yönetilmesi oldukça maliyetli ve zor bir süreçtir. Müşterilerin sipariş etmiş olduğu ürünler müşterilere zamanında ve doğru kalitede ulaştırılmadığı takdirde hem müşteri kaybı hem de maliyete neden olmaktadır. Bu yüzden, bu zorlu sürecin verimli bir şekilde yönetilmesi oldukça önemlidir ve doğru bir yönetim için depo içi ve depo dışı süreçlerin eş zamanlı olarak yürütülmesi gerekmektedir. Bu süreçler depo içinde sipariş toplama sürecinin bir alt dalı olan sipariş gruplama, depo dışında ise bir dağıtım problemi olan araç rotalama süreci olmaktadır. Bu iki süreç entegre olarak düşünülürse, bütünleşik Sipariş Gruplama ve Araç Rotalama Problemi oluşmaktadır. İlgili probleme zaman faktörü eklenmesi ile problem bütünleşik Sipariş Gruplama ve Zaman Pencereli Araç Rotalama Problemi (SG_ZP_ARP)’ ne dönüşmektedir. Bu çalışmada, SG_ZP_ARP için literatürdeki çalışmalar sınıflandırılarak incelenmiş ve yeni bir karma tamsayılı doğrusal olmayan programlama modeli geliştirilmiştir. Geliştirilen bu model, belirli koşullar altında doğrusallaştırılmış ve paket çözücü programlar ile yalnızca küçük boyutlu veri setinin bir kısmı çözülebildiğinden dolayı, problemin çözümü için bir metasezgisel arama algoritması olan Genetik Algoritma yaklaşımı önerilmiştir. İlgili alanda mevcut problem için test verileri olmadığından dolayı alt problemlerin test verileri araştırılmış ve bulunan literatürdeki test verileri ile problemleri problemin uygulaması yapılan bir firmanın bazı verileri entegre edilerek problem için test verileri literatüre eklenmiştir.

Anahtar Kelimeler

Genetik algoritma, Sipariş gruplama, Zaman pencereli araç rotalama problemi, Sipariş toplama problemi

Destekleyen Kurum

Eskişehir Teknik Üniversitesi

Proje Numarası

20DRP060

Kaynakça

• Altiparmak, F., Gen, M., Lin, L., & Karaoglan, I. (2009). A steady-state genetic algorithm for multi-product supply chain network design. Computers and Industrial Engineering, 56(2), 521–537. https://doi.org/10.1016/j.cie.2007.05.012
• Boz, E., & Aras, N. (2022). The order batching problem: A state-of-the-art review. Sigma Journal of Engineering and Natural Sciences, 40(2), 402–420. https://doi.org/10.14744/sigma.2022.00018
• Cergibozan, Ç., & Tasan, A. S. (2019). Order batching operations: an overview of classification, solution techniques, and future research. In Journal of Intelligent Manufacturing (Vol. 30, Issue 1, pp. 335–349). Springer New York LLC. https://doi.org/10.1007/s10845-016-1248-4
• Cergibozan, Ç., & Tasan, A. S. (2022). Genetic algorithm based approaches to solve the order batching problem and a case study in a distribution center. Journal of Intelligent Manufacturing, 33(1), 137–149. https://doi.org/10.1007/s10845-020-01653-3
• Chen, M. C., & Wu, H. P. (2005). An association-based clustering approach to order batching considering customer demand patterns. Omega, 33(4), 333–343. https://doi.org/10.1016/j.omega.2004.05.003
• Gademann, A., Berg, V. den, & H, H. (2001). An order batching algorithm for wave picking in a parallel-aisle warehouse. IIE Transactions, 33(5), 385–398.
• Gademann, N., & van de Velde, S. (2005). Order batching to minimize total travel time in a parallel-aisle warehouse. IIE Transactions (Institute of Industrial Engineers), 37(1), 63–75. https://doi.org/10.1080/07408170590516917
• Gen, M., & Cheng, R. (1999). Genetic algorithms and engineering optimization. John Wiley \& Sons.
• Gil-Borras, S., Pardo, E. G., Alonso-Ayuso, A., & Duarte, A. (2021). A heuristic approach for the online order batching problem with multiple pickersA heuristic approach for the online order batching problem with multiple pickers. Computers & Industrial Engineering, 160, 107517.
• Goetschalckx, M., & Donald Ratliff, H. (1988). Order picking in an aisle. IIE Transactions, 20, 53--62.
• Görçün, Ö. F. (2013). Depo ve envanter yönetimi (Beta Basım Yayım).
• Henn, S., Koch, S., Doerner, K. F., Strauss, C., & Wäscher, G. (2010). Metaheuristics for the order batching problem in manual order picking systems. Business Research, 3, 82–105.
• Holland, J. C. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
• 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. https://doi.org/10.1016/j.compind.2004.06.001
• Katoch, S., Chauhan, S. S., & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80(5), 8091–8126. https://doi.org/10.1007/s11042-020-10139-6
• Kuhn, H., Schubert, D., & Holzapfel, A. (2020). Integrated Order Batching and Vehicle Routing Operations in Grocery Retail – A General Adaptive Large Neighborhood Search Algorithm. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2020.03.075
• Li, H., Love, P. E. D., & Ogunlana, S. (1998). Genetic algorithm compared to nonlinear optimization for labour and equipment assignment. Building Research and Information, 26(6), 322–329. https://doi.org/10.1080/096132198369652
• Liberatore, F., Righini, G., & Salani, M. (2011). A column generation algorithm for the vehicle routing problem with soft time windows. 4OR, 9(1), 49–82. https://doi.org/10.1007/s10288-010-0136-6
• Lipowski, A., & Lipowska, D. (2012). Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and Its Applications, 391(6), 2193–2196.
• Marinakis, Y., Marinaki, M., & Migdalas, A. (2019). A Multi-Adaptive Particle Swarm Optimization for the Vehicle Routing Problem with Time Windows. Information Sciences, 481, 311–329. https://doi.org/10.1016/j.ins.2018.12.086
• Nicolas, L., Yannick, F., & Ramzi, H. (2018). Order batching in an automated warehouse with several vertical lift modules: Optimization and experiments with real data. European Journal of Operational Research, 267(3), 958–976. https://doi.org/10.1016/j.ejor.2017.12.037
• Öncan, T. (2015). MILP formulations and an Iterated Local Search Algorithm with Tabu Thresholding for the Order Batching Problem. European Journal of Operational Research, 243(1), 142–155. https://doi.org/10.1016/j.ejor.2014.11.025
• Pan, J. C.-Hsien., Shih, P.-Hsun., & Wu, M.-Hung. (2015). Order batching in a pick-and-pass warehousing system with group genetic algorithm. Omega, 57, 238–248.
• Pei, Z., Wang, Z., & Yang, Y. (2019). Research of Order Batching Variable Neighborhood Search Algorithm based on Saving Mileage.
• Pinto, A. R. F., & Nagano, M. S. (2019). An approach for the solution to order batching and sequencing in picking systems. Production Engineering, 13(3–4), 325–341. https://doi.org/10.1007/s11740-019-00904-4
• Roodbergen, K. J. (2001). Layout and routing methods for warehouses. ERIM, Erasmus Research Institute of Management].
• Schmid, V., Doerner, K. F., & Laporte, G. (2013). Rich routing problems arising in supply chain management. European Journal of Operational Research, 224(3), 435–448. https://doi.org/10.1016/j.ejor.2012.08.014
• Schulze, J., & Fahle, T. (1999). A parallel algorithm for the vehicle routing problem with time window constraints. Annals of Operations Research, 86, 585–607.
• Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254–265.
• Song, M., Li, J., Han, Y., Han, Y., Liu, L., & Sun, Q. (2020). Metaheuristics for solving the vehicle routing problem with the time windows and energy consumption in cold chain logistics. Applied Soft Computing, 95, 106561.
• Talbi, E.-G. (2009). Metaheuristics: from design to implementation (John Wiley).
• Toth, P., & Vigo, D. (1999). A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. European Journal of Operational Research, 113(3), 528–543.
• 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. https://doi.org/10.1080/00207540701441947
• Vinod, H. D. (1969). Integer Programming and the Theory of Grouping. Journal of the American Statistical Association, 64(326), 506–519. https://doi.org/10.1080/01621459.1969.10500990
• Xiang, X., Liu, C., & Miao, L. (2018). Storage assignment and order batching problem in Kiva mobile fulfilment system. Engineering Optimization, 50(11), 1941–1962. https://doi.org/10.1080/0305215X.2017.1419346
• Yağmur, E., & Kesen, S. E. (2020). A memetic algorithm for joint production and distribution scheduling with due dates. Computers & Industrial Engineering, 142, 106342.
• Yağmur, E., & Kesen, S. E. (2021). Multi-trip heterogeneous vehicle routing problem coordinated with production scheduling: Memetic algorithm and simulated annealing approaches. Computers & Industrial Engineering, 161, 107649.
• Yassen, E. T., Ayob, M., Nazri, M. Z. A., & Sabar, N. R. (2017). An adaptive hybrid algorithm for vehicle routing problems with time windows. Computers and Industrial Engineering, 113, 382–391. https://doi.org/10.1016/j.cie.2017.09.034
• Zhang, J., Wang, X., & Huang, K. (2016). Integrated on-line scheduling of order batching and delivery under B2C e-commerce. Computers and Industrial Engineering, 94, 280–289. https://doi.org/10.1016/j.cie.2016.02.001