Vehicle routing problem - sectorization using hybrid methods

Abstract

1959 yılında ilk olarak ortaya atılan Araç Rotalama Problemi, geçen yıllarda önem kazanmaya devam etmiştir. Buna karşılık bu problemin en uygun sonucunu tam olarak bulan bir algoritma henuz geliştirilmemistir. Bu araştırmamızda ilk Araç Rotlama Problemi'nin tanıtımına yer verilmiştir. Bununla Araç Rotalama Problemi'nin iş dünyasındaki önemi, bu problemin sozumesnin. Gözükesinin sağlayacağı faydalar ve problemin sınırlamalarından bahsedilmektedir.O tezde, geçmişte bu konuyla ilgili olarak yapılan tüm araştırmalar hakkında bilgilere verilmiş ve tiplerine göre ayrıştırılmıştır. Sonrasında ise en uygun sonucu bulan kesin ve bir amaca yönelik sezgisel yöntemleri kullanan bir algoritma tarafımızdan oluşturmuştk. Bu algoritma, sezgisel yöntemler kullanılarak müşteriler küçük gruplara ayırmaktadır. Her bir grupta olan müşteri, bir araca ait olup, sonrasında yapılan kesin metotlar ile bütün müşterilerden, her aracın depodan çıkış bölümünden geçip, tekrar depoya dönme yolu bulunmaktadır. Bu bölümde müşteri adedi az olduğundan dolayı kesin metotlar kullanılmaktadır. Bu nedenle bulunan yol planının, en iyi plan olduğu kesindir. Sonrasında algoritmanın bulduğu sonuç, geçmişte bulunan sonuçlar ile karşılaştırılmış ve ona göre ya (1) aynı sonuç ile yoluna devam eder, ya (2) yolu değişir, ya da (3) şu ana kadar en iyi bulunan sonucu vererek tamamlanır. Bu tezi, söz konusu algoritmayı test etmek için, merkez Ankara seçilmiş olup, Ankara'dan başlayarak sekiz (8) araç ile Türkiye'nin diğer kalan seksen (80) ilinden geçerek, yeniden Ankara`ya dönmesi için en az masraflı olan yol planı bulunmaya çalışılmıştır. Belirtilen bu bilgiler iki (2) kez test edilmiş olup, her defasında farklı ayarlar kullanılmıştır. Sonrasında ise aynı ayarlar ile 2017 yılında Prof. Güneş Erdoğan`nın tarafından Microsoft Ofis Programı olan Excel kullanılarak geliştirmiş olan uygulama ile performansları karşılaştırılmıştır. Performans çıktı sonuçlarının analizi yapılıp, her aracın avantajları, dezavantajları, faydaları, kusurları ve bu kusurların sebepleri anlatılarak açıklanmaya çalışılmıştır. Yapılan bu testler, Microsoft Excel kullanılan bu uygulama ile aynı ayarla, aynı zamanda ve çok daha iyi ve başarılı sonuçlar verdiğini göstermiştir.Anahtar Kelimeler: VRP, Araç Rotlama Problemi, Exact Methodları, Metaheuristics, Heuristics, Lojistik, Algoritma.

VRP (Vehicle Routing Problem) is a problem that was first introduced in the late 1950s and has been since studied thoroughly. However there are no algorithms that have the ability to conclude an optimum solution for the problem yet.In this paper a brief introduction is given to familiarize the reader with the problem. Afterwards scope of the study along with its limitations, and assumptions are expressed briefly. Motivations are explained as well to indicate the importance of the problem and its effects in our everyday lives. A summary of previously done researches along with their types of solutions are studied throughout this paper.Then a new algorithm that uses a combination of exact methods and metaheuristics to find the solution closest to the optimum one is introduced. The algorithm in question uses metaheuristics to divide the clients population into smaller populations called sections where each section represents a group of clients that will be served by one of the available vehicles. The algorithm then finds the best route within each of the sections using exact methods which have the advantage of guaranteeing best solutions for small numbers of clients within acceptable time windows. The algorithm then compares newly found solutions with previous ones and decides accordingly whether it must (1) continue in the same path, (2) change it, or (3) stop processing and outputs the best solution that has been found until this moment as the best solution possible.Afterwards, the algorithm is tested using two different sets of configurations to find the best way to visit all 80 cities in the Republic of Turkey with 8 vehicles starting and ending at Ankara with the lowest possible cost. The algorithm is then benchmarked against a tool that has been developed by Dr. Erdoğan Güneş and makes use of Microsoft Excel to find the optimal solution for the same problem with the exact same configurations and circumstances and then both tools are compared to one another stating advantages of each of them. The comparison shows Dr. Güneş's excel tool was more successful in finding the better solution within the same time window allowed for processing the given data.At the end of the paper, applications of the algorithm, along with suggestions for further improvements are suggested.Keywords: VRP, Vehicle Routing Problem, Exact Methods, Metaheuristics, Heuristics, Logistics, Delivery, Pick-up, Supply chain.