Cluster-First Route-Second Approach For The Solution Of Vehicle Routing Problem With Soft Time Windows; A Supermarket Chain Application

Abstract

The vehicle routing problem with soft time windows is a type of vehicle routing problem with time windows which allow to serve customers outside their time windows, but the penalty costs is applied for the company for early or late service. In this study, an approach consisted of two stages as "cluster-first route-second” is proposed for the vehicle routing problem with soft time windows. Firstly, customers are clustered according to K-Means and K-Medoids clustering algorithms, then routed by the help of mixed integer linear programming model. Finally, the ANOVA test is used to show the effectiveness of the algorithms and the experimental results showed that the results obtained with the algorithms provides a better solution than the actual costs of the firm.

Keywords

• Vehicle Routing Problem with Soft Time Windows,K-Means Algorithm,K-Medoids Algorithm

ESNEK ZAMAN PENCERELİ ARAÇ ROTALAMA PROBLEMİNİN ÇÖZÜMÜ İÇİNÖNCE KÜMELE-SONRA ROTALA TEMELLİ BİR YÖNTEM ÖNERİSİ; BİR SÜPERMARKET ÖRNEĞİ

Abstract

Esnek zaman pencereli araç rotalama problemi, belirli zaman aralıklarında servis görmek isteyen müşterilere, erken ya da geç hizmet verilmesine ceza maliyeti uygulanması koşuluyla izin veren zaman pencereli araç rotalama probleminin bir çeşididir. Bu çalışmada, ele alınan esnek zaman pencereli araç rotalama problemi için önce kümele-sonra rotala yöntemine dayalı bir yöntem önerilmiştir. İlk olarak müşteriler K-Means ve K-Medoids kümeleme algoritmalarına göre kümelenmiş, daha sonra ise karışık tam sayılı doğrusal programlama modeli yardımıyla rotalanmıştır. Son olarak, algoritmaların etkinliğini göstermek için ANOVA testi kullanılmış ve deneysel sonuçlar, algoritmalar ile elde edilen sonuçların firmanın gerçek maliyetleri ile karşılaştırıldığında daha iyi olduğunu göstermektedir.

Keywords

• Esnek Zaman Pencereli Araç Rotalama Problemi,K-Means Algoritması,K-Medoids Algoritması

References

1. Aydemir, E., 2006, Esnek Zaman Pencereli Araç Rotalama Problemi ve Bir Uygulama, Yüksek Lisans Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ankara.
2. Badeau, P., Guertin, F., Gendreau, M., Potvin, J., Taillard, E., 1997, “A Parallel Tabu Search Heuristic for The Vehicle Routing Problem with Time Windows”, Transportation Research Part-C, Vol. 5, No. 2, pp. 109-122.
3. Blashfield, R. K., Aldenferder, M. S., 1978, “The Literature on Cluster Analysis”, MultivariateBehavioralResearch, Vol. 13, pp. 271-295.
4. 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, Vol. 7, pp. 29-37.
5. Chiang, W. C., Cheng, C. Y., 2017, “Considering the Performance Bonus Balance in the Vehicle Routing Problem with Soft Time Windows”, Procedia Manufacturing,Vol. 11, pp. 2156 – 2163.
6. Calvete, H. I., Galé, C., Oliveros, M. J., Sánchez-Valverde, B., 2007, “A Goal Programming Approach to Vehicle Routing Problems with Soft Time Windows”, EuropeanJournal of OperationalResearch,Vol. 177, pp. 1720–1733.
7. Cömert, S.E., Yazgan, H.R., 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, Vol. 22, No. 2, pp. 1-6.
8. 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.

9. Çalışkan, K., 2011, Karınca Kolonisi Optimizasyonu ile Araç Rotalama Probleminin Maliyetlerinin Kümeleme Tekniği ile İyileştirilmesi, Yüksek Lisans Tezi, TOBB Ekonomi ve Teknoloji Üniversitesi, Fen Bilimleri Enstitüsü, Ankara.
10. Fagerholt, K., 2001, “Ship Scheduling with Soft Time Windows: An Optimisation Based Approach”, EuropeanJournal of OperationalResearch, Vol. 131, pp. 559- 571.
11. Hair, J. F., Jr., Anderson, R. E., Tatham, R. L., Black, W. C., 1995, Multivariate Data Analysis, 3rd ed, Macmillan Publishing Company, New York.
12. Işık, M., 2006, Bölünmeli Kümeleme Yöntemleri ile Veri Madenciliği Uygulamaları, Yüksek Lisans Tezi, Marmara Üniversitesi, Fen Bilimleri Enstitüsü, İstanbul.
13. Johnson, A. R., Wichern, D. W., 1992, Applied multivariate statistical analysis, International Editions, New Jersey: PrenticeHall.
14. Kaufman, L., Rousseeuw, P. J., 1990, Finding Groups in Data: An Introduction to Cluster Analysis, New York: John Wiley & Sons Inc.
15. Min, H., 1991, “A Multiobjective Vehicle Routing Problem with Soft Time Windows: The Case of a Public Library Distribution System”, Socio-Economic Planning Science, Vol. 25, No. 3, pp. 179-188.
16. Nallusamy, R., Duraiswamy, K., Dhanalaksmi, R., Parthiban, P., 2010, “Optimization of Non-Linear Multiple Traveling Salesman Problem Using K-Means Clustering, Shrink Wrap Algorithm and Meta-Heuristics”, International Journal of Nonlinear Science, Vol. 9, No. 2, pp. 171-177.
17. Qureshi, A. G., Taniguchi, E., Yamada, T., 2009, “An Exact Solution Approach for Vehicle Routing and Scheduling Problems with Soft Time Windows”, TransportationResearchPart E,Vol. 45, pp. 960–977.
18. Qureshi, A. G., Taniguchi, E., Yamada, T., 2010, “Exact Solution for the Vehicle Routing Problem with Semi Soft Time Windows and Its Application”, Procedia Social and Behavioral Sciences, Vol. 2, 5931–5943.
19. Sarıman, G., 2011, “Veri Madenciliğinde Kümeleme Teknikleri Üzerine Bir Çalışma K-Means ve K-Medoids Kümeleme Algoritmalarının Karşılaştırılması”, Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, Vol. 15, No. 3, pp. 192-202.
20. Sexton, T. R., Choi, Y. M., 1986, “Pickupand Delivery of Partial Loads with Soft Time Windows”, American Journal of Mathematical and Management Sciences, Vol. 6, No. 3, pp. 369-398.
21. Şen, T., 2014, Kümeleme ve Genetik Algoritma Destekli Yaklaşımlarla Kapasite Kısıtlı Araç Rotalama Probleminin Çözümü: Perakende Zincirinde Uygulanması, Yüksek Lisans Tezi, Sakarya Üniversitesi, Fen Bilimleri Enstitüsü, Sakarya.
22. Taş, D., Jabali, O., Woensel, T. V., 2014, “A Vehicle Routing Problem with Flexible Time Windows”, Computers& Operations Research, Vol.52, pp. 39–54.
23. Tatlıdil, H., 2002, Uygulamalı çok değişkenli istatistiksel analiz, Ziraat Matbaacılık A.Ş., Ankara, 329-332.
24. Thangiah, S. R., Salhi, S., 2001, “Genetic Clustering: An Adaptive Heuristic for the Multidepot Vehicle Routing Problem”, Applied Artificial Intelligence, Vol. 15, No. 4, pp. 361-383.
25. Toth, P., Vigo, D., 2002a, “An overview of vehicle routing problems-chapter 1”, The vehicle routing problem, SIAM, Philadelphia, 1-26.
26. Toth, P., Vigo, D., 2002b, The vehicle routing problem, Philadelphia: SIAM Monographs on Discrete Mathematics and Applications.
27. Ünsal, Ö., Yiğit, T., 2018, “Yapay Zeka ve Kümeleme Teknikleri Kullanılarak Geliştirilen Yöntem ile Okul Servisi Rotalama Probleminin Optimizasyonu”, Mühendislik Bilimleri ve Tasarım Dergisi, Vol. 6, No. 1, pp. 7-20.
28. Yücenur, G. N., Demirel, N. G., 2011, “A Hybrid Algoritm with Genetic Algorithm and Ant Colony Optimization for Solving Multi-Depot Vehicle Routing Problems”, Journal of Engineering and Natural Sciences, Vol. 29, pp. 340-350.
29. Zare-Reisabadi E., Miirmohammadi, S. H., 2015, “Site Dependent Vehicle Routing Problem With Soft Time Window: ModelingandsolutionApproach”,Computers&IndustrialEngineering,Vol. 90, pp. 177-185.