1. 学ぶ
    2. /
  2. コース
    3. /
  3. Pythonで学ぶサプライチェーン分析
Connected

演習

巡回セールスマン問題（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,

指示1 / 3

undefined XP
    1
    2
    3
  • LpVariable.dicts を使って、各都市間ペアに対応する二値変数を保持する辞書 x を作成し、各都市に対する整数の LpVariable を保持する辞書 u を作成してください。