BaşlayınÜcretsiz başlayın

Gezgin satıcı problemi (TSP)

Gezgin Satıcı Problemi (TSP), lojistikte uygulamaları olan popüler bir problemdir. TSP'de bir satıcıya şehirlerin bir listesi ve her bir çift arasındaki mesafeler verilir. Amaç, başlangıç şehrinden çıkıp tüm noktalardan geçerek tekrar başlangıca dönen en kısa rotayı bulmaktır. Bu, hesaplaması zor bir problemdir ancak Miller-Tucker-Zemlin (MTZ), bunun Tamsayılı Doğrusal Programlama ile çözülebileceğini göstermiştir. Bu egzersizde, aşağıdaki görselde yer alan 15 şehirli küçük bir veri kümesi için TSP'nin amaç fonksiyonunu ve bazı kısıtlarını tanımlayacaksın. Hedefin, liste üreteci (list comprehension) ile LpVariable.dicts kullanımını denemek.

Photo of Cities

Üç Python değişkeni n, cities ve dist senin için oluşturuldu \(^{1}\). n şehir sayısını, cities numaralandırılmış şehirlerin listesini, dist ise her şehir çifti arasındaki mesafeyi içeren bir pandas DataFrame'ini ifade eder. Konsolda inceleyebilirsin. Ek olarak, model de senin için başlatıldı.

\(^{1}\) Veri kümesi: Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,

Bu egzersiz, kursun bir parçasıdır

Python ile Tedarik Zinciri Analitiği

Kursa Göz Atın

Uygulamalı etkileşimli egzersiz

Bu egzersizi bu örnek kodu tamamlayarak deneyin.

# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____], 
                     cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____], 
                     lowBound=0, upBound=(n-1), cat=____)
Kodu Düzenle ve Çalıştır