Seçici Kümelendirilmiş Gezgin Satıcı Problemi ve Matematiksel Formülasyonları

Authors : Tusan Derya, Esra Dinler, Barış Keçeci

Pages : 531-551

Doi:10.35414/akufemubid.1368379

View : 94 | Download : 90

Publication Date : 2024-06-27

Article Type : Research Paper

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.
Keywords : Kümelendirilmiş gezgin satıcı problemi, Oryantiring problemi, Kâr getirili gezgin satıcı problemi, Karma tamsayılı matematiksel modelleme