私のブックマーク
物流から始める組合せ最適化
近藤 愛(沖電気工業株式会社)
1. はじめに
物流業界は,組合せ最適化の代表的な応用分野の一つである.配送計画,拠点配置,荷物の積載方法など,さまざまな問題を対象として盛んに研究が行われている.
従来,中小企業の多い物流業界では,IT化が遅れていると指摘されてきた.しかし近年では,法改正や人手不足などを背景とする,いわゆる「2024年問題」を契機として,業務の属人化の解消や業務効率の向上を目的としたシステム導入が進んでいる.
本稿では,物流関連の最適化問題の中でも代表的な組合せ最適化問題である配送計画問題( Vehicle Routing Problem:VRP)を入口として,そのさまざまなバリエーション,実装のアプローチ,関連するコミュニティなどを紹介する.
2. 代表的な問題
2・1 配送計画問題
物流の組合せ最適化というと,まず巡回セールスマン問題(Traveling Salesman Problem:TSP)や VPRを思い浮かべる方が多いだろう.
実際,TSPは最も基本的な経路最適化問題として広く知られており,これを出発点として,複数車両への拡張,時間窓制約の導入,車両容量制約の追加など,現実の配送業務に近い問題へと自然に拡張されてきた.
以下に,実務上必要な制約を追加したいくつかの問題を示す.
- 配送計画問題( VRP):車両への顧客割当てと配送先への訪問順序を同時に決定し,総走行距離や輸送コストの最小化を目的とする問題.
- 容量制約付き配送計画問題(Capacitated Vehicle Routing Problem:CVRP):車両ごとの容量制約をもつ VPR.
- Laporte, G., Nobert, Y. and Desrochers, M.: Optimal routing under capacity and distance restrictions, Operations Research,Vol. 33, No. 5, pp. 1050-1073(1985)
- 車両容量制約を考慮した古典的な VRPに対し,数理最適化に基づく厳密解法を提案し,CVRP研究の基盤を築いた.
- Laporte, G., Nobert, Y. and Desrochers, M.: Optimal routing under capacity and distance restrictions, Operations Research,Vol. 33, No. 5, pp. 1050-1073(1985)
- 時間窓制約付き配送計画問題(Vehicle Routing Problem with Time Windows:VRPTW):各顧客の訪問可能時間帯(時間窓)が決まっている VPR.
- Solomon, M. M.: Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research,Vol. 35, No. 2, pp.254-265(1987)VRPTWを体系的に定式化し,現在でも広く利用されるベンチマーク問題および挿入法ヒューリスティクスを提案している.
- Solomon, M. M.: Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research,Vol. 35, No. 2, pp.254-265(1987)
- 分割配送可能な配送計画問題(Split Delivery Vehicle Routing Problem:SDVRP):1顧客への配送を複数車両に分割できる VPR.
- Dror, M. and Trudeau, P.: Split delivery routing, Naval Research Logistics, Vol. 37, No. 3, pp. 383-402(1990)
- 顧客需要を複数車両で分担可能とする SDVRPを提案し,配送距離や必要車両数の削減効果を実証している.
- Dror, M. and Trudeau, P.: Split delivery routing, Naval Research Logistics, Vol. 37, No. 3, pp. 383-402(1990)
- 集荷配送計画問題(Vehicle Routing Problem with Pickup and Delivery:VRPPD):1車両で集荷と配送の両方を扱える VPR.
- Savelsbergh, M. W. P. and Sol, M.: The general pickup and delivery problem, Transportation Science, Vol.29, No. 1, pp.17-29(1995)
- 集荷地点と配送地点の対応関係を考慮する配送問題を体系化し,Pickup and Delivery問題群の基本的枠組みを整理している.
- Savelsbergh, M. W. P. and Sol, M.: The general pickup and delivery problem, Transportation Science, Vol.29, No. 1, pp.17-29(1995)
2・2 不確実性をはらむ配送計画問題
一般的な VPRでは,需要量や移動時間などの情報が既知であることを前提としている.しかし実際の物流現場では,需要予測の誤差,交通渋滞,荷待ち時間,配送依頼の追加・変更など,不確実な要因が数多く存在する.このような環境下で効率的な配送を実現するため,不確実性を考慮した問題や,運行中の情報変化に応じて計画を更新する問題が研究されている.代表的なアプローチとして以下が挙げられる.
- 確率的配送計画問題( Stochastic VRP):顧客需要や移動時間などを確率変数として扱い,不確実性を考慮した配送計画手法.
- ロバスト最適化:需要分布を明示的に仮定せず,最悪ケースに対して頑健な配送計画を求める手法.
- 動的配送計画問題(Dynamic VRP):配送要求や交通状況が運行中に変化する環境を対象とし,リアルタイムな経路更新を行う.
2・3 その他の問題
- 施設配置問題( Facility Location Problem:FLP):倉庫や工場,通信基地などの施設の配置を決定する問題.物流分野では,倉庫や配送センターなどの物流拠点の配置を対象とすることが多い.
- マルチエージェント経路計画( Multi-Agent Path Finding:MAPF):複数のエージェントが衝突することなく,目的地まで効率的に移動する経路を求める問題.物流分野では,倉庫内を走行する搬送ロボットを対象とすることが多い.
- オーダーピッキング問題(Order Picking Problem:OPP):倉庫内での商品回収順序や作業者経路を最適化する問題.EC物流における主要な研究テーマの一つ.
3. 実装のアプローチ
組合せ最適化の研究や実務では,問題の定式化そのものに加えて,それをどのような手法で実装するかが重要になる.特に物流のように制約が多く,問題設定が現場ごとに異なる分野では,まず既存のソルバでどこまで解けるかを試し,必要に応じてモデルをつくり替えたり,アプローチを変えたりすることが多い.以下では,その入口として役立つ代表的な選択肢を挙げる.
3・1 オープンソースソルバ
線形計画(Linear Programming:LP),整数計画(Integer Programming:IP),混合整数計画(Mixed Integer Programming:MIP)などを解く手段の一つである.物流最適化で現れる経路問題や配車問題の多くは混合整数計画問題として定式化できるため,まずはソルバによる定式化・求解を試みることが多い.
研究・試作段階では,オープンソースソルバも有力な選択肢となる.商用ソルバと比較すると,大規模な整数計画問題における求解性能や利用できる機能に差がある場合もあるが,近年では高性能なオープンソースソルバも数多く登場している.
- SCIP一部の非線形問題も扱える高性能ソルバ.分枝カット法などの高度なアルゴリズムを実装し,研究用途での評価も高い.
- HiGHSLP,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 ヒューリスティクス
実務の物流問題では,変数や制約が増えるほどモデルが大きくなり,実用的な時間で厳密解を得ることが難しくなる.また現場では,時間をかけて得られる厳密解よりも,短時間で得られる近似解のほうが価値をもつ場合も少なくない.
このような場合に利用されるのがヒューリスティクスである.ヒューリスティクスは,問題の構造やドメイン知識を利用して,近似解を高速に求める手法の総称である.物流最適化では以下のような手法が広く利用されている.
- 貪欲法( Greedy Method):近い顧客から順に訪問するなど,各時点で最も評価の高い選択を繰り返して解を構築する手法.
- セービング法( Savings Method):個別につくられた経路を,統合によるコスト削減量が大きい順に結合して解を構築する手法.
- 挿入法( Insertion Heuristics):つくりかけの解に対して,評価値が良くなる位置を選んで顧客を挿入し,解を構築する手法.
- 局所探索法( Local Search):現在の解の周辺の近傍解を調べ,より良い解が見つかればそこへ移動することを繰り返して解を改善する手法.
3・4 メタヒューリスティクス
ヒューリスティクスが問題ごとに設計された近似解法であるのに対し,メタヒューリスティクスは幅広い組合せ最適化問題に適用可能な汎用の探索手法である.
多くの場合,まず初期解を生成し,その後に近傍探索や確率的な操作によって探索範囲を広げながら解を改善する.物流最適化の分野では,100以上の配送先をもつ VPRなど,厳密解法では扱えない大規模問題に対して広く利用されている.
代表的な手法として以下が挙げられる.
- 焼きなまし法(Simulated Annealing):探索中に一時的な改悪を許容することで,局所最適解からの脱出を図る手法.
- タブーサーチ( Tabu Search):探索履歴を利用して同じ解への戻りを防ぎながら探索する手法であり,VRP分野で特に広く利用されている.
- 遺伝的アルゴリズム(Genetic Algorithm):解を染色体として表現し,交叉や突然変異を繰り返して解を進化させる手法.
4. 発展的なアプローチ
物流最適化の実務では,ヒューリスティクスやメタヒューリスティクスを活用したシステムが広く利用されている.一方で,近年は計算機性能や機械学習技術の発展に伴い,従来とは異なるアプローチも活発に研究されている.本節では,現時点では研究段階であるものの,今後の発展が期待されるアプローチについて紹介する.
4・1 強化学習の活用
近年では,強化学習を用いて組合せ最適化を解こうとする研究も活発化している.
強化学習では,配送順序の決定や車両の割当てを逐次的な意思決定問題として捉え,試行錯誤を通じて方策を学習する.特に深層学習と組み合わせた手法により,TSPや VRPを対象とした研究が数多く提案されている.
- Bello, I., Pham, H., Le, Q. V., Norouzi, M. and Bengio, S.: Neural combinatorial optimization with reinforcement learning, arXiv preprint arXiv:1611.09940(2016)
- 強化学習を用いて TSPを解く先駆的研究であり,組合せ最適化への深層強化学習応用の契機となった.
- Nazari, M., Oroojlooy, A., Snyder, L. V. and Takáč, M.: Reinforcement learning for solving the vehicle routing problem, Advances in Neural Information Processing Systems,Vol. 31, pp.9839-9849(2018)
- 対象の問題を VRPに拡張し,エンドツーエンドで解を生成する手法を提案している.
- Kool, W., van Hoof, H. and Welling, M.: Attention, learn to solve routing problems!, Int. Conf. on Learning Representations(2019)
- Attention機構の導入により,TSP・VRPなどの解品質を向上させた.
4・2 量子アニーリング
量子アニーリングは,組合せ最適化問題をイジングモデルや QUBO(Quadratic Unconstrained Binary Optimization)形式へ変換し,量子技術を利用して良好な解を探索する計算手法である.
物流分野では配送計画などを対象とした研究が進められている.しかし現時点では,取り扱える問題規模や制約表現に一定の制約があり,大規模な実務問題を単独で解くよりも,古典的な最適化手法と組み合わせたハイブリッドアプローチとしての活用が期待されている.
- Kadowaki, T. and Nishimori, H.: Quantum annealing in the transverse ising model, Physics. Rev. E, Vol. 58,No. 5, pp.5355-5363(1998)
- 量子アニーリングを提案した先駆的研究.
- Lucas, A.: Ising formulations of many NP problems, Frontiers in Physics,Vol. 2, Article5(2014)TSP問題や最大カット問題など,多数の NP困難問題をイジングモデルとして定式化する方法を体系的に整理している.
- Abel, S., Constantin, A. and Nutricati, L. A.: Quantum annealing: Optimisation, sampling, and many-body dynamics, arXiv preprint arXiv:2605.06857(2026)
- 量子アニーリングの理論から応用までを俯瞰したサーベイ論文.
4・3 ブラックボックス最適化
これまで紹介した数理最適化手法では,解の良し悪しを評価する目的関数を数式として明示的に記述できることを前提としている.しかし実際の物流業務では,担当者の経験や勘に基づいた意思決定が行われている場合も多く,「何が良い計画なのか」を明確な数式として表現できないことも少なくない.
このような状況では,シミュレーションや実績データを用いて解を評価しながら探索を行うブラックボックス最適化が有効となる.代表的な手法としてベイズ最適化や進化計算が知られており,物流シミュレータと組み合わせた運用パラメータの調整や,経験則のモデル化などに活用されている.
- Jones, D. R., Schonlau, M. and Welch, W. J.: Efficient global optimization of expensive black-box functions, J. of Global Optimization,Vol. 13, No. 4, pp.455-492(1998)
- ベイズ最適化の代表的な古典論文であり,高コストな評価関数を少ない試行回数で最適化する枠組みを提案している.
- Jiang, H., Ai, C., Wang, C., Xiang, X. and Zhang, X.: A surrogate-assisted bi-level evolutionary algorithm for multi-depot vehicle routing problems with uncertain demand, IEEE Trans. on Intelligent Transportation Systems,Vol. 26, No. 10, pp.16854-16868(2025)
- サロゲートモデルを用いたブラックボックス最適化を,需要が不確実な複数デポの VRPに適用している.
- Nadi, A., Yorke-Smith, N., Snelder, M., Van Lint, J. W. C. and Tavasszy, L.: Data-driven preference-based routing and scheduling for activity-based freight transport modelling, Transportation Research Part C: Emerging Technologies,Vol. 158,104413(2024)ベイズ最適化を用いて目的関数パラメータを調整し,ソルバが生成する計画と現場担当者が好む計画の一致度を高める手法を提案している.
5. ベンチマーク問題とデータセット
物流最適化の分野には長年利用されているベンチマーク問題があり,多くの論文でこれらのベンチマークに対する結果が報告されている.近年では,アルゴリズムの再現性向上や公平な性能比較を目的として,問題インスタンスや既知の最良解をまとめたサイトも整備されている.
- TSP 系
- TSPLIBTSPの代表的ベンチマーク集.
- TSPLIB
- VRP 系
- VRPTW系
- Solomon benchmarkVRPTWの最もメジャーなベンチマーク集.顧客分布の特徴(疎密など)に応じて分類されている.
- Gehring & Homberger benchmarkSolomon benchmarkを大規模化したベンチマーク集.
- Solomon benchmark
- 積載・倉庫問題系
- OR-Libraryビンパッキング問題やナップサック問題をはじめ,多数の問題のベンチマークを収録している.
- OR-Library
6. 参考メディア
組合せ最適化や数理最適化を学ぶ際に参考となる書籍,Webサイト,コミュニティを紹介する.
- 梅谷俊治:しっかり学ぶ数理最適化モデルからアルゴリズムまで,pp.368,講談社(2020)数理最適化の入門書として評価の高い書籍であり,線形計画問題や整数計画問題の定式化から代表的な求解アルゴリズムまで体系的に学ぶことができる.
- Python言語による実務で使える 100+の最適化問題配送計画やスケジューリングなど,実務で現れる多様な最適化問題の定式化例と実装例が公開されており,実践的な学習に適している.本 Webページの作者の著書(久保幹雄:Pythonによる実務で役立つ最適化問題 100+(1),同(2),同(3),朝倉書店(2022)と対応しており,書籍を購入すると追加のプログラム集をダウンロードできる.
- 数理最適化用語集NTTデータ数理システムが提供している用語集.問題や手法名だけでなく,「求解」「実行不可能」などの最適化用語や,「ポートフォリオ」「ロジスティクス」といった業界用語も紹介されている.
- Google OR-ToolsVRPなどの解説や実装例が豊富に提供されている.
- Casual Optimization数理最適化コミュニティによる勉強会.研究者と実務家の双方が最新の研究成果や実装事例を共有している.
7. 関連学会・研究コミュニティ
物流最適化は,物流,OR,交通工学,機械学習など複数の研究分野にまたがるテーマである.ここでは,本分野の研究動向を把握するうえで参考となるコミュニティ・論文誌を紹介する.
7・1 国内学会
- 日本オペレーションズ・リサーチ学会OR分野を幅広く扱う国内最大級の学会.物流最適化やサプライチェーン最適化に関する研究発表も多い.
- スケジューリング学会生産計画,勤務シフト作成,プロジェクト管理,配送計画など,スケジューリング問題を中心に扱う学会.理論研究から実務応用まで幅広く議論されている.
- 日本物流学会物流・ロジスティクス・サプライチェーンマネジメントを対象とする学会.物流 DXや配送効率化,倉庫運営,物流政策など実務寄りの話題が多く扱われる.
- 土木学会物流最適化そのものを主題とする発表は多くないが,交通流や交通ネットワークを考慮した配送計画研究と関連が深い.
- 人工知能学会本学会全国大会においても,2025年よりオーガナイズドセッション「数理最適化」が開催されており,機械学習と最適化の融合や最適化の実応用に関する発表が行われている.
7・2 主要な国際会議・論文誌
§1 OR・数理最適化分野
§2 物流・交通分野
8. おわりに
本稿では,物流業界の代表的な組合せ最適化問題を皮切りに,問題のバリエーション,実装のアプローチ,関連するコミュニティなどを紹介した.
物流業務向けの最適化ツールはさまざまなものが存在するが,実務者にヒアリングすると,既製ツールの活用が困難であるという声も聞かれる.企業や顧客ごとに独自の業務ルールや商習慣が存在し,制約条件や目的関数が用意された問題の枠に当てはまらないためである.見方を変えると,現場は新しい問題の宝庫であるともいえる.
このような声を拾い上げ,問題設定や求解手段を現場に近づけていくことで,より多くの物流企業の業務改善に貢献できると考える.
本稿に記載されている会社名,商品名は一般に各社の商標または登録商標です.
9. 謝辞
本稿を執筆する貴重な機会を与えてくださった編集委員会の皆様に,心より感謝申し上げます.