Google ORtoolsでTSP（巡回セールスマン問題）を解いてみる

最近、GoogleのORToolsを使って配送最適化問題にかかわることがあったので
軽いメモがてら、配送最適化を知らない人に興味を持ってもらえればなという気持ちで書いていこうと思います。

Google OR-Toolsの概要

Google OR-Toolsは、複雑な数理最適化問題を解くためのプログラムライブラリです。このツールキットは、ルーティング問題、ビークルルーティング、整数線形プログラミングなど、多岐にわたる問題に対応しています。OR-Toolsを使用することで、開発者は効率的なアルゴリズムを容易に実装し、実際の問題に応用することが可能となります。

インストール手順と使用するライブラリ

公式サイトにLinux、macOS、Windowsでのインストール方法が記載されています。

pip install ortools
pip install pandas
pip install numpy
pip install geopy

問題の定義

今回は、Uber　Eatsなどのフードデリバリーサービスの最適化を例としていこうかと思います。
目標としては最小限の移動距離で、すべての顧客に食事を届けるルートを計算します。
必要なデータとしては下記になります。
・各レストランなどの住所
・顧客先の住所
・顧客先への配達物名

ライブラリをインポート

import pandas as pd
import numpy as np
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
from geopy.distance import great_circle

インプットデータの準備

# レストランと顧客のデータ
restaurant_data = {
    'name': ['Gyudon', 'Curry', 'Sushi', 'Hamburger', 'Pizza'],
    'latitude': [35.6895, 35.6581, 35.6897, 35.6824, 35.6938],
    'longitude': [139.6917, 139.7016, 139.7004, 139.7731, 139.7044]
}
customer_data = {
    'name': ['Suzuki', 'Honda', 'Sato', 'Aoki', 'Yamada'],
    'latitude': [35.6895, 35.6897, 35.6824, 35.6938, 35.7004],
    'longitude': [139.6917, 139.7004, 139.7731, 139.7044, 139.7713],
    'order_details': [
        '2 Gyudon, 1 Miso Soup',
        '3 Curry Plates',
        '5 Sushi Pieces, 2 Salads',
        '2 Hamburger Sets',
        '1 Large Pizza, 2 Sodas'
    ]
}

# データフレームの作成
restaurants_df = pd.DataFrame(restaurant_data)
customers_df = pd.DataFrame(customer_data)

# 全ノードの座標を結合
coordinates = pd.concat([restaurants_df[['latitude', 'longitude']], customers_df[['latitude', 'longitude']]], ignore_index=True)

主に使う関数

最適化

# 距離行列の計算
def calculate_distance_matrix(coords):
    num_nodes = len(coords)
    distance_matrix = np.zeros((num_nodes, num_nodes))
    for i in range(num_nodes):
        for j in range(num_nodes):
            distance_matrix[i][j] = great_circle(
                (coords.iloc[i]['latitude'], coords.iloc[i]['longitude']),
                (coords.iloc[j]['latitude'], coords.iloc[j]['longitude'])).meters
    return distance_matrix

distance_matrix = calculate_distance_matrix(coordinates)

# OR-Toolsの設定
manager = pywrapcp.RoutingIndexManager(len(distance_matrix), 1, 0)
routing = pywrapcp.RoutingModel(manager)

# 距離コールバックの定義
def distance_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return int(distance_matrix[from_node][to_node])

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# 解の探索
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
solution = routing.SolveWithParameters(search_parameters)

# 解の出力
if solution:
    print('Route found:')
    index = routing.Start(0)
    route = []
    while not routing.IsEnd(index):
        node_index = manager.IndexToNode(index)
        route.append(node_index)
        if node_index < len(restaurants_df):
            print(f"Depart from {restaurants_df.iloc[node_index]['name']}")
        else:
            customer_index = node_index - len(restaurants_df)
            customer_info = customers_df.iloc[customer_index]
            print(f"Deliver to {customer_info['name']} -> Order: {customer_info['order_details']}")
        index = solution.Value(routing.NextVar(index))
    print('Complete route:', ' -> '.join(map(str, route)))
else:
    print('No solution found.')

出力結果

Route found:
Depart from Gyudon
Deliver to Suzuki -> Order: 2 Gyudon, 1 Miso Soup
Depart from Curry
Deliver to Sato -> Order: 5 Sushi Pieces, 2 Salads
Depart from Hamburger
Deliver to Yamada -> Order: 1 Large Pizza, 2 Sodas
Depart from Pizza
Deliver to Aoki -> Order: 2 Hamburger Sets
Depart from Sushi
Deliver to Honda -> Order: 3 Curry Plates
Complete route: 0 -> 5 -> 1 -> 7 -> 3 -> 9 -> 4 -> 8 -> 2 -> 6

最小限の移動距離でフードデリバーリーをするには上記のような結果がいいことがわかりました。

次の記事では複数の出発地点や運べる量などの制約を追加して書いていこうと思います。