6

ここでの私の最初の投稿–しばらくの間検討していたアルゴリズムの設計を手伝ってくれることを願っています–どのアプローチを取るべきかわからない（VRPTWまたはリソーススケジューリングまたは他の何か！？）

実例に言えば、少数の場所（通常は5つ未満）に大量の庭ごみがあります。廃棄物はすべて、所定の時間枠内に他の場所に輸送する必要があります。庭のゴミを移動するために、車で牽引しなければならないトレーラーがあります。庭のゴミは、特定の時間（時間枠）にのみゴミ捨て場に捨てることができます。いくつかの場所では、トレーラーを降ろしてそこにいる人々がいっぱいになるか空にすることができますが、他の場所では、車の運転手が自分でそれをしなければならず、車はそこに留まらなければなりません。すべてのタイミングを計算できます（つまり、ロード/アンロード時間、通過時間など）。車はトレーラーなしでサイト間を移動できます。トレーラーは空に牽引できますが、トレーラーは場所間を移動できません。

私たちの目的は、トレーラーに積まれたすべての廃棄物が輸送されていることを確認することです。

  • 使用中のトレーラーと車の数を最小限に抑える
  • 廃棄物を落とすためのすべての時間枠を満たす
  • トレーラーの「バランスをとる」–つまり、1日の終わりには、1日の始まりにあったのと同じ数のトレーラーが各場所にあります。

これをリソーススケジューリングアルゴリズムとしてアプローチすることを考えましたが、トレーラーの「バランシング」をどのように処理するかがわかりません。

私が考えたもう1つの方法は、最初に車を検討することでした。次に、最も早いタスクを選択し、その後に実行可能なすべてのタスクのグラフを作成できます。次に、トレーラーの最大積載数に対応するグラフの最長パスを選択した場合。次に、これらのタスクをタスクのリストから削除し、すべてのタスクが処理されるまで繰り返すことができます。次に、これらのトレーラーの負荷のリストを調べて、必要なトレーラーの数を計算する必要があります。

アプローチについての考えはありがたいです！

4

5 に答える 5

4

ここでは確かにNP完全アルゴリズムについて話していますが、いくつかの車やトレーラーを超えて、これはすべての可能な解決策から最良の解決策を取得し、それを破棄して再び実行して回避することができるタスクではありませんあなたが提案するように最長のパス。このようにアルゴリズムを設計した場合、ある日、車とトレーラーをもう少し追加すると、ソリューションの計算が完了しなくなる可能性が非常に高くなります。

おそらく、問題の十分な解決策を適度に高速に生成できるアルゴリズムを使用することをお勧めします。ソリューションの品質のメトリックを作成することを確認してください。理想的なソリューションのメトリックの値を見積もる良い方法が得られます。次に、ソリューションを理想的なソリューションから除外する％を設定します。範囲内にメトリックがある最初のソリューションを取ります。これには、このアルゴリズムの計算に時間がかかりすぎて中止した場合でも、予想される範囲内にない場合でも、計算されたメトリックが最も低いソリューションを使用できるという追加の利点があります。

しかし、問題自体を解決するためのアプローチはわかりません。acmポータルで検索した後、いくつかの記事を読むことをお勧めします。UPSとFedexにも同様の問題があると思いますが、Googleでの検索にキーワードとして追加すると、さらに役立つ結果が得られる可能性があります。

于 2009-12-18T05:38:13.993 に答える
4

私は Jiri に同意します...許容できるソリューションにすばやく近づき、そこから改良するヒューリスティック アルゴリズムが必要です。

私は以前、配達経路指定ソフトウェアを持っている会社で働いていましたが、彼らがとったアプローチは、遺伝的アルゴリズムを使用して、非常に類似した、しかしはるかに大規模な問題を解決することでした。アプローチに慣れていない場合は、こちらをご覧ください。そのサイトから：

  1. [開始] n 個の染色体のランダムな母集団を生成します (問題の適切な解)
  2. [適応度] 集団内の各染色体 x の適応度 f(x) を評価する

  3. 【新規個体群】 新規個体群が完成するまで以下の手順を繰り返して新規個体群を作成します

    [選択] 適合度に応じて母集団から 2 つの親染色体を選択します (適合度が高いほど、選択される可能性が高くなります)。

    【交叉】 交叉確率で親を交配し、新たな子孫（子）を形成します。クロスオーバーが実行されなかった場合、子孫は親の正確なコピーです。

    [Mutation] 突然変異の確率で、各遺伝子座（染色体上の位置）で新しい子孫を突然変異させます。

    [承認] 新しい子孫を新しい集団に配置する

  4. [置換] アルゴリズムをさらに実行するために新しく生成された母集団を使用する
  5. [テスト] 終了条件が満たされた場合は停止し、現在の母集団での最適解を返します
  6. [ループ] ステップ 2 へ

これの秘訣は、制約を「染色体」にエンコードし、「適合」関数を記述することです。フィットネス関数は、潜在的なソリューションの結果の入力を取得し、ソリューションがどれだけ優れているかのスコアを吐き出すか、制約に違反する場合はそれを破棄する必要があります。

Jiri が述べたように、このソリューションの利点は、実行可能な (最善ではないかもしれませんが) 回答が非常に迅速に得られることです。

于 2009-12-18T11:54:58.490 に答える
1

一般的方法：

問題は小さいので、車やトレーラーを最小限に抑えるのではなく、実行可能な解決策が得られるまで車やトレーラーを追加するアプローチをお勧めします。

解決：

制約のあるGAでの成功は少なく、整数変数（場所内のトレーラーの数など）に制約のあるGAではさらに成功していません。移動距離を最小限に抑えるのではなく、特定の数の車とトレーラーに対して実行可能なソリューションを生成したいだけなので、制約プログラミングの方が優れたアプローチである可能性があります。

観察：

あなたは、最後の動きが空のトレーラーを再配置することであるかもしれないネットワーク上の問題を解決しています。

幸運を ！

于 2009-12-30T18:47:25.313 に答える
1

私はロバートに同意する傾向があります。これは、彼が説明する遺伝的アルゴリズムの実装のような進化的最適化手法の非常に優れた候補のように思えます。

また、粒子群最適化 (PSO) を使用して、特定の問題で非常に優れた成功を収めました。基本的に、各ゲノムは多次元空間内の粒子と考えることができます。粒子の座標は、計算のパラメーターです (適合関数)。各パーティクルは、ランダムな速度でランダムに開始されます。シミュレーションの反復ごとに、各パーティクルの位置を現在の移動ベクトルで更新し、他のベクトルのコンポーネントを追加します。たとえば、これまでで最高のパーティクルへの方向、これまでで最高のパーティクルへの方向、ローカル グループへの方向などです。ベストなど...

最初は GA または PSO を実装するのはかなり困難に思えるかもしれませんが、最適化しようとしている実際の問題領域からアルゴリズム (GA/PSO) を抽象化する小さなフレームワークを簡単に作成できることを保証します。アルゴリズムの詳細については、いつでもウィキペディアに戻ることができます。

フレームワークができたら、通常は 2 つのパラメーターの問題 (おそらく問題の単純化、または画像上の X と Y の位置) から始めます。これにより、アルゴリズムを簡単に視覚化して微調整できるため、群れの動作が良好になります。次に、それをより多くの次元に拡大します。

私がこのアプローチを気に入っているのは、実際の問題ステートメント (車やトレーラーなど) に対してかなり複雑で入り組んだ部分がある問題を簡単に最適化できるからです。

また、進化的手法が魅力的な理由は、一定の時間をシミュレーションに当てて、やめると決めた時点でそれまでのベストアンサーが取れるからです。

私の経験では、ハードコードされたヒューリスティック ソリューションを作成するのと同じくらい、パラメータを GA または PSO に微調整するのに (実装が完了したら) 時間がかかる傾向がありますが、その利点は、通常、ソリューションを見つけるための戦略を変更することです。問題をゼロからヒューリスティックに解決するためのまったく異なる戦略をコーディングするのではなく、パラメーターの変更のみを必要とするか、非常に明確に定義されたアルゴリズムを別の実装に交換する必要があります。

2 つのアルゴリズムのいずれかの汎用フレームワークの設計に関するガイダンスが必要な場合は、声をかけてください。いくつかの優れた無料のサードパーティ フレームワークも入手できることを指摘しておく必要があります。アルゴリズムのすべての側面を理解し、どこで戦略を調整できるかを知っているので、私は自分でコーディングするのが好きなことがあります。

于 2009-12-19T09:07:04.143 に答える
1

ローカル検索は、遺伝的アルゴリズムに代わるものです。2007 年の国際時刻表コンペティションでは、ローカル検索アルゴリズム (タブー検索やシミュレーテッド アニーリングなど) が明らかに遺伝的アルゴリズムのエントリを上回りました (約 80 の競合他社 IIRC のうちトラック 1 で、LS が 1 位から 4 位、GA が 5 位)。

また、OptaPlanner (Tabu Search、Simulated Annealing、Late Acceptance、オープン ソース、Java)、JGap (遺伝的アルゴリズム、オープン ソース、Java)、OpenTS (Tabu Search、.. .

于 2011-01-16T16:25:35.187 に答える