Cluster-First, Then-Route Based Heuristic Algorithm for the Solution of Capacitated Vehicle Routing Problem

- Lojistik, insanoğlunun uzun zamandır üzerinde çalıştığı en temel konulardan birisidir. Son yüzyıl içerisinde müşteri taleplerinin kısa zamanda ve verimli bir şekilde ulaştırılabilmesi ihtiyacı, lojistik faaliyetlerinin içerisinde yer alan araç rotalama problemlerinin (ARP) öneminin artmasına neden olmuştur. Gün geçtikçe artan önemi nedeniyle birçok araştırmaya konu olan araç rotalama problemlerinin çözülebilmesi için farklı yöntemler geliştirilmiştir. En iyi sonuca ulaşmayı mümkün kılan yöntemlerde problem boyutu arttıkça daha fazla hesaplama süresine ihtiyaç duyulmaktadır. Bundan dolayı daha kısa sürede kabul edilebilir sonuçlara ulaşmayı sağlayan sezgisel yöntemler hakkında da oldukça fazla çalışma yapılmıştır. Bu çalışmada da, kapasite kısıtlı araç rotalama problemlerinin (KKARP) çözümüne yönelik önce grupla sonra rotala prensibine dayanan sezgisel bir yöntem önerilmiştir. Gruplandırma adımında, talep noktalarının bulanık c-ortalama kümeleme yöntemi ile olası tüm rotalara 0-1 arasında üyelik dereceleri hesaplanmıştır. Rotalama adımında ise sezgisel bir algoritma olan tabu arama prensiplerine dayanan bir arama algoritması ile rotalar iyileştirilmeye çalışılmıştır. Sonuç olarak KKARP'lerinin gezgin satıcı problemine dönüştürülerek çözülebileceği görülmüştür. Önerilen yöntem literatürde yer alan veri kümelerine uygulanmış ve elde edilen sonuçlar tartışılmıştırLogistics has important effects on human life throughout the history. Within the past century the need to convey customer demands shortly and efficiently has resulted in the increasing importance of the vehicle routing problems (VRPs) that included in logistics activities. Different methods have been developed in order to solve vehicle routing problems that are subject of various researchs due to its increasing importance day by day. More computation time is required to the methods that provides to find the optimal results while the problem size increases. Therefore, pretty much work has been done about heuristic methods that provide access to acceptable results in a shorter time. In this paper, a “cluster-first, then-route” based heuristic algorithm is proposed for the solution of Capacitated Vehicle Routing Problem (CVRP). The membership degrees of demand points to each potential route are calculated by using fuzzy c-means in clustering step; and then the routes are improved by using a search procedure based on Tabu Search algorithm in the routing step. As a result of, the capacitated vehicle routing problems can be solved by conversion to the traveling salesman problem has been observed. The proposed method is applied on literature problems and the results are discussed