数理最適化手法を用いたガス開栓業務差配の自動化事例

Theme（目的）

新たにガスの利用を開始する際にガスメータの開通作業を行う「開栓業務」。最適化手法を用いて作成することで管理者が行う差配の負荷を軽減し、効率的な巡回経路の自動作成を目指す。

Point（内容・効果）

適応的巨大近傍探索（Adaptive Large Neighborhood Search,　ALNS）を実装し、数分程度で作業員への分担案と巡回経路を作成。拠点毎に重視する要素を考慮した差配が可能。

背景

東京ガス株式会社様ではお客さまが新たにガスの利用を開始する際に、ガスメータの開通作業を行う「開栓業務」を実施しています。管理者が開栓業務を作業員に差配していますが、繁忙期では1 日 1,000 件以上を差配することもあります。そのため管理者の業務負荷が問題になっています。また、差配する際には案件の指定時間や地理的な巡回のしやすさ、さらには作業員の資格を考慮するため、効率的な巡回経路を目的とした差配自体が難しいという問題もあります。

次の画像は案件の分担案と巡回経路のイメージです。

業務要件

開栓業務の差配と巡回経路を自動的に作成する上で次の三つの業務要件に対応できる手法を選択する必要があります。

1. 差配で重視する条件が拠点によって異なる。
2. 条件を遵守する度合いが調整できること。
3. 数分程度で分担案と巡回経路が作成されること。

1 については例えば、作業時間の平準化を重視する拠点もあれば、エリアと呼ばれる区分けを重視する拠点もあります。拠点毎に重視する条件が調整可能であることが業務要件の一つとしてありました。2 については繁忙期を想定すると全ての条件を満たすことができないと予想されます。状況に応じて条件を重視する度合いが調整できることが望ましいです。3 について、拠点によっては 1,000 案件以上を差配することもあるため、高速なアルゴリズムの実装が必要になります。 以上から、実際の業務で必要とされる条件を考慮しつつ柔軟で高速なアルゴリズムの実装が求められ、適切なアプローチの選択がとても重要になります。

アプローチ（最適化手法）

作業員の巡回経路を最適化する問題は作業員を車両と見なすことで配車計画問題と見なすことができます。配車計画問題において様々な最適化手法が知られていますが、本取組では業務要件を満たす手法として適応的巨大近傍探索 （Adaptive Large Neighborhood Search, ALNS）を採用しました。

ALNS は配車計画問題において非常に強力な手法です。ALNS の仕組みはシンプルであり、様々な条件に対応できます。また、ヒューリスティクスな手法であることからも非常に高速です。ALNS を用いると各種条件の重要度を「重み」という数値データで考慮することで業務要件 2 を達成できます。1 については拠点毎に好ましい重みを設定することで達成できます。さらに、非常に高速であることから業務要件 3 も達成することができます。配車計画問題における ALNS の詳細については例えば参考文献[1] をご覧ください。

次の画像は条件と重みの関係性のイメージです。

株式会社NTTデータ数理システムではこの ALNS を開栓業務の分担案と巡回経路の作成に用い、手法の開発を行いました。開発した手法は 日本オペレーションズ・リサーチ学会 2024年 秋季研究発表会 で発表しました。[2]

業務への導入と効果

ALNS を採用したプロトタイプツールの作成と現場トライアルを実施し、管理者からのフィードバックを受けながら手法を洗練させていきました。従来では多くの時間が取られていた業務ですが、トライアルでは 1 日あたり 30% ～ 90% の業務時間の削減が見られました。最適化手法を用いた開栓業務の差配を行うシステムへの期待感の高まりと共に、2025 年に本機能を取り込んだシステムが稼働しています。今後は本システムを開栓作業だけではなく他の業務に広げることを目指しています。

参考文献

• David, P. and Stefan R. “A general heuristic for vehicle routing problems”, Computers & Operations Research, Volume 34, Issue 8, Pages 2403-2435.
• 飯野佑樹,土岐爽真,笹谷俊徳,多田明功,石橋保身,佐久間寛人,藤井智仁,“最適化手法を用いた巡回業務分担システムの導入”,日本オペレーションズ・リサーチ学会 2024 年秋季研究発表会.