Kapasite kısıtlı araç rotalama probleminin yabani ot ve hibrit metasezgisel algoritmalarla çözümü

Abstract

Lojistik planlamada araç rotalama problemleri operasyonel bazda firmalar için önemli kararlardan birisini oluşturmaktadır. Bu tez çalışmasında; özellikle lojistik planlarının oluşturulmasında sıklıkla karşılaşılan araç rotalama problemi incelenmiştir. Araç rotalama problemi Np-Zor sınıfındaki popüler bir optimizasyon problemidir. Problemin karakteristiğinden dolayı büyük ölçekli veri setlerini kesin çözüm yöntemler ile çözmek çok zordur. Makul sürelerde optimale yakın çözümler için sezgisel ve metasezgisel algoritmalar yaygın olarak kullanılmaktadır. Bundan dolayı bu çalışmada araç rotalama problemi; tasarruf algoritması ve genetik algoritmayla çözülmesinin yanında yabani ot algoritması ve bu yaklaşımlardan oluşturulan hibrit yöntemler ile çözülerek bu algoritmaların performansları karşılaştırılmıştır. Böylelikle, kapasite kısıtlı statik araç rotalama problemine yeni bir hibrit çözüm yöntemi önerilmiştir. Sonuçlar önerilen yaklaşımın kısa sürede optimale oldukça yakın sonuçlar verdiğini göstermektedir. Buna ek olarak problemin dinamik koşullar altında davranışını incelemek için tek depolu, çok araçlı, dinamik talepli, kapasite kısıtlı araç rotalama problemi ele alınmıştır. Statik problem için önerilen çözüm yaklaşımları dinamik koşullara adapte edilmiştir. Problemin uygulama problemlerine implementasyonu için çalışma sonucunda ortaya çıkan çözüm yaklaşımlarını temel alan bir arayüz programı tasarlanmıştır.

Vehicle routing problems in logistics planning constitute one of the important operational decisions for companies. In this thesis, the vehicle routing problem that is frequently faced in the building of logistics plans has been examined. Vehicle routing problem is a popular problem in optimization which is known as NP-Hard class problem. Due to the characteristics of the problem, it is very difficult to solve large-scale data instances with exact solution methods. Heuristic and meta-heuristic algorithms are widely used for achieving near optimal solutions at reasonable time. Therefore, in this study, vehicle routing problem is solved by savings algorithm, genetic algorithm, invasive weed optimization algorithm and hybrid methods that developed by these approaches and their performances are compared. Thus, a new hybrid solution method has been proposed for the capacitated vehicle routing problem. The results show that the proposed approach is very close to optimal results in a short computational time. In addition, in order to investigate the behavior of the problem under dynamic conditions, a single-depot, multi-vehicle, dynamic demand, capacity-constrained vehicle routing problem is considered. The proposed solution approaches for classic problem are adapted to dynamic conditions. In order to implement the problem into the real-life application problems, a graphical user interface is designed based on the proposed solution approaches.