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

SERTVURAN, İrem; ŞENGÜL, Hanife; yazgan, harun resit; CÖMERT ERCAN, Serap

doi:10.19113/sdufbed.20568

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

Serap CÖMERT ERCAN, (Sakarya Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Sakarya, Türkiye)

Harun Reşit YAZGAN, (Sakarya Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Sakarya, Türkiye)

İrem SERTVURAN, (Sakarya Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Sakarya, Türkiye)

Hanife ŞENGÜL (Sakarya Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Sakarya, Türkiye)

Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi

0 0

Yıl: 2018 Cilt: 22 Sayı: 2 Sayfa Aralığı: 685 - 694 Metin Dili: Türkçe DOI: 10.19113/sdufbed.20568 İndeks Tarihi: 25-11-2020

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

Öz:

Bu çalışmada bir süpermarket zincirinin belirli zaman aralıklarındaservis 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 veDBSCAN kümeleme algoritmaları kullanılarak araçlara atanmıştır. İkinciaş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 elealınırken kesin çözüm yöntemlerini kullanmamıza olanak sağlamasıdır.Son olarak önerilen yaklaşım bir süpermarket zincirinde uygulanmış, ikialgoritmanın sonuçları ve firmadan alınan gerçek sonuçlar ANOVA ilekarşılaştırılmıştır. Test sonucuna göre DBSCAN’ın daha iyi sonuç verdiğigörülmüştür.

Anahtar Kelime:

A New Method for the Solution of Vehicle Routing Problem with Hard Time Windows and A Supermarket Chain Application

Öz:

In this study, VRPHTW (Vehicle routing problem with hard time windows) which appeared to meet demands of customers serviced within time intervals in a supermarket chain is solved. A hierarchical approach consisted of two stages as "cluster-first route-second” is proposed. In the first stage, customers are assigned to vehicles using different clustering algorithms as K-Medoids and DBSCAN. In the second stage, a VRPHTW is solved by a MILP. The main contribution of the paper is that the proposed approach enables us to deal with a large size real problem using an exact solution method. Finally, the proposed approach is employed on a supermarket chain. Two algorithms’ and the actual results are compared with the ANOVA test to illustrate the feasibility of the proposed approach. The results illustrate that the DBSCAN algorithm provides a better solution than the other.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

[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 PencereliEş 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 PickUp 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 clusterfirst 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.

APA	CÖMERT ERCAN S, yazgan h, SERTVURAN İ, ŞENGÜL H (2018). Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. , 685 - 694. 10.19113/sdufbed.20568
Chicago	CÖMERT ERCAN Serap,yazgan harun resit,SERTVURAN İrem,ŞENGÜL Hanife Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. (2018): 685 - 694. 10.19113/sdufbed.20568
MLA	CÖMERT ERCAN Serap,yazgan harun resit,SERTVURAN İrem,ŞENGÜL Hanife Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. , 2018, ss.685 - 694. 10.19113/sdufbed.20568
AMA	CÖMERT ERCAN S,yazgan h,SERTVURAN İ,ŞENGÜL H Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. . 2018; 685 - 694. 10.19113/sdufbed.20568
Vancouver	CÖMERT ERCAN S,yazgan h,SERTVURAN İ,ŞENGÜL H Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. . 2018; 685 - 694. 10.19113/sdufbed.20568
IEEE	CÖMERT ERCAN S,yazgan h,SERTVURAN İ,ŞENGÜL H "Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması." , ss.685 - 694, 2018. 10.19113/sdufbed.20568
ISNAD	CÖMERT ERCAN, Serap vd. "Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması". (2018), 685-694. https://doi.org/10.19113/sdufbed.20568

APA	CÖMERT ERCAN S, yazgan h, SERTVURAN İ, ŞENGÜL H (2018). Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 22(2), 685 - 694. 10.19113/sdufbed.20568
Chicago	CÖMERT ERCAN Serap,yazgan harun resit,SERTVURAN İrem,ŞENGÜL Hanife Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 22, no.2 (2018): 685 - 694. 10.19113/sdufbed.20568
MLA	CÖMERT ERCAN Serap,yazgan harun resit,SERTVURAN İrem,ŞENGÜL Hanife Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, vol.22, no.2, 2018, ss.685 - 694. 10.19113/sdufbed.20568
AMA	CÖMERT ERCAN S,yazgan h,SERTVURAN İ,ŞENGÜL H Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi. 2018; 22(2): 685 - 694. 10.19113/sdufbed.20568
Vancouver	CÖMERT ERCAN S,yazgan h,SERTVURAN İ,ŞENGÜL H Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi. 2018; 22(2): 685 - 694. 10.19113/sdufbed.20568
IEEE	CÖMERT ERCAN S,yazgan h,SERTVURAN İ,ŞENGÜL H "Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması." Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 22, ss.685 - 694, 2018. 10.19113/sdufbed.20568
ISNAD	CÖMERT ERCAN, Serap vd. "Sıkı Zaman Pencereli Araç Rotalama Probleminin Çözümü için Yeni Bir Yöntem Önerisi ve Bir Süpermarket Zincirinde Uygulanması". Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 22/2 (2018), 685-694. https://doi.org/10.19113/sdufbed.20568