最適輸送理論

最適輸送理論について

最適輸送理論
高津 飛鳥(著)
https://www.asakura.co.jp/detail.php?book_code=11876

配車計画問題（VRP：Vehicle Routing Problem）は、複数の車両を用いて複数の配送先（顧客）を効率よく巡回し、全体の移動コストや車両数を最小化する組み合わせ最適化問題です。
☆基本概念
・定義: 出発地（デポ）から出た複数の車両が、指定されたすべての顧客に荷物を届け、デポに戻る最適なルートを求めます。
・巡回セールスマン問題（TSP）との違い: TSPが「1台の車両がすべての地点を巡回する問題」であるのに対し、VRPは「複数台の車両を使い、積載容量などの制約を考慮する問題」です。
・性質: 組合せの数が爆発的に増えるため、数学的にはNP困難（解くのが非常に難しい問題）に分類されます。

巡回セールスマン問題（英: Traveling Salesperson Problem、略称: TSP）とは、いくつかの都市とそれぞれの都市間の移動コスト（距離や時間など）が与えられたとき、すべての都市をちょうど1回ずつ訪れて出発地に戻ってくる巡回路の中で、総移動コストが最も小さくなる（最短の）ルートを求める問題です。
☆主な特徴と難しさ
・組み合わせ爆発: 都市の数 N が増えると、考えられるルートの数が爆発的に増加します。
例：5都市なら12通り、10都市なら約18万通り、30都市なら約 4.42 × 10³⁰ 通り（京を越える数）に達します。
・NP困難: コンピュータを用いても、都市数が増えるとすべての組み合わせを総当たりで調べることは現実的な時間内では不可能です

微分幾何も離散的なものにどんどん拡張されていくね