輸送問題（読み）ゆそうもんだい

改訂新版　世界大百科事典

輸送問題 (ゆそうもんだい)

製品を生産地から消費地まで最も安い費用で輸送する方法を求めるという問題。線形計画問題（線形計画法で扱う問題）の一種であるが，条件によっていくつかのタイプに分けられる。

ヒッチコック型輸送問題

生産地と消費地がそれぞれ複数個所あって，おのおのの生産地における生産量，おのおのの消費地における消費量およびおのおのの生産地からおのおのの消費地に単位量を輸送するときの費用が与えられているときに，総輸送費が最小になるような輸送方法を求めよという問題。F.L.ヒッチコックが1941年に定式化し，解法を示したので，その名がつけられている。T.C.クープマンス，L.V.カントロビチらも，同じ時期に独立に同じ問題の解法を示している。その定式化は，一般の線形計画問題の定式化に先立つが，現在では，線形計画問題の特殊な場合として扱われている。

容量制約付輸送問題

生産量，消費量に対する制約のほかに，おのおのの生産地からおのおのの消費地への輸送路の容量，すなわち輸送量の上限が定められている輸送問題。

一般型輸送問題

生産地と消費地以外に，いくつかの中継地点があるネットワーク上での輸送問題。ネットワーク型輸送問題ともいう。中継地点があっても，容量制約がなければ，ヒッチコック型に変換できるので，容量制約がある場合に限る。

解法

まず，生産量と消費量の条件を満たす輸送方法を一つ見つけておいて，その後，経路変更により，少しずつ費用を安くしておく方法，最も安い輸送路を見つけては，そこに輸送することにより，少しずつ輸送量を増やし，最後に，生産量，消費量の条件を満たす方法などがある。
執筆者：古林 隆

出典　株式会社平凡社「改訂新版　世界大百科事典」