Exact and heuristic algorithms for the variants of the vehicle routing problem

Abstract

Dünyanın globalleşmesi ile, ürünlerin ve hizmetlerin dağıtımı hem ticaretin hem de günlük hayatın kaçınılmaz bir parçası haline gelmiştir. Ürünlerin ve hizmetlerin dağıtımına kısaca lojistik denilebilir. Bütün bir lojistik sistemi, malzemeleri tedarikçilerden fabrika binasına üretime ya da işlenmeye götürmeyi, ardından ürünleri depolara taşımayı, ve son olarak da depolardan müşterilere ulaştırmayı kapsamaktadır. Hem tedarik hem de dağıtım işlemleri etkili taşıma planlamasını gerektirir. İyi bir taşıma planı, firmaların toplam dağıtım maliyetlerinin önemli bir kısmını azaltabilir. Araç Rotalama Problemi (ARP) temel olarak dağıtım planlaması ile ilgilenir ve ticari önemi sayesinde yöneylem araştırması literatüründe çok ilgi toplamıştır. ARP toplam dağıtım maliyetlerini minimize etmek amacıyla, tümü depoda başlayıp depoda biten ve her müşteriye sadece bir defa uğrayan m adet rota tasarlama işleminde kullanılır. ARP literatürde ilk tanımlandığından bu yana, probleme çeşitli varsayımlar eklenerek birçok değişik tipi elde edilmiştir. Bu tez çalışmasında, gerçek yaşam dağıtım problemlerinde sıkça karşılaşılan ARP'nin üç farklı tipi ele alınmıştır. Bunlar sırasıyla, heterojen filolu ARP (HARP), bölünmüş dağıtımlı ARP (BDARP) ve zaman pencereli ARP'dir (ZPARP). HARP, BDARP ve küçük ölçekli ZPARP için yeni bir Eşik Algoritması geliştirilmiştir. Büyük ölçekli ZPARP için ise yine orjinal olan KümeKaplama Algoritması geliştirilmiştir. Bu algoritmaların verimliliğini ve performansını ölçmek için, literatürde bulunan test problemleri üzerinde deneyler yapılmıştır. Elde edilen sonuçlar önerilen algoritmaların özellikle hızlı karar vermenin çok önemli olduğu problemlerde faydalı olabileceğini göstermiştir. Literatür deneylerine ek olarak, geliştirilen algoritmalar bir market zincirinin taze gıda dağıtımı problemine uygulanmıştır. Elde edilen sonuçlar firmaya sunulmuş ve yeni dağıtım stratejileri önerilmiştir. As the world is globalizing, distribution of goods and services becomes an inevitable part of both trade and daily life. Distribution of goods and services from a supply point to various demand points is called logistics. A complete logistics system includes transporting materials from a number of suppliers to the factory plant for manufacturing, transporting the products to warehouses and finally distributing them to the customers. Both the supply and distribution procedures require effective transportation planning. Good transportation planning can save a company a considerable amount of its total distribution costs. Vehicle Routing Problem (VRP) basically considers transportation planning and has received a lot of attention in operations research literature due to its commercial value. VRP consists of designing m vehicle routes to minimize total cost, each starting and ending at the depot such that each customer is visited exactly once. Since VRP was first introduced in literature, many variations have appeared by including additional assumptions into the problem. In this dissertation, three of the variants of VRP, which are faced quite often in real life distribution problems, are considered. These are heterogeneous VRP (HVRP), split delivery VRP (SDVRP) and VRP with time windows (VRPTW). A novel Threshold Algorithm is developed for HVRP, SDVRP and small scale VRPTW. For large scale VRPTW, a SetCovering Algorithm is developed. In order to see the efficiency and performance of these algorithms, they are tested on the literature benchmark problems. The results of the computational experiments indicate that the proposed methodologies are useful tools especially for large scale real life problems where fast decision making is of crucial importance. In addition to performance tests, the proposed methodologies are employed to solve the real life fresh goods distribution problem of a retail chain store. The results achieved are presented to the firm and new distribution strategies are offered.