Karınca Kolonisi Optimizasyonu ile Araç Rotalama Probleminin Maliyetlerinin Kümeleme Tekniği ile İyileştirilmesi

Abstract

In multi-depot vehicle routing problems meeting the customer demand in the shortest time with the shortest path and appropriate number of vehicles is the major point for the solution of these problems. Many practical approaches and algorithms have been established for the solution of a kind of hard NP vehicle routing problems. These algorithms can be divided into two groups in general, to be precise and approximate. The bad side of the exact algorithms is that they show poor performance. But unlike the exact algorithms, many approximate algorithms reveal high-quality solutions in short time periods for combinational problems. One of these high-quality solution techniques is known as ant colony optimization. In this thesis ant colony optimization with k-means clustering technique is applied for the vehicle routing problem. The changes in the total realization of demands in time, total distance and total number of vehicles are observed for the applications.

Çok depolu araç rotalama problemlerinde müşteri taleplerinin en kısa sürede, en kısa yoldan karşılanması ve taleplerin karşılanması için kullanılacak olan araç sayısının en uygun sayıda seçilmesi oldukça önemlidir. NP zor bir problem olan araç rotalama probleminin çözümü için pratik yaklaşımlar ve birçok algoritmalar oluşturulmuştur, Bu algoritmalar kesin ve yaklaşımsal olmak üzere genel olarak iki gruba ayrılabilirler. Kesin algoritmaların kötü tarafı düşük performans göstermesidir fakat birçok yaklaşımsal algoritma kombinasyonel problemlerde kesin algoritmaların aksine kısa zaman dilimlerinde yüksek kalitede çözümler ortaya koyarlar. Bilinen bu tekniklerden biriside karınca kolonisi optimizasyonudur. Bu tez çalışmasında araç rotalama problemine karınca kolonisi optimizasyonu k ortalama kümeleme tekniği ile birlikte uygulanarak taleplerin toplam gerçekleşme süresi, toplam mesafe ve kullanılan toplam araç sayısının değişimleri izlenmiştir.