アルゴリズムクエリ - 複数のドライバ、複数の場所

Question

私は正直なところ、これをどこに投稿するのか分かりませんが、あなたが提供できるアドバイスについては、誰にでも非常に感謝しています。

タクシー（長距離プライベートレンタル）会社の最適なスケジュールを計算するアルゴリズムを作成したいと考えています。複数のドライバーと複数の予約があります。

いずれの日でも、それぞれ約5〜10人の仕事があり、それぞれに異なる量の時間がかけられます。

Google Distance APIを使用して、すべての場所間の座標と距離を取得できます。

できるだけ効果的にすべてのジョブを完了するために、運転者のマイル/時間を最小限に抑える最適なスケジュールを計算したいと考えています。就業時間と場所は固定されていますが、ドライバーは最大10人までのプールから任意のドライバーになることができます。ドライバーは必ずしも毎日ジョブを完了する必要はありません。一部のドライバーは、重複しない限り、1日に複数のジョブを完了することがあります。例については

---

：

ドライバーAはありB点から別のジョブが後の日であるので、ドライバーAは自然にこのジョブに割り当てる必要がありますB.

をポイントツーポイントAから行きます運転手Aは次の仕事の開始時刻までポイントBで待機することができるので、別の運転手が空の車でポイントBに行くための燃料を無駄にすることはない。

---

私は、長さのために謝罪簡潔にしようとしています。私は完全な答えを期待していないが、誰かが似たようにしようとすると、いくつかのヒントをいただければ幸いです！

Answer 1

いくつかのスケジューリング擬似コードについてお手伝いします。やってみよう！

まず、キューごとにN個のキューとM個のスロットを持つスケジューリング構造が必要です。あなたは、毎日のスケジュール、各可能なドライバのキュー、および可変数のスロットを持っていなければなりません。

私の見解では、1日を15分の時間帯に分割します。この構造を念頭に置くと、スケジューリングアルゴリズムは、新しい相互作用のそれぞれが新しい経路を割り振ろうとする対話的プロセスとなる。

最初の手順は、ルート内の各終了点の最も近い開始点を見つけるすべての保留中のルートを注文することです。この大きなルートの注文ルートでは、次のステップは、その日の彼のすべてのスロットが満たされるまで、これらのルートを最初の利用可能なドライバーに順番に移動することです。予定されている配送がなくなるまで、次の運転手のために同じ分割を続けます。

「スロット」の概念をすべて取り入れずにこのような問題に対処することは可能ですが、非常に厳しいスケジュールを避けることが安全な方法だと思います。この提案されたアルゴリズムはまた、開始点から（トラックがロードされている）出発点に戻る必要のある時間を処理しない。私はあなたがすべてのスケジュールを2度目のパスを行い、ロードポイントとの間で必要なルートを追加することで、公平だが最適化されていないソリューションを作ることができると思います。そうすることによって、 "帰って家に帰る"ルートが収まるように、ドライバーの最後のルートのいくつかを別のドライバーに移動する必要があります。

あなたの仕事で幸運を祈る。それが助けてくれることを願っています！