車両ルーティング /リソーススケジューリングアルゴリズム設計

StackOverflow https://stackoverflow.com/questions/1925439

質問

ここでの私の最初の投稿 - 私がしばらく検討してきたアルゴリズムを設計するのを手伝ってくれることを願っています - どのアプローチを取るべきか（VRPTWまたはリソーススケジューリングなど、完全に何か）がわかりません。

それを本当の言葉の例に置くために、少数の場所（通常は5未満）にたくさんの庭の廃棄物があります。廃棄物はすべて、指定された時間枠内の他の場所に輸送する必要があります。庭の廃棄物を動かすには、車でけん引しなければならないトレーラーがあります。庭の廃棄物は、特定の時間（時間の窓）で廃棄物デポでのみ落とすことができます。一部のサイトでは、トレーラーを降ろしてそこにいる人がいっぱいにしたり空にしたりすることができますが、他の場所では車の運転手が自分でそれをしなければならず、車はそこに留まらなければなりません。すべてのタイミングを計算できます（つまり、荷重 /荷重時間、通過時間など）。車はトレーラーなしでサイト間を移動できます。トレーラーは空にけん引することができますが、トレーラーは場所を移動できません。

私たちの目的は、すべてのトレーラーの廃棄物が輸送されるようにすることです

  • 使用中のトレーラーと車の数を最小限に抑える
  • 廃棄物を落とすためのすべての時間の窓に会います
  • トレーラーの「バランスをとる」 - つまり、一日の終わりには、一日の初めにそこにあったように、各場所に多くのトレーラーがあります

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

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

アプローチについての考えは大歓迎です！

役に立ちましたか？

解決

私はJiriに同意します...あなたは、許容可能なソリューションでかなり近づき、そこから洗練するヒューリスティックアルゴリズムが必要です。

私は以前に配信ルーティングソフトウェアを持っていた企業で働いていましたが、彼らが取ったアプローチは、非常に類似した問題を解決するために遺伝的アルゴリズムを使用することでした。を取る ここを見て アプローチに精通していない場合。そのサイトから：

  1. 開始] N染色体のランダム集団を生成します（問題に適した解決策）
  2. フィットネス]集団の各染色体Xのフィットネスf（x）を評価する

  3. 新しい人口]新しい人口が完了するまで、次の手順を繰り返すことで新しい人口を作成します

    選択]フィットネスに応じて集団から2つの親染色体を選択します（より良いフィットネス、より大きなチャンスを選択する）

    クロスオーバー]は、クロスオーバー確率が両親を越えて新しい子孫（子供）を形成します。クロスオーバーが行われなかった場合、子孫は両親の正確なコピーです。

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

    受け入れる]新しい子孫を新しい人口に置く

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

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

Jiriが述べたように、このソリューションの利点は、おそらく最高ではないかもしれませんが、非常に迅速に答えて、それを実行する時間が長くなればなるほど、ソリューションが良くなることです。

他のヒント

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

おそらく、問題の十分な解決策を合理的に高速に生成できるアルゴリズムを使用したいと思うでしょう。ソリューションの品質のメトリックを作成することを確認してください。理想的なソリューションのメトリックの値を推定する良い方法が得られ、それからあなたのソリューションが理想的なソリューションからのものであり、単に単にあなた自身を設定します境界内にメトリックがある最初のソリューションを使用します。これには、このアルゴリズムが計算に時間がかかりすぎてそれを中止している場合、予想される範囲にない場合でも、最低の計算メトリックでソリューションを使用できます。

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

私はロバートに同意する傾向があります。これは、彼が説明する遺伝的アルゴリズムの実装のような進化的最適化手法の本当に素晴らしい候補のように聞こえます。

また、粒子群最適化（PSO）の特定の問題に非常に成功しました。基本的に、各ゲノムをいくつかの多次元空間の粒子と考えることができます。粒子の座標は、計算（フィットネス関数）のパラメーターです。各粒子は、ランダムな速度でランダムに開始されます。シミュレーションの各反復について、各粒子の位置を現在の移動ベクトルで更新し、次のような他のベクトルのコンポーネントを追加します。最高など...

最初はGAまたはPSOを実装するのはかなり気が遠くなるように思えるかもしれませんが、最適化しようとしている実際の問題ドメインからアルゴリズム（GA/PSO）を抽象化する小さなフレームワークを簡単に記述するのが簡単であることを保証します。アルゴリズムの詳細については、いつでもウィキペディアに戻ることができます。

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

このアプローチは、実際の問題ステートメント（車やトレーラーなど）にかなり複雑で複雑な部分がある問題に対して簡単に最適化できるため、このアプローチが気に入っています。

また、進化のテクニックが魅力的である理由は、シミュレーションに固定された時間を捧げ、停止することを決めたときにこれまでのところ最良の答えを得ることができるためです。

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

2つのアルゴリズムのいずれかの一般的なフレームワークを設計するためのガイダンスが必要な場合は、私に叫んでください。私は、あなたもいくつかの良い無料のサードパーティのフレームワークを得ることを指摘しなければなりません。アルゴリズムのあらゆる側面を理解していて、戦略をどこで調整できるかを知っているので、私は時々自分でコーディングするのが好きです。

一般的方法：

問題は小さいので、車やトレーラーを最小限に抑えようとするのではなく、実行可能なソリューションが得られるまで、車とトレーラーを追加するアプローチをお勧めします。

解決：

私は、制約を伴うガスの成功が少なく、整数変数（場所内のトレーラーの数など）に制約を伴うガスの成功がさらに少なくなりました。走行距離を最小限に抑えようとするのではなく、特定の数の車やトレーラーのために実行可能なソリューションを生成したいだけなので、制約プログラミングはより良いアプローチである可能性があります。

観察：

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

幸運を ！

ローカル検索 遺伝的アルゴリズムの代替品です。の中に 2007年の国際時間計算コンペティション, 、、ローカル検索アルゴリズム（Tabu SearchやSimulated Annealealなど）は、遺伝的アルゴリズムエントリを明確に打ち負かしました（LSの1〜4位対GAの5位の場合は、約80の競合他社のIIRCのうちトラック1では）。

また、そのようなような、そこにあるいくつかのライブラリを見てみましょう Optaplanner （タブー検索、シミュレーションアニーリング、後期受け入れ、オープンソース、Java）、JGAP（遺伝的アルゴリズム、オープンソース、Java）、Opents（Tabu Search、...

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top