Driver scheduling problem とは

ドライバスケジューリング問題(DSP)は、オペレーションズリサーチと理論的コンピュータサイエンスの問題の1つです。
DSPは、乗客または物品の輸送に関与する車両(例えば、バス、列車、ボート、または飛行機)の運転手またはパイロットのための一連の任務(割り当て)を選択することからなる。
この非常に複雑な問題には、労働規則と企業規則、また異なる評価基準と目標に関連するいくつかの制約があります。この問題を効率的に解決できることは、公共交通機関のコストとサービス品質に大きな影響を与える可能性があります。実現可能な義務が満足されることが要求されるかもしれない多くの異なる規則があります。
 最小および最大ストレッチ期間最小および最大休憩時間最小および最大作業時間最小および最大合計時間最大余分作業時間最大車両変更数特定の車両の最小運転時間
オペレーションリサーチでは、この問題の効率的な解決策につながる最適化モデルとアルゴリズムが提供されています。 DSPを解決するために提案されている最も一般的なモデルには、Set Covering and Set Partitioning Models(SPP / SCP)があります。 SPPモデルでは、各ワークピース(タスク)は1つの義務でしかカバーされません。 SCPモデルでは、与えられたワークピースを複数のデューティで処理することができます。両方のモデルでは、カバーする必要があるワークピースのセットが列に並んでおり、特定のワークピースをカバーするために使用可能な以前に定義された実行可能な義務のセットが列に配置されています。これらのモデルのいずれかに基づくDSPの解像度は、最終的なスケジュールの総コストを最小限に抑えながら、各ワークピースをカバーする1つ(SPP)以上の義務があることを保証する実行可能な義務の選択です。