船舶スケジューリング

船舶スケジューリングとは、運搬しなければならない貨物を、自らが管理している船舶をもちいて効率的に運搬するスケジュールを作成する問題およびその解決手法を指します。英語で、Ship Schedulingという用語が定着しているため、その対訳として「船舶スケジューリング」という用語を用いています。実務的には「配船計画」と呼ばれることが多いようです。また、研究開発の世界でもそのまま「配船計画問題」とよばれてきました。このページの作成者は、Ship Schedulingという英語の用語との対応を明確にするために、「船舶スケジューリング」という用語を使用しています

船舶スケジューリングは、数理的には配送計画問題(または運搬経路問題)とよばれ、数理計画・組合せ最適化の分野で80年代から非常によく研究されている問題の特殊ケースです。英語ではVehicel Routing Prolem(VRP)とよばれる配送計画問題には、様々なバリエーションが提案され、それらを効率的に解く手法が数多く提案されています(たとえば「応用数理計画ハンドブック」(朝倉書店)参照)。それらを巧みに実装したものが市販のソフトウェアとして販売されています。たとえば、"配送計画 ソフト"と検索すると、様々な製品の紹介ページを見つけることができます。実務上の計画問題は、積み込み時間、時間枠指定、容量制約、などさまざまな制約があるわけですが、解きたい問題に合ったバリエーションを選択することにより、実務規模の問題を解くことができます。

注意しなければならないのは、VRPはNP困難な問題だけれども、実際には解ける(=最適解に非常に近い近似解が現実的な計算時間で得られる)、ということです.それを実現するためのメタ解法とよばれる技術が盛んに研究され、定石といえる手法が確立されてきています。目の前の問題を解きたい、という立場からは、(2010年では)もはやどのような解法が有効か、を確認する段階ではなく、有効だとわかっている手法を効率的に実装する・自分たちの条件に合うように修正する、という観点が正解です。その意味では「船舶スケジューリング」の基本モデルはもはや枯れた技術だと言えます。

VRPは、その説明で用いられる例題で陸上のトラック(宅配便)がよく用いられることから、陸上の計画でのみ有効なものだと誤解されることがあります。しかし、VRPの枠組みは船舶スケジューリングでもそのまま有効です。 とくに国内での陸上トラック輸送と船舶の輸送では運用形態で異なる部分が多くあります。たとえば、トラックによる宅配便では一日の中で数カ所〜数十カ所の顧客をまわるのに対して、船舶では数日のうちに一箇所の港を訪問する、という違いがあります。しかし、この違いも含めて、船舶スケジューリングで有効なモデルがVRPの既存研究では提示されています。これらを用いることによって、目の前の解きたい船舶スケジューリングの問題を解くことができます.

解法

陸上のVRPでは、数百台、数百箇所の顧客を対象として計画をたてる必要があることから、メタ解法とよばれるフレームワークを用いた計算が実用的と言われています(ちなみに、よく話題にされる遺伝(的)アルゴリズムは、このメタ解法というフレームワークの1パターンです)。よく設計されたメタ解法によって、かなり難しい条件のVRPでも、実用的な計算時間で非常によい解を得ることができます。たとえば、400の顧客の問題に対して、5分程度でよい解を得ることができるアルゴリズムが提案されています(参考文献,PDFファイルが開きます)。 VRPに対しては、1960年代に集合分割問題による定式化が提案されています。陸上のVRPでこの定式化が実務的に用いられない理由の1つに、扱う台数と箇所が多すぎて、集合分割問題が大きくなりすぎることが挙げられます。これに対して、船舶スケジューリング問題では、扱う隻数、港の数が少なく、制約条件が厳しいことから、集合分割問題による定式化が実用的に用いることができます。船舶スケジューリングの数理計画による研究は、1970年代から行われていますが、実務的な問題意識に基づいた多くの研究は、この集合分割問題の基づくものであり、成果を挙げています。その意味では、この集合分割問題によるアプローチが、実務的な船舶スケジューリング問題を解く手法の決定版と言えます。

集合分割問題

集合分割問題とは、整数計画問題とよばれる数理計画問題の特殊ケースです。整数計画問題とは、

と書かれる最適化問題です.NP困難な問題ではありますが、近年のソルバの発展により、相当大きな問題も解けるようになってきています. (参考:宮代他「ここまで解ける整数計画」)。 x_jが一般の整数ではなく0または1のみをとる場合、この問題を0-1整数計画問題とよびます。さらに、 制約行列の成分a_{ij}が全て0または1、右辺のベクトルbの成分b_iが全て1の場合を、集合分割問題(set partitioning problem)とよびます.