問題タブ [hungarian-algorithm]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 割り当て問題を最大フロー問題に変換する
このリンクで読んだ記事によると、割り当て問題は特定の条件下で最大フロー問題に変わる可能性があります。最小コスト フロー問題の変換については知っていますが、この方法から、この問題が最大フロー問題になる条件とは何かを知りたいです。
algorithm - ジョブごとに 2 人のワーカーの割り当ての問題
問題設定
現在、フードテック スタートアップ (電子食料品店) の派遣問題に取り組んでいます。私たちには仕事（配達される注文）と労働者（宅配業者/梱包業者/ユニバーサル）があります。問題は、注文を労働者に効率的に割り当てることです。最初のステップでは、CTE (クリックして食べる - 注文してから配達までの時間) を最適化することにしました。
問題そのもの
問題は、単一のエグゼキューターではなく、1 つのジョブにつき 2 人のワーカーを持つことが効率的であるという事実から生じます。なぜなら、パッカーは店舗の「マップ」を知っている可能性があり、宅配業者は自転車を持っている可能性があるため、それぞれを個別に比較した場合でもジョブをより速く実行できるからです。注文転送費用の会計。
アルゴリズムを調査したところ、私たちの問題は割り当て問題のように見え、アルゴリズムによる解決策 (ハンガリーのアルゴリズム) があることがわかりましたが、問題は、古典的な問題では、「各ジョブが 1 つのワーカーに割り当てられ、各ワーカーに 1 つのジョブが割り当てられる」必要があることです。私たちの場合、1 つのジョブに 2 人のワーカーを配置すると効率的な場合があります。
これまでに試したこと
(パッカー A +ユニバーサル B ) の組み合わせをコストのマトリックスに挿入しますが、この場合、ユニバーサル B をマトリックスに追加することは できません。パッカーAとの組み合わせの一部として）
その結果、2 つのハンガリー語アルゴリズムを実装します。最初にパッケージを割り当て、次に配送を割り当てます。これはほとんどの場合に機能しますが、非効率的なソリューションにつながることもあります。必要に応じて、例を追加します。
質問自体
私はたくさんグーグルで検索しましたが、問題の解決策を教えてくれるものは何も見つかりませんでした。解決の手がかりとして使用できるリンクやアイデアがあれば、喜んでチェックさせていただきます。
編集:私の質問のブルート フォース ソリューションを追加しました。問題をよりよく理解するのに役立つことを願っています