株式会社NTTデータ数理システム

数理最適化を用いたバス運転者の勤務シフト自動作成（MSI）© 2023DATA
MathematicalSystemsInc.
Inc.
© 2023
NTT NTTDATA
MathematicalSystems自己紹介
かれこれ10年くらい最適化の受託案件を扱ってきました。

© 2023 NTT DATA Mathematical Systems Inc.

2

発表概要
- 遠州鉄道様案件について- 技術者の視点から、案件をどのように進めたか→ 上記踏まえて最適化案件全般について効果を出すためのポイントなどお伝えします。

© 2023 NTT DATA Mathematical Systems Inc.

3

数理計画部の業務概要紹介
パッケージ開発
 Nuorium Optimizer 開発
分析・コンサルティング
 新規案件の要件定義・POC
 分析手段としての最適化計算
受託開発
 計算ツール開発
 DXシステム等の計算エンジン開発© 2023 NTT DATA Mathematical Systems Inc.

4

計算ツール開発について大きく以下3つを開発
 最適化計算エンジン➢ お客様の問題を数理計画問題に定式化
 UI➢ お客様が日常的に使用するツールの設計・開発
 制御プログラム➢ UI と最適化計算エンジンとのデータ連携プログラム© 2023 NTT DATA Mathematical Systems Inc.

5

計算ツール開発の流れ

1. 最適化計算に関する要件定義- 制約条件の洗い出し- 変数・目的関数の定義→ 線形計画問題として記述できるか
2. 最適化計算に関するPOC- 計算できるか- 有効な結果が得られるか
3. UIの要件定義- どのデータを可視化・自動計算するか- ユーザの操作は何か
4. ツール開発

工数振り分け12

最適化計算エンジン

○

◎
△UI

制御プログラム△© 2023 NTT DATA Mathematical Systems Inc.

○34○○

◎

◎
6

「線形計画問題として記述できるか」補足 ソルバーが使えるか➢ 制約条件を変数の一次式で記述できるか• 記述でき、かつ、現実的な時間で計算結果が得られる見込みか→ ソルバーを用いたツール実装の提案• 記述できるが、現実的な時間で計算結果が得られない可能性が高い→ ソルバーを用いたプロトタイプ検証の提案→ 専用アルゴリズム実装の提案• 記述できない→ 専用アルゴリズム実装の提案© 2023 NTT DATA Mathematical Systems Inc.

7

「計算できるか」補足

 Nuorium Optimizer がどの程度適用できる問題であるか➢ 問題全体に適用できそうな場合、計算時間・利用計算資源が実務環境に適うか➢ 問題の一部に適用できそうな場合、適用できない部分を補う方法は何か➢ 適用困難な場合、問題解決の手段があるか、プログラム実装の工数はどの程度か

 要件定義の定式化を基にして、制約条件を記述できるか© 2023 NTT DATA Mathematical Systems Inc.

8

遠州鉄道様案件

シフトスケジュール問題
 「割当て問題」の定式化が基➢ 𝑥𝑝,𝑑,𝑠 ∈ 0,1 : 人 𝑝 の日 𝑑 にシフト 𝑠 を割当てる場合 1、そうでない場合 0 を取る変数➢ Nuorium Optimizer の wcsp-ts アルゴリズムが有効
 実用上必要な制約条件が 𝑥𝑝,𝑑,𝑠 だけでは記述できない➢ 「割当て問題」の定式化を踏まえたうえで、いくつか変数を追加する必要がある• 休日出勤 - 振替休日の対応• etc.

© 2023 NTT DATA Mathematical Systems Inc.

9

数理計画の応用分野とデザインパターン

配合・組立て輸送

選択
１００１順列ネットワーク
分布集約

フィッティング
x+ y+z割り当て© 2023 NTT DATA Mathematical Systems Inc.

10

wcsp-ts アルゴリズム

Nuorium Optimizer では、0-1 変数のみで記述された整数計画問題に対して適用可能なアルゴリズム
暫定解 → 解近傍の定義 → 近傍内のその時点の評価方法でいい感じの解を探索© 2023 NTT DATA Mathematical Systems Inc.

11

自動車運転者の労働時間等の改善のための基準（厚生労働省告示）

2024年3月まで✓ インターバル 8 時間以上
✓ 1 日の拘束時間は原則13時間✓ 1日の拘束時間15時間超は1週間に2回まで✓ 4週間を平均した1週間あたりの拘束時間は 65 時間以下
✓ 4週間を平均した1週間あたりの運転時間は 40 時間以下
✓ etc.

インターバルを 8 時間以上確保し、必要な運行業務を充足させる→ 運行業務のローテーション表を作成し、運転士別で 1 日ずらしながら割当てる© 2023 NTT DATA Mathematical Systems Inc.

12

全体のスケジュール

シス
テム
面の整
備

コンサルティング期間★残課題の整理★最終システム範囲

PoC②★貸切を含めた交番
・貸切仕事など★応用的制約・運転手能力設定＜PoC①＞★簡単な交番作成
・乗合仕事★基本的制約・休暇/教育/会議③課題見直し2021.4~1営業所で実証実験⓪検討開始
2019.12~④システム本開発
2021.7~⑤正式運用の開始
2022.4~
全営業所展開組合と運用ルール協議

3営業所で実証実験②貸切交番
2020.11~①乗合交番
2020.5~

コンサルティング期間★不具合の対応★機能追加の検討

本開発★システム連携★アウトプット★残課題の解決

2営業所で実証実験

プロトタイプログラムで検証いただきました

運営面の整備システム本開発前にUI仕様設計+追加すべき制約の検討を目的とするコンサルティング

「UI 仕様設計」補足
遠州鉄道様でご利用の Excel を基に、以下の拡張を検討
 最適化エンジン開発者として結果から確認したい項目の視覚化・数式化➢ 最適化計算が想定通りの振舞いをしているか• Nuorium Optimizer 内の計算値と Excel 上の計算値と比較• 計算中に許容した制約違反箇所
 UI ユーザとして結果から確認したい項目の視覚化・数式化➢ 不足交番・不足業務➢ 改善基準➢ 交番表と休日出勤・振り替え休日• アルファベットのラベリング© 2023 NTT DATA Mathematical Systems Inc.

14

有効な結果を得るために
 最適化計算のための前処理➢ 固定設定による制約違反箇所を、制約条件の対象外にする➢ 固定設定を踏まえて、探索空間を小さくする アルゴリズムの特徴を踏まえ逐次計算➢ 「wcsp-ts」は大規模データの計算ができるが、局所的に物足りない結果になりがち➢ 「単体法+分枝限定法」は小規模・中規模データに対して、結果が出せる© 2023 NTT DATA Mathematical Systems Inc.

15

最適化ソリューションについて（個人的考察）「最適化計算」は人との距離がひどく遠い ユーザ視点➢ 最適化計算の結果の確認・解釈に時間がかかる• 結果全体の統計値を見て「何となくヨシ」はNG

 技術者視点➢ 最適化計算の結果 ≠ お客様が知りたいこと• お客様の多くは「なぜその結果が得られたか」が知りたいが、明瞭な回答は難しい© 2023 NTT DATA Mathematical Systems Inc.

16

最適化ソリューションについて（個人的考察）つづき
ユーザと技術者の距離もかなり遠い お互いに「業界用語」がある➢ それとない一言が最悪な印象を与えることがある→ ソリューションの提供側として、「如何にしてユーザと最適化結果を近づけるか」が課題である一方、ユーザも最適化計算について歩み寄る必要があります。
解いた後も重要 ツールのメンテナンス体制➢ ルールの変更・増加に耐えられるか➢ データ変更に手間がかかりすぎないか© 2023 NTT DATA Mathematical Systems Inc.

17

© 2023 NTT DATA Mathematical Systems Inc.