Otel seçimli gezgin satıcı problemi için karşıt çözüm temelli değişken komşu iniş sezgiseli

Abstract

Bu tez kapsamında Gezgin Satıcı Problemi (GSP)'nin bir versiyonu olan Otel Seçimli Gezgin Satıcı Problemi (OSGSP) ele alınmıştır. GSP, aralarındaki uzaklıkları bilinen noktaların her birine yalnız bir kez uğramak şartıyla, başlangıç noktasına dönen en az maliyetli turun bulunması problemidir. OSGSP ise günlük çalışma süresi/mesafesi kısıtı içermektedir. Bu kısıt, tüm noktaların bir seferde ziyaret edilmesini mümkün kılmamaktadır. Bu nedenle gezgin, gün (kısıtlı çalışma süresi/mesafesi) sonunda uygun bir bekleme (otel) noktasında duraklar (konaklar) ve bir sonraki gün, tura kaldığı otel noktasından başlayarak devam eder. Her otele uğrama zorunluluğu bulunmamakla birlikte bir otele birden fazla kez de uğranabilmektedir. Bir otelde başlayıp yine bir otelde son bulan sıralı noktalar kümesine "gezi", tüm müşterileri kapsayan sıralı geziler kümesine "tur" denmektedir. Problemde birincil amaç tur içinde yapılan gezi sayısını en küçüklemektir. İkincil amaç ise gezi başına geçen süre/mesafenin günlük çalışma süresi kısıtını aşmaması şartı ile turun toplam mesafesini en küçüklemektir. Tez çalışmasında, bu problemin çözümü için Değişken Komşu İniş algoritmasına dayalı bir algoritma geliştirilmiştir. En Yakın Komşu Prensibi (EYKP) ile başlangıç çözüm elde edilmiş ve bu çözümü iyileştirmek amacıyla Karşıt Çözüm Temelli Değişken Komşu İniş Sezgiseli (KÇTDKİS) uygulanmıştır. Elde edilen sonuçlar literatürde var olan diğer sezgisel algoritmalardan elde edilen sonuçlar ile karşılaştırılmıştır. Yapılan analizler sonucunda 120 problemin 35 tanesinde daha iyi sonuçlar elde edilmiştir. Ayrıca sonuçlar, yine literatürde var olan Cplex çözücüsü ile elde edilen sonuçlarla karşılaştırılmış ve 78 problemin 17'sinde ya optimal sonuçlar elde edilmiş ya da bilinen en iyi sonuçlardan daha iyi sonuçlara ulaşılmıştır. In this dissertation, The Travelling Salesperson Problem with Hotel Selection (TSPHS), which is a variant of The Travelling Salesperson Problem (TSP), is considered. TSP consist of a salesman and set of nodes known distances between them. The salesman has to visit each one of the nodes starting from a certain one and returning to the same node. The goal is to have the least cost tour during the salesman's trip. TSPHS includes daily working time / distance restriction. This constraint does not allow to visit all points at once. For this reason, the traveler stops (roosts) at a suitable waiting (hotel) point at the end of the day (limited working time / distance) and continues on the next day's trip from the hotel point where he stayed. There is no obligation to visit each hotel, and a hotel can be visited more than once. A set of ordered nodes starting and ending at a hotel is called a trip, and a set of ordered trips covering all nodes is called a tour. The primary objective of the problem is to minimize the number of trips. The secondary objective is to minimize the total distance of the tour, provided that the time / distance per trip does not exceed the daily working time limit. In the dissertation, an algorithm based on Variable Neighborhood Descent algorithm is developed for the solution of this problem. The starting solution with The Nearest Neighbor Principle (NNP) is obtained. Opposition Based Variable Neighborhood Descent (OBVND) Algorithm is applied to improve this solution. The results are compared with the other heuristic algorithms in the literature. As a result of the analysis, better results are obtained in 35 of 120 problem. In addition, the results are compared with those obtained with Cplex solvent, which is also available in the literature. In 17 of 78 problems, either optimal results are obtained or better results are obtained than the best known results.