Selective Clustered Traveling Salesman Problem and Mathematical Formulations

Tusan Derya; Esra Dinler; Barış Keçeci

Makale detayları

Selective Clustered Traveling Salesman Problem and Mathematical Formulations

Yazarlar:

Tusan Derya | Esra Dinler | Barış Keçeci

Yayıncı:

Afyon Kocatepe University

Ana Başlıklar:

Yöneylem | Matematikte Optimizasyon

Dergi:

Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi Vol.24 Issue 3, pp.531-551

Belge Tipi:

Makale

Yayın Tarihi:

6/2024

Belge Dili:

Türkçe

Document ID (Org No.):

2001317578

pISSN:

2149-3367

Anahtar kelimeler:

Özet:

 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.

 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.

 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.

 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, KGSPnin genel bir uzantısı olan Seçici Kümelendirilmiş GSP SKGSP tanımlanmaktadır. SKGSPde 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.

Makale detayları

Selective Clustered Traveling Salesman Problem and Mathematical Formulations

Yazarlar:

Tusan Derya | Esra Dinler | Barış Keçeci

Yayıncı:

Afyon Kocatepe University

Ana Başlıklar:

Yöneylem | Matematikte Optimizasyon

Dergi:

Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi Vol.24 Issue 3, pp.531-551

Belge Tipi:

Makale

Yayın Tarihi:

6/2024

Belge Dili:

Türkçe

Document ID (Org No.):

2001317578

pISSN:

2149-3367

Clustered traveling salesman problem

Orienteering problem

Traveling salesman problem with profits

Mixed integer mathematical programmingKümelendirilmiş gezgin satıcı problemi;

Oryantiring problemi;

Kâr getirili gezgin satıcı problemi

Karma tamsayılı matematiksel modelleme

Sayı

Makale detayları

Yazarlar: Tusan Derya | Esra Dinler | Barış Keçeci

Yayıncı: Afyon Kocatepe University

Ana Başlıklar: Yöneylem | Matematikte Optimizasyon

Dergi: Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi Vol.24 Issue 3, pp.531-551

Belge Tipi: Makale

Yayın Tarihi: 6/2024

Belge Dili: Türkçe

Document ID (Org No.): 2001317578

pISSN: 2149-3367

Sayı

Yazarlar:

Tusan Derya | Esra Dinler | Barış Keçeci

Yayıncı:

Afyon Kocatepe University

Ana Başlıklar:

Yöneylem | Matematikte Optimizasyon

Dergi:

Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi Vol.24 Issue 3, pp.531-551

Belge Tipi:

Makale

Yayın Tarihi:

6/2024

Belge Dili:

Türkçe

Document ID (Org No.):

2001317578

pISSN:

2149-3367