車両スケジューリング最適化の新しい方法

公共交通の会社は、乗客を一つの場所から別の場所に運ぶために、効率的に車両を旅行に割り当てる必要がある。そこで車両のスケジューリングが重要になってくる。目的は、車両が正しい時間と場所で利用可能であることを確認しながら、異なる旅行のスケジュールを可能な限り最適に組み合わせることだ。

車両が異なるデポから出発できる場合、すべての旅行をカバーしつつコストを最小限に抑えるという課題がある。この特定の問題は「マルチデポ車両スケジューリング問題（MDVSP）」と呼ばれる。旅行の開始時間を少し調整すること、つまり「旅行シフト」を許可することで、スケジューリングが改善される。この少しの変更を許可することで、旅行の組み合わせが良くなり、コストを節約できる。

しかし、すべての可能な開始時間の調整を考慮しようとすると、問題は非常に複雑になり、現在の解決法では扱いにくくなる。そのため、研究者はしばしば「ヒューリスティック法」と呼ばれる簡単な方法を使用して、大きな問題を解決しており、最良の解決策を保証するものではない。

この記事では、「ダイナミック・ディスクリタイズ・ディスカバリー（DDD）」という新しい方法を紹介する。この方法は、すべての可能な開始時間の調整を明示的にリストアップすることなく、旅行シフトを伴うマルチデポ車両スケジューリング問題（MDVSP-TS）の最良の解決策を見つけることができる。代わりに、問題をより単純なネットワークのバージョンで段階的に解決して、実行可能な車両スケジュールを見つける。

#車両スケジューリングの概要

車両スケジューリングプロセスでは、会社が定めた時間割に基づいて車両のルートとスケジュールを計画する必要がある。各車両は、特定の場所に指定された時間に訪れる必要があり、すべての旅行がカバーされていることを確認する。複数のデポが関与する場合、ルートを完了した後に車両が正しいデポに戻る必要があるため、複雑さが増す。

定められた時間割がスケジューリング問題を簡素化するのに役立つ一方で、全体のスケジュールを改善する可能性を制限することもある。旅行の開始時間をわずかに変更することを許可することで、そうでなければ不可能な旅行をつなげる機会が生まれる。この旅行の開始を少し早めたり遅らせたりする柔軟性は、旅行シフトとして知られ、より複雑な問題をマルチデポ車両スケジューリング問題（MDVSP-TS）に変える。

すべての可能な旅行調整を考慮する際の課題は、圧倒的な数の選択肢を生むことだ。許可される調整が多ければ多いほど、問題は大きくなり、現在の解決方法の能力を超える可能性がある。だからこそ、ヒューリスティックアプローチがよく利用されるが、最良の解決策を保証するものではない。

#ダイナミック・ディスクリタイズ・ディスカバリー（DDD）

ダイナミック・ディスクリタイズ・ディスカバリー（DDD）は、MDVSP-TSを解決するために開発された高度な方法だ。すべての可能な旅行シフトの完全な表現を必要とせず、簡単なネットワークモデルを段階的に洗練させて最適な連続時間解決策を見つける。

DDDアルゴリズムは、問題の簡略化された表現から始まる。つまり、すべての可能な旅行シフトが示されるわけではない。この表現は部分的に時間拡張されたネットワークと呼ばれる。アルゴリズムはこの簡略化されたネットワークで問題を解決し、解の下限を提供する。解が実際の移動時間に適合するように調整できれば、それは最適と見なされる。もしそうでなければ、ネットワークが更新され、新しい時間点を追加し、モデルを洗練させて再度解決する。

DDDの主な利点の一つは、すべてを一度に解決しようとするのではなく、問題を段階的に洗練することで、より良い解決策を迅速に発見できることだ。このプロセスにより、効率的な車両スケジュールの探索が可能になり、複雑な計算に挟まれることがない。

#車両スケジューリングにおけるDDDの実装

MDVSP-TSにDDDを適用するには、まず部分的に時間拡張されたネットワークを作成する。このネットワークには、すべての旅行が含まれ、実行可能な旅行のシーケンスのパスが含まれている。ネットワークは、スケジュールされた旅行とその可能な時間調整を示す旅行アークや、旅行間の空の移動を示すデッドヘッディングアークなど、異なるタイプの接続を使用する。

このネットワーク内の旅行は、移動時間に基づいており、調整が可能だ。目的は、すべての旅行がカバーされながら、運用コストを最小化する解決策を見つけることだ。

アルゴリズムは、部分的に時間拡張されたネットワークを作成するための3つの主要な方法を使用する：

1. 最初の方法は、既存のDDDメソッドに非常に似ており、すべてのアークが正確またはそれより短くなることを保証する。
2. 2つ目と3つ目の方法は、MDVSP-TSの特定の構造を考慮し、時間点の数を増やさずに長いアークを許可し、より強力な解決策を実現する。

さらに、DDDは解決策が実行可能であることを保証するために複数の洗練戦略を組み込んでいる。最初の戦略は、解決策を義務（車両によって行われる旅行のシーケンス）に分解し、その実行可能性をチェックすることに焦点を当てている。義務を実行できない場合、アルゴリズムは時間点を追加して、その義務が今後の反復に含まれないようにしている。

#DDDのパフォーマンス評価

DDDアルゴリズムの効果を評価するために、一連の計算実験が実施される。これらの実験では、500から1000までの旅行の生成インスタンスを使用し、アルゴリズムのパフォーマンスを分析する。

主な評価は、最適解に到達するまでの時間と、異なるデッドヘッディングアーク構築スキームがパフォーマンスに与える影響に焦点を当てている。結果は、より効率的なアーク構築を伴うDDDが、特に最大許可調整時間が増加するにつれて、従来の方法を大幅に上回ることを示している。

実験は、特により多くの旅行が関与する場合に、DDDを実装することで平均計算時間が大幅に短縮されることを示している。改善された構築スキームを使用することで、すべての可能な調整が表現されている場合と比べて最適解をはるかに早く見つけることができる。

#旅行シフトの利点

研究はまた、旅行シフトの利点とそれがコストに及ぼす影響を調査している。分析によると、旅行スケジュールのわずかな調整を許可することで、かなりのコスト削減につながることが示されている。旅行のタイミングをシフトできることで、必要な車両の総数が減少し、運用経費を最小化できる。

アルゴリズムの結果の調査は、旅行の数が増えるにつれてこれらの節約が増加することを示している。例えば、最大の許容偏差が増加する場合、コストは最小の調整で約1％、より大きな柔軟性を持つ場合で約5％削減される可能性がある。

興味深いことに、コストが低くても、元の時間割からの平均的な偏差は比較的小さいままである。これは、システムが確立されたスケジュールに大きな混乱を引き起こすことなく効率を達成できることを示している。

#結論

この記事では、旅行シフトを伴うマルチデポ車両スケジューリング問題を解決するために特化した新しい方法「ダイナミック・ディスクリタイズ・ディスカバリー」について説明した。この反復的な洗練アプローチにより、すべての潜在的な旅行シフトをマッピングすることなく、最適な解決策を得ることができる。

計算研究は、DDDが従来のモデリング方法を大幅に上回り、より大きな問題インスタンスを効果的に処理できることを支持する。重要なのは、DDDがスケジュールの変更を許可することで、全体の運用に過度な影響を与えることなく、高い柔軟性を示すことだ。

今後、DDDの開発は、特に電気自動車の計画や車両と乗務員のスケジューリングの課題を統合する分野において、交通研究の新しい可能性を開く。公共交通システムが進化し続ける中で、DDDのような方法は効率的で適応可能な車両スケジューリングの需要に応えるために重要となるだろう。