ビームサーチ対応バッチ配車アルゴリズムを実装した SAVS バージョン “o-samampe” リリース

高度化されたバッチ配車アルゴリズムを実装した SAVS バージョン “o-samampe(長万部)” をリリースしました。
SAVSで利用する当社独自開発のAI配車アルゴリズムは、1つのデマンド*1 発生に対して即時に配車決定を行うリアルタイム計算方式と、一定期間デマンドを溜めた後、複数のデマンドを一括で配車決定するバッチ計算方式の2つに分類されます。
数年にわたる研究開発と試行錯誤の結果、従来の当社開発バッチ配車アルゴリズムよりも配車計画精度が大きく上回り、応用範囲が拡がる新型のバッチ配車アルゴリズムが完成しましたのでお知らせします。
主な改善点、期待できる効果は以下の3点となります。

1. ビームサーチ導入による配車計画の精度向上

従来のバッチ配車アルゴリズムは、貪欲法により初期解を求め、その初期解を確定的アニーリング法(DA)により改善することで配車計画を求めていました。新たなバッチ配車アルゴリズムでは、初期解を多目的ビームサーチで求めるように改善しました。
この対応により、精度の良い多様な初期解集合を求めることができ、その多様な初期解集合をDAにより改善することで、より最適解に近い配車計画を求めることが可能となります。また、車両台数の最小化、乗客の待ち時間の最小化、乗客の迂回時間の最小化、大型車両への優先配車など、多様なニーズに合わせた配車計画の作成も可能となります。

Deterministic annealing with Greedy search

 

Deterministic annealing with Beam search

2. 車両の運行ルートの精度向上

従来のバッチ配車アルゴリズムは、道路ごとに区別がなく、時間変化のない静的な条件下での配車計算を行っていました。新たなバッチ配車アルゴリズムでは、道路ごとの異なる速度の設定、時刻による道路速度変化、時刻による多種多様な道路規制など、より現実的な地図データを考慮した配車計算を行えるようになりました。
この対応により、実世界における運行状況に近い配車計画の作成、運行ルートの決定が可能となります。

3. リアルタイム運行中の割り当てデマンドの断片化解消

本アルゴリズムの完成により、SAVSのリアルタイム配車計算とバッチ配車計算の親和性が向上しました。
リアルタイム配車運行中には、デマンドキャンセル、遅延の発生など、突発的な事象によるデマンド割り当ての断片化が起こります。この断片化状態のデマンドに対し、定期的な短時間バッチ計算を行うことでデマンドの再配置が可能となり、さらなる車両の有効活用と利用者の利便性向上につながります。

Defragmentation

*1 利用者の移動要求

SAVS バージョン履歴
リリース バージョン 主な追加機能・特徴
2024 o-samampe(長万部) ビームサーチ対応した確定的アニーリング法の導入
2023 yu-rap(遊楽部) 小休止デマンド(ドライバーのひとやすみ時間取得)対応
2022 kaya-un-pe-nupuri(駒ヶ岳) クラウド版シミュレーター、SAVS OS 提供開始
2021 tu-pok-ke(椴法華) 外部有償地図情報(交通規制や渋滞統計等)を利用した配車計算
2020 ye-san(恵山) MaxSAT対応型アルゴリズム 提供、物流・貨客混載利用 開始
2018 toy-o-i(戸井) 確定的アニーリング処理によるバッチ配車計算サービス提供開始
2017 yu-pet(湯の川) API 接続型クラウドプラットフォーム提供開始
2016 us-kes(函館) 未来シェアからのサービス提供開始、東京実験 にて利用
2015 mo-peci(茂辺地) クラウドサービスへ移行、人工知能学会 函館大会 にて実験運行
2013 rir-o-nay(木古内) はこだて未来大学による初回実験、世界初の完全自動・リアルタイム・フルデマンド運行実施
2002 mat-oma-i(松前) 逐次最適挿入法によるマルチエージェント・シミュレーション

関連ニュース

  1. 熊本県天草市栖本町において、栖本地域乗合タクシーの運行を開始…

  2. 栃木県下野市のデマンド交通「おでかけ号」へSAVSが導入され…

  3. 未来シェアとヴァル研究所、MaaS分野で業務提携

  4. R5年度「成長型中小企業等研究開発支援事業(Go-Tech事…

  5. 北海道南幌町にて、SAVSを利用したデマンド交通「あいるーと…

  6. SAV応用サービス第一弾「つばめエアポートリムジン」就航

最近のニュース

PAGE TOP