チュートリアルより少し踏み込んだOR-Tools

OR-Tools Python

はじめに

この記事は GO Inc. Advent Calendar 2025 の21日目です。

AI技術開発部の小南です。
この記事ではOR-Toolsで解くルート最適化について、公式のチュートリアルより少し詳しい解説を行います。
制約条件の設定をカスタマイズしたくなった時などに、基本的な使い方の理解を深めておきたい方向けの内容となります。

ルート最適化について

そもそもルート最適化とはどのような問題を指すのでしょうか。
複数の地点を効率的に回るルートを考える問題で、一般的には「巡回セールスマン問題 (TSP)」や、それを複数車両に拡張した「配送計画問題 (VRP)」として知られています。

例えば以下のような状況が考えられます。

  • 積載量の限られたトラックで配送を行いたい
  • 出発地・目的地の指定がある乗車予約に限られた車両で対応したい
  • 時間指定のある訪問修理を回るスケジュールを組みたい

これらには訪問先の場所以外にも、時間・積載量・訪問順などの制約がかけられています。
このような制約を守りながら、効率的に回れるようなルートを考えるのがルート最適化です。

これ以降の記載内容については、解きたい問題がルート最適化であること、Pythonでの実装であることを前提とします。

OR-Toolsについて

OR-Tools はGoogleが提供している組み合わせ最適化用のOSSです。 この記事で取り扱うルート最適化のほか、スケジューリング問題や割り当て問題などの様々な最適化問題に対応しています。
導入が手軽であり、問題定義や制約条件の設定の自由度が高く、直感的な実装ができる点も使っていて良いところだと感じます。
今回はPythonでの実装を紹介しますが、C++, C#, Javaにも対応しています。ちなみに、OR-Tools自体はC++で実装されているようです。

チュートリアルも充実しており、基本的な使い方であれば スタートガイド を参照すれば実装ができます。
例えば、前述した制約条件である

  • 車両の最大積載量の追加
  • 訪問順の指定の追加
  • 訪問場所の時間制約の追加

などのよくある制約であればチュートリアルを参照しながらほぼコピペでも動作するかと思います。

今回はマネージャ・モデルの設定方法からこれらの制約条件がどう設定されていくのかについて詳しく追っていきます。

基本的な制約条件の設定方法

基本的な流れは以下の通りです。

  1. マネージャ・モデルを設定する
  2. コールバック関数を定義する
  3. 目的関数を設定する
  4. 制約条件を設定する

実際に動かす際はこの後各種パラメータ設定等を行い、ソルバーを実行します。

マネージャ・モデルを設定する

実装は非常に簡単です。

manager = pywrapcp.RoutingIndexManager(...)
routing = pywrapcp.RoutingModel(manager)

これ以降を理解するのに重要な点はそれぞれの役割になります。

マネージャ：ソルバー内部で扱っているデータとユーザが扱っているデータを結びつける役割
モデル：問題定義や制約条件を管理する役割

マネージャについては主に以下のような使い方で登場します。

node = manager.IndexToNode(index)

これは、ソルバー内部で扱っている地点ID（index）をユーザが扱う地点ID（node）に変換する処理です。 例えば、

  • 0 デポ
  • 1 訪問地点A
  • 2 訪問地点B

の3地点ついて、1台の車両でデポから出発し、全て訪問してデポに戻ってくる場合を考えます。
ソルバーは一度通った地点は二度と通らないというルールで動いているため、同じデポでも出発する時と到着する時は別の地点として扱われています。
この時ソルバー内部では地点情報を複製して対応しています。

  • 0 車両の出発地点
  • 1 車両の到着地点
  • 2 訪問地点A
  • 3 訪問地点B

のようなイメージです。
このようにソルバー内部で扱っている地点IDとユーザが持っている地点IDは一致しない可能性があるため、マネージャによる変換が必要になります。
使っていると概ねIDが一致しているような気もしますが、対応関係のマッピングは保証されていない ため、必ず変換を通すようにしましょう。

逆にノードからインデックスを得たい場合もあります。

index = manager.NodeToIndex(node)

この時、nodeにデポを指定すると内部で複製された2つのindexが返却されるのかというとそうではありません。
NodeToIndex()は代表地点1つを返却するようです。

デポ以外の地点はソルバー内部で複製されることがないので、NodeToIndex()を利用して大丈夫です。
デポはマネージャを作成する際に定義した車両IDを用いて出発・到着のインデックスを取得する必要があります。

# 車両ID0の出発indexと到着indexを取得する
start_index = routing.Start(0)
end_index = routing.End(0)

コールバック関数を定義する

移動コストや、積荷の量、サービス時間の定義です。ルーティングの場合コールバックは関数で設定します。

def distance_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return distance_matrix[from_node][to_node] # distance_matrixは自分で定義する必要あり

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

callbackはソルバー内部で頻繁に呼び出されるため、設定する関数の内部が高速であることが重要になります。
通常、所要時間や距離をコストとして扱う場合は事前に計算し行列として定義しておきます。
また、ソルバー内部ではこの関数の計算結果をキャッシュとして持っているようなので、呼び出すたびに値が変わるような関数は設定しない方が良いです。

モデルに渡す際はサービス時間のように地点そのものに発生するコストについては、RegisterUnaryTransitCallback()、所要時間や距離のように地点間に発生するコストにはRegisterTransitCallback()を利用します。

モデルから返却されたインデックスはモデルが保持したコールバック関数のIDであり、この後のアークコストの評価で利用します。

目的関数を設定する

ルーティングの場合は、通常「総移動時間または距離を最小化する」ように目的関数を設定することになります。 以下のようにモデルに定義した関数のIDを渡すことで、この関数を最小化するようにモデルが動作します。

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

目的関数の設定は車両ごとに変更することもできます。

# マネージャ作成の際に定義する車両のインデックスを渡す
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_A, 0)
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_B, 1)

制約条件を設定する

制約条件の付与の仕方は様々ですが、よく使うのは積載量の制約・時間枠制約・訪問数の制約など「ルートが進むにつれて積み上がっていく制約」かと思います。
このような制約はDimensionを定義することで、実行時にソルバーが積み上げの値を保持し、判定を行います。

例えば

  • 車両の最大稼働時間は600以下にしたい
  • ID3の地点には30~50の間に訪問したい

という制約は以下のように設定します。

# Dimensionを作成
routing.AddDimension(
    transit_callback_index,
    30,    # slack_max: 早着の許容時間（時間以外の制約ではあまり使わない）
    3000,  # capacity: 1車両あたりの最大稼働時間
    True,  # 開始時の時間を0にする
    "Time" # Dimensionの名前
)

time_dimension = routing.GetDimensionOrDie("Time")

# CumulVar()を利用することでその地点での累積時間を取得することができる
# 地点3での累積時間を30から50の間にするという制約を設定している
time_dimension.CumulVar(manager.NodeToIndex(3)).SetRange(30, 50)

# ソフト制約にしたい場合はSetCumulVarSoftUpperBound()などを使う
# 地点3の累積時間が50を超えたら目的関数にペナルティ60を加算する
time_dimension.SetCumulVarSoftUpperBound(manager.NodeToIndex(3), 50, 60)

また、OR-Toolsで用意している関数では表現しきれない制約がある場合は、routing.solver().Add() をよく使います。
Add()の中には自由に制約条件式を定義し、直接ソルバーに渡すことができます。

例えば地点3は地点4より前に必ず訪問しなければならないというルールは以下のように実装できます。

routing.solver().Add(
    time_dimension.CumulVar(NodeToIndex(3)) <= time_dimension.CumulVar(NodeToIndex(4))
)

地点5と地点6は同じ車両で配送しなければならない場合は以下のように実装できます。

# VehicleVar()で指定したインデックス地点の担当車両を取得することができる
routing.solver().Add(
    routing.VehicleVar(NodeToIndex(5)) == routing.VehicleVar(NodeToIndex(6))
)

以上を理解しておけば、よく使いたくなるような制約はほぼカバーできるのではないかと思います。

おわりに

いかがでしたでしょうか。
OR-Toolsの使い方についてかなり詳しく掘り下げることができたかと思います。
この記事が、どなたかの参考になれば幸いです。