始める無料で始める

巡回セールスマン問題（TSP）

巡回セールスマン問題（TSP）は有名な問題で、物流などに応用があります。TSPでは、セールスマンに都市の一覧と各組み合わせの距離が与えられ、出発地からすべての都市を回って再び出発地に戻るまでの最短経路を求めます。これは計算的に難しい問題ですが、Miller-Tucker-Zemlin（MTZ）により整数線形計画法で解けることが示されました。この演習では、下の画像にある15都市という小さなデータセットに対して、TSPの目的関数といくつかの制約を定義します。目的は、リスト内包表記とともに LpVariable.dicts を使ってみることです。

Photo of Cities

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=____)
コードを編集して実行