Satıcı Sorunu

Almanya'nın en büyük 15 şehri boyunca seyahat eden bir satıcı için ideal seyahat rotası . Verilen rota, mümkün olan en kısa 43.589.145.600'dür.

Gezgin satıcı problemi (ayrıca haberci sorun , gezgin satıcı problemi , Engl. Gezgin Satıcı Problemleri veya Satış görevlisi Sorunu Seyahat (TSP)) bir olduğunu kombinatoryal optimizasyon problemi ait Yöneylem Araştırması ve teorik bilgisayar bilimleri . Görev, birkaç yeri ziyaret etmek için bir sıra seçmektir, böylece ilk istasyon dışında hiçbir istasyon birden fazla ziyaret edilmez, seyahat eden satıcının tüm seyahat mesafesi mümkün olduğunca kısa olur ve ilk istasyon son istasyonla aynı olur.

İlk kez 1930'da matematiksel bir problem olarak bahsedildiğinden, birçok araştırmacı bununla ilgilenmiş ve şu anda diğer optimizasyon problemleri için de kullanılan yeni optimizasyon yöntemleri geliştirmiş ve test etmiştir. Bugün, birkaç bin şehirdeki zor vakaların bile en iyi şekilde çözülebildiği çok sayıda sezgisel ve kesin yöntem mevcuttur.

Seyahat eden satıcı problemi, birçok pratik uygulamada, örneğin rota planlamada , lojistikte veya mikroçiplerin tasarımında en saf haliyle ortaya çıkar . Bununla birlikte, daha sık olarak, bir müşterinin veya arıza hizmetinin veya genom diziliminin planlanmasında malların dağıtımında olduğu gibi bir sorun olarak ortaya çıkar . "Şehir" ve "mesafe" terimleri tam anlamıyla alınmamalıdır, daha ziyade şehirler ziyaret edilecek müşterileri, sondaj deliklerini veya DNA alt zincirlerini temsil ederken, mesafe seyahat süresi, maliyetler veya iki DNA zincirinin eşleştiği dereceyi ifade eder. . Birçok pratik uygulamada, zaman aralıkları veya sınırlı kaynaklar gibi ek koşullar da gözlemlenmelidir, bu da problemi çözmeyi oldukça zorlaştırır.

Gezici satıcı problemi , NP açısından zor bir problemdir. P ve NP karmaşıklık sınıflarının farklı olduğuna dair daha önce kanıtlanmamış varsayım altında , bu nedenle , polinom en kötü durum çalışma zamanında en kısa gidiş dönüşü belirleyen bir algoritmanın olmadığı doğrudur .

Tarih

Seyahat eden satıcı sorununun bilimsel olarak ilk kez ne zaman araştırıldığı belirsizdir. Gezici satıcılar için bir el kitabı 1832 yılından beri bilinmektedir (başlık: Seyyar satıcı - siparişleri almak ve işinde mutlu bir başarıdan emin olmak için nasıl olması gerektiği ve ne yapması gerektiği - eski bir komisyondan) voyageur ), problemin bahsedildiği ancak matematiksel olarak ele alınmadığı. Almanya ve İsviçre'deki bazı bölgeler için örnek turlar önerir .

William Rowan Hamilton (1805-1865)

Icosian Oyun ile William Rowan Hamilton hangi 19. yüzyılın gelen görev 20 düğümler arasındaki turlar bulmaktı bir de grafiğe, kabul edilebilir sorunun öncüsü olarak . Matematiksel optimizasyon problemi olarak ilk açık söz , bunu 1930'da Viyana'da bir matematiksel kolokyumda formüle eden Karl Menger'e kadar uzanıyor gibi görünüyor :

Kısa süre sonra artık ortak tanımı Gezgin Satıcı Problemi tanıtıldı tarafından Hassler Whitney ait Princeton Üniversitesi .

Görevin basit tanımına ve anlaşılabilirliğine ek olarak, seyahat eden satıcı problemi, iyi çözümlerin belirlenmesinin nispeten kolay olduğu ve kanıtlanabilir bir optimal çözüm bulmanın çok zor olduğu gerçeğiyle karakterize edilir . Bu nedenle, bu problemin incelenmesi, 20. yüzyılın ikinci yarısından bu yana doğrudan uygulamalar tarafından daha az motive edildi - optimizasyon yöntemlerinin geliştirilmesi için bir tür oyun alanı görevi görüyor.

Kesme düzlemi yöntemleri , dallanma ve kesme ve çeşitli sezgisel yaklaşımlar gibi günümüzün standart integral doğrusal optimizasyon yöntemlerinin çoğu , örnek olarak TSP kullanılarak geliştirilmiş ve test edilmiştir.

1950'lerden bu yana, seyahat eden satıcı sorunu, Amerika Birleşik Devletleri'nin yanı sıra Avrupa'da da popülerlik kazanıyor. Üstün katkıları ile yapılmıştır George Dantzig , Delbert Ray Fulkerson ve Selmer M. Johnson 1954 yılında, RAND Corporation, Institute in Santa Monica geliştirdiği de bunu çözmek için bir kesme düzlemi yöntemi olarak ayrılmaz bir doğrusal program olarak sorunun ilk formülasyonunu . 49 şehirle belirli bir gidiş-dönüş problemi (sözde problem örneği ) için bir tur hesapladılar ve daha kısa bir tur olmadığını kanıtladılar. 1960'larda ve 1970'lerde, birçok disiplinler arası araştırma grubu, problemin diğerlerinin yanı sıra bilgisayar bilimi , ekonomi , kimya ve biyolojideki uygulamalarıyla ilgilendi .

Richard M. Karp 1972 kanıtlanmıştır NP-eksiksiz Hamilton daire sorunu olan, NP-denkliği TSP olabilir kolay olması türevi. Bunu yaparken, bu problemi pratikte çözmenin zorluğuna teorik bir gerekçe sağladı.

Martin Grötschel , Manfred Padberg , Giovanni Rinaldi ve diğerleri, yeni kesim seviyeleri ve bir dal ve kes yöntemi ile 2.392'ye kadar şehirdeki bazı problem örneklerini en iyi şekilde çözdüklerinde , 1970'lerin sonlarında ve 1980'lerin sonlarında daha büyük ilerleme kaydedildi .

Nicos Christofides ve Anatoli I. Serdyukov tarafından 1976'da bağımsız olarak açıklanan bir algoritma, optimum turdan maksimum yarıya kadar daha uzun bir gidiş dönüşle sonuçlandı.

1990'larda, David Applegate , Robert Bixby , Vašek Chvátal ve William Cook , birçok çözüm kaydının oluşturulmasına yardımcı olan Concorde programını geliştirmeye başladı . 1991'de Gerhard Reinelt, birçok araştırma grubunun sonuçlarını karşılaştırabileceği, çeşitli zorluklara sahip standartlaştırılmış test örneklerinden oluşan bir koleksiyon olan TSPLIB'yi sağladı. 2006 yılında Cook ve diğerleri, 85.900 şehirde, entegre devreler için bir yerleşim probleminin bariz bir şekilde en kısa turunu hesapladı ; bu, bugüne kadarki en iyi şekilde çözülmüş TSPLIB örneği oldu. Milyonlarca şehir içeren diğer örnekler için, uzunluğu optimumdan% 1'den az olduğu kanıtlanabilen turları belirlemek için ek ayrıştırma teknikleri kullandılar.

2014 yılında Grenoble Üniversitesi'nden András Sebö ve Bonn Üniversitesi'nden Jens Vygen , polinom çalışma süresine sahip bir algoritma ile kalite garantisiyle sezgisel tarama alanında yeni bir rekor kırdı : Yeni algoritmaları güzel kulaklar olarak adlandırıldı. ayrıştırma , yeni bir rekor olan optimal gidiş-dönüş güzergahının en fazla 1,4 katı olan grafik -TSP çözümlerini belirler.

Matematiksel açıklama

Grafik olarak modelleme

Dört şehirde simetrik TSP

Çözümde matematiksel yöntemlerin kullanılabilmesi için, önce gerçek bir durumun basit bir modelle temsil edilmesi gerekir . Gezici satıcının problemi bir grafik yardımıyla , yani düğümler ve kenarlar aracılığıyla modellenebilir . (: Şekilde A'dan D'ye) şehirler, her kenarda ise Düğümler iki düğüm arasını temsil ediyor ve bu şehirler arasındaki bir bağlantıyı açıklıyor. Her kenar için, bağlama bağlı olarak bir bağlantının coğrafi uzunluğu, seyahat süresi veya aralarındaki seyahatin maliyeti olarak yorumlanabilen bir uzunluk (resimde: 20, 42, ...) vardır. iki şehir. Bir tur ( Hamilton çemberi de denir ), bu grafikte her düğümü tam olarak bir kez içeren bir çemberdir . Amaç mümkün olan en kısa turu bulmaktır. ${\ displaystyle (i, j)}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle (i, j)}$${\ displaystyle c_ {ij} \ geq 0}$

Sorunun araştırılmasını basitleştirmek ve bir tur olmasını sağlamak için genellikle grafiğin tamamlandığı , yani her iki düğüm arasında her zaman bir kenar olduğu varsayılır . Bu, kenarın olmadığı her yere yapay, çok uzun bir kenar yerleştirilerek elde edilebilir. Uzun uzunluğu nedeniyle, başka türlü bir tur olmadığı sürece, böyle bir sırt asla en kısa turda görünmeyecektir.

Kenar ağırlıklarının özelliklerine bağlı olarak, sorunun farklı özel durumları arasında bir ayrım yapılır, bunlardan en önemlileri simetrik ve metrik TSP'dir.

Asimetrik ve simetrik TSP

Genel asimetrik TSP ile kenarlar ileri ve geri yönde farklı uzunluklara sahip olabilir, bu nedenle bu sorunun yönlendirilmiş bir grafik yardımıyla modellenmesi gerekir . Bu nedenle, sadece iki düğüm arasındaki bağlantıdan ve bunların uzunluklarından bahsetmek yeterli değildir; yön de belirtilmelidir.

Öte yandan, simetrik TSP'de, kenar uzunlukları tüm düğüm çiftleri için her iki yönde aynıdır. yani geçerlidir . Sonuç olarak, her tur her iki yönde de aynı uzunluktadır. Simetri, olası turların sayısını yarıya indirir. Simetrik bir TSP genellikle yönsüz bir grafik yardımıyla modellenir (resimdeki gibi). Gerçek şehirler arasındaki seyahat eden bir satıcı problemi asimetrik veya simetrik olabilir, örneğin şantiyelerde veya tek yönlü sokaklarda, bir yöndeki yolculuk diğerinden daha uzun sürer veya sürmez. Aynı şekilde, suda veya havada yolculuk farklı akımlara maruz kalabilir. ${\ displaystyle (i, j)}$${\ displaystyle c_ {ij} = c_ {ji}}$

Metrik TSP

Kenar uzunlukları da üçgen eşitsizliğini sağlıyorsa , simetrik bir TSP metrik olarak adlandırılır . Bu açıkça doğrudan bağlantı çünkü dolambaçlar değerli olmadığı anlamına gelmektedir etmektir uzun yoldan daha gelen asla üzere üçüncü bir düğüm aracılığıyla : ${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle k}$

${\ displaystyle c_ {ij} \ leq c_ {ik} + c_ {kj}}$

Bu tür kenar uzunlukları , düğümler kümesi üzerinde bir psödometrik , yani bir mesafeden sezgisel olarak beklenen koşulları karşılayan bir mesafe ölçüsü tanımlar. Pratikte sıklıkla ortaya çıkan çeşitli mesafe fonksiyonları psödometridir, yani üçgen eşitsizliğini karşılarlar:

• Öklid metrik Öklid TSP ,
• Manhattan metrik (aynı zamanda blok boyunca metrik) düz çizgisel TSP (örneğin, Manhattan sokak ağı gibi) bir ızgara şekilli grafiğin iki düğüm arasındaki mesafe x ve y yönlerinde mesafelerinin toplamı olduğu,
• veya ızgara şeklindeki bir grafiğin iki düğümü arasındaki mesafenin x veya y yönündeki mesafelerin maksimum olduğu maksimum metrik .

Son iki ölçü, örneğin, mümkün olan en kısa sürede belirli sayıda deliği işlemesi gereken bir matkabın bir delikten diğerine geçmek için her iki boyutta da bağımsız olarak hareket ettirilebildiği devre kartlarını delerken kullanılır . Manhattan metriği, hareketin her iki yönde de birbiri ardına gerçekleşmesine karşılık gelirken, maksimum metrikte her iki hareket aynı anda gerçekleşir ve toplam süre, x veya y yönündeki daha uzun mesafeyle belirlenir.

Örneğin, bir seyahatin süresinin en aza indirilmesi gerektiğinde ve farklı rotalarda farklı taşıma araçlarının mümkün olduğu durumlarda, metrik olmayan bir TSP mevcut olabilir. Uçakla dolambaçlı yol, araba ile doğrudan bağlantıdan daha hızlı olabilir.

Pratik planlama probleminde, yerleri birkaç kez ziyaret etmeye izin veriliyorsa, simetrik TSP, metrik TSP'ye indirgenebilir. Bu amaçla, gidiş-dönüş problemi sözde mesafe grafiğinde ele alınmıştır . Bu, orijinal grafikle aynı düğüm kümesine sahiptir ve ayrıca tamamlanmıştır . Kenar uzunlukları iki düğüm arasında ve en kısa uzunluğuna mesafe grafik tekabül ettiği - orijinal grafikte, bu düğümler arasındaki yol. Bu şekilde tanımlanan değerler her zaman üçgen eşitsizliğini karşılar ve mesafe grafiğindeki her tur, orijinal grafikte olası düğüm tekrarları olan bir tura karşılık gelir. ${\ displaystyle c_ {ij}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle c_ {ij}}$

Eğer öyleyse değil daha yerleri ziyaret caiz daha sonra, herhangi bir TSP da aynı negatif olmayan sabiti her kenar uzunluğunu arttırarak bir metrik TSP indirgenebilir: Sürekli daima edilebilir yeterince büyük olduğu tespit Tümüne buluştuğu düğüm üçlüsü için. Optimumdan maksimum sapmayı garanti eden buluşsal yöntemler söz konusu olduğunda, bu prosedür doğal olarak orijinal görevin sapma faktörünü artırır. ${\ displaystyle q \ geq 0}$${\ displaystyle (c_ {ij} + q) \ leq (c_ {ik} + q) + (c_ {kj} + q)}$

Entegre bir doğrusal program olarak formülasyon

Problemi çözmeye yönelik bir yaklaşım, onu , kararların değişkenler tarafından ve koşulların doğrusal eşitsizlikler tarafından tanımlandığı integral bir doğrusal program olarak formüle etmektir . Bunun birkaç olası çeşidi vardır. Bir dizi düğüm içeren simetrik TSP için bir modelleme burada örnek olarak sunulacaktır. Her kenar için, belirli bir tur için kenarın bu tura dahil edilip edilmediğini ( ) gösteren bir ikili değişken eklenir . Her tur, ilişkili değişken değerleri belirtilerek bu şekilde belirtilebilir, ancak değişken değerlerinin her 0-1 ataması bir turu tanımlamaz. Bir turu tanımlamak için değişken atamanın koşulları, aşağıda sunulan doğrusal eşitsizliklerle ifade edilebilir. ${\ displaystyle V}$ ${\ displaystyle \ {i, j \}}$${\ displaystyle x _ {\ {i, j \}} \ in \ {0,1 \}}$${\ displaystyle \ {i, j \}}$${\ displaystyle x _ {\ {i, j \}} = 1}$${\ displaystyle x _ {\ {i, j \}} = 0}$

Derece koşulu: Turun tam olarak bir kenarı her düğümün içine veya dışına çıkmalıdır i.

Her düğüm, diğer düğümlere tam olarak iki tur kenarı, yani bir içe ve bir dışa doğru kenar yoluyla bağlanmalıdır:

${\ displaystyle \ toplamı _ {j \ in V \ setminus \ {i \}} x _ {\ {i, j \}} = 2 \ qquad (1)}$

herkes için . Olarak toplamı , her bir toplam kısmı olan ya da (tur dahil), 1 veya 0 (dahil) içerir. Dolayısıyla toplam, düğümü bir uç düğüm olarak içeren turun kenarlarının sayısını tam olarak sayar . Bir kenar girip çıkması gerektiğinden 2 değerine sahip olmalıdır. Sağdaki resim, gelen ve giden kenarları olan bir düğümü gösterir ve turne kenarları kalın olarak işaretlenmiştir. Kenarlarda, yukarıda belirtilen toplamlara katkıda bulunan değerler vardır. ${\ displaystyle i \ V’de}$ ${\ displaystyle x _ {\ {i, j \}}}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle x _ {\ {i, j \}}}$

Kısa döngüler: Bu değişken atama, tüm derece koşullarını yerine getirir, ancak bir tur tanımlamaz.

Yukarıdaki derece koşulları sadece turlarla değil, aynı zamanda her bir düğümün tam olarak bir daire içinde yer aldığı birkaç ayrı daireyi (sözde kısa döngüler ) tanımlayan değişken atamalarla da karşılanmaktadır (şekle bakınız). Böyle bir şeyi dışlamak için, kısa döngü eşitsizliklerinin ( alt yol yok etme koşulları olarak da adlandırılır ) karşılanması gerekir. Dantzig, Fulkerson ve Johnson tarafından 1954'te döngü koşulları olarak ortaya konan bu kısıtlamalar, ne boş ne de tüm düğümleri içeren her düğüm kümesinin , turun en az iki kenarı ile kalan düğümlere bağlanması gerektiğini belirtir: ${\ displaystyle S \ alt küme V}$

${\ displaystyle \ toplamı _ {i \ S, \; j \ notin S} x _ {\ {i, j \}} \ geq 2 \ qquad (2)}$

düğümlerin her kümeleri için birlikte . Toplam, bir düğüm ile başka bir düğüm arasındaki turun tüm kenarlarını sayar . Gereksiz eşitsizliklerden kaçınmak için, kişi kendisini en az iki ve en çok düğüm içeren düğüm kümeleriyle sınırlandırabilir . Kenarlarına resim tekrar birlikte değerinin kalan kenarları ise, kalın çizilmiş var. Soldaki üç düğümden oluşan düğüm kümesi için koşul (2) eklenmesi , S'nin sağdaki üç düğüme en az iki tur kenarı ile bağlanmasını ve böylece gösterilen iki kısa döngüyü hariç tutmasını sağlar. Dantzig, Fulkerson ve Johnson alt tur eleme koşullarının sayısı . Miller, Tucker ve Zemlin tarafından 1960 yılında yayınlanan alt turlardan kaçınmaya yönelik kısıtlamaların alternatif bir temsili, ziyaret edilen yerlerin sırasını gösteren yeni değişkenler sunarak yalnızca kısıtlamalarla geçer. Bununla birlikte, TSP'nin ikili yapısı nedeniyle, Miller, Tucker ve Zemlin'e göre formülasyonda bile , TSP NP-zor olmaya devam etmektedir . ${\ displaystyle S}$${\ displaystyle 1 \ leq | S | \ leq | V | -1}$${\ displaystyle i \ S’de}$${\ displaystyle j \ notin S}$${\ displaystyle S}$${\ displaystyle | V | -2}$${\ displaystyle \ {i, j \}}$${\ displaystyle x _ {\ {i, j \}} = 1}$${\ displaystyle x _ {\ {i, j \}} = 0}$${\ displaystyle S}$${\ displaystyle 2 ^ {n} -2 (n-1)}$${\ displaystyle n}$${\ displaystyle n ^ {2} -n + 1}$${\ displaystyle x _ {\ {i, j \}}}$

Tüm bu eşitsizlikleri karşılayan 0 ve 1'den girişlere sahip her vektör geçerli bir gidiş dönüş tanımladığından, satıcının yeniden formüle edilmiş sorunu ortaya çıkar: ${\ displaystyle x = (x _ {\ {i, j \}}) _ {i, j \ V, i \ neq j}}$

${\ displaystyle \ min \; \ sol \ {\ sum _ {i \ in V} \ sum _ {j \ in V \ setminus \ {i \}} c _ {\ {i, j \}} x _ { \ {i, j \}} \; | \; x {\ text {yerine getirir (1) ve (2)}}, \; x _ {\ {i, j \}} \ in \ {0,1 \ } \ sağ \}. \ qquad (3)}$

Değişkenler yalnızca 0 veya 1 değerlerini aldığından, toplam , turda bulunan kenarların uzunluklarını tam olarak toplar . ${\ displaystyle x _ {\ {i, j \}}}$${\ displaystyle c _ {\ {i, j \}}}$${\ displaystyle \ {i, j \}}$

Neredeyse her düğüm alt kümesi bir eşitsizlik tanımladığından , (2) türündeki eşitsizliklerin sayısı şehirlerin sayısıyla katlanarak artar . Ancak, bu eşitsizliklerin ancak gerçekten ihtiyaç duyulduğunda eklendiği düzlem kesme yöntemleri yardımıyla bu sorun aşılabilir. Geometrik olarak, her doğrusal denklem , değişkenlerin uzayında bir hiper düzlem olarak yorumlanabilir. Kabul edilebilir çözümler dizisi, bu alanda bir politop oluşturur, yani tam şekli maliyetlere bağlı olan ve çoğunlukla bilinmeyen çok boyutlu bir çokgen . Bununla birlikte, koşulların (1) ve (2) çoğunun , TSP politopunun fasetlerini , yani politopun mümkün olan en yüksek boyuta sahip yan yüzeylerini tanımladığı gösterilebilir. Bu, onları bir turu tanımlamak için kullanılabilecek en güçlü doğrusal eşitsizliklerden biri yapar. İlişkili eşitsizlikleri yalnızca birkaç durumda bilinen başka birçok yön vardır. (1) ve (2), 0/1 vektörlerine kısıtlama ile birlikte sorunu tam olarak modellese de, bu tür ek eşitsizlikler, tamsayı olmayan belirli LP çözümlerini tanımlamak için bir dallanma ve kesme yöntemi dahilinde formülasyona eklenebilir. Koordinatları hariç tutun (bkz . Tam çözüm yöntemleri bölümü ). ${\ displaystyle 2 ^ {| V |}}$${\ displaystyle c _ {\ {i, j \}}}$

Algoritmik Karmaşıklık

Gezici satıcı, henüz gitmediği şehirleri her adımda seçebildiği için, asimetrik ve simetrik TSP (ile ) için turlar mümkündür . Arama alanının boyutu, üstel bir şekilde şehirlerin sayısına bağlıdır. ${\ displaystyle (n-1)!}$${\ displaystyle (n-1)! / 2}$${\ displaystyle n> 2}$

Seyahat eden satıcı problemi, hem genel hem de simetrik veya metrik durumlar için NP'ye eşdeğerdir . Genel olarak varsayılan ancak şimdiye kadar kanıtlanmamış P ve NP karmaşıklık sınıflarının farklı olduğu varsayımı altında ( bkz.P-NP problemi ), polinom çalışma süresine göre her bir örnek için sorunu çözebilecek deterministik bir Turing makinesi olmadığını takip eder . şehir sayısı çözülür.

Gezici satıcının genel problemi için P NP varsayımı altında, değeri optimal değerden en fazla bir faktör sapan herhangi bir polinom için temel olarak bir çözüm hesaplayan bir polinom zaman algoritmasının olamayacağı da bilinmektedir . ${\ displaystyle \ neq}$${\ displaystyle p}$${\ displaystyle 2 ^ {p (n)}}$

Bununla birlikte, en iyi çözüm olarak (aşağıya bakın ) en fazla iki katı ( minimum yayılma ağacı yaklaşımı ) veya en fazla 1,5 katı ( Christofides algoritması ) olan bir polinom çalışma zamanında bir çözüm sunan metrik TSP için yaklaşık algoritmalar belirtilebilir . Şimdiye kadar, 1.5'ten daha iyi kalite garantisine sahip bilinen bir polinom zaman algoritması yoktur. 8/7 kalite garantili bir polinom zaman algoritması, 1 ve 2 mesafelerinin kısıtlanmasıyla bilinir. P NP varsayımı altında (bilinmeyen) bir sabit vardır , böylece Karpinski, Lampis ve Schmied 2013'ün gösterdiği gibi kaliteyi garanti eden metrik TSP için hiçbir polinom zaman algoritması mevcut olamaz . Grafik TSP için karşılık gelen en iyi bilinen sabittir . Arora (1996) ve Mitchell (1996) bağımsız olarak Öklid TSP için bir polinom yaklaşımı şeması (PTAS) verdiler .${\ displaystyle \ neq}$${\ displaystyle c \ geq {\ tfrac {1} {122}} \ yaklaşık 0 {,} 0081}$${\ displaystyle 1 + c}$${\ displaystyle c}$${\ displaystyle {\ tfrac {1} {534}}}$

Çözüm yöntemi

Bilinen çözüm yöntemleri, birbiriyle birleştirilebilen iki gruba ayrılır. Kesin çözüm prosedürleri, her uzunlukta bir çalışma süresi varsayılarak her zaman kanıtlanabilir bir optimal çözüm bulacaktır. Sezgisel yöntemler genellikle kısa sürede iyi çözümler bulur, ancak genel olarak istediğiniz kadar kötü olabilirler. Metrik TSP için , çözümleri genellikle en kısa gidiş-dönüş yolculuğundan en fazla 1.5 veya 2 kat daha uzun olan polinom buluşsal yöntemler vardır .

Kesin çözüm yöntemleri

Seyahat eden satıcı sorunu, tüm olası gidiş-dönüş yolculuklarının mesafeleri hesaplanarak ve ardından en küçük mesafeli olanı seçerek tam olarak çözülebilir. Ancak, bu artık az sayıda şehir için mümkün değildir. En basit varyantta, şehirlerle simetrik TSP'de , 15 şehirde 43 milyarın üzerinde ve 18 şehirde 177 trilyonun üzerinde çeşitli gidiş-dönüş seferleri vardır . Aşağıdaki örnek, artan sayıda şehirle birlikte bilgi işlem süresinin ne kadar hızlı büyüdüğünü göstermektedir: Bir saatte 30 şehrin çözümünü hesaplayan bir bilgisayarınız varsa, iki şehir için neredeyse bin kat daha fazla zamana ihtiyaç duyar; bu 40 günden fazla. ${\ displaystyle n}$${\ displaystyle (n-1)! / 2}$

Üç düğümde TSP: Kırmızı kesikli kesme düzlemi, izin verilmeyen tüm çözümleri en fazla bir kenarla keser . Kırmızı politoptaki tüm noktalar, kabul edilebilir tek nokta da dahil olmak üzere bu eşitsizliği karşılar (1,1,1).${\ displaystyle x_ {1} + x_ {2} + x_ {3} \ geq 2}$

Diğer yandan, tamsayı doğrusal optimizasyon yöntemleriyle, özellikle dal ve kesme işlemleriyle , pratik olarak ilgili büyüklük sıralamalarının en iyi şekilde çözüldüğü kanıtlanabilir veya en azından bulunan bir turun kalitesi, bir en uygun çözüm. Geometrik olarak yorumlanır, bu yöntemler, bir şekilde problemi dikkate dışbükey politop de çok boyutlu bir çokgen olarak, diğer bir deyişle boyutlu birim küp olduğu, grafik kenarlarının sayısı. İlişkili 0/1 vektörünün yukarıda açıklanan doğrusal eşitsizlikleri karşılaması koşuluyla, bu birim küpün her köşesi bir turu tanımlar. Bu eşitsizliklere ait hiper düzlemler bu nedenle birim küpün bir turu temsil etmeyen köşelerini keser. ${\ displaystyle m}$ ${\ displaystyle [0,1] ^ {m}}$${\ displaystyle m}$

Sağdaki resim bunu üç düğümlü (çok basit) TSP için göstermektedir. Ayrıca üç ikili değişken vardır ve bu düğümler arasındaki olası üç kenara karşılık gelir . Bu durumda, üç kenarı da kullanan tek bir olası tur vardır. Bu tur , her turun en az iki kenara sahip olması gerektiği konusundaki eşitsizliği karşılar . (1,1,1) noktasına tekabül eden bu tur dışında kırmızı bordürlü alandaki tüm noktalar da bu eşitsizliği karşılar. Kırmızı kesikli çizgilerle yayılan karşılık gelen kesme düzlemi , imkansız turlara karşılık gelen tüm köşeleri en fazla bir kenarla, yani sıfır vektörü (0,0,0) ve birim vektörler (1,0,0 ), (0,1,0) ve (0,0,1). Daha güçlü eşitsizlik , birim küpün kabul edilebilir tek noktası (1,1,1) dışında her şeyi keserdi. Bu özel durumda, (1) tipindeki üç eşitsizlik kullanılarak aynı etki elde edilebilir. ${\ displaystyle x_ {1}, \, x_ {2}}$${\ displaystyle x_ {3}}$${\ displaystyle x_ {1} + x_ {2} + x_ {3} \ geq 2}$${\ displaystyle x_ {1} + x_ {2} + x_ {3} \ geq 3}$

Birçok doğrusal programı çözerek , birim küpün gereksiz kısımlarını daha fazla kesme düzlemi yardımıyla (örneğin (2) tipi veya ayrıca tarak , klik ağacı ve domino parite eşitsizlikleri ) kullanarak ve çeşitli alt politoplara bölerek Branch-and -Bound yardımı, minimum amaç fonksiyon değerine sahip izin verilebilir bir 0/1 köşesi belirlemeye çalışılır . Bu yöntemlerin daha ayrıntılı bir açıklaması Tamsayı Doğrusal Optimizasyon makalesinde bulunabilir .

Bu prosedürleri tek başına uygulamak genellikle iyi turları hızlıca bulmak için yeterli değildir. Başlıca avantajları, en kısa turun minimum uzunluğu hakkında bilgi vermeleridir. Optimal çözüm değeri için böylesine düşük bir sınırla, bulunan bir turun optimal bir gidiş-dönüş yolculuğuna kıyasla ne kadar iyi olduğunu bilmeden tahmin etmek mümkündür. Örneğin, 100'lük bir alt sınır ve 102 uzunluğunda bir tur bulduysanız, en uygun tur yalnızca 100 ile 102 arasında olabilir. Sözde optimumu boşluk, yani optimal bir tur uzunluğu ve en kısa bilinen tur uzunluğu arasındaki maksimum nispi mesafeye, bu nedenle (102-100) / 100 =% 2, diğer bir deyişle H; bulunan çözüm değeri 102, optimum değerden en fazla% 2 uzaktadır. Bulunan bir turun uzunluğu alt sınırla tam olarak aynıysa, bu, bulunan çözümün optimal olduğunu kanıtlar. İyi turlar bulmak için, bu kesin prosedürler sezgisel tarama ile birleştirilebilir, bunlardan bazıları aşağıdaki bölümde açıklanmıştır.

Sezgisel

Kullanılabilir çözümlere hızlı bir şekilde ulaşmak için, sezgisel yöntemlerle motive edilen yaklaşım yöntemleri genellikle gereklidir, ancak bunlar genellikle bulunan çözümler için bir kalite değerlendirmesi sağlamaz. Sezgisel yöntemin yeni bir tur oluşturup oluşturmadığına veya mevcut bir turu iyileştirmeye çalışıp çalışmadığına bağlı olarak, bir açılış (aynı zamanda inşaat ) veya iyileştirme süreci olarak adlandırılır. Ek olarak, bir tur için minimum uzunlukları hesaplayan ikili buluşsal yöntemler vardır. Meta sezgisel yöntemler, bu bireysel buluşsal yöntemlerin birkaçını farklı şekillerde birleştirebilir. Burada sunulan sezgisel yöntemlerin çoğuna genel bir bakış, Genel Bakış bölümünde bulunabilir .

Açılış prosedürü

En yakın komşu buluşsal yöntemi , her adımda en yakın düğümü ziyaret eder.

En yakın komşu sezgisel yöntemi , seyahat eden bir satıcının sezgisel yaklaşımına karşılık gelir . Bir şehirden başlayarak, şehir en yakın olanı aşağıdaki konum olarak seçer. Bu, tüm şehirler ziyaret edilene ve gezici satıcı başlangıç ​​noktasına dönene kadar kademeli olarak devam edecektir. Her şehirde en kısa giden yol aranmalıdır. Grafikteki düğümler kadar şehir başına yalnızca giden kenarlar olabilir. Bu , O (n²) ' lik bir algoritmik karmaşıklıkla sonuçlanır , bu nedenle hesaplama adımlarının sayısı şehirlerin sayısının karesine bağlıdır. Bu buluşsal yöntemin genellikle en iyi çözümü sağlamaması gerçeği, başlangıç ​​şehri ile son ziyaret edilen şehir arasındaki mesafenin sonuna kadar hesaba katılmamış olmasından kaynaklanmaktadır. En yakın ve en uzak komşu sezgisel tarama, herhangi bir sayıda kötü sonuç verebilir; yani, optimum değere kıyasla çözüm değeri için sabit, örnekten bağımsız bir yaklaşım faktörü yoktur .

Sözde ekleme buluşsal yöntemi , daha fazla açma prosedürlerinin bütün bir sınıfını oluşturur . Bunun en basit varyantları, en yakın ekleme buluşsal yöntemi (en yakın ekleme) ve en uzak ekleme buluşsal yöntemidir (en uzak ekleme) . Kesin prosedürler kullanılarak en uygun gidiş-dönüş yolculuğunun hızla belirlenebileceği (birkaç) komşu şehir olsun. Henüz ziyaret edilmemiş olan şehrin önceki gidiş-dönüş yolculuktaki bağlantı hatlarından birine en yakın (veya en uzak) olduğunu belirlemek için şimdi adım adım kontrol yapılır. Bu şehir bulunduktan sonra, ona en yakın şehirler arasındaki tura dahil edilecek. Süreç tur tüm şehirleri kapsayana kadar devam eder. Bu buluşsal yöntemin çözümleri, en uygun çözüme kıyasla istediğiniz kadar kötü olabilir.

Bir minimum kapsayan ağaç az kenar uzunluğuna sahip bir grafik tüm noktaları bağlayan

Başka bir sezgisel tarama sınıfı, düğüm kümesini her biri kısmen optimize edilmiş ayrı bölümlere (örneğin coğrafi kriterlere göre) böler . Kısmi çözümler daha sonra genel bir çözüm oluşturmak için birleştirilir. Kural olarak, bu yalnızca yerel olarak optimaldir ve global optimal ile karşılaştırıldığında istendiği kadar kötü olabilir.

Minimum kapsayan ağaç buluşsal (MST) ilk olarak bir hesaplar asgari karış ağacı , yani bir grafiktir tüm noktaları bir asgari uzunluğa sahip birbirine bağlı olduğuna değinilmesi gerekir. Buna dayanarak, önce tüm ağaç kenarlarını ikiye katlayarak ve ardından ortaya çıkan Euler'in grafiğinde bir " Euler turu" aranarak bir tur oluşturulur . Düğümler iki kez ziyaret edilirse, bu nihayet doğrudan kenarlarla kısaltılır. Minimum yayılma ağacı Kruskal yöntemi kullanılarak hesaplanırsa, MST buluşsal yöntemi en yakın ekleme buluşsal yöntemiyle aynı sonucu verir. Optimal bir çözüme kıyasla sonuç istediğiniz kadar kötü olabilir. Bununla birlikte, bir metrik TSP durumunda, bu şekilde oluşturulan turun en kısa turdan en fazla iki kat daha uzun olduğu gösterilebilir.

Metrik TSP için daha da iyi bir yaklaşım kalitesi , Christofides ve Serdyukov tarafından algoritma ile elde edilir . Optimal olanın en fazla bir buçuk katı olan bir gidiş-dönüş yolculuğu hesaplamak için kullanılabilir. MST buluşsal yönteminde kenarları ikiye katlamak yerine, bir Euler grafiği oluşturmak için en küçük ölçüde yayılan ağaçtaki tek dereceli düğümler üzerinde en küçük mükemmel eşleşme hesaplanır. Ancak bu algoritma daha karmaşıktır.

İyileştirme süreci

Optimizasyon yöntemlerinin iyileştirilmesi, ayrıca optimizasyon sonrası yöntemler (optimizasyon sonrası) küçük değişiklikler yaparak mevcut bir turu kısaltmaya çalışır. Dikkate alınan değişikliklerin hiçbiri bir iyileşmeye yol açmazsa, yerel bir optimum bulunmuştur (ancak küresel bir optimum olması şart değildir). K-Opt sezgisel sistematik grupları kaldırarak bu yaklaşımı takip turu kenarları ve değiştirilmesi ile bir tur tekrar oluşturulur, böylece diğer kenarlar. Bu prosedürün eksiksiz bir şekilde uygulanması, tüm olası yolların bir listesine karşılık geleceği için , pratik uygulamalarda genellikle maksimum 5'tir. Genellikle, iki ve üç kenarın tüm değişim olasılıkları denenirken, üçten fazla kenarın değiş tokuşu yapılır. yalnızca hesaplama çabası nedeniyle çok tutumlu bir şekilde kullanıldı. ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$

Pratikte bir k-iyimserliğin kalitesi, büyük ölçüde değiş tokuş edilecek kenarların seçimine ve çeşitli sezgisel kriterlerin bulunduğu parametrenin seçimine bağlıdır . İyi bilinen bir k-opt-tabanlı buluşsal yöntem , 1973 yılında S. Lin ve BW Kernighan tarafından geliştirilen ve Keld Helsgaun'un uygulanmasında, diğer şeylerin yanı sıra en uygun çözümde yer alan Lin-Kernighan buluşsal yöntemidir. 2004 yılında 24.978 İsveç lokasyonuna göre TSP oldu. İlk olarak iki uçtaki tüm değişim olasılıklarının, ardından üç kenarlı olanların vb. Olası birkaç sonlandırma kriterinden biri karşılanana kadar test edilmesine dayanır. ${\ displaystyle k}$

Meta-sezgisel Prosedürler

Meta- sezgisel yöntemler, bir problemin sezgisel optimizasyonu için yerel ve küresel arama yöntemlerini soyut bir stratejide birleştirir. Bu yöntemlerin çoğu yerel aramaya dayanmaktadır ; Başka bir deyişle, sezgisel bir başlangıç ​​çözümünü hesaplarlar (örneğin en yakın komşu sezgisel yöntemle) ve daha iyi bir tur bulunmayana kadar K-Opt sezgisel yöntemi gibi yerel bir arama yöntemini kullanarak geliştirirler . Tabu arama veya simüle edilmiş soğutma gibi çeşitli stratejiler , mümkün olduğunca yerel minimumlarda takılıp kalmamak için kullanılabilir. Karınca algoritmaları , genetik algoritmalar veya yapay sinir ağları (özellikle oradaki Hopfield ağı ) gibi diğer yaklaşımlar doğal süreçlere dayanmaktadır. Prensip olarak, tüm bu yöntemler iyi çözümleri hesaplayabilir, ancak aynı zamanda optimal bir çözüme kıyasla istediğiniz kadar kötü de olabilirler. Kaliteleri ve süreleri büyük ölçüde münferit adımların tanımlanmasına ve uygulanmasına bağlıdır.

Çift sezgisel tarama

Gezici satıcı problemi, bir turun minimum uzunluğu için kullanılabilir alt sınırların (genel olarak: bir çözümün minimum maliyeti) basit bir şekilde belirlenebildiği birkaç kombinasyonel optimizasyon probleminden biridir. Bu sınırlar, izin verilen bir turun kalitesi hakkında açıklama yapmak için özellikle önemlidir. Örneğin, her tur, yani özellikle optimal olanı hassas kenarlar içerdiğinden, en az en küçük kenar uzunluklarının toplamı kadar uzun olmalıdır . Diğer bir alt sınır, bir turdan herhangi bir kenarı sildiğinizde, bir kapsayan ağacın , yani tüm düğümleri içeren ancak daire içermeyen bir alt grafiğin ortaya çıktığı gözleminden kaynaklanır. Tur, en az bu ağaç kadar uzun ve bu nedenle, tanım gereği, kolayca belirlenebilen, asgari düzeyde uzanan bir ağaç (yani, kenar uzunluklarının minimum toplamına sahip bir yayılan ağaç) kadardır . Bu her tur için geçerli olduğundan, minimal bir yayılma ağacının uzunluğu, optimal bir turun uzunluğu için daha düşük bir sınır sağlar. Biraz daha genel bir şekilde, minimum 1 ağaç olarak adlandırılan bir ağaç da hesaplanabilir. Bu, olası iki en kısa kenar (dolayısıyla adı) aracılığıyla 1 numaralı düğüme bağlanan, 2'den (herhangi bir numaralandırmaya sahip) düğümler arasında minimal olarak uzanan bir ağaçtır . Uzunluğu ayrıca bir alt sınır sağlar. Dahası, her tur aynı zamanda mükemmel bir 2 eşleştirmedir . Bu, en kısa turun en az O (n³) cinsinden hesaplanabilen minimum mükemmel 2-eşleşmenin değeri kadar uzun olması gerektiği anlamına gelir. ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n}$

Genel Bakış

Aşağıdaki genel bakış tablosu , burada sunulan buluşsal yöntemlerin çoğu için yordam türünü, şehirler için maksimum çalışma süresini ve hesaplanan çözümler için herhangi bir kalite garantisini listeler. Meta-sezgiselliğin çalışma süresi ve kalitesi büyük ölçüde alt algoritmaların seçimine bağlı olduğundan ve genel olarak belirtilemediğinden, bunlar burada listelenmemiştir. ${\ displaystyle n}$

Prosedür	Tür	çalışma süresi	Optimumdan maksimum sapma
En Yakın Komşu Sezgisel	Sezgisel açılış	${\ displaystyle {\ mathcal {O}} (n ^ {2})}$	Faktör (log (n) +1) / 2 (metrik TSP)
En Uzak Komşu Sezgisel	Sezgisel açılış	${\ displaystyle {\ mathcal {O}} (n ^ {2})}$	herhangi beden
En uzak ekleme buluşsal yöntemi	Ekleme buluşsal yöntemi	${\ displaystyle {\ mathcal {O}} (n ^ {2})}$	herhangi beden
En yakın ekleme buluşsal yöntemi	Ekleme buluşsal yöntemi	${\ displaystyle {\ mathcal {O}} (n ^ {2})}$	herhangi bir boyut, faktör 2 (metrik TSP)
Minimum kapsayan ağaç buluşsal yöntemi	Sezgisel açılış	${\ displaystyle {\ mathcal {O}} (n ^ {2} \ log (n))}$	en yakın ekleme gibi
Christofides buluşsal yöntemi	Sezgisel açılış	${\ displaystyle {\ mathcal {O}} (n ^ {3})}$	Faktör 1.5 (metrik TSP)
K-opt sezgisel	İyileştirme sezgisel	${\ displaystyle {\ mathcal {O}} (k!)}$ adım başına	herhangi beden
Yuva en kısa kenarların toplamı	Çift sezgisel tarama	${\ displaystyle {\ mathcal {O}} (n ^ {2} \ log (n))}$	herhangi beden
Minimum yayılan ağacın uzunluğu	Çift sezgisel tarama	${\ displaystyle {\ mathcal {O}} (n ^ {2} \ log (n))}$	herhangi beden

Tahmin Edilebilirliğin Pratik Sınırları

Şimdiye kadar en iyi şekilde çözülmüş olan (simetrik) bir gidiş-dönüş probleminin önemsiz olmayan en büyük örneği, 33.810 düğümlü entegre devrelerin yerleşimi için bir planlama problemidir . Bu rekor, 2005 yılında William Cook ve diğerleri tarafından , çeşitli sezgisel yöntemler ve dal ve kesim tabanlı program Concorde'un bir kombinasyonunun yardımıyla, çeşitli üniversite çalışma gruplarından önceki kısmi sonuçları temel alarak oluşturuldu. O zamana kadarki en iyi şekilde çözülen en büyük örnek, 2004'te çözülen 24.978 İsveç şehrinden oluşuyordu. Özel ayrıştırma teknikleri ve birkaç paralel bilgisayarın yardımıyla William Cook, bir TSP için uzunluğu 526 milyondan fazla yıldız için turlar buldu . Optimumdan% 0,798'den fazla sapma göstermediği kanıtlanmıştır.

Bununla birlikte, belirli bir boyuttaki bir TSP'nin en iyi şekilde çözülebileceği gerçeği , bu boyuttaki her bir örneğin en iyi şekilde çözülebileceği anlamına gelmez, çünkü - çoğu kombinatoryal optimizasyon probleminde olduğu gibi - çözümün zorluğu büyük ölçüde girdi parametrelerine bağlıdır. bu durumda kenar ağırlıkları). Daha küçük bir sorunun çözülmesi çok daha zor olabilir; Örneğin, TSPLIB'de çok sayıda simetrisi nedeniyle çözülmesi zor olan sadece 225 şehirli bir örnek var. Pratik uygulamalardan kaynaklanan TSP'ler söz konusu olduğunda, zaman pencereleri gibi diğer ikincil koşullar genellikle dikkate alınmalıdır. Bu nedenle, bu tür varyantların optimal olarak çözülebilen en büyük problem örnekleri, genellikle klasik gezici satıcı probleminden önemli ölçüde daha küçüktür, bu nedenle pratikte problemi çözmek için sıklıkla sezgisel yaklaşımlar kullanılır. Sezgisel prosedürlerin, dallanma ve kesme gibi LP tabanlı prosedürlerle kombinasyonları , tur uzunluğu için alt sınırlar yardımıyla çözümlerin kalitesini ve çözüm prosedürlerini değerlendirebilmek için temel olarak araştırmada kullanılır.

Varyantlar ve uygulamalar

Sorunun klasik varyantı bile birçok uygulamada, örneğin DNA dizilişinde , entegre devrelerin düzeninde veya baskılı devre kartlarının imalatında bir matkabın kontrolünde ortaya çıkar . Gökbilimciler ayrıca gökyüzünü incelerken yıldızdan yıldıza en kısa yolu ararlar.

Çok sayıda birleştirilebilir varyant birlikte TSP ailesini oluşturur - bunların tümü NP açısından zor kabul edilir . Bazı genellemeler, birkaç seyyar satıcıyı ele alırken, diğer varyantlar, temelde değiştirilmiş optimizasyon kriterleri veya ek kısıtlamalar nedeniyle klasik versiyondan farklıdır.

Pratikte prosedür matematiksel teoriden farklıdır, çünkü kişi genellikle en iyi çözümü değil, sadece yeterince iyi olanı arar. Burada, uygulama ve hesaplama çabası olarak toplam çaba dikkate alınmalıdır . "İyi" nin ne anlama geldiği ve hangi kriterlerin kullanıldığı, sorunun bağlamına bağlıdır. Bu nedenle, bir defaya mahsus bir teslimat turu için milyonlarca üretilen bir devre kartının montaj planlamasına göre daha az çaba sarf edeceksiniz.

Birkaç seyyar satıcı

İle çoklu TSP (MTSP) , şehirler birçok arasında paylaşıldı ticari onların yuvarlak gezileri tüm başlangıç ve aynı şehirde biten, seyahat. Her şehir, tam olarak bir seyyar satıcı tarafından ziyaret edilmelidir. Amaç, kat edilen toplam mesafeyi en aza indirmektir. Tembel olmayan satıcı varyantına sahip mTSP'de , yalnızca en az iki şehirle gidiş-dönüş gezilere izin verilir, böylece her gidiş-dönüş yolcunun gerçekten dolaşması gerekir. Klasik versiyon, yalnızca bir seyyar satıcıya sahip özel bir durumdur.

Araç Yönlendirme sorun (ARP) ek taşıma kapasitesi kısıtlamaları ile bir çok TSP olup. Doğrudan, malların müşterilere merkezi bir depodan teslim edileceği rota planlamasının pratik gerekliliğinden ortaya çıktı . Gidiş- dönüş seferleri , ortak depodan başlayan ve geri dönen minibüs turlarına karşılık gelir . VRP'nin amacı, tüm müşterilere mümkün olduğunca ucuza tedarik sağlamaktır. Bir müşteriye birden çok kez tedarik edilebilir, ancak bir seferde yalnızca bir minibüsten. Minibüslerin kapasitelerinin tüm sipariş miktarlarının toplamından daha büyük olduğu özel durumda, VRP, mTSP'ye karşılık gelir ve bu nedenle de NP-ağırdır . Elde edilen varyantlar, gelen Araç Yönlendirme Problem ( ARP ) aşağıdaki gibidir:

Kapasiteli VRP ( CVRP )

Tüm kamyonetler maksimum kapasiteye sahiptir.

Çoklu Depo VRP ( MDVRP )

Minibüsler birkaç farklı depodan başlayabilir.

Zaman Pencereli VRP ( VRPTW )

Müşterilere yalnızca belirli bir zaman çerçevesinde tedarik edilebilir.

Periyodik VRP ( PVRP )

Müşterilerin ihtiyaçları aralıklarla büyüyor. Belli bir süre dikkate alınır.

Bölünmüş Teslim VRP'si ( SDVRP )

Bir müşteriye farklı taşıyıcılar tedarik edilebilir.

Backhauls ile VRP ( VRPB )

Tedarikçiler ve teslimat miktarları dikkate alınır.

Dinamik VRP ( DVRP )

Hesaplama sırasında önceden dikkate alınması gereken ek gereksinimler ortaya çıkabilir.

Şehir kümeleri

İle genelleştirilmiş TSP (GTSP) (Almanca: TSP genelleştirilmiş) birkaç şehirler bir küme olarak birleştirilmiştir. Gezici satıcı, her kümeden tam olarak bir şehri ziyaret etmek zorundadır. TSP, her şehrin yalnızca bu şehri içeren bir kümede bulunduğu özel bir GTSP durumudur. GTSP'nin her bir örneği, basit TSP'nin bir örneğine dönüştürülebilir ve bu problem için bilinen algoritmalarla çözülebilir. Bu nedenle, GTSP de NP açısından zordur.

Uygulamada, GTSP'nin çözüm algoritmaları, örneğin CNC kesme makinelerinin boşta hareketini optimize etmek için kullanılır . Bunlar, diğer şeylerin yanı sıra, tekstil endüstrisinde büyük bir kumaş tabakasından daha küçük giysi parçalarını kesmek için kullanılır. Kesilecek konturlar kümeleri temsil eder ve konturlardaki kesici takımın olası başlangıç ​​noktaları şehirleri temsil eder.

Optimizasyon kriterindeki değişiklikler

İle TSP Toplama Ödülü ( PCTSP ), seyahat satıcısı olduğu (örneğin satış için her ildeki belli para ödülü ödenen gelirler ). Ancak bir şehirden diğerine seyahat etmek için maliyetleri artırması gerekiyor. Şimdi belirli sayıda şehir seçmeli ve bu şehirler arasında karı maksimize edecek şekilde bir gidiş-dönüş yolculuğu seçmelidir. Sorun, özel bir durum olarak klasik varyantı içerdiğinden (tüm şehirler ziyaret edilir ve tüm para ödülü 0'dır), PCTSP de NP-zordur. Bundan türetilen bir form , herhangi bir şehir arasındaki en kısa yolun belirli bir şehir için arandığı , para ödülü ve metrik mesafelerin varsayılmadığı Gezici Satış Elemanı Seçme Problemidir ( TSSP ) . ${\ displaystyle k}$${\ displaystyle k}$

İle darboğaz TSP ( BTSP ), bu en aza düşürülmesi gerekmektedir kenar uzunlukları toplamı değil, uzun kenarın uzunluğu kullanılır. Sırayla tek tek mesafeleri daha az belirgin bir yayılma Bu sonuçlar olası darboğazları, karşı koymak darboğazları . İlgili bir varyant, kullanılan en küçük uzunluğun maksimize edildiği maksimum dağılım TSP'dir .

Ek kısıtlamalar

Uygulamalardaki yaygın bir sınırlama, bir şehrin ziyaret edilmesi gereken zaman pencereleridir . Örneğin, ev aletlerinin onarımı için bir teknik müşteri hizmeti, genellikle teknisyenin ziyaret edeceği bir süre boyunca müşterilerle anlaşır. Turu planlarken bu süre dikkate alınmalıdır.

İle çevrimiçi TSP , tüm şehirler önceden verilmiştir, fakat seyyar satıcı yolda zaten iken sadece kademeli olarak anılır oldu. Daha sonra, yeni şehirlerin önceden planladığı turuna "mümkün olduğu kadar" uyması için turunu değiştirir. Bu varyant, örneğin, arızalı arabaların konumlarının yalnızca kademeli olarak bilindiği ve merkezin yeni vakaları mevcut turlara mümkün olduğunca ucuz bir şekilde dahil etmeye çalıştığı ADAC gibi arıza hizmetlerinde ortaya çıkar . Yolda birçok arıza yardımcısı olduğundan ve bir arıza bildirildiğinde, kontrol merkezi, arıza yardımcısının ne zaman geleceğini yaklaşık bir süre verir, bu, zaman pencereli çoklu çevrimiçi bir TSP'dir .

Yaklaşık 55.000 kurye şoförü ve günde ortalama 120 paket ve şoförle parsel hizmeti UPS , her araç için önceden optimize edilmiş statik rotaları kullandı ve sürücüler tarafından deneyimlerine göre ayrı ayrı modifiye edildi. 2013'ten itibaren şirket ORION ( Yolda Entegre Optimizasyon ve Navigasyon ) sistemine geçecek . Bu, bireysel paketler, kayıtlı koleksiyonlar ve tercih edilen hizmet ile özel müşteri sınıfları için garantili teslimat sürelerinin yanı sıra gerçek zamanlı trafik akışından gelen verileri hesaba katar. Deneyimli personele önerilen rotadan sapma seçeneği sunar. Bu şirket için, UPS sürücülerinin normal karayolu ağına sahip şehirlerde sola dönmemesi için ek bir koşul vardır, çünkü bu, karşıdan gelen trafiği beklemede aşırı gecikmelere ve aşırı kaza riskine neden olur.

Bireysel kanıt

1. ^ René van Bevern, Viktoriia A. Slugina: Metrik gezici satıcı problemi için 3/2 yaklaşım algoritmasına ilişkin tarihsel bir not . İçinde: Historia Mathematica . Mayıs 2020, doi : 10.1016 / j.hm.2020.04.003 , arxiv : 2004.02437 ( elsevier.com ). 
2. ^ David L. Applegate, Robert E. Bixby, Vašek Chvátal ve William J. Cook: The Traveling Salesman Problem. Hesaplamalı Bir Çalışma . Princeton University Press, Şubat 2007. s. 522-524. ISBN 0-691-12993-2
3. ↑ András Sebö, Jens Vygen: Daha güzel kulaklarla daha kısa turlar: grafik-TSP için 7/5 yaklaşım, yol versiyonu için 3/2 ve iki kenara bağlı alt grafikler için 4/3 . Combinatorica 34 (5) (2014), 597-629, ( doi: 10.1007 / s00493-011-2960-3 )
4. ↑ Pjotr ​​Berman, Marek Karpinski, (1,2) -TSP için 8/7 yaklaşım algoritması , Proceedings SODA '06, s. 641-648. doi: 10.1145 / 1109557.1109627
5. ↑ Marek Karpinski, Michael Lampis ve Richard Schmied, New Inapproximability Bounds for TSP , Algorithms and Computation - 24th International Symposium'da yayınlandı, ISAAC 2013, s. 568-578, 2013, doi: 10.1007 / 978-3-642-45030- 3
6. ^ Marek Karpinski, Richard Schmied: Kübik Grafiklerde Grafik TSP'nin Yaklaşım Sertliği . İçinde: RAIRO Yöneylem Araştırması . 49, 2015, s. 651-668.
7. ^ Sanjeev Arora: Öklid Yolculuğu Satıcısı ve diğer Geometrik Problemler için Polinom Zaman Yaklaşım Şemaları . İçinde: J. ACM . 45, No. 5, 1998, s. 753-782. doi : 10.1145 / 290179.290180 .
8. ^ Joseph SB Mitchell: Giyotin Alt Bölümleri Yaklaşık Çokgen Alt Bölümler: Geometrik TSP, k-MST ve İlgili Problemler için Basit Bir Polinom Zaman Yaklaşım Şeması . İçinde: SIAM J. Comput. . 28, No. 4, 1999, s. 1298-1309. doi : 10.1137 / S0097539796309764 .
9. ^ ^{A b} William Cook, Daniel Espinoza, Marcos Goycoolea: TSP için Domino-Parity Eşitsizlikleriyle Hesaplama. 2005. (Önbaskı, pdf; 261 kB)
10. ↑ Keld Helsgaun: Lin-Kernighan Seyahat Satıcısı Buluşsal Yönteminin Etkili bir uygulaması. (PDF; 646 kB) In: European Journal of Operational Research. Amsterdam 126.2000, No. 1, s. 106-130. ISSN  0377-2217
11. ↑ Rosenkrantz'dan sonra DJ; Stearns, RE; Lewis, PM "Seyahat eden satış elemanı problemi için yaklaşık algoritmalar," Anahtarlama ve Otomata Teorisi Konferansı, 1974. doi: 10.1109 / SWAT.1974.4
12. ^ Vašek Chvátal'ın TSP sayfası
13. ↑ Concorde'un Belgelenmiş Uygulamaları
14. ↑ Wired.com: UPS'in Paketleri Daha Hızlı Teslim Etmek İçin Yeni Aracının Arkasındaki Astronomik Matematik , 13 Haziran 2013
15. ^ New York Times: Left-Hand-Turn Eleme , 9 Aralık 2007

Edebiyat

• David Applegate, Robert Bixby , Vašek Chvátal , William Cook : Seyahat Eden Satıcı Sorunlarının Çözümü Üzerine . Documenta Mathematica. Uluslararası Matematikçiler Kongresi için ekstra cilt 3. Berlin 1998, s. 645-656. ( Postscript ; Gzip ; 68 kB)
• David L. Applegate, Robert E. Bixby, Vašek Chvátal ve William J. Cook: Seyahat Eden Satıcı Sorunu. Hesaplamalı Bir Çalışma . Princeton University Press, Şubat 2007. ISBN 0-691-12993-2
• William J. Cook: Seyahat Eden Satıcının Peşinde: Hesaplamanın Sınırlarında Matematik. Princeton University Press 2011, ISBN 0-691-15270-5 .
• Lawler, Lenstra, Rinnooy Kan, Shmoys (Ed.): The Traveling Salesman Problem. Kombinatoryal Optimizasyon Rehberli Turu . Wiley, Chichester 1985. ISBN 0-471-90413-9
• W. Domschke: Lojistik - gidiş- dönüş geziler ve turlar . Oldenbourg-Verlag, Münih / Viyana 1997 (4. baskı). ISBN 3-486-29472-5
• T. Grünert, S. Irnich: Taşımacılıkta optimizasyon. Cilt 2. Yollar ve turlar. Çalkalayıcı Verlag , Aachen 2005. ISBN 3-8322-4515-4
• Gregory Gutin, Abraham P. Punnen: Gezici satıcı sorunu ve çeşitleri . Kluwer Academic Publishers. Çevrimiçi alıntılar (İngilizce)
• Walter Schmitting: Seyahat Eden Satıcı Problemi - Öklid, İki Boyutlu Seyahat Eden Satıcı Problemlerini Çözmek İçin Voronoi / Delaunay Yapılarının Uygulamaları ve Sezgisel Kullanımı .

İnternet linkleri

• TSP oyunu - Çözüm prosedürünün ayrıntılı açıklaması ve gösterimi ile Seyahat Eden Satıcı sorunu için etkileşimli bir oyun
• Gezgin Satıcı Problemi Ev - hakkında detaylı bilgi Seyahat etmek Salesman Problem (İngilizce)
• TSPLIB - TSP'nin karşılaştırma örnekleri ve farklı varyantların toplanması (İngilizce)
• Spectrum of Science (4/99): The Optimized Odyssey - Makale, Martin Grötschel ve Manfred Padberg
• VRP Web - araç yönlendirme sorunu hakkında ayrıntılı bilgi (İngilizce)
• Haftanın 40. algoritması - 2006 BT yılı TSP veya St. Nicholas için en uygun tur
• Ücretsiz Tourplan - TSP dahil, tur planlama sorunlarını çözmek için açık kaynaklı yazılım

Bu makale, 7 Kasım 2006 tarihinde bu sürümde mükemmel makaleler listesine eklenmiştir .