開始使用免費開始

旅行推銷員問題（TSP）

旅行推銷員問題（TSP）是經典問題，並在物流領域有許多應用。在 TSP 中，一位推銷員會拿到一份城市清單，以及每對城市之間的距離。他要找出一條最短路徑：從起點出發，走訪所有城市後，再回到起點。這是計算上相當困難的問題，不過 Miller-Tucker-Zemlin（MTZ）證明可以用整數線性規劃來完成。在這個練習中，你要為一個包含 15 個城市的小型資料集（見下圖）定義 TSP 的目標式與部分限制式。你的目標是試著搭配串列生成式使用 LpVariable.dicts。

Photo of Cities

已為你建立 3 個 Python 變數 n、cities 與 dist $^{1}$。n 是城市數量，cities 是依序編號的城市清單，dist 是一個 pandas DataFrame，包含每對城市之間的距離。你可以在主控台中探索它們。此外，模型也已經為你初始化完成。

\(^{1}\) 資料集來源：Gerhard Reinelt，TSPLIB - A Traveling Salesman Problem Library，ORSA Journal on Computing。

本練習屬於課程

Python 的供應鏈分析

檢視課程

動手互動練習

試著完成這個範例程式碼，體驗一下這個練習。

# 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=____)
編輯並執行程式碼