Mulai sekarangMulai gratis

Traveling salesman problem (TSP)

Traveling Salesman Problem (TSP) adalah masalah yang populer dan memiliki aplikasi dalam logistik. Pada TSP, seorang wiraniaga diberi daftar kota dan jarak antar setiap pasang kota. Ia mencari rute terpendek yang berangkat dari kota asal, mengunjungi semua titik, lalu kembali lagi ke kota asal. Ini adalah masalah yang sulit dihitung, tetapi Miller-Tucker-Zemlin (MTZ) menunjukkan bahwa masalah ini dapat diselesaikan menggunakan Integer Linear Programming. Dalam latihan ini, Anda akan mendefinisikan fungsi objektif dan beberapa kendala untuk TSP pada himpunan data kecil dengan 15 kota (lihat gambar di bawah). Tujuan Anda adalah mencoba menggunakan LpVariable.dicts dengan list comprehension.

Photo of Cities

Tiga variabel Python n, cities, dan dist telah dibuat untuk Anda \(^{1}\). Variabel n adalah jumlah kota, cities adalah daftar kota yang diberi nomor, dan dist adalah pandas DataFrame yang berisi jarak berpasangan antar kota. Anda dapat menelusurinya di konsol. Selain itu, model telah diinisialisasi untuk Anda.

\(^{1}\) Himpunan data berasal dari Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,

Latihan ini merupakan bagian dari kursus

Analitik Rantai Pasok dengan Python

Lihat Kursus

Latihan interaktif langsung praktik

Cobalah latihan ini dengan melengkapi kode contoh ini.

# 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=____)
Edit dan Jalankan Kode