Steiner gezici satıcı sorunu - Steiner travelling salesman problem

Steiner gezici satıcı sorunu (Steiner TSPveya STSP) bir uzantısıdır seyyar satıcı sorunu. Bazıları gerekli olan şehirlerin bir listesi ve aralarındaki yolların uzunlukları göz önüne alındığında, amaç, gerekli her şehri ziyaret eden ve ardından başlangıç ​​şehre geri dönen mümkün olan en kısa yürüyüşü bulmaktır. [1]. Bir yürüyüş sırasında, köşeler birden fazla ziyaret edilebilir ve kenarlar birden fazla kez geçilebilir[2].

Referanslar

  1. ^ Interian, Ruben; Ribeiro, Celso C. (15 Temmuz 2017). "Yol yeniden bağlamayı kullanan bir GRASP buluşsal yöntemi ve Steiner gezici satıcı sorunu için yeniden başlatılıyor". Yöneylem Araştırmasında Uluslararası İşlemler. 24 (6): 1307–1323. doi:10.1111 / itor.12419.
  2. ^ Álvarez-Miranda, Eduardo; Sinnl, Markus (2019-09-05). "Steiner gezici satıcı sorununun sayısal yönleri hakkında bir not". Yöneylem Araştırmasında Uluslararası İşlemler. 26 (4): 1396–1401. doi:10.1111 / itor.12592.
  • M. R. Garey ve D. S. Johnson. Bilgisayarlar ve İnatçılık: NP-Tamlık Teorisine Bir Kılavuz. W.H. Freeman ve Şirketi, 1979.
  • Huili Zhang, Weitian Tong, Yinfeng Xu ve Guohui Lin. Çevrimiçi kenar tıkanmalarıyla ilgili gezgin satıcı sorunu. Avrupa Yöneylem Araştırması Dergisi, 243(1):30–40, 2015.
  • Gerard Cornuejols, Jean Fonlupt ve Denis Naddef. Bir grafik üzerindeki seyyar satıcı problemi ve bazı ilgili tamsayı çokyüzlüler. Matematiksel Programlama, 33(1):1–27, 1985.
  • S. Borne, A.R. Mahjoub ve R. Taktak. Çoklu yönlendirici TSP için sipariş kısıtlamaları olan bir dallanma ve kesme algoritması. Ayrık Matematikte Elektronik Notlar, 41:487–494, 2013.
  • Huili Zhang, Weitian Tong, Yinfeng Xu ve Guohui Lin. Çevrimiçi gelişmiş kenar tıkanmalarıyla ilgili seyahat eden satıcı sorunu. Bilgisayarlar ve Yöneylem Araştırması, 70:26–38, 2016.
  • Adam N. Letchford, Saeideh D. Nasiri ve Dirk Oliver Theis. Steiner gezgin satıcı problemi ve ilgili problemlerin kompakt formülasyonları. Avrupa Yöneylem Araştırması Dergisi, 228(1):83–92, 2013.
  • Adam N. Letchford ve Saeideh D. Nasiri. İlişkili maliyetlerle ilgili gezgin satıcı sorunu. Avrupa Yöneylem Araştırması Dergisi, 245(1):62–69, 2015.
  • Juan-Jos´e Salazar-Gonz´alez. Steiner döngüsü politopu. Avrupa Yöneylem Araştırması Dergisi, 147(3):671–679, 2003.