Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması

Yıl 2018, Cilt: 22 Sayı: 2, 685 - 694, 15.08.2018

Serap Ercan Cömert , Harun Reşit Yazgan , İrem Sertvuran Hanife Şengül

https://doi.org/10.19113/sdufbed.20568

Cited By: 2

Öz

Bu çalışmada bir süpermarket zincirinin belirli zaman aralıklarında servis gören müşterilerinin taleplerinin karşılanmasında ortaya çıkan Sıkı Zaman Pencereli Araç Rotalama Problemi (SZRARP)’nin çözümü yapılmıştır. Önce kümele sonra rotala yaklaşımına dayanan iki aşamalı hiyerarşik bir yöntem önerilmiştir. İlk aşamada müşteriler K-medoids ve DBSCAN kümeleme algoritmaları kullanılarak araçlara atanmıştır. İkinci aşamada ise rotalama problemi MILP ile çözülmüştür. Çalışmanın en önemli katkısı, önerilen yöntem büyük boyutlu gerçek problemler ele alırken kesin çözüm yöntemlerini kullanmamıza olanak sağlamasıdır. Son olarak önerilen yaklaşım bir süpermarket zincirinde uygulanmış, iki algoritmanın sonuçları ve firmadan alınan gerçek sonuçlar ANOVA ile karşılaştırılmıştır. Test sonucuna göre DBSCAN’ın daha iyi sonuç verdiği görülmüştür.

Anahtar Kelimeler

Sıkı zaman pencereli araç rotalama problemi, Kümeleme; K-Medoids kümeleme algoritması; DBSCAN kümeleme algoritması

Kaynakça

• [1] Dantzig, G. B., Ramser, J. H. 1959. The Truck Dispatching Problem. Management Science, 6, 80-91.
• [2] Han, J., Kamber, M. 2001. Data Mining and Concepts Techniques. San Francisco: Morgan Kaufmann Publishers Inc.
• [3] Laporte, G., Semet, F. 2002. Classical Heuristics for the Capacitated VRP. ss 109-128. Toth, P., Vigo, D., ed. 2002. The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia.
• [4] Clarke, G., Wright, J. W. 1964. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12, 568-581.
• [5] Dumas, J. E., Wolf, L. C., Fisman, S. N., Culligan, A. 1991. Parenting stress, child behavior problems, and dysphoria in parents of children with autism, Down syndrome, behavior disorders, and normal development. Exceptionality, 2, 97–110.
• [6] Aydemir, E. 2006. Esnek Zaman Pencereli Araç Rotalama Problemi ve Bir Uygulama. Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Ankara.
• [7] Boer, J. W. D. 2008. Approximate Models and Solution Approaches for the Vehicle Routing Problem with Multiple Use of Vehicles and Time Windows. Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Orta Doğu Teknik Üniversitesi, Ankara.
• [8] Tezer, T. 2009. Toplama ve Dağıtım Zaman Pencereli Araç Rotalama Problemi için Kesin Çözüm Yaklaşımı ve Örnek Uygulamalar. Balıkesir Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Balıkesir.
• [9] Çetin, S., Gencer, C. 2010. Kesin Zaman Pencereli- Eş Zamanlı Dağıtım Toplamalı Araç Rotalama Problemi: Matematiksel Model. Gazi Üniv. Müh. Mim. Fak. Der., 25, 579-585.
• [10] Çetin, S., Gencer, C. 2011. Heterogeneous Fleet Vehicle Routing Problems with Time Windows and Simultaneous Pickup and Delivery: Mathematical Model. International Journal of Research and Development, 3, 19-27.
• [11] Çetinkaya, C. 2011. İki Aşamalı Hat Zaman Pencereli Araç Rotalama Problemi. Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Ankara.
• [12] Taş, D., Jabali, O., Woensel, T. V. 2014. A Vehicle Routing Problem with Flexible Time Windows. Computers & Operations Research, 52, 39–54.
• [13] Çetinkaya, C. 2014. Terör bölgelerine yapılan askeri sevkiyatlar için yer seçimi ve hat zaman pencereli araç rotalama problemi. Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Doktora Tezi, Ankara.
• [14] Akca, K. 2015. Hammadde Tedarik Aktivitesi için Kesin Zaman Pencereli Araç Rotalama Optimizasyonu. Uludağ Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Bursa.
• [15] Liu, F. H., Shen, S. Y. 1999. A Method for Vehicle Routing Problem with Multiple Vehicle Types and Time Windows. Proc. Natl. Sci. Counc. ROC(A), 23, 526-536.
• [16] Demircioğlu, M. 2009. Araç Rotalama Probleminin Sezgisel Bir Yaklaşım ile Çözümlenmesi Üzerine Bir Uygulama. Çukurova Üniversitesi, Fen Bilimleri Enstitüsü, Doktora Tezi, Adana.
• [17] Şahin, M., Şahin, G., Çavuşlar, G., Özcan, T., Tüzün, D. 2010. Separable Weight Pickup and Delivery Problem Using Tabu Search Algorithm. Operational research and Industrial Engineering 30th National Meeting, Sabancı Üniversitesi, Istanbul.
• [18] Schulze, J., Fahle, T. 1999. A Parallel Algorithm for the Vehicle Routing Problem with Time Window Constraints. Annals of Operations Research, 86, 585–607.
• [19] Ho, S., Haugland, D. 2004. A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows and Split Deliveries. Computers and Operations Research, 31, 1947–1964.
• [20] Jiang, J., Ng, K. M., Poh, K. L., Teo, K. M. 2014. Vehicle Routing Problem with a Heterogeneous Fleet and Time Windows. Expert Systems with Applications: An International Journal, 41, 3748-3760.
• [21] Barán, B., Schaerer, M. 2003. A Multiobjective Ant Colony System for Vehicle Routing Problem with Time Windows. Proceeding of the 21st IASTED International Conference Applied Informatics, 10-13 February, Innsbruck, Austria, 97-102.
• [22] Tokaylı, M. A. 2005. Zaman Pencereli Araç Rotalama Problemi için Bir Karar Destek Sistemi. Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Ankara.
• [23] Bouthillier, A. L., Crainic, T. G. 2005. A Cooperative Parallel Meta Heuristic for the Vehicle Routing Problem with Time Windows. Computers & Operations Research, 32, 1685–1708.
• [24] Dondo, R., Cerda, J. 2007. A Cluster-Based Optimization Approach for the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows. European Journal of Operational Research, 176, 1478–1507.
• [25] Dursun, P. 2009. Zaman Pencereli Araç Rotalama Probleminin Genetik Algoritma ile Modellenmesi. İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, İstanbul.
• [26] Nazif, H., Lee, L. S. 2010. Optimized Crossover Genetic Algorithm for Vehicle Routing Problem with Time Windows. American Journal of Applied Sciences, 7, 95-101.
• [27] Kiremitci, B., Kiremitci, S., Keskintürk, T. 2014. Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı. İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43, 391-403.
• [28] Gülsoy, N. 2013. Av Arama Algoritması ile Sıkı Zaman Pencereli Araç Rotalama Problemlerinin Çözümü. Erciyes Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Kayseri.
• [29] Iqbal, S., Kaykobad, M., Rahman, M. S. 2015. Solving the Multi-Objective Vehicle Routing Problem with Soft Time Windows with the Help of Bees. Swarm and Evolutionary Computation, 24, 50–64.
• [30] Çetin, S., Gencer, C. 2015. A Heuristic Algorithm for Vehicle Routing Problems with Simultaneous Pick-Up and Delivery and Hard Time Windows. Open Journal of Social Sciences, 3,35-41.
• [31] Hiquebran, D. T., Alfa, A. S., Shapiro, J. A., Gittoes, D. H. 2007. A revised simulated annealing and cluster-first route-second algorithm applied to the vehicle routing problem. Engineering Optimization, 22, 77-107.
• [32] Crainic, T. G., Mancini, S., Perboli, G., Tadei, R. 2008. Clustering-based heuristics for the two-echelon vehicle routing problem. Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation.
• [33] Çalışkan, K. 2011. Karınca Kolonisi Optimizasyonu ile Araç Rotalama Probleminin Maliyetlerinin Kümeleme Tekniği ile İyileştirilmesi. TOBB Ekonomi ve Teknoloji Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Ankara.
• [34] Boyzer, Z., Alkan, A., Fığlalı, A. 2014. Cluster-First, Then-Route Based Heuristic Algorithm for the Solution of Capacitated Vehicle Routing Problem. International Journal of Informatics Technologies, 7, 29-37.
• [35] Şen, T. 2014. Kümeleme ve Genetik Algoritma Destekli Yaklaşımlarla Kapasite Kısıtlı Araç Rotalama Probleminin Çözümü: Perakende Zincirinde Uygulanması. Sakarya Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Sakarya.
• [36] Rushton, A., Croucher, P., Baker, P. 2006. Handbook of Logistics and Distribution Management. 3rd edn, Kogan Page, Limited.
• [37] Ho, W., Ho, G. T. S., Ji, P., Lau, H. C. W. 2008. A Hybrid Genetic Algorithm for the Multi-Depot Vehicle Routing Problem. Engineering Applications of Artificial Intelligence, 21, 548–557.
• [38] Hax, A. C., Candea, D. 1984. Production and Inventory Management. Prentice-Hall, Englewood Cliffs, NJ.
• [39] Tan, K. C., Lee, L. H., Zhu, Q. L., OU, K. 2001. Heuristic Methods for Vehicle Routing Problem with Time Windows. Engineering Applications in Engineering, 15, 281-295.
• [40] Koç, Ö. N. 2012. Zaman Pencereli Gezgin Satıcı Problemi için Yeni Karar Modelleri. Başkent Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Ankara.
• [41] Kaufman, L., Rousseeuw, P. 1987. Clustering by Means of Medoids. No. 87 in Reports of the Faculty of Mathematics and Informatics, Delft University of Technology.
• [42] Işık, M. 2006. Bölünmeli Kümeleme Yöntemleri ile Veri Madenciliği Uygulamaları. Marmara Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, İstanbul.
• [43] Ester, M., Kriegel, H. P., Sander, J., Xu, X. 1996. A Destiny-Based Algorithm for Discovering Clusters In Large Spatial Databases with Noise. Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, Portland, 226-231.
• [44] Güven, A., Bozkurt, Ö., Kalıpsız, O. 2007. Veri Madenciliğinin Geleceği. IX. Akademik Bilişim Konferansı Bildirileri, Dumlupınar Üniversitesi, Kütahya.
• [45] Bilgin, T. T., Çamurcu, Y. 2005. Comparative Comparing of DBSCAN, OPTICS and K-Means Algorithms. Journal of Polytechnic, 8, 139-145.
• [46] Moreira, A., Santos, M. Y., Carneiro, S. 2005. Destiny-Based Clustering Algorithms-DBSCAN and SNN. University of Minho, Portugal.