Problem komiwojażera (TSP)
Problem komiwojażera (TSP) to klasyczne zagadnienie z obszaru logistyki. Komiwojażer otrzymuje listę miast wraz z odległościami między każdą parą. Jego celem jest znalezienie najkrótszej trasy prowadzącej z punktu startowego przez wszystkie miasta i z powrotem do miejsca wyjścia. To obliczeniowo trudny problem, jednak Miller, Tucker i Zemlin (MTZ) wykazali, że można go rozwiązać przy użyciu całkowitoliczbowego programowania liniowego. W tym ćwiczeniu zdefiniujesz funkcję celu oraz kilka ograniczeń dla TSP na małym zbiorze danych zawierającym 15 miast (patrz rysunek poniżej). Twoim celem jest wypróbowanie LpVariable.dicts w połączeniu z wyrażeniami listowymi.
Przygotowano dla ciebie trzy zmienne Pythona: n, cities i dist\(^{1}\). Zmienna n oznacza liczbę miast, cities to lista miast oznaczonych numerycznie, natomiast dist to ramka danych pandas zawierająca parzyste odległości między każdą parą miast. Możesz je zbadać w konsoli. Model został już zainicjalizowany.
\(^{1}\) Zbiór danych pochodzi od: Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
To ćwiczenie jest częścią kursu
Analityka łańcucha dostaw w Pythonie
Interaktywne ćwiczenie praktyczne
Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.
# 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=____)