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

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

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

References

1. 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. Chen, D. Y. (2017). Pandas for everyone: Python data analysis. Addison-Wesley Professional.
8. 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

9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. Energy Market Regulatory Authority. (2023). Akaryakıt Fiyatları. EPDK. https://www.epdk.gov.tr/Detay/Icerik/21-48/akaryakit-fiyatlari
16. 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
17. 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
18. 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
19. 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
20. 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
21. 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
22. Kumar, S. N., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. https://doi.org/10.4236/iim.2012.43010
23. 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
24. 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
25. 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
26. 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
27. Linderoth, J. T., & Lodi, A. (2010). MILP software. Wiley encyclopedia of operations research and management science, 5, 3239-3248.
28. 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
29. Mitchell, J. E. (2002). Branch-and-cut algorithms for combinatorial optimization problems. Handbook of applied optimization, 1(1), 65-77.
30. 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
31. 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.
32. Özaydın, E. (2003). Capacitated vehicle routing problem with time windows (Doctoral dissertation). https://research.sabanciuniv.edu/id/eprint/8533
33. 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
34. 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
35. 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
36. Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
37. Ş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.
38. 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
39. 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
40. Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for industrial and applied mathematics.
41. Ü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
42. 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