【T3】物流が数学になった日 ORは物流研究を「経路最適化」でなく「資源配分の最適化」へ変えたのか

本レポートの対象と方法Scope and Method

本稿が検証の対象とするのは、オペレーションズ・リサーチ(OR)が物流に関わる研究へもたらした最適化問題群と、それによって物流研究の対象が変化したか否かである。本稿はORの通史や軍事史を記述することを目的としない。焦点は「ORが物流研究にどのような最適化対象を持ち込んだか」にある。

エビデンスの扱いHandling of Evidence

本稿は、ORの歴史を扱う学会資料(INFORMSなど)、査読論文、大学資料、原著論文の二次的確認を主たる典拠とする。歴史的経緯(OR成立の背景、各問題の定式化年・提唱者)は、二次文献によって繰り返し確認できる事項を中心に記述する。各問題が「何を最適化するか」という定式化は、ORの標準的教科書・解説で広く共有されている事項として扱う。ORが物流研究を「変化させた」か否かの評価的記述は、事実と区別し推論として扱う。アメリカ企業への普及などについては、具体的事例を確認できる範囲で記し、確認できない場合は「不明」とする。

OR以前の輸送研究Transport Research before OR

本章では、第2回の検討を踏まえ、OR登場以前の輸送・経済研究が何を扱っていたかを確認する。ただし「OR以前には限界があった」という後知恵による評価は避け、当時の研究が何を対象としていたかの記述にとどめる。

輸送経済学が扱っていた対象What Transport Economics Addressed

第2回で整理したとおり、輸送経済学には、運賃・料金そのものを分析する系統(デュピュイ以降の運賃理論・公共料金理論)と、輸送費を市場形成・市場統合・経済厚生の文脈で扱う系統(スミス・リカード以来の議論、社会的節約の推計)とが並行して存在していた^[1]。これらの系統に共通するのは、輸送を主として経済理論(価格・需要・厚生・市場)の枠組みで捉える点である。運賃の水準、料金設定の原則、輸送費が市場や成長に与える効果が、中心的な関心であった。

ORの成立The Emergence of OR

本章では、ORがいつ・どのように成立し、何を解決しようとした営みであったかを、確認できる文献に基づいて整理する。物流との関係を論じる前提として、ORそのものの性格を確認することが目的である。

イギリスにおける初期OREarly OR in Britain

ORの歴史を扱う複数の資料は、現代的なORが第二次世界大戦期のイギリスに起源を持つこと、当時それが「Operational Research」と呼ばれたことを記述している^[2][3]。INFORMS(米国OR・経営科学系の専門学会)の歴史資料によれば、近代的なORは1937年、英国のボードジー研究所(Bawdsey Research Station)において、所長 A. P. ロウの主導で始まったとされる。ロウは、英国の早期警戒レーダー網(Chain Home, CH)の運用を分析・改善する手段としてこれを構想した^[3]。当初の対象はレーダー機器とその通信網の運用分析であり、後に運用要員の行動を含むまでに拡張されたとされる^[3]。

物理学者パトリック・ブラケットは、この初期ORの中心人物の一人として複数の資料に記述される。1940年8月、ブラケットは英陸軍の対空司令部(Anti-Aircraft Command)に科学者の研究グループを編成し、その後、空軍沿岸司令部・海軍にもグループを設けたとされる^[2][4]。このグループは「ブラケットのサーカス(Blackett’s circus)」と呼ばれ、生理学者・数理物理学者・天体物理学者・数学者など、多様な専門分野の科学者から構成されていたと記述される^[4]。

ORは何を解決しようとしたかWhat OR Sought to Solve

初期ORが扱った問題について、ある解説資料は、その目的を限られた軍事資源を諸作戦・諸活動へ最も効果的に配分すること(the most effective allocation of limited military resources)と記述している^[4]。具体的な応用例として挙げられるのは、新たに発明されたレーダーの効果的な運用、英空軍機の各任務への割当(allocation of aircraft to missions)、潜水艦を捜索する際の最適な探索パターンの決定などである^[4]。

数理最適化・システム分析・資源配分Mathematical Optimization and Resource Allocation

本章では、ORの方法的な核をなす概念──数理最適化、数学的モデル、システム分析、資源配分──を、確認できる範囲で整理する。これらはORが物流に持ち込んだ枠組みを理解する前提となる。

ORの方法的な核The Methodological Core

ORは、戦後、軍事の文脈から民間(産業・企業・行政)へと応用範囲を広げ、複雑なシステムを分析・最適化するための数学的モデルの開発へと重心を移していったと、複数の資料が記述している^[5]。その方法的な核は、(1)対象とする問題を数学的モデルとして定式化し、(2)目的関数(最小化または最大化すべき量)と制約条件を明示し、(3)その制約のもとで目的関数を最適化する解を求める、という手続きにある。すなわち、ORの特徴は、特定の対象(運賃・在庫・経路など)にあるのではなく、問題を「制約つき最適化」として定式化し解く、という方法にある。

資源配分という関心Resource Allocation as a Concern

前章で見たとおり、初期ORの目的は「限られた資源の効果的な配分」と記述されていた^[4]。この「資源配分」という関心は、戦後の数理計画(mathematical programming)の発展にも引き継がれる。後述する線形計画法は、限られた資源を複数の用途へどう配分すれば目的関数(費用・利潤など)を最適化できるか、という問題を扱う枠組みである。すなわち、ORが扱う最適化は、その出発点から、特定の輸送経路の問題に限定されず、資源を諸用途へ配分する一般的な問題を含んでいた。

線形計画法Linear Programming

本章では、ORの中核的な手法である線形計画法(linear programming, LP)について、その理論的貢献を整理する。プロンプトの指示に従い、人物伝には立ち入らず、理論的内容に焦点を当てる。

線形計画法の定式化The LP Formulation

線形計画法は、線形の制約条件のもとで、線形の目的関数を最大化または最小化する解を求める数学的枠組みである。線形計画の一般的な定式化と、その解法である単体法(simplex method)については、ジョージ・ダンツィークが1947年に定式化し、後に公表したという経緯が、ORの歴史を扱う複数の資料およびダンツィーク自身の歴史的記述によって確認できる^[6]。ダンツィークがこの定式化に取り組んだ動機が、米空軍における計画立案(logistic plans / planning)の困難にあったことも、これらの資料に記述されている^[6][7]。

線形計画における最適化の構造は、決定変数を \( x \)、目的関数の係数を \( c \)、制約を行列 \( A \) とベクトル \( b \) で表すと、次のように書ける。

$$
\min\ c^{\mathsf{T}} x \quad \text{subject to}\quad A x \le b,\ x \ge 0
$$

ここで最適化の対象は、目的関数 \( c^{\mathsf{T}} x \) であり、これは費用・時間・距離など、問題に応じて多様な量を表しうる。すなわち、線形計画法は特定の最適化対象に固有の手法ではなく、制約つき配分問題を一般的に扱う枠組みである。これに先立つカントロヴィチ(1939年)の線形計画の研究は、西側では長く知られなかったとされる^[6]。

動的計画法Dynamic Programming

本章では、ORのもう一つの中核的手法である動的計画法(dynamic programming, DP)について、その理論的内容を整理する。人物伝ではなく理論中心に記述する。

動的計画法と最適性原理DP and the Principle of Optimality

動的計画法は、リチャード・ベルマンが1957年の著書『Dynamic Programming』(Princeton University Press)で体系化し、その分野を命名したとされる^[8][9]。動的計画法は、問題を多段階の意思決定(multi-stage decision process)として捉え、各段階での決定の系列(政策, policy)を最適化する枠組みである。ベルマンが1952年にランド研究所(RAND)に加わったこと、動的計画法の発展が冷戦期の軍事的な文脈(多段階の意思決定問題)を背景に持つことも、複数の資料に記述されている^[9]。

動的計画法の核心は、最適性原理(principle of optimality)と呼ばれる原則にある。ベルマンによる定式化は、二次文献で次のように引用される。「最適政策は、初期状態と初期決定が何であれ、残りの決定が、最初の決定から生じる状態に関して最適政策を構成する、という性質を持つ」^[8]。これは、最適解の部分解がそれ自体、対応する部分問題の最適解になっている、という性質であり、これによって、多段階の問題を後ろ向き(backward)に解くことが可能になる^[8]。

動的計画法の最適化対象What DP Optimizes

動的計画法における最適化の対象は、特定の物理的対象(経路・在庫など)ではなく、多段階にわたる意思決定の系列(政策)である。決定変数は各段階での決定であり、目的関数は最終的な状態に関する評価関数である。動的計画法は、在庫管理、設備更新、経路探索など、多段階の構造を持つ多様な問題に適用される。後述する巡回セールスマン問題に対しても、動的計画法は古典的かつ代表的な厳密解法(ベルマン－ヘルド－カープ型, 計算量 \( O(n^{2} 2^{n}) \))を与える^[10]。ただしこれが「現在知られる最良の解法」であるという含意はなく、その後も理論計算機科学において、改良された指数時間アルゴリズムが多数提案されている^[10]。

四つの古典的問題Four Classical Problems

本章では、ORが定式化した古典的な最適化問題のうち、輸送問題・割当問題・最短経路問題・最大流問題の四つを取り上げ、それぞれが何を最適化する問題か、物流とどう関係するかを整理する。これらは、ORの標準的な教科書で広く扱われる基本的な問題である。

輸送問題Transportation Problem

輸送問題(transportation problem)は、複数の供給地から複数の需要地へ、各経路の単位輸送費を所与として、供給量・需要量の制約のもとで総輸送費を最小化するように輸送量を割り当てる問題である。この問題の定式化に関して、文献は1930年代のトルストイによる先行的検討、ヒッチコックによる1941年の定式化、カントロヴィチ(1939年)の研究、クープマンス(1947年前後)の研究という系譜を記述している^[6][7]。供給地 \( i \) から需要地 \( j \) への単位輸送費を \( c_{ij} \)、輸送量を \( x_{ij} \) とすると、目的関数は次の総輸送費の最小化である。

$$
\min \sum_{i}\sum_{j} c_{ij}\, x_{ij}
$$

物流との関係：輸送問題は、その名のとおり、財をどこからどこへどれだけ運ぶかという、物流の中核的な配分問題を直接に定式化したものである。最適化の対象は「総輸送費」であり、決定変数は各供給地・需要地間の輸送量である。

割当問題Assignment Problem

割当問題(assignment problem)は、複数の作業(またはタスク)を複数の主体(機械・人・車両など)へ一対一で割り当てる際、各割当に伴う費用を所与として、総費用を最小化する割当を求める問題である。輸送問題の特殊な場合(供給・需要がいずれも1単位)として位置づけられる。物流との関係：割当問題は、車両への配送先の割当、荷役設備への作業の割当など、物流における資源と作業の対応づけを最適化する問題に対応する。最適化の対象は「総割当費用」である。

最短経路問題Shortest Path Problem

最短経路問題(shortest path problem)は、ネットワーク上の二点間を結ぶ経路のうち、各辺の費用(距離・時間など)の合計が最小となる経路を求める問題である。物流との関係：最短経路問題は、ある地点から別の地点へ財や車両を移動させる際の経路選択を最適化する問題に対応し、配送計画・輸送計画の基礎をなす。最適化の対象は「経路の総費用(距離・時間)」である。本シリーズの仮説でいう「経路」に最も直接的に対応する問題は、この最短経路問題である。

最大流問題Maximum Flow Problem

最大流問題(maximum flow problem)は、各辺に容量の上限があるネットワークにおいて、始点から終点へ流せる流量を最大化する問題である。物流との関係：最大流問題は、輸送ネットワークの容量制約のもとで、どれだけの量を流せるか(達成可能な最大の流量)を評価・最適化する問題に対応する。最適化の対象は「所与の容量制約下で流せる総流量」であり、容量(輸送能力)そのものを設計・変更する問題ではなく、与えられた容量のもとで実際に流せる量を最大化する問題である点に注意を要する。費用ではなく流量を目的関数とする点で、前三者(いずれも費用の最小化)とは目的が異なる。

巡回セールスマン問題と配車問題TSP and the Vehicle Routing Problem

本章では、巡回セールスマン問題(TSP)と配車問題(車両経路問題, VRP)を取り上げ、それらが物流研究へ与えた影響を整理する。これらは、経路の最適化に直接関わる問題群である。

巡回セールスマン問題The Traveling Salesman Problem

巡回セールスマン問題(Traveling Salesman Problem, TSP)は、複数の地点をすべて一度ずつ訪問して出発地に戻る巡回路のうち、総移動距離(または費用)が最小となるものを求める問題である。TSPは組合せ最適化の代表的な問題として知られ、後述する配車問題の基礎をなす。前章で述べたとおり、動的計画法はTSPに対する古典的かつ代表的な厳密解法の一つであり、その後も多くの改良アルゴリズムが提案されている^[10]。

配車問題(車両経路問題)The Vehicle Routing Problem

配車問題(Vehicle Routing Problem, VRP)は、一つの基地(デポ)から複数の顧客へ車両群で配送する際、各車両の経路と顧客への割当を、総移動距離(または費用)が最小となるように決定する問題である。VRPの起源は、ジョージ・ダンツィークと J. H. ラムザーが1959年に発表した「トラック配送問題(The Truck Dispatching Problem)」とされ、これは Management Science 誌に掲載された^[11]。この問題は、一つのターミナルから多数のガソリンスタンドへ燃料を配送する車両群について、総走行距離を最小化するものであった^[11]。その後、G. クラークと J. W. ライトが1964年にこれを拡張し、容量の異なる車両群で多数の顧客に配送する一般的な問題(現在 VRP と呼ばれる)へと展開したとされる^[11]。VRPは巡回セールスマン問題の一般化として位置づけられ、ORで最も広く研究された組合せ最適化問題の一つとされる^[11]。

物流研究への影響Impact on Logistics Research

TSPとVRPは、配送計画という物流に固有の問題を、明示的な数理最適化問題として定式化したものである。とりわけVRPは、ガソリン配送という具体的な物流問題から出発し^[11]、その後、時間枠・容量・複数デポなど現実の制約を取り込む多数の変種へと展開し、ORの一大研究領域を形成した^[11]。この点で、TSP・VRPは、ORが物流研究へ「経路・配送の最適化」という対象を持ち込んだことを示す直接的な例である。

アメリカ企業への普及Diffusion to U.S. Industry

本章では、ORが軍事から民間(アメリカ企業)へ普及し、生産管理・輸送計画・配送計画にどう応用されたかを、確認できる範囲で整理する。

軍事から産業への展開From Military to Industry

ORの歴史を扱う資料は、英国でのORの成功を受けて米国が防衛ORを拡大したこと、戦後にORの技術が企業・産業・社会の問題へより広く適用されたこと、その過程でORが複雑なシステムを分析・最適化する数学的モデルの開発へと重心を移したことを記述している^[5]。ORは、戦後、石油化学・航空・金融・物流・行政など多様な産業で用いられる分野へと拡大したとされる^[5]。

物流分野への応用Application to Logistics

物流に関わる応用として、前章までに見たVRPの起源(1959年のガソリン配送問題)は、ORが企業の配送計画という具体的な問題に適用された確認できる事例である^[11]。一方、ORが生産管理・輸送計画・配送計画の各領域で、いつ・どの企業に・どの程度普及したかについての体系的・定量的な記述は、本稿が参照しえた資料の範囲では十分に確認できなかった。したがって、アメリカ企業への普及の全体像(普及率・時期・代表的事例の網羅)については、本稿では「十分なエビデンスが見当たらない」とせざるをえない。確認できるのは、ガソリン配送問題のような個別の応用が早期(1950年代末)に存在したこと、およびORが戦後に産業全般へ拡大したという一般的記述までである^[5][11]。

ORと輸送経済学の相違OR versus Transport Economics

本章では、これまでの整理を踏まえ、ORが輸送経済学と何が異なるか、ORによって物流研究の対象が変化したかを検討する。

方法と対象の相違Differences in Method and Object

第2回で整理した輸送経済学と、本稿で見たORとを対照すると、両者の相違は次の点に現れる。輸送経済学は、運賃・需要・厚生・市場といった経済学的な概念を用いて、輸送に関わる現象を説明・評価することを主とした。一方ORは、問題を数学的モデルとして定式化し、制約のもとで目的関数を最適化(最小化・最大化)することを主とした。すなわち、両者は対象だけでなく、方法(説明・評価 対 最適化)においても異なる。

仮説の検証Testing the Hypotheses

本章では、本稿が掲げた二つの仮説について、支持される部分・支持されない部分・不明な部分に分けて整理する。

仮説が支持される部分Supported

次の点は、エビデンスによって支持される。第一に、ORが、物流に関わる問題(輸送・配分・経路・割当・配送)を明示的な数理最適化問題として定式化したことは、複数の文献で確認できる^[6][11]。第二に、ORが「経路」を最適化対象として持ち込んだことは、最短経路問題・TSP・VRPの存在によって支持される^[10][11]。第三に、ORが物流研究に、運賃・市場の経済分析とは異なる方法(制約つき最適化)と対象群(輸送量の配分、経路、流量、割当)を体系的に持ち込んだことは、確認できる。ただしこれは、ORが経路や数理的検討を新たに「発明した」ことを意味しない。前述のとおり在庫理論はOR以前から存在し、ORの寄与は、こうした個別の数理的検討を含む多様な物流問題を、制約つき最適化問題として定式化・求解する枠組みへと体系化した点にある。この限りで、「ORによって物流研究に経路・配分・資源配置という最適化対象が(最適化という方法とともに)体系的に加わった」という命題は支持される。

仮説が支持されない部分Not Supported

一方、次の点は仮説に対する留保・反証となる。第一に、「ORは経路問題を中心に発展した」という見方は、支持されない。本稿で見たとおり、ORの中核手法(線形計画・動的計画)は特定対象に固有でない汎用的な枠組みであり、ORが扱った古典的問題は経路(最短経路)だけでなく、配分(輸送問題)・対応づけ(割当問題)・流量(最大流問題)を含む^[6]。初期ORの目的も「限られた資源の効果的な配分」と記述されており^[4]、経路に限定されない。したがって、ORを「経路中心」と特徴づけることは、その実態より狭い。第二に、「ORによって物流研究の中心が運賃から経路へ移行した」という単線的な移行の図式も、そのままでは支持されない。ORは運賃研究を置き換えたのではなく、最適化という別の方法・別の対象群を追加したと見るのが、確認できる事実と整合的である。運賃・市場の経済分析(第2回)は、ORの登場後も消滅していない。

不明な部分Indeterminate

次の点については、本稿の範囲で十分なエビデンスを確認できなかった。第一に、ORの登場によって物流「研究」全体の重心が量的にどの程度移動したか(運賃研究と最適化研究の比重の変化)を、体系的に示す資料は確認できなかった。「中心が移行した」と言えるか否かは、何をもって研究の中心とするかの基準に依存し、本稿では確定できない。第二に、アメリカ企業へのORの普及の全体像(時期・普及率・代表的事例の網羅)は、前章のとおり十分に確認できなかった。第三に、ORが物流に持ち込んだ「資源配分」と、本シリーズが想定する「資源配置」が、概念として完全に対応するか否かも、本稿の範囲では判断できない。

総合的な整理Overall Assessment

以上を総合すると、本稿が検証した仮説について次のように整理できる。ORが物流研究に、経路を含む複数の最適化対象(配分・経路・割当・流量)と、最適化という新しい方法を持ち込んだことは、エビデンスによって支持される。しかし、「ORは経路を中心に発展した」という見方は支持されず、ORはより広い資源配分・最適化の枠組みであったと見るほうが、確認できる文献と整合的である。また、「物流研究の中心が運賃から経路へ移行した」という単線的な図式も支持されず、ORは運賃の経済分析を置き換えたのではなく、最適化という別系統を追加したと整理できる。どちらが研究の「中心」かという重みづけの判定は、本稿の資料からは不明である。

参考文献References

1. [1] 本シリーズ第2回「市場はなぜ物流を必要とするのか ― 輸送経済学の誕生」（輸送経済学が運賃系統と市場統合系統を並行して扱っていたという整理）。
2. [2] “Operations Research in World War II.” U.S. Naval Institute Proceedings, Vol. 94/5/783, May 1968.（ORが英国で「Operational Research」として始まったこと、ブラケットの役割に関する記述）https://www.usni.org/magazines/proceedings/1968/may/operations-research-world-war-ii
3. [3] INFORMS. “The Origins of OR.”（ボードジー研究所1937年、A. P. ロウ、Chain Homeレーダー網の運用分析に関する記述）https://www.informs.org/Explore/History-of-O.R.-Excellence/
4. [4] 「History of Operations Research（Pre–World War II ほか）」OR史の概説資料。（”Blackett’s circus” の構成、初期ORの目的＝限られた軍事資源の効果的配分、レーダー運用・航空機の任務割当・潜水艦探索パターンに関する記述。米国での戦後拡大を含む）
5. [5] Operational Research の概説（学術機関のOR史資料）。（戦後、軍事から産業・社会への応用拡大、複雑システムの数理モデル開発への重心移動、石油化学・航空・金融・物流・行政等への拡大に関する記述）
6. [6] INFORMS. “Optimization / Mathematical Programming.”（線形計画と単体法のダンツィークによる定式化、輸送問題のHitchcock 1941・Kantorovich 1939・Koopmans 1947、米空軍の計画立案が動機であったことに関する記述）https://www.informs.org/Explore/History-of-O.R.-Excellence/
7. [7] Dantzig, G. B. “Linear Programming.”（線形計画の歴史に関するダンツィーク自身の記述）https://www.engineering.iastate.edu/~jdm/ee458/DantzigHistoryLP.pdf
8. [8] Bellman, R. Dynamic Programming. Princeton University Press, 1957.（動的計画法の体系化と命名。最適性原理の定式化。二次文献により内容を確認）
9. [9] Dreyfus, S. “Richard Bellman on the Birth of Dynamic Programming.” Operations Research, Vol. 50, No. 1, 2002, pp. 48–51.（動的計画法の成立、ベルマンのRAND（1952年）での研究背景に関する記述）
10. [10] 動的計画法の計算量に関するOR・アルゴリズム文献。（DPがTSPに対して古典的な厳密解法を与えること、ベルマン－ヘルド－カープ型の計算量が \( O(n^{2} 2^{n}) \) であること、およびその後に改良された指数時間アルゴリズムが提案されてきたことに関する記述。Bellman 1962; Held & Karp, “A Dynamic Programming Approach to Sequencing Problems,” Journal of SIAM, 1962 等）
11. [11] Dantzig, G. B. & Ramser, J. H. “The Truck Dispatching Problem.” Management Science, Vol. 6, No. 1, 1959, pp. 80–91.（VRPの起源。Clarke & Wright 1964 への言及を含む二次文献 Braekers, Ramaekers & Van Nieuwenhuyse, “The Vehicle Routing Problem: State of the Art Classification and Review,” Computers & Industrial Engineering, 2016 により確認）

本レポートは「物流研究史から見る最適化思想の拡張」シリーズ第3回として、オペレーションズ・リサーチ(OR)が物流研究へもたらした最適化問題群と、それによる物流研究の対象の変化を、既存の研究文献(OR史の学会資料・査読論文・原著論文の二次的確認)に基づいて整理した調査レポートである。歴史的経緯および各問題の定式化は、二次文献によって確認できる範囲で記述し、評価的記述は推論として明示した。アメリカ企業へのORの普及の全体像など、十分なエビデンスを確認できない事項は「不明」「十分なエビデンスが見当たらない」と記した。本レポートは提言・経営提案・政策提案・将来予測・独自理論・現代企業への応用提案を含まない。第1回で提示した「最適化対象＝経路」という対応づけは、本稿では検証対象の仮説として扱い、結論において支持される部分・支持されない部分・不明な部分に分けて整理した。