OPTIMIZING READY-MIXED CONCRETE TRANSPORTATION BY A TRUCK MIXER ROUTING MODEL FOR CONCRETE PLANTS

Year 2024, Volume: 12 Issue: 4, 802 - 820, 25.12.2024

Ozan Aykut Dönmez , Erdinç Öner

https://doi.org/10.21923/jesd.1445781

Abstract

This study aims to develop a truck mixer routing model to increase the efficiency of concrete delivery operations in concrete plants and to propose suitable solution methods for the model. In this study, a mixed-integer linear programming model was developed, based on a variant of the vehicle routing problem known as the capacitated vehicle routing problem with time windows, by incorporating constraints specific to concrete transportation. The objective of the model is to reduce transportation costs by minimizing the total distance travelled by truck mixers and the total number of truck mixers used. The model was first addressed by exact solution methods in Gurobi Optimizer. Since the vehicle routing problem is classified as an NP-hard problem, the complexity of the model increases with the number of customers, leading to a longer computation time. Thus, the model was addressed by a heuristic method developed for this study. The results show that the Gurobi Optimizer provided optimal solutions for up to 15 customers and 15 vehicles within a reasonable computation time, whereas the heuristic method quickly provided near-optimal solutions with a 3.39% cost increase on average.

Keywords

Concrete Delivery, Optimization, Time Windows, Truck Mixer, Vehicle Routing Problem

BETON SANTRALLERİ İÇİN BİR TRANSMİKSER ROTALAMA MODELİ İLE HAZIR BETON TAŞIMACILIĞININ OPTİMİZE EDİLMESİ

Abstract

Bu çalışma hazır beton santrallerinin beton sevkiyatı verimliliğini arttırmaya yönelik bir transmikser rotalama modeli oluşturmayı ve bu modele uygun çözüm yöntemlerini sunmayı amaçlamaktadır. Bu çalışmada araç rotalama probleminin bir çeşidi olan kapasite kısıtlı ve zaman pencereli araç rotalama problemi kullanılarak, hazır beton taşıma operasyonlarına özgü kısıtlar da eklenerek, bir karma tam sayılı doğrusal programlama modeli oluşturulmuştur. Bu modelin amacı transmikserlerin katettiği toplam mesafeyi ve kullanılan toplam transmikser sayısını azaltarak, taşıma operasyonlarının maliyetini azaltmaktır. Model ilk olarak Gurobi Optimizer kullanılarak kesin çözüm yöntemleriyle ele alınmıştır. Fakat araç rotalama probleminin NP-zor sınıfında olması, müşteri sayısı arttıkça modelin karmaşıklığını arttırmıştır ve bu da problemin çözüm süresini uzatmıştır. Bu nedenle model, bu çalışma için geliştirilen sezgisel bir yöntemle çözülmüştür. Elde edilen sonuçlar, Gurobi Optimizer’in makul bir hesaplama süresiyle 15 müşteriye ve 15 araca kadar optimal çözümler sağladığını, sunulan sezgisel yöntemin ise ortalama 3.39%’lık bir maliyet artışıyla hızlı bir şekilde optimale yakın çözümler verdiğini göstermektedir.

Keywords

Araç Rotalama Problemi, Beton Sevkiyatı, Optimizasyon, Transmikser, Zaman Penceresi

References

• Aydemir, E., Karagül, K., & Tokat, S. (2016). KAPASİTE KISITLI ARAÇ ROTALAMA PROBLEMLERİNDE BAŞLANGIÇ ROTALARININ KURULMASI İÇİN YENİ BİR ALGORİTMA. Mühendislik Bilimleri Ve Tasarım Dergisi, 4(3), 215-226. https://doi.org/10.21923/jesd.60313
• Baldacci, R., Mingozzi, A., & Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1), 1-6. https://doi.org/10.1016/j.ejor.2011.07.037
• Borcinova, Z. (2017). Two models of the capacitated vehicle routing problem. Croatian Operational Research Review, 463-469. https://doi.org/10.17535/crorr.2017.0029
• Brandao, J. (2006). A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research, 173(2), 540-555. https://doi.org/10.1016/j.ejor.2005.01.042
• Bräysy, O., & Gendreau, M. (2005). Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transp. Sci., 39, 104-118. https://doi.org/10.1287/trsc.1030.0056
• Bruno, L. (2019). Solving a food-delivery problem with a Vehicle Routing Problem-based approach (Doctoral dissertation, Politecnico di Torino). http://webthesis.biblio.polito.it/id/eprint/10456
• Chen, D. Y. (2017). Pandas for everyone: Python data analysis. Addison-Wesley Professional.
• Chen, S., Golden, B., & Wasil, E. (2007). The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results. Networks: An International Journal, 49(4), 318-329. https://doi.org/10.1002/net.20181
• Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581. https://doi.org/10.1287/opre.12.4.568
• Cook, W., & Rich, J. L. (1999). A parallel cutting-plane algorithm for the vehicle routing problem with time windows. https://hdl.handle.net/1911/101910
• Cordeau, J. F., & Laporte, G. (2005). Tabu search heuristics for the vehicle routing problem (pp. 145-163). Springer US. https://doi.org/10.1007/0-387-24977-X_9
• Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91. https://doi.org/10.1287/mnsc.6.1.80
• Dönmez, O. A. (2024). Optimizing ready-mixed concrete transportation by a truck mixer routing model for concrete plants [Master’s thesis, Yaşar University]. Council of Higher Education (YÖK) Thesis Center (Thesis No. 874566). https://tez.yok.gov.tr/UlusalTezMerkezi
• El-Sherbeny, N. A. (2010). Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University-Science, 22(3), 123-131. https://doi.org/10.1016/j.jksus.2010.03.002
• Energy Market Regulatory Authority. (2023). Akaryakıt Fiyatları. EPDK. https://www.epdk.gov.tr/Detay/Icerik/21-48/akaryakit-fiyatlari
• Erdoğan, S., & Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation research part E: logistics and transportation review, 48(1), 100-114. https://doi.org/10.1016/j.tre.2011.08.001
• Fitriani, N. A., Pratama, R. A., Zahro, S., Utomo, P. H., & Martini, T. S. (2021). Solving capacitated vehicle routing problem using saving matrix, sequential insertion, and nearest neighbor of product ‘X’in Grobogan district. https://doi.org/10.1063/5.0039295
• Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. D., Reis, M., Uchoa, E., & Werneck, R. F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical programming, 106, 491-511. https://doi.org/10.1007/s10107-005-0644-x
• Gursel, A. P., Masanet, E., Horvath, A., & Stadel, A. (2014). Life-cycle inventory analysis of concrete production: A critical review. Cement and Concrete Composites, 51, 38-48. https://doi.org/10.1016/j.cemconcomp.2014.03.005
• Keskintürk, T., Topuk, N., & Özyeşil, O. (2015). Araç rotalama problemleri ve çözüm yöntemleri. İşletme Bilimi Dergisi, 3(2), 77-107. https://dergipark.org.tr/en/pub/jobs/issue/22921/245436
• Kinable, J., Wauters, T., & Berghe, G. V. (2014). The concrete delivery problem. Computers & Operations Research, 48, 53-68. https://doi.org/10.1016/j.cor.2014.02.008
• Kumar, S. N., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. https://doi.org/10.4236/iim.2012.43010
• Laporte, G., Gendreau, M., Potvin, J. Y., & Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International transactions in operational research, 7(4‐5), 285-300. https://doi.org/10.1111/j.1475-3995.2000.tb00200.x
• Lenstra, J. K., & Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227. https://doi.org/10.1002/net.3230110211
• Li, X. (2015). Capacitated vehicle routing problem with time windows: a case study on pickup of dietary products in nonprofit organization. Arizona State University. https://keep.lib.asu.edu/_flysystem/fedora/c7/142371/Li_asu_0010N_15360.pdf
• Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. Y. (2014). Survey of green vehicle routing problem: past and future trends. Expert systems with applications, 41(4), 1118-1138. https://doi.org/10.1016/j.eswa.2013.07.107
• Linderoth, J. T., & Lodi, A. (2010). MILP software. Wiley encyclopedia of operations research and management science, 5, 3239-3248.
• Lysgaard, J., Letchford, A. N., & Eglese, R. W. (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical programming, 100, 423-445. https://doi.org/10.1007/s10107-003-0481-8
• Mitchell, J. E. (2002). Branch-and-cut algorithms for combinatorial optimization problems. Handbook of applied optimization, 1(1), 65-77.
• Nazif, H., & Lee, L. S. (2012). Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling, 36(5), 2110-2117. https://doi.org/10.1016/j.apm.2011.08.010
• Nurcahyo, G. W., Alias, R. A., Shamsuddin, S. M., & Sap, M. N. M. (2002). Sweep algorithm in vehicle routing problem for public transport. Jurnal Antarabangsa Teknologi Maklumat, 2, 51-64.
• Özaydın, E. (2003). Capacitated vehicle routing problem with time windows (Doctoral dissertation). https://research.sabanciuniv.edu/id/eprint/8533
• Pichpibul, T., & Kawtummachai, R. (2012). An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem. ScienceAsia, 38(3), 307-318. https://doi.org/10.2306/scienceasia1513-1874.2012.38.307
• Pop, P. C., Zelina, I., LupÅŸe, V., Sitar, C. P., & Chira, C. (2011). Heuristic algorithms for solving the generalized vehicle routing problem. International Journal of Computers Communications & Control, 6(1), 158-165. https://www.univagora.ro/jour/index.php/ijccc/article/view/2210
• Schmid, V., Doerner, K. F., Hartl, R. F., &tas Salazar-González, J. J. (2010). Hybridization of very large neighborhood search for ready-mixed concrete delivery problems. Computers & operations research, 37(3), 559-574. https://doi.org/10.1016/j.cor.2008.07.010
• Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
• Şahin, Y., & Eroğlu, A. (2015). SİPARİŞ TOPLAMA VE KAPASİTE KISITLI ARAÇ ROTALAMA PROBLEMLERİNİN HİYERARŞİK ÇÖZÜMÜ. Mühendislik Bilimleri Ve Tasarım Dergisi, 3(1), 15-28.
• Tan, K. C., Lee, L. H., Zhu, Q. L., & Ou, K. (2001). Heuristic methods for vehicle routing problem with time windows. Artificial intelligence in Engineering, 15(3), 281-295. https://doi.org/10.1016/S0954-1810(01)00005-X
• Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123(1-3), 487-512. https://doi.org/10.1016/S0166-218X(01)00351-1
• Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for industrial and applied mathematics.
• Ünsal, Ö., & Yiğit, T. (2018). YAPAY ZEKA VE KÜMELEME TEKNİKLERİ KULLANILARAK GELİŞTİRİLEN YÖNTEM İLE OKUL SERVİSİ ROTALAMA PROBLEMİNİN OPTİMİZASYONU. Mühendislik Bilimleri Ve Tasarım Dergisi, 6(1), 7-20. https://doi.org/10.21923/jesd.340220
• Van Der Walt, S., Colbert, S. C., & Varoquaux, G. (2011). The NumPy array: a structure for efficient numerical computation. Computing in science & engineering, 13(2), 22-30. https://doi.org/10.1109/MCSE.2011.37