Dinamik araç rotalama problemi için kesin ve sezgisel çözüm yaklaşımları geliştirilmesi

Abstract

Araç rotalama problemleri (ARP) birçok lojistik uygulamanın merkezinde yer almaktadır. Bir araç filosunun rotasının maliyet etkin olarak belirlenmesi birçok endüstride önemli bir rol oynamaktadır. Gelişen endüstri standartlarıyla birlikte gerçek zamanlı verilerin kullanıldığı dinamik ARP uygulamalarının önemi artmıştır. Rotalama problemlerini dinamik kılan temel unsur ise rotalama esnasında değişen ortam koşullarıdır.Dinamik ARP, üretim ve lojistik alanındaki en önemli sorunlardan biridir. Dinamik ARP'de; müşteri taleplerinin oluşma anı, iptali ve değişmesi, hizmet süreleri, seyahat süreleri ve araçların kullanılabilirliği dinamizm kaynağı olarak ifade edilmektedir. Bu tez kapsamında ele alınan dinamik ARP'nin dinamizm kaynağı ise başlangıç rotalarının oluşturulması sonrasında müşterilerin bir kısmının bilinmeyen veya öngörülemeyen bir anda dinamik olarak ortaya çıkması veya mevcut müşteri talep miktarlarındaki değişim durumudur. Müşteri taleplerinin her zaman minimum maliyetle efektif bir şekilde karşılanabilmesi dinamik ARP çözümünün temel amacıdır. Gerçek hayatta karşılaşılan problemlere karşı hızlı ve yüksek doğruluk oranı ile aksiyon alınması gerekliliği karşısında, dinamik ARP gibi NP-zor problemlerin çözümü için geliştirilen sezgisel algoritmalar büyük bir avantaj sunmaktadır. Özellikle araçların başlangıç rotasındaki müşteri taleplerini karşılarken dinamik taleplerin oluşması durumunda, yeniden rotalama yapılarak güncel rotaların hızlı bir şekilde düzenlenmesi önem arz etmektedir. Bu süre ne kadar kısa olur ise araçların gecikme olmadan müşteri taleplerini karşılaması da o kadar mümkün olacaktır. Bu nedenle büyük boyutlu problemlerde dinamik ARP yapılabilmesi amacıyla Clarke & Wright Tasarruf Algoritması baz alınarak Rassal İteratif MDROL – HFS CW Tasarruf Algoritması geliştirilmiştir.Dinamik ARP'nin her bir problem boyutu için optimum çözüm imkanı sunan bir yöntem bulunmamaktadır. Bu nedenle akademik çalışmalar, mevcut teknolojik imkanlar doğrultusunda mümkün olan en büyük boyuttaki problemler için kesin çözüm metotlarının geliştirilmesi ve optimum sonuca en yakın sonucun en kısa sürede elde edilmesine imkan sunan algoritmalar üzerine yoğunlaşmıştır. Bu tez kapsamında ise dinamik ARP'ye çözüm imkanı sunan matematiksel model ve büyük boyutlu problemlerde hızlı ve yüksek doğruluk oranında çözümü garanti eden sezgisel algoritma geliştirilmiştir.

Vehicle routing problems (VRP) are at the center of many logistics applications. Cost effective determination of the route of a vehicle fleet plays an important role in various industries. With the developing industry standards, the importance of real-time dynamic VRP applications has increased. The key factor that makes routing problems dynamic is the changeable environmental conditions while routing.Dynamic VRP is one of the most important problems in production and logistics. The moment of occurrence, cancellation or change of customer demands, service times, travel times and availability of vehicles are expressed as sources of dynamism for dynamic VRP. The source of dynamism of the dynamic VRP addressed within the scope of this thesis is the dynamic emergence of some of the customers at an unknown or unpredictable moment or the change of the current client demand after the initial routes are created.It is necessary to take action with a fast and high accuracy rate against the problems encountered in real life. Thankfully, heuristic algorithms developed to solve NP-hard problems such as dynamic vehicle routing offer remarkable and undeniable advantages. Especially in case of dynamic demands while meeting the customer requests in the starting route of the vehicles, it is the key factor to arrange up-to-date routes quickly by rerouting. It is undeniable that the shorter this period the more it can be possible for vehicles to meet customer demands without delay. Hence, Random Iterative MDROL-HFS CW Saving Algorithm has been developed based on Clarke & Wright Savings Algorithm to perform large-scale dynamic VRP.There is no method that provides optimum solution for each problem dimension of dynamic VRP. For this reason, academic studies have focused on the development of exact solution methods for the largest possible problems in line with the current technological possibilities and algorithms that allow the closest result to the optimum result in the shortest time. The main purpose of this master thesis is to develop a mathematical model that offers exact solutions to dynamic VRP and a heuristic algorithm that guarantees a fast and high accuracy solution in large-scale problems.