Seçici Kümelendirilmiş Gezgin Satıcı Problemi ve matematiksel formülasyonları

Abstract

Kümelendirilmiş gezgin satıcı problemi (KGSP), gezgin satıcı probleminin (GSP) bir uzantısıdır ve tüm düğümler kesişimleri boş küme olan kümelere bölünerek her küme bir turda mutlaka bir kez ziyaret edilmelidir. Ayrıca uğranan her kümede bulunan tüm düğümler mutlaka ziyaret edilmelidir. Bu çalışmada, KGSP'nin genel bir uzantısı olan Seçici Kümelendirilmiş GSP (SKGSP) tanımlanmaktadır. SKGSP’de amaç, belirli bir zaman kısıtı içerisinde en büyük toplam kazancı elde edecek şekilde kümelerin seçilerek ziyaret edilecek düğüm sırasının bulunmasıdır. Problemde, gezgin eğer bir kümeyi ziyaret edecek ise küme içindeki tüm düğümleri ziyaret etmelidir. Bu problem, küme seçimi ve seçilen kümelerde düğümler arasındaki en kısa yolun belirlenmesi karar problemlerini birlikte içerir. Çalışmada, SKGSP tanımı ve ilgili problem için yeni formülasyonlar önerilmektedir. Formülasyonların performansı, 52 test probleminden türetilmiş 416 problem üzerinde denenerek sonuçlara yer verilmiştir.

The Clustered Traveling Salesman Problem (CTSP) is an extension of the Traveling Salesman Problem (GSP). All nodes must be divided into clusters that whose intersections are empty sets, and each cluster must be visited once in a tour. In addition, all nodes in each cluster must be visited. In this study, Selective Clustered TSP (SCTSP), which is a general extension of CTSP, is defined. The aim of SCTSP is to find the order of nodes to be visited by selecting clusters to obtain the largest total profit within a certain time limit. In the problem, if the traveler is to visit a cluster, it must visit all nodes in the cluster. This problem includes cluster selection and determination of the shortest path between nodes in selected clusters. In this study, the SCTSP is defined and new formulations are proposed for this problem. The performance of the formulations is tested on 416 problems derived from 52 test problems and the results are included.