【記事更新】私のブックマーク「物流から始める組合せ最適化」


私のブックマーク

物流から始める組合せ最適化

近藤 愛(沖電気工業株式会社)

1. はじめに

 物流業界は,組合せ最適化の代表的な応用分野の一つである.配送計画,拠点配置,荷物の積載方法など,さまざまな問題を対象として盛んに研究が行われている.
 従来,中小企業の多い物流業界では,IT化が遅れていると指摘されてきた.しかし近年では,法改正や人手不足などを背景とする,いわゆる「2024年問題」を契機として,業務の属人化の解消や業務効率の向上を目的としたシステム導入が進んでいる.
 本稿では,物流関連の最適化問題の中でも代表的な組合せ最適化問題である配送計画問題( Vehicle Routing Problem:VRP)を入口として,そのさまざまなバリエーション,実装のアプローチ,関連するコミュニティなどを紹介する.

2. 代表的な問題

2・1 配送計画問題

 物流の組合せ最適化というと,まず巡回セールスマン問題(Traveling Salesman Problem:TSP)や VPRを思い浮かべる方が多いだろう.
 実際,TSPは最も基本的な経路最適化問題として広く知られており,これを出発点として,複数車両への拡張,時間窓制約の導入,車両容量制約の追加など,現実の配送業務に近い問題へと自然に拡張されてきた.
 以下に,実務上必要な制約を追加したいくつかの問題を示す.

2・2 不確実性をはらむ配送計画問題

 一般的な VPRでは,需要量や移動時間などの情報が既知であることを前提としている.しかし実際の物流現場では,需要予測の誤差,交通渋滞,荷待ち時間,配送依頼の追加・変更など,不確実な要因が数多く存在する.このような環境下で効率的な配送を実現するため,不確実性を考慮した問題や,運行中の情報変化に応じて計画を更新する問題が研究されている.代表的なアプローチとして以下が挙げられる.

2・3 その他の問題

3. 実装のアプローチ

 組合せ最適化の研究や実務では,問題の定式化そのものに加えて,それをどのような手法で実装するかが重要になる.特に物流のように制約が多く,問題設定が現場ごとに異なる分野では,まず既存のソルバでどこまで解けるかを試し,必要に応じてモデルをつくり替えたり,アプローチを変えたりすることが多い.以下では,その入口として役立つ代表的な選択肢を挙げる.

3・1 オープンソースソルバ

 線形計画(Linear Programming:LP),整数計画(Integer Programming:IP),混合整数計画(Mixed Integer Programming:MIP)などを解く手段の一つである.物流最適化で現れる経路問題や配車問題の多くは混合整数計画問題として定式化できるため,まずはソルバによる定式化・求解を試みることが多い.
 研究・試作段階では,オープンソースソルバも有力な選択肢となる.商用ソルバと比較すると,大規模な整数計画問題における求解性能や利用できる機能に差がある場合もあるが,近年では高性能なオープンソースソルバも数多く登場している.

  • SCIP
    一部の非線形問題も扱える高性能ソルバ.分枝カット法などの高度なアルゴリズムを実装し,研究用途での評価も高い.
  • HiGHS
    LP,MIP向けの高速ソルバであり,近年急速に普及している.大規模 LPを高速に解くことができる.
  • COIN-OR CBC
    オープンソースの MIPソルバとして長年利用されている.
  • Google OR-Tools
    内部で複数のソルバを利用できるライブラリ.特に VRPの求解に強みをもつ.
3・2 商用ソルバ

 LP,IP,MIPなどを高精度に解くことができ,非線形問題にも対応しているものが多い.

  • Gurobi
    最も広く利用されている商用ソルバの一つ.求解性能が非常に高い.
  • IBM ILOG CPLEX
    大規模な実務問題への適用実績が豊富であり,制約プログラミングとの連携も強み.
  • FICO Xpress
    高速な数理最適化エンジンに加え,モデリングや分析機能が充実している.
  • MOSEK
    二次錐計画(Second-Order Cone Programming:SOCP),半正定値計画(Semidefinite Programming: SDP)などの凸最適化問題に強みをもつ.
  • Nuorium Optimizer
    国産の数理最適化ソルバであり,日本企業の業務最適化への適用実績が豊富.
3・3 ヒューリスティクス

 実務の物流問題では,変数や制約が増えるほどモデルが大きくなり,実用的な時間で厳密解を得ることが難しくなる.また現場では,時間をかけて得られる厳密解よりも,短時間で得られる近似解のほうが価値をもつ場合も少なくない.
 このような場合に利用されるのがヒューリスティクスである.ヒューリスティクスは,問題の構造やドメイン知識を利用して,近似解を高速に求める手法の総称である.物流最適化では以下のような手法が広く利用されている.

3・4 メタヒューリスティクス

 ヒューリスティクスが問題ごとに設計された近似解法であるのに対し,メタヒューリスティクスは幅広い組合せ最適化問題に適用可能な汎用の探索手法である.
 多くの場合,まず初期解を生成し,その後に近傍探索や確率的な操作によって探索範囲を広げながら解を改善する.物流最適化の分野では,100以上の配送先をもつ VPRなど,厳密解法では扱えない大規模問題に対して広く利用されている.
 代表的な手法として以下が挙げられる.

4. 発展的なアプローチ

 物流最適化の実務では,ヒューリスティクスやメタヒューリスティクスを活用したシステムが広く利用されている.一方で,近年は計算機性能や機械学習技術の発展に伴い,従来とは異なるアプローチも活発に研究されている.本節では,現時点では研究段階であるものの,今後の発展が期待されるアプローチについて紹介する.

4・1 強化学習の活用

 近年では,強化学習を用いて組合せ最適化を解こうとする研究も活発化している.
 強化学習では,配送順序の決定や車両の割当てを逐次的な意思決定問題として捉え,試行錯誤を通じて方策を学習する.特に深層学習と組み合わせた手法により,TSPや VRPを対象とした研究が数多く提案されている.

4・2 量子アニーリング

 量子アニーリングは,組合せ最適化問題をイジングモデルや QUBO(Quadratic Unconstrained Binary Optimization)形式へ変換し,量子技術を利用して良好な解を探索する計算手法である.
 物流分野では配送計画などを対象とした研究が進められている.しかし現時点では,取り扱える問題規模や制約表現に一定の制約があり,大規模な実務問題を単独で解くよりも,古典的な最適化手法と組み合わせたハイブリッドアプローチとしての活用が期待されている.

4・3 ブラックボックス最適化

 これまで紹介した数理最適化手法では,解の良し悪しを評価する目的関数を数式として明示的に記述できることを前提としている.しかし実際の物流業務では,担当者の経験や勘に基づいた意思決定が行われている場合も多く,「何が良い計画なのか」を明確な数式として表現できないことも少なくない.
 このような状況では,シミュレーションや実績データを用いて解を評価しながら探索を行うブラックボックス最適化が有効となる.代表的な手法としてベイズ最適化や進化計算が知られており,物流シミュレータと組み合わせた運用パラメータの調整や,経験則のモデル化などに活用されている.

5. ベンチマーク問題とデータセット

 物流最適化の分野には長年利用されているベンチマーク問題があり,多くの論文でこれらのベンチマークに対する結果が報告されている.近年では,アルゴリズムの再現性向上や公平な性能比較を目的として,問題インスタンスや既知の最良解をまとめたサイトも整備されている.

  • TSP 系
    • TSPLIB
      TSPの代表的ベンチマーク集.
  • VRP 系
    • CVRPLIB
      CVRPのベンチマーク集.
    • VRP-REP
      多様な VRP派生問題に対する問題インスタンスや最良既知解を提供している.
  • VRPTW系
    • Solomon benchmark
      VRPTWの最もメジャーなベンチマーク集.顧客分布の特徴(疎密など)に応じて分類されている.
    • Gehring & Homberger benchmark
      Solomon benchmarkを大規模化したベンチマーク集.
  • 積載・倉庫問題系
    • OR-Library
      ビンパッキング問題やナップサック問題をはじめ,多数の問題のベンチマークを収録している.

6. 参考メディア

 組合せ最適化や数理最適化を学ぶ際に参考となる書籍,Webサイト,コミュニティを紹介する.

  • 梅谷俊治:しっかり学ぶ数理最適化モデルからアルゴリズムまで,pp.368,講談社(2020)
    数理最適化の入門書として評価の高い書籍であり,線形計画問題や整数計画問題の定式化から代表的な求解アルゴリズムまで体系的に学ぶことができる.
  • Python言語による実務で使える 100+の最適化問題
    配送計画やスケジューリングなど,実務で現れる多様な最適化問題の定式化例と実装例が公開されており,実践的な学習に適している.本 Webページの作者の著書(久保幹雄:Pythonによる実務で役立つ最適化問題 100+(1),同(2),同(3),朝倉書店(2022)と対応しており,書籍を購入すると追加のプログラム集をダウンロードできる.
  • 数理最適化用語集
    NTTデータ数理システムが提供している用語集.問題や手法名だけでなく,「求解」「実行不可能」などの最適化用語や,「ポートフォリオ」「ロジスティクス」といった業界用語も紹介されている.
  • Google OR-Tools
    VRPなどの解説や実装例が豊富に提供されている.
  • Casual Optimization
    数理最適化コミュニティによる勉強会.研究者と実務家の双方が最新の研究成果や実装事例を共有している.

7. 関連学会・研究コミュニティ

 物流最適化は,物流,OR,交通工学,機械学習など複数の研究分野にまたがるテーマである.ここでは,本分野の研究動向を把握するうえで参考となるコミュニティ・論文誌を紹介する.

7・1 国内学会
  • 日本オペレーションズ・リサーチ学会
    OR分野を幅広く扱う国内最大級の学会.物流最適化やサプライチェーン最適化に関する研究発表も多い.
  • スケジューリング学会
    生産計画,勤務シフト作成,プロジェクト管理,配送計画など,スケジューリング問題を中心に扱う学会.理論研究から実務応用まで幅広く議論されている.
  • 日本物流学会
    物流・ロジスティクス・サプライチェーンマネジメントを対象とする学会.物流 DXや配送効率化,倉庫運営,物流政策など実務寄りの話題が多く扱われる.
  • 土木学会
    物流最適化そのものを主題とする発表は多くないが,交通流や交通ネットワークを考慮した配送計画研究と関連が深い.
  • 人工知能学会
    本学会全国大会においても,2025年よりオーガナイズドセッション「数理最適化」が開催されており,機械学習と最適化の融合や最適化の実応用に関する発表が行われている.
7・2 主要な国際会議・論文誌

§1 OR・数理最適化分野

§2 物流・交通分野

8. おわりに

 本稿では,物流業界の代表的な組合せ最適化問題を皮切りに,問題のバリエーション,実装のアプローチ,関連するコミュニティなどを紹介した.
 物流業務向けの最適化ツールはさまざまなものが存在するが,実務者にヒアリングすると,既製ツールの活用が困難であるという声も聞かれる.企業や顧客ごとに独自の業務ルールや商習慣が存在し,制約条件や目的関数が用意された問題の枠に当てはまらないためである.見方を変えると,現場は新しい問題の宝庫であるともいえる.
 このような声を拾い上げ,問題設定や求解手段を現場に近づけていくことで,より多くの物流企業の業務改善に貢献できると考える.
 本稿に記載されている会社名,商品名は一般に各社の商標または登録商標です.

9. 謝辞

 本稿を執筆する貴重な機会を与えてくださった編集委員会の皆様に,心より感謝申し上げます.