Ulaştırma ve Lojistik Kongreleri

Kapasite Kısıtlı Araç Rotalama Probleminin Süpürme Algoritması ile Çözümü

İlhan Demir
Süleyman Demirel Üniversitesi, Isparta, Türkiye

Hakan Altunay
Dr. Öğr. Üyesi, Süleyman Demirel Üniversitesi, Isparta, Türkiye

Araç rotalama problemi; bir veya birkaç merkezi depodan, coğrafi olarak farklı noktalara dağılmış belirli müşterilere ürünlerin dağıtılmasını veya müşterilerden toplanmasını ifade etmektedir. Bir araç rotalama probleminde genellikle araç kapasiteleri ve servis süreleri dikkate alınarak katedilen toplam mesafeyi minimize edecek en uygun dağıtım ve toplama rotalarının belirlenmesi amaçlanmaktadır. Araç rotalama problemleri NP-zor problem sınıfında yer alan kombinatoryal optimizasyon problemlerinden birisidir. Bu sebeple bu tür problemlerin çözümünde kesin çözüm algoritmalarından ziyade, en iyi çözümü garanti etmeyen sezgisel yöntemler tercih edilmektedir. Bu çalışmada da kapasite kısıtlı araç rotalama probleminin çözümü için sezgisel yöntemlerden Süpürme Algoritması kullanılmıştır. Çalışmanın uygulama bölümünde iki aşamalı bir prosedür takip edilmiştir. İlk aşamada Kümeleme Analizi uygulanarak merkezi dağıtım noktaları tespit edilmiştir. İkinci aşamada ise Süpürme Algoritması kullanılarak merkezi dağıtım noktalarını içeren dağıtım planları belirlenmiştir. Elde edilen dağıtım planları, kaynak kullanımı ve katedilen mesafeler açısından kıyaslanarak alternatif çözümlerin değerlendirilmesi sağlanmıştır.

Anahtar Kelimeler: Sezgisel Yöntemler, Kümeleme Analizi, Kapasite Kısıtlı Araç Rotalama Problemi, Süpürme Algoritması

Sweep Algorithm for The Capacitated Vehicle Routing Problem

The vehicle routing problem refers to the distribution or collection of products from one or several main warehouses to specific customers geographically distributed at different points. In the vehicle routing problems, it is generally aimed to determine the most appropriate distribution and collection routes that will minimize the total distance traveled by considering vehicle capacities and service times. The vehicle routing problem is a combinatorial optimization problem in the NP-Hard category. Therefore, heuristic methods that do not guarantee the best solution are preferred rather than exact solution algorithms in solving these problems. In this paper, Sweep Algorithm, which is one of the heuristic methods, is used to solve the Capacitated Vehicle Routing Problem. In this study, a two-stage solution procedure is used. Firstly, the main distribution points are determined by Cluster Analysis. In the second stage, distribution routes including the main distribution points are determined by the Sweep Algorithm. Alternative routes are evaluated by comparing the obtained distribution routes in terms of capacity utilization and distances traveled.

Keywords: Sweep Algorithm, Heuristic Methods, Cluster Analysis, Capacitated Vehicle Routing Problem