Amazon Location Service と Amazon SageMaker でゴミ収集の最適化

ゴミ収集のためのルーティング最適化

日常生活では A 地点（＝自宅）から B 地点（＝職場）までの道順を調べるためにルート検索サービスをよく利用します。これらのサービスの裏側には、A 地点から B 地点に到達するための最適なルートを計算するアルゴリズムがあり、交通手段や交通状況、その他多くのパラメータに応じて最適なルートを提供しています。

Amazon Location Service （以下、Amazon Location）は、出発点のセットから目的地のセットまでのルートのリストを定義できる機能をリリースしました。このリストはルートプランニングアルゴリズムの入力として使用されます。ルートプランニングアルゴリズムとは、ある場所から別の場所へ、いくつかの停留所を経由して最も効率の良いルートを計算するプロセスです。物流、輸送、配送の各企業は、ルート計画ソフトウェアを使用して、必要なルートを編集しています。

本記事では、Amazon Location Service と最適化アルゴリズムを使って、ゴミ収集の最適化問題で最も効率的なルートを見つける方法を紹介します。ゴミ収集は、ゴミをゴミ置き場からゴミ処理場に移送することです。収集にはゴミ収集車を使用します。

構築するもの

インタラクティブな GUI を使用して、街中のゴミ収集のルーティングを最適化するための Web アプリケーションの構築方法を説明します。ブラウザに表示される地図上で数回クリックするだけで、ゴミ収集車の出発点、ゴミ置き場の位置、トラックの台数、寸法を定義することができます。
フロントエンドを構築する前に、Amazon SageMaker （以下、SageMaker）を使用した最適化アルゴリズムでバックエンドを構築し、テストします。このアルゴリズムは、以下の制約条件に従って、すべてのトラックのルートを最適化します。

現在の交通状況
トラックは、車両（高さ、幅、質量）に適した道路のみ走行可能
トラック 1 台が収集できるゴミ置き場の数として表される最大容量
ゴミ収集終了時のトラックは全てゴミ処理センターのある出発地点に戻る

そして、最適化プロセスのアウトプットとして、ユーザーインターフェイスに最適なルートを表示します。

図1：ルート最適化の結果を示すアプリケーション画面

ソリューション概要

ルート計画は過去の記事で説明したように、A 地点から B 地点へのルートをただ計算するだけではありません。ルートには、A 地点と B 地点のような複数の出発地点と、X 地点と Y 地点のような複数の目的地位置があります。A とB から X と Y へのルートを計画し最適化するには、マトリックス内のすべてのルート候補の移動時間と移動距離が必要になります。各ポイントの組み合わせ間の時間、または距離の計算がルートマトリックスを構成しています。

図2：この複雑なルーティング問題では、ゴミ置き場が始点と終点の両方を兼ねています

マトリックスルーティングの機能を活用して問題を解決するには、各ゴミ置き場をホップの終点として、また次のホップの始点として考えることになります。

これにより、あるゴミ置き場から他のゴミ置き場までの距離をすべて取得することができます。出発地点と 9 つのゴミ置き場がある場合、10 x 10のルーティングマトリックス（100 個の値）が得られます。SageMaker は、アルゴリズムを構築し、サーバーレス推論エンドポイントとしてデプロイし、私たちのアプリケーションを従量課金のコストモデルにします。

図 3：アーキテクチャ概要

構築する全体のアーキテクチャは、以下の通りです。

アーキテクチャは、疎結合な 3 つの部分に分かれています。

フロントエンドは React アプリケーションで、AWS Amplify クライアントライブラリを活用して AWS サービスに接続します。ゴミ置き場やトラックの預け先を地図上にピン留めし、Lambda 関数に座標を送り、最適なルートを受信して地図上に描画することができます。
Lambda 関数は、ゴミ置き場の座標を Amazon Location に渡し、ルートマトリックスを取得します。その後、ルートマトリックスを SageMaker エンドポイントに送り、アルゴリズムがすべてのトラックの最適なルートを計算し、ルートを Lambda 関数に返します。
ルートジオメトリは、地図上で可視化するためにブラウザに送り返されます。

2つの AWS CloudFormation （以下、CloudFormation）テンプレートを使ってコンポーネントをデプロイします。

setup_environment.yaml – Amazon Location サービスと関連するポリシーを作成します。
api_gateway_template.yaml – Amazon API Gateway、Lambda 関数、Amazon Location への認証なしアクセス用の Amazon Cognito ID プールを作成します。

Amazon Location と Amazon SageMaker

解こうとしている問題は、容量制約のある車両ルーティング問題です。これは巡回セールスマン問題に似ていますが、いくつかの違いがあります。すべてのゴミ置き場を回収するために使用されるトラックは複数台あり、各トラックは収集できるゴミの容量に制限があります。

このアルゴリズムは NP 困難であり、最適解を見つけるのに必要な計算量は収集するゴミ置き場の数に応じて指数関数的に増大します。この問題を解決するために、合理的な時間で準最適解を見つけるために、一連の異なるアルゴリズムとライブラリを開発しました。

ソリューションの実装をシンプルにするために、Google Optimization Tools（通称、OR-Tools）を使用します。これは、組み合わせ最適化問題を解くためのオープンソースで高速かつ移植可能なソフトウェアです。OR-Tools は C++ で書かれていますが、Python、C#、Java のラッパーを提供しています。

Web アプリケーションを設計してコーディングする前に、Amazon SageMaker Studio ノートブックを使って、Amazon Location と車両ルーティングアルゴリズムについて実験してみましょう。

環境のセットアップ

本記事では、CloudFormation を使用して SageMaker Studio 環境を構築し、以下のリソースを作成します。

最適化アルゴリズムの構築とデプロイ、および Amazon Location の実験を行うための SageMaker Studio Domain
地図を表示するための Amazon Location マップリソース
ルートを計算するための Amazon Location ルーティングリソース
SageMaker が前者のサービスにアクセスできるよう、適切な権限を提供します

このステップで使用する CloudFormation テンプレートは setup_environment.yaml という名前で、ここからダウンロード出来ます。このリンクを使用して CloudFormation テンプレートをデプロイできます。図4 のような新しいウィンドウがブラウザに表示されます。

図 4：AWS CloudFormation コンソール

次のフォームで「Upload a template file」を選択し、「Choose file」ボタンを使用して、ダウンロードしたテンプレートをアップロードします。

次に、「Next」をクリックし、「Stack name」フィールドに「LocationServiceDemo」と入力し、他のパラメータはすべてデフォルト値のままにしておきます。

最後の画面で CloudFormation が図 5 に示すように AWS Identity and Access Management（IAM）リソースを作成することを確認し、「Submit」をクリックします。

図 5：CloudFormation が IAM リソースの作成を承認する

CloudFormation スタック作成処理が完了するまで待ちます。最後には図 6 のようなものが表示されます。

図 6：AWS CloudFormation のチェック完了画面

スタックがすべてのリソースを作成した後、このリンクから SageMaker Studio にアクセスし、コンソールで図 7 のようなリソースを確認することができます。

図 7 ：Amazon SageMaker Studio コンソール

ここで MyDomain をクリックすると、ドメイン内の利用可能なユーザーを一覧表示する新しいウィンドウが開きます。SageMaker Studio 環境を開くには、図 8 に示すように「Launch」を選択し、次に「Studio」を選択します。

図 8：Amazon SageMaker Studio でユーザーコンソールを開く

SageMaker Studio を開いたら図 9 に示すように、左の Git アイコンをクリックし、左のパネルでリポジトリのクローンを選択し、コンボボックスにリポジトリ名を入力し、「Clone https://github.com/aws-samples/wastecollector-planner」を選択し、「Clone」を押してリポジトリをクローンします。

図 9：Amazon SageMaker Studio で GitHubリポジトリのクローン

左のパネルで SageMaker Notebook のローカルフォルダを参照し、Amazon Location の実験に使用するノートブックを開きます。

ノートブックは wastecollector-planner/SageMaker/Using Sagemaker-OR-Tools.ipynb にあるので、それをダブルクリックします。

このノートブックに使用するカーネルを選択するプロンプトが表示され、Datascience カーネルがすでに選択されているはずです。これでノートブックが開き、これから説明するすべてのステップが表示されます。ノートブックのツールバーの再生アイコンをクリックすると、ステップを実行することができます。

ノートブックに必要なライブラリをすべてインストールしたら、ノートブック内から OR-Tools を呼び出してテストしたり、ノートブックの外から呼び出せるサービスとして公開するために、SageMaker 推論エンドポイントをデプロイします。

SageMaker 推論エンドポイントを構築するには、ノートブックのステップを踏んで推論を構築・テストし、インターフェースエンドポイントでデプロイします。

OR-Tools は、少なくともルートに含まれる少数のアイテムを扱う場合は、学習フェーズを必要としません。ランダムな初期化を考慮して最適なルートの探索を開始することができるので、デプロイする準備ができている SageMaker モデルを構築することができます。コンテナと学習フェーズで生成された初期重み（この例では空のファイル）を使用したアルゴリズムを SageMaker に提供するだけです。

SageMaker モデルの構築

アルゴリズムを含むコンテナをセットアップするために、「use-your-own-script」アプローチを使用します。このアプローチは、Tensorflow、Pythorch、Mxnet、SKLearn といった一般的なフレームワークのために Amazon が用意した既存のコンテナを活用するもので、アルゴリズムとライブラリのリストを含む追加ファイル（requirements.txt）を含むカスタムスクリプトを渡します。

この例では、SKLearn コンテナを使用する予定です。今回はルート最適化問題で事前に定義された初期条件を使用する必要はなく、トレーニングフェーズを実行する必要もないため、ダミーのトレーニング出力ファイルを構築して Amazon Simple Storage Service (Amazon S3) にアップロードし、SKLearnModel オブジェクトを呼び出してモデルを構築します。

from sagemaker.serverless import ServerlessInferenceConfig
from sagemaker.serializers import JSONSerializer
from sagemaker.deserializers import JSONDeserializer

# Create an empty ServerlessInferenceConfig object to use default values
serverless_config =  ServerlessInferenceConfig(
          memory_size_in_mb=4096,
          max_concurrency=10)

predictor=sklearn_preprocessor.deploy(
    serverless_inference_config=serverless_config,
    serializer=JSONSerializer(content_type='application/json'),
    deserializer=JSONDeserializer(accept='application/json'))

SageMaker モデルのデプロイ

モデルの準備ができたら、SageMaker Serverless Inference のエンドポイントをデプロイし、そのために割り当てるメモリの量とサポートできる最大同時呼び出し数についての情報をセットします。また、エンドポイントでは入出力のデータ形式として json を使用するようにします。

from sagemaker.serverless import ServerlessInferenceConfig
from sagemaker.serializers import JSONSerializer
from sagemaker.deserializers import JSONDeserializer

# Create an empty ServerlessInferenceConfig object to use default values
serverless_config =  ServerlessInferenceConfig(
          memory_size_in_mb=4096,
          max_concurrency=10)

predictor=sklearn_preprocessor.deploy(
    serverless_inference_config=serverless_config,
    serializer=JSONSerializer(content_type='application/json'),
    deserializer=JSONDeserializer(accept='application/json'))

アルゴリズムのテスト

フロントエンドのアプリケーションでアルゴリズムを使用する準備が整いました。デプロイする前にテストしてみましょう。SageMaker に Amazon Location の実行を指示し、結果を可視化するためのテストデータを生成するつもりです。最初の CloudFormation スタックが作成した Amazon Location ルート計算機と Amazon Location マップリソースを使用します。次のコードのスニペットは、スタック出力からこの情報を自動的に取得するものです。

import time
cf=boto3.client ('CloudFormation')
stackName='provalocation'
response = cf.describe_stacks( StackName=stackName) 

while response['Stacks'][0]['StackStatus'] == 'CREATE_IN_PROGRESS':
    time.sleep(10)
    response = cf.describe_stacks( StackName=stackName) 
    print (response['Stacks'][0]['StackStatus'])
response['Stacks'][0]['StackStatus']   
for output in response['Stacks'][0]['Outputs']:
    if output['OutputKey']=='CalculatorName':
        locationCalculatorName=output['OutputValue']
    if output['OutputKey']=='MapName':
        locationMapName=output['OutputValue']

これで、Amazon Location を使用してルートマトリックスを取得する準備が整いました。トラックの大きさ、狭い道を通らないようにすること、重量などの属性を指定することができます。すべてのポイントは、ルートマトリックス内のホップの始点と終点になる予定です。

location=boto3.client('location')
response=location.calculate_route_matrix(
  CalculatorName= locationCalculatorName,
  DepartNow= True,
  DistanceUnit= "Kilometers",
  TravelMode= "Truck",
  TruckModeOptions= {
    'AvoidFerries': True,
    'AvoidTolls': True,
    'Dimensions': {
      'Height': 3.5,
      'Length': 4.95,
      'Unit': "Meters",
      'Width': 1.9,
    },
    'Weight': {
      'Total': 4500,
      'Unit': "Kilograms",
    },
   },
  DeparturePositions=PointOfInterest,
  DestinationPositions=PointOfInterest)

出力から関連するデータを抽出し、マトリックス形式にすると、以下のような結果になります：

array([
  [0, 0.812, 0.731, 0.679],
  [0.824, 0, 0.674, 0.622],
  [0.787, 0.718, 0, 0.263],
  [0.88, 0.963, 1.09, 0],
]);

地点 0 から地点 3 への距離は 0.67 km、地点 3 から地点 0 への距離は 0.88 kmです。この行列を最適化アルゴリズムを用いることで最適なルートを求めることができます。

data = {}
data['distance_matrix'] = DistanceMatrix.tolist()
data['num_vehicles'] = 1
data['depot'] = 0
data['vehicle_capacities']=[20]

最適化アルゴリズムを適用すると次のような結果が得られます： [[0, 3, 2, 1, 0]].

これは 1 つのアイテムの配列です。ルートは 1 本の線路に最適化するようリクエストしたわけですが、出力の結果は、地点 0 地点から地点 3、地点 2、地点 1 地点を通って、地点 0 に戻るというものです。

各ポイントを表す数値は、GPS 座標に変換し直して、地図上に表示することができます。

図 10：ルーティング最適化の出力を示す Amazon Location Service マップリソース

外部サービスからSageMaker エンドポイントを利用

ゴミ置き場の位置のリストを入力として受け取り、最適化されたルートを地図上にプロットするために必要な情報を返すサービスを公開するのに役立つ REST API を実装します。アーキテクチャは図 11 のようになります。

図 11： REST API アーキテクチャ

Lambda 関数は、ルートマトリックスを計算するために Amazon Location を呼び出し、SageMaker エンドポイントを呼び出してルート最適化を実行します。SageMaker が結果を返すと、Lambda 関数はルートジオメトリを計算し、呼び出し元にレスポンスを返す API Gateway に転送します。
Lambda 関数が行っていることを詳しく説明すると、このようになります。

Webアプリケーションから渡されたパラメータを起点にルートマトリクスを計算します。

Lambda 関数は AWS SDK for JavaScript V3 を使用し、ブラウザから渡されたパラメータからルート行列を計算し、matrixParams 変数に格納されます。

try {
      const client = new LocationClient({region: region});
      const command = new CalculateRouteMatrixCommand(matrixParams);
      const routeMatrix = await client.send(command);
      …
     }
catch (err){...}

matrixParams は、ルートマトリックスを計算するためのすべての関連情報を含む Web アプリケーションから送信される JSON オブジェクトです。

const options = {
  DepartNow: true,
  IncludeLegGeometry: true,
  DistanceUnit: "Kilometers",
  TravelMode: "Truck",
  TruckModeOptions: {
    AvoidFerries: true,
    AvoidTolls: true,
    Dimensions: {
      Height: 2.5,
      Length: 4.95,
      Unit: "Meters",
      Width: 1.8,
    },
    Weight: {
      Total: 1000,
      Unit: "Kilograms",
    },
  },
  DeparturePositions: [],
  DestinationPositions: [],
};

DeparturePositions は、トラックの経度、緯度の配列であり、DestinationPositions は、すべてのゴミ置き場の座標を有する行列である。

ルート設定、出発時刻、トラックの寸法など、利用可能なすべてのオプションのリストはここを確認してください。

SageMaker エンドポイントに手順 1 で取得したルートマトリックスを渡し、最適なルートを取得します。

const client = new SageMakerRuntimeClient({ region: region });
const command = new InvokeEndpointCommand(input);
const data = await client.send(command);
var optimal = new TextDecoder().decode(data.Body);

Lambda 関数は Amazon Locationを呼び出して、手順 2 で取得した最適なルートからジオメトリを取得し、それを Web アプリに渡します。

以下は、CalculateRouteCommand を呼び出し、単一ルートのジオメトリを取得するコードです。

const client = new LocationClient({region: region});
const command = new CalculateRouteCommand(matrixParams);
const leg = await client.send(command);

Lambda 関数が Amazon Location と SageMaker を呼び出すには、IAM ロールが必要です。

API Gateway、Lambda 関数、関連ロールをデプロイするには、apigateway_ template.yaml CloudFormation テンプレートを使用します。

この 2 番目の CloudFormation テンプレートをデプロイするには、setup_environment.yaml と同じ手順を実行します。以下を指定する必要があるパラメータです。

1. - 2 つ目のテンプレート名：LocationServiceDemoBackend
  - SageMaker エンドポイント名：Jupyter ノートブックから取得できます。ノートブックには、predictor.endpoint_name を実行することでエンドポイントの名前を表示するセルが用意されています。
  - Amazon Loaction へのアクセスに使用する IAM ポリシー名：環境のセットアップに使用した setup_environment.yaml CloudFormation テンプレートの出力から取得することができます。
  - Lambda 関数で使用する Amazon Location Service ルート計算機名：環境のセットアップに使用した CloudFormation テンプレート setup_environment.yaml の出力から取得できます。

CloudFormation テンプレートのデプロイが完了したら、その出力から以下の値を取得できます。これらの値は Web アプリケーションで使用されます。

1. - REST API の URL
  - Web アプリケーションが使用している Amazon Cognito Identity Pool ID、UserPoolID、AppClientIDWeb

Web アプリケーションの構築

SageMaker 推論エンドポイントから公開される最適化アルゴリズムを使用する Web アプリケーションを構築します。Web アプリケーションは React を使用し、Amplify JavaScript Library とAmazon Location を利用して、Web ページ上に地図を表示させます。
Amplifyは、フルスタックアプリを構築するためのいくつかのプロダクトを提供しています。

1. - Amplify CLI – 必要なサービスをセットアップするためのシンプルなコマンドラインインターフェイスです。
  - Amplify Libraries – フロントエンドのコードとバックエンドを統合するためのケースセントリックなクライアントライブラリを使用します。
  - Amplify UI Components– React、React Native、Angular、Vue、Flutter 用の UI ライブラリです。

この例では、CloudFormation テンプレートで必要なサービスをすべて作成済みなので、Amplify CLI は使用せず、Amplify JavaScript Library のみを使用することにします。

クライアントコードは、GitHubリポジトリからダウンロードできます、

リポジトリでは、各サービスのエンドポイントに関する正しい情報を提供するために、CloudFormation スタックの出力から収集した情報で aws-exports.js.template を修正し、aws-exports.js として保存する必要があります。

必要な情報は以下の通りです。

1. - aws_project_region と aws_cognito_region：CloudFormation テンプレートを実行するリージョン（例：us-east-1）
  - aws_cognito_identity_pool_id、aws_user_pools_id、aws_user_pools_web_client_id：apigateway_ template.yaml の出力からこの値を得ることができます。
  - Geo セクション：
    - region：上記と同じリージョン
    - default：setup_environment.yaml CloudFormation テンプレートの出力に記載されています。
  - API セクション：
    - endpoint：apigateway_template.yaml の出力に記載されている API Gatweway の URL

Web アプリを実行する準備ができました。

npm install
npm run build
npm run start

完了したら、ブラウザで以下の URL にアクセスしてください。
http://localhost:8080
そして、楽しんでください！

後片付け

本記事で作成したすべてのリソースを削除するために、SageMaker ノートブックの最後に記載されている手順に従って、2 つの CloudFormation テンプレートを削除してください。

まとめ

本記事では AWS サービスを活用して複雑な問題を解決する方法を紹介しました。このソリューションは、最適化アルゴリズムが現在小さな問題に対してリアルタイムで回答しているため、本番環境で使用したり、膨大な数のトラックやゴミ置き場を処理したりすることには向いていません。実際は数万個のゴミ置き場が街中に分散しているような場合、最適化アルゴリズムは非同期バッチプロセスで実行されるはずです。

AWS は堅牢でよく設計されたソリューションを可能にし、お客様は位置情報と機械学習ベースの技術を組み合わせて最適なルートを決定し、予測される需要と容量のバランスをとり、道路上の生産性を向上させることができます。

ゴミ収集、フィールドサービスのルート計画、商品配送の自動化と最適化の準備が整ったなら AWS は重要な課題を克服して業務を改善するための支援を提供します。

本記事は、Optimize waste collection with Amazon Location Service and SageMaker を翻訳したものです。翻訳はソリューションアーキテクトの稲田大陸が担当しました。

Amazon Web Services ブログ