ドライバースケジューリング問題(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日閲覧。
- ^ サルヴェンディ、ガブリエル (2001-05-25). 『インダストリアルエンジニアリングハンドブック：テクノロジーとオペレーションズマネジメント』ジョン・ワイリー・アンド・サンズ. 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 .
