Gezgin Satıcı Problemi (TSP - Traveling Salesman Problem), operasyonel araştırma ve teorik bilgisayar bilimi alanlarında önemli bir problemi ifade eder. Bu problem, bir satıcının bir dizi şehri ziyaret etmesi ve başlangıç şehrine dönmesi gerektiği durumu ele alır. Ancak, burada ana hedef, toplam yolculuk süresini veya mesafeyi minimize etmektir.

Gezgin Satıcı Problemi'nin çeşitli versiyonları vardır, ancak en yaygın olanı şudur:

1. Satıcının her şehri yalnızca bir kez ziyaret etmesi gerekmektedir.
2. Satıcı başladığı yere dönmelidir, bu da yolculuğun bir döngü olduğu anlamına gelir.
3. Amacımız, toplam yolculuk mesafesini veya maliyetini en aza indiren rotayı bulmaktır.

Bu problem, gerçek dünyadaki pek çok farklı senaryoyu temsil edebilir. Örneğin, bir lojistik şirketi, belirli bir zaman diliminde teslimat yapılacak bir dizi yer belirlemiş olabilir. Bu yerler arasındaki en etkili rota, şirketin hem zamanı hem de maliyeti minimize etmesine yardımcı olabilir. Benzer şekilde, bir havaalanı ağındaki uçuşları planlarken ya da bir İnternet servis sağlayıcısı, veri paketlerinin bir ağda etkin bir şekilde nasıl yönlendirileceğini belirlerken de TSP'ye benzer problemlerle karşılaşılabilir.

Ancak, TSP'nin çözülmesi oldukça zor bir problemdir ve "NP-hard" olarak bilinen sınıfta yer alır. Bu, problemin boyutunun artmasıyla (yani ziyaret edilecek şehirlerin sayısı arttıkça) çözümünün bulunmasının üstel olarak zorlaştığı anlamına gelir. Bu nedenle, büyük ölçekli TSP'ler için genellikle yaklaşık çözümler (örneğin genetik algoritmalar, tabu arama, simüleli tavlama vb.) kullanılır.