Eş zamanlı topla dağıt araç rotalama probleminin çözümü için bir hibrit meta sezgisel algoritma önerisi

Abstract

Araç rotalama problemleri, belirli sayıda araç kullanılarak müşteriler ve depo arasında taşıma taleplerinin karşılanması ile ilgilenmektedir. Problemin sahip olduğu özelliklere göre literatürde birçok araç rotalama problemi türü bulunmaktadır. Bu tezde, müşterilerin eş zamanlı olarak hem dağıtım hem de toplama talepleri karşılanan Eş Zamanlı Topla Dağıt Araç Rotalama problemi (EZTDARP) ele alınmıştır. Söz konusu problem, kesikli (kombinatoryal) bir optimizasyon problemidir. Bu nedenle problem boyutu büyüdükçe çözülmesi zorlaşmaktadır. Bu tür problemleri kısa sürede kesin yöntemlerle çözmek mümkün olmadığı için meta sezgisel yöntemlere ihtiyaç duyulmaktadır. Meta sezgisel yöntemler, bir optimizasyon probleminin arama uzayında çeşitli yaklaşımlarla arama yaparak daha iyi çözümlere ulaşmayı hedefler. Bu yaklaşımlarla kısa sürelerde optimal ya da optimale yakın çözümlere ulaşmak mümkün olabilmektedir. Kesin yöntemler ile optimal sonuçları elde etmenin mümkün olmadığı ya da çok uzun süre beklemenin gerektiği durumlarda meta sezgisel yöntemleri kullanmak mantıklı bir seçim olmaktadır. Bu tezde yinelemeli yerel arama, değişken komşuluk iniş ve eşik kabul meta sezgisellerine dayanan ILS-RVND-TA olarak isimlendirilen hibrit bir algoritma önerilerek seçilen araç rotalama probleminin çözülmesi amaçlanmıştır. Yinelemeli yerel arama, çözümler üzerinde sarsım yoluyla değişiklikler yaparak arama uzayının farklı bölgelerini keşfeden ve bu sayede yerel optimuma takılmamaya çalışan bir meta sezgiseldir. Değişken komşuluk iniş, çözümlerin birden fazla komşuluğunda arama yaparak yoğun bir şekilde daha iyi çözümler arayan bir meta sezgiseldir. Eşik kabul ise daha kötü çözümlerin kabul edilmesine izin veren bir meta sezgiseldir. Önerilen algoritma, belirli test problemleri kullanılarak bulgular analiz edilmiştir.

Vehicle routing problems deal with the meeting of transportation demands between customers and the depot by using a certain number of vehicles. There are many sub-types of vehicle routing problems in the literature depend on the characteristics of the problem. In this thesis, the Vehicle Routing Problem with Simultaneous Pickup and Deliveries (VRPSPD), where customers have both distribution and collection demands are met simultaneously, is addressed. The problem in question is a discrete (combinatorial) optimization problem. For this reason, solving this problem is getting more difficult as the size of the problem is increasing. Since it is not possible to solve such problems with exact methods in a short time, metaheuristics methods are required. Metaheuristics aim to reach good solutions by seeking the search space of an optimization problem with various approaches. With this approach, it is possible to reach optimal or near-optimal solutions in a short time. It is a reasonable choice to use metaheuristics in cases where it is not possible to obtain optimal results with exact methods or when it is necessary to wait too long. It is aimed to solve the selected vehicle routing problem by proposing a hybrid algorithm based on Iterative Local Search, Variable Neighborhood Descent, and Threshold Acceptance metaheuristics and called as ILS-RVND-TA in this thesis. Iterative local search is a metaheuristic that explores different regions of the search space by making changes with a mechanism named perturbation on solutions, thus trying not to be trapped to the local optimum. Variable neighborhood descent, on the other hand, is a metaheuristic that searches more than one neighborhood of solutions intensely for improving solutions. Threshold acceptance is a metaheuristic that allows worse solutions to be accepted. The proposed algorithm was tested on certain test problems and the findings were analyzed. Keywords: