Genelleştirilmiş seçici gezgin satıcı problemleri için yeni matematiksel modeller
New mathematical formulations for the generalized selective travelling salesman problems
Yazar: GÖZDE GÜRKAN ALTUNSOY
Danışman: YRD. DOÇ. DR. TUSAN DERYA
Başkent Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2017
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Oryantiring Problemi (OP) diğer adıyla Seçici Gezgin Satıcı Problemi (SGSP), bir gezginin bir başlangıç düğümünden (merkez, depo) başlayarak, belirli bir maliyet (zaman veya mesafe) kısıtı altında, en yüksek getiriyi sağlayacak düğümlere (müşterilere) uğrayarak bitiş noktasına varan turu bulmayı amaçlayan bir optimizasyon problemidir. SGSP, maliyetin en küçüklenmesi yerine ziyaret edilen müşterilerden elde edilen kazancın en büyüklenmesini amaçlayan bir Gezgin Satıcı Problemi (GSP) türüdür. SGSP'inde, GSP'inde olduğu gibi tüm müşterilere uğrama zorunluluğu yoktur. Müşteriler tek olabileceği gibi birçok müşteriyi içeren gruplar (kümeler) halinde de olabilirler. Birden fazla müşterinin oluşturduğu kümeye salkım denir. Gezginin salkımlara ayrılmış müşterileri ziyaret ettiği problemler, SGSP'nin genelleştirilmiş halleridir. Bu tezde SGSP'nin daha önceden üzerinde çalışılmamış olan iki farklı genelleştirilmiş uzantısı ele alınmıştır. Gezginin salkım içerisindeki müşterilerden sadece bir tanesine uğradığı problem Seçici Genelleştirilmiş Gezgin Satıcı Problemi (SGGSP), salkım içerisindeki tüm müşterilere uğradığı problem ise Seçici Kümelendirilmiş Gezgin Satıcı Problemi (SKGSP) olarak isimlendirilmiştir. Tez kapsamında tanımlanan bu iki yeni problem için iki tane düğüm tabanlı ve iki tane ayrıt tabanlı matematiksel modeller önerilmiştir. Önerilen matematiksel modellerin test problemleri üzerinde performansları analiz edilmiştir. Yapılan sayısal analizler sonucunda her iki problem için de ayrıt tabanlı matematiksel modelin üstünlüğü görülmüştür.

Abstract:
The Orienteering Problem (OP), in other words the Selective Traveling Salesman Problem (STSP) is an optimization problem which salesman starts from a starting node (center, warehouse) under the cost (time or distance) constraint and aims to find a tour by visiting the nodes (customers) that supply the maksimum profit. The STSP is a type of Traveling Salesman Problem (TSP) which aims to maximize the profit from the visited customers rather than minimizing the cost. There is no obligation to visit all customers as in TSP. Customers can be single, or they can be groups (clusters) that containing many customers. It is called clusters formed by more than one customer. The problems that the salesman visits to customers who are divided into clusters are the generalized aspects of the STSP.This thesis deals with two different generalized extensions of STSP that have not been studied previously. The problem that the salesman visits only one of the customers in the cluster is the Selective Generalized Traveling Salesman Problem (SGTSP), another type of problem in which all customers in the cluster are being visited is called the Selective Clustered Travelling Salesman Problem (SCTSP). Two node-based and two edge-based mathematical models are proposed for two new problems described in the scope of this thesis. The performances of the proposed mathematical models on test problems are analyzed. As a result of the numerical analyzes, the superiority of the edge-based mathematical model for both problems is seen.