1. Nauka
    2. /
  2. Kursy
    3. /
  3. Analityka łańcucha dostaw w Pythonie
Connected

ćwiczenie

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.

Photo of Cities

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,

Instrukcje 1/3

undefined XP
    1
    2
    3
  • Użyj LpVariable.dicts, aby utworzyć słownik x przechowujący zmienne binarne dla każdej pary miasto–miasto, oraz słownik u przechowujący całkowitoliczbową zmienną LpVariable dla każdego miasta.