PuLPで数理最適化問題(TSP、VRP)



表題の通り、数理最適化問題の中でもNP困難の基本的な問題の1つ、巡回セールスマン問題と、その一般化、運搬経路問題を、PuLPで解いてみます。

PuLPは、最適化問題を解くためのPythonライブラリです。

今回は、このライブラリを使って、巡回セールスマン問題および運搬経路問題を、混合整数計画問題として解いてみます。

今回の実装の全コードは以下のいずれかから。

Github: https://github.com/Gin04gh/datascience/blob/master/kaggle_env_solving_tsp_and_vrp_by_mip_using_pulp/solving-tsp-and-vrp-by-mip-using-pulp.ipynb

kaggle notebook: https://www.kaggle.com/itoeiji/solving-tsp-and-vrp-by-mip-using-pulp

PuLP

PuLPは、線形計画問題・混合整数計画問題をPythonで定義し、ソルバーを使って解くためのライブラリです。

公式サイトは以下などから。

https://coin-or.github.io/pulp/index.html
https://pypi.org/project/PuLP/
https://github.com/coin-or/pulp

ソルバーは、与えられた制約条件・問題数式に則って、最適解を解析するソフトウェアです。

対して、PuLP自体は最適化問題をモデルする役割を持つため、モデラーと呼ばれたりすることもあります。

PuLPインストール時に同時にデフォルトのソルバーCBCもインストールされ、PuLPで最適化問題を解く時、内部では以下のようなフローが実行されます。

  1. [PuLPが実行] PuLPで定義した最適化問題を、.mpsファイルとして出力する
  2. [Solverが実行] .mpsファイルを読み込んで問題を解く
  3. [Solverが実行] 最適解を.solファイルとして出力する
  4. [PuLPが実行] .solファイルを読み込んで、最適解を変数に格納する

MPS形式については、以下wikiなども参考。

https://en.wikipedia.org/wiki/MPS_%28format%29

ソルバーはCBC以外にも、以下のようなツールを別途購入・インストールして、PuLPから使用することができます。

・GLPK(無料)
・SCIP(学術利用無料、商用有料)
・Gurobi(有料)
・CPLEX(有料)

意外とPythonを使った最適化問題の解法に関しては、あまり書籍なども出ていないのですが、以下の書籍は、基本的な最適化問題をPuLPで解くコードが全て載っているので、オススメです。

巡回セールスマン問題(Traveling Salesman Problem; TSP)

巡回セールスマン問題(Traveling Salesman Problem; TSP)とは、ある都市から出発して全ての都市を1度ずつ訪れて、元の都市に戻ることを考えた時に、総移動距離が一番最短となるルートを求める最適化問題です。

組み合わせ最適化問題の代表的な問題の1つで、NP困難と呼ばれる問題のクラスに属します。

都市の数が増えれば増えるほど、組み合わせ候補が爆発的に増えてしまって、計算量的に解析が困難になる問題です。

これを、PuLPを使って、混合整数計画法で解いてみます。

混合整数計画法については、以下のリンクが参考になると思います。

線型計画法よりも、解を探索しづらそうなことが分かりやすですよね。

https://www.msi.co.jp/nuopt/introduction/algorithm/mip.html

今回の問題となるデータは、以下のようにして自前で作成します。

n_customer で都市(訪問するクライアント)の数を設定し、各都市の座標 x, y を乱数でランダムに振り分けて作成しました。

ただし、最初の1点だけは、出発する都市(DEPOT)とします。

DEPOTからスタートして、これらの点を全て経由して、DEPOTに戻る最短経路を求めてみます。

どんな感じの配置関係になっているのかを確認してみると、こんな感じ。

なんかえらく全体的に左側に寄っちゃいましたが、乱数なので仕方がない。(俺くじ運悪いし)

さて、これを解くためのPuLPの実装ですが、コード量は多くないんで、一気に書くと以下のようになります。

書き方は自己流かもしれないですけど、問題の宣言・変数の宣言・目的関数の宣言・制約条件を含む定式化のパート別に書いてあります。

x_{i,j}i から j に移動する場合は1, そうでない場合は0とする決定変数となり、

problem += pulp.lpSum(distances[i][j] * x[i, j] for i in range(n_point) for j in range(n_point)) で、

x_{i,j}=1 の場合にその区間の距離 distance_{i,j} をかけて総移動距離を計算し、これを最小化しています。

また # set constrains のパートでは、同じ都市への移動はありませんので、x_{i, i} = 0.

都市間の区間は必ず1回だけ通るという制約を入れています。

また # eliminate subtour では、部分巡回経路ができてしまわないように制御しています。

すなわち以下のような状態になってしまわないようにしているということですね。

これも確かに、都市間の区間の移動はいずれも1回ですし、同じ都市への移動もないです。

だけど、問題としては巡回して一筆書きのようにしながら最短距離を求めてほしいので、こういった制約を加えます。

以上として問題を解いて、

解析実行後のステータス pulp.LpStatus[status]Optimal で最適解が見つかったという結果となり、

最適化された目的関数の値は、 240.18 となりました。

最適化された巡回経路を可視化してみると、以下のような感じ。

一番頑張ったのは、Matplotlibで矢印を描くところだったと言っても過言ではない←

上記のような回り方で、総移動距離が 240.18 といった感じです。

運搬経路問題(Vehicle Routing Problem; VRP)

運搬経路問題(Vehicle Routing Problem; VRP)はTSPの一般化問題の一種で、複数の車両で複数の顧客のいる場所に訪れ、荷物の集荷or配達をするときに、その総移動距離を最小化するような経路を求める問題です。

巡回セールスマン問題の時よりも、少し実用的な問題に昇格した感じがする一方で、このような運搬経路を実用的な観点で考えると、他にも様々な制約条件が想像できます。

VRPの種類:

名前 内容
Capacitated VRP; CVRP 車両に載せることができる荷物の容量の制約付き
VRP with Time Windows; VRPTW 何時から何時の間に集荷or配達して欲しいという顧客の希望の時間帯の制約付き
Distance Constrained VRP; DCVRP 車両が走行できる距離の制約付き
Multi Depots VRP; MDVRP 車両が出発・到着する車両倉庫(depot)が複数ある場合のVRP
VRP with Pick-up and Delivery; VRPPD 集荷および配達を行う場合のVRP。荷物の集荷が配達より先という制約が付く

この辺りをサーベイしているような資料とか探せばある気はしますけど、本題じゃないので、今回は基本的な車両に積載キャパシティがある場合によるVRP(上記でいうCVRP)を、PuLPを使って解いてみます。

先ほどと同様に、各拠点の座標と、その場所から運んでもらいたい需要 demand を適当に作成します。

1台あたりの車両の積載キャパシティは 8 と設定しました。

様子を確認してみるとこんな感じ。

各拠点の場所と括弧で需要を描きました。

これを、積載キャパシティが 8 の車両を使って、総移動距離を最小化した時に必要な台数およびそれぞれの運搬経路を求めるコードが以下の通りです。

やっぱり巡回セールスマン問題の時と定式化が結構似てきますが、特に、

の部分で、使っている車両の台数の辻褄を合わせていて(出て行く車両と帰ってくる車両の数を合わせる)、かつ、

で需要と車両のキャパシティ制限の制約を制御しています。

上記で解析すると、総移動距離は 598.24 となり、

使う車両の台数は3台となりました。

最適化された結果を可視化してみると、以下のような感じです。

それぞれの色が車両を表して、3台を使って、上記のように回ってもらう経路が総移動距離最小化の最適解となっています。

割と各車両の走行距離に差がある結果になっていますね。

何かしらの、それぞれの車両の移動距離(業務時間)に制約を入れたりするとか、車両を利用することにかかる時間や距離当たりのコストで目的関数を構築するなどの工夫をした方が良いかもしれません。

まとめ

TSP、VRPの簡単な問題設定において、PuLPで最適解を求めるコードを公開しました。

今回は特に多くの制約は設けてはおらず、かつ問題の規模(都市の数)はとても少ないもので解いていますので、瞬間的に最適解は求められますが、これを色々と増やしていくと、組合せ爆発的に解析時間もかかるようになっていきます。

最近、数理最適化も勉強をしているのですが、機械学習・ディープラーニングとも異なるし、統計学・ベイズ統計などとも異なる感じで、難しいですね。

特に、シミュレーションとかエージェントとかみたいに、プログラムで最適化したい対象を模倣して動かしてみるような感じではない場合が多く、

定式化でどんどん行動の辻褄を合わせていくような感覚に近いので、この辺りが直感的な思考通りに作っていけなさみたいなものがあります。

数理最適化問題の経験歴が長いわけではないので、感想みたいなものですけども。

個人的には、どちらかというと、強化学習みたいなエージェントを模写して行動させて学習させる方法論の方がしっくりくるかもです。



“PuLPで数理最適化問題(TSP、VRP)” への 0 件のフィードバック

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です