4

複数のレストラン(たとえば20)へのフードデリバリーを想定しましょう。利用可能な(たとえば10個の)ドライバーがあります。さらに、これらのレストランから家庭に食べ物を配達するために、4時間で100件の注文があったとします。

そのため、ドライバーは、ある場所で食べ物を受け取り、自宅の顧客に配達するように調整する必要があります。

主な目標は、配達までの時間、つまり注文から自宅に到着するまでの時間を最小限に抑えることです。2番目の目標は、ドライバーの容量を最大化することです(つまり、すべての注文を配信するための最小時間)。

注文は4時間以上かかるので、均等に、つまり3分ごとに注文することに注意してください。また、注文がランダムに20軒のレストランに向けられていると仮定します。

任意の場所から目的地、そして秒までの移動時間を計算できると仮定します。

私はすべてのドライバーの位置をリアルタイムで知っています。私は彼らのステータスも知っています。つまり、彼らは現在注文を受け取る途中(既知の目的地に行くため)であり、すでに注文を受け取り、既知の目的地に向かう途中ですか。

制約は次のとおりです。1)指定された時間の後に注文を受け取る必要があります(つまり、レストランの食事の準備時間)2)45分以内に注文を配信する必要があります(それ以外の場合はアラートがスローされます)3)時間に対応するために「x」分で時間を埋める必要があります注文を受け取るために店まで歩いて過ごしたなど。4)顧客への注文の配送と支払いの回収に費やした時間に対応するために、時間を「y」分で埋める必要があります。5)ドライバーは、特定の支払い方法のセット(Cash、Visa、Amex、MasterCardなど)しか持っていません。顧客の要求(現金、ビザなど)とドライバーの能力(現金、ビザ、アメックスなど)を一致させる必要があります。

したがって、たとえば、目的地の近くと集荷場所の近くで2つの注文を受け取った場合、別の「無料」ドライバー(何もしていない)があったとしても、同じドライバーを使用して両方の注文を集荷して配達する方が効率的です。両方の注文。

各レストランに配達ゾーンが適用されると想定できます。つまり、レストランから注文するほとんどの人は、レストランの近くにいる可能性があります。したがって、このアルゴリズムは、ドライバーを自動的に都市ゾーンにセグメント化し、ゾーン内のドライバーをすでに優先するように管理する必要があります。

4

2 に答える 2

1

それは、アルゴリズム自体にどれだけの開発時間を費やしたかによって異なります (GUI、アラートなどは含まれません)。

  • 1 日または 2 日について話している場合は、決定論的アルゴリズムを使用します。注文を FIFO スタックに入れ、次の注文を繰り返し取り、最初に利用可能なドライバーに割り当てます。これは、ほとんど人間が行う方法です。また、あまり効率的ではありません (特に 3 つ以上のレストランでは)。
  • もっと時間があれば (大企業のためにこの問題について話しているので)、楽しみが始まります。メタヒューリスティック(タブー検索、遺伝的アルゴリズム、シミュレーテッド アニーリング) を調べます。既存のライブラリを調べて、多くの作業を行ってください。たとえば、Java で作業している場合は、Drools Plannerを見てください。

ところで:ブルートフォースを考えているなら。気にしないでください。スケーリングしません。

于 2011-05-09T07:28:59.810 に答える
1

これは、タイム ウィンドウを使用した配車ルートの問題のオンライン バージョンのように思えます。それをGoogleで調べて、出てくる論文を読むことをお勧めします。

于 2011-05-08T20:12:30.910 に答える