Loading article…
ドライバースケジューリング問題(DSP) は、オペレーションズ リサーチと理論計算機科学における問題の一種です。
DSPは、様々な法的および物流上の基準の制約の範囲内で、乗客または貨物の輸送に関与する車両（バス、電車、船、飛行機など）の運転手または操縦士の一連の職務（割り当て）を選択することから成ります[1] [2]。
基準とモデリング
この非常に複雑な問題には、労働や会社の規則に関連するいくつかの制約、そしてさまざまな評価基準と目標が関係しています。この問題を効率的に解決できるかどうかは、公共交通機関のコストとサービスの質に大きな影響を与える可能性があります。[3]実行可能な義務が満たす必要があるさまざまなルールが多数あります。たとえば、
- 最小および最大のストレッチ期間
- 休憩時間の最小値と最大値
- 最小および最大作業時間
- 最小および最大合計期間
- 最大残業時間
- 車両変更の最大回数
- 特定の車両の最小運転時間
オペレーションズ・リサーチは、この問題の効率的な解決につながる最適化モデルとアルゴリズムを提供してきました。 DSPを解決するために提案されている最も一般的なモデルには、セット・カバーリング・モデルとセット・パーティショニング・モデル（SPP/SCP）があります。[4] [5] SPPモデルでは、各ワークピース（タスク）は1つの職務のみでカバーされます。 SCPモデルでは、特定のワークピースをカバーする職務が複数ある可能性があります。 どちらのモデルでも、カバーする必要があるワークピースのセットは行に配置され、特定のワークピースをカバーするために使用できる、以前に定義された実行可能な職務のセットは列に配置されます。 これらのモデルのいずれかに基づくDSP解決は、最終スケジュールの総コストを最小限に抑えながら、各ワークピースをカバーする職務が1つ（SPP）または複数（SCP）あることを保証する実行可能な職務のセットを選択することです。
参照
参考文献
- ^ ヴォス、ステファン;ダドゥナ、ヨアヒム R. (2001)。コンピューターを利用した公共交通機関のスケジュール管理。スプリンガー。 122ページ–。ISBN 9783540422433. 2013年5月22日閲覧。
- ^ Salvendy, Gavriel (2001-05-25). ハンドブック オブ インダストリアル エンジニアリング: テクノロジーとオペレーションズ マネジメント. John Wiley & Sons. pp. 813–. ISBN 9780471330578. 2013年5月22日閲覧。
- ^ Borndörfer, Ralf; Martin Grötschel ; Marc E. Pfetsch (2006). 「公共交通機関の未来へ」OR/MS Today . 33 (2): 30–40.
- ^ ロレンソ、HR;パイサン、日本。ポルトガル、R. (2009)。 「ドライバーのスケジュール問題のモデリング」。公共交通機関: 計画と運営。1 (2):103-120。土井：10.1007/s12469-008-0007-0。hdl : 10230/303。
- ^ Lourenço, HR; Paixão, JP ; Portugal, R. (2001). 「GIST システムの乗務員スケジュール モジュール」。経済ワーキング ペーパー シリーズ、ポンペウ ファブラ大学経済経営学部。547 。