PuLP と VeRoViz を使用した数学的モデリング、ソリューション、および視覚化
オンライン ショッピングの急速な成長に伴い、企業は迅速かつ低コストの配送に対するますます高まる需要に直面しています。 ラストマイル配送 サプライチェーンの最終段階を指し、荷物が倉庫から顧客の玄関口まで配送されます。これは複雑な戦術的な問題であり、荷物をトラックに割り当てる方法と、トラックを顧客まで配送する方法を共同で決定する必要があります。これは非常にコストのかかる問題でもあります。 最近の推定 ラストワンマイル配送は送料総額の 53% となります。これは、効率的な配送計画を作成する必要性を強調しています。
この問題の古典的な形式には、すべてのトラックがそこから積み込まれ、配達に送り出される 1 つの拠点 (通常は倉庫) が関係します。より複雑なバージョンでは、複数の倉庫が互いに近接して配置されます。たとえば、小売チェーンが店舗から配送する場合などです。この場合、特定の顧客に対して複数の拠点がサービスを提供する可能性があるため、企業はどの拠点がどの顧客に出荷するかを決定する必要もあります。場合によっては、顧客の注文に含まれるすべての品目を単一のデポに用意できない場合があり、注文を複数のデポに分割する必要があります。
以下では、このより複雑なマルチデポの問題形式をモデル化して解決する方法について説明します。 整数計画法 (IP)。この問題には次のような側面があります。
- トラック、倉庫、顧客、製品のセットがあります。
- 各顧客は各製品を特定の数量で注文しており、各デポには各製品が一定の数量で用意されています。
- 各トラックは 1 つの拠点を拠点としています (つまり、そのルートは常に拠点で始まり、拠点で終わります)。さらに、トラックは同一である必要はなく、各トラックの積載量や 1 マイルあたりのコストが異なる場合があります。
目的は、1) 各拠点から各顧客に出荷する製品、2) 荷物をトラックに割り当てる方法、3) 各トラックを顧客に配送する方法を、すべての合計が最小になる方法で同時に決定することです。送料負担可能です。
IP モデルを実装して解決します。 パルプ 使用する ベロヴィズ トラックのルートを視覚化します。まず、必要なライブラリをインポートします。
シナリオの例
ある家具会社はバージニア州フレデリックスバーグ地域に 2 つの倉庫を持ち、顧客からの 8 件の注文を配達しています。データと地図を以下に示します。 注： ノード配列 変数は、 VeRoViz スケッチ ツール、位置データをグラフィカルに作成し、Python にエクスポートできるようになります。
問題のモデル化
この問題にアプローチする方法は数多くありますが、ここでは整数計画法モデルを構築して解決します。これにより、問題の正確な数学的仕様が得られ、中程度のサイズの問題インスタンスを既製のソルバーを使用して最適に解決できるようになります (ただし、私たちの範囲を超えて、より大きなインスタンスは既製のソルバーではすぐに解決できないことが多く、特別な処理が必要です) -設計されたソリューションアルゴリズム)。モデルの入力から始めます。
次に、決定変数を定義します。
最後に、最適化モデルを定義します。
このモデルでは、最小化したい目的関数 (1) は、単に発生したすべての旅行コストの合計です。 (2) の制約により、各場所で、特定のトラックがその場所に到着すると、そのトラックも出発することが保証されます。 (3) の制約により、トラックが拠点以外の拠点から出発することはなくなります。 (4) の制約により、各顧客は注文したすべての製品を確実に入手できます。 (5) の制約により、どのルートでもサブサーキットが発生しないことが保証されます。回路を形成するロケーションのグループにはノードと同じ数のエッジがあるため、各トラックの空ではない顧客の可能なすべてのサブセットでこの問題が発生するのを防ぎます。 (6) の制約により、各拠点および製品について、トラックに積み込まれ、その拠点から顧客に出荷される製品の総ユニット数が、拠点での利用可能数量を超えないことが保証されます。 (7) の制約により、トラックが顧客を訪問しない限り、いかなる製品もトラックに積み込まれて顧客に出荷されることはありません。 (8) の制約により、各トラックに積載される製品の総量がその積載量を超えないようにすることができます。最後に、(9–10) の制約は、決定変数のドメイン (バイナリ変数) を指定します。 x 変数;負でない整数 u 変数）。
容易さと再利用性を高めるために、次を使用して特定の入力データに対してこのモデルのインスタンスを構築する Python 関数を作成します。 パルプ:
サンプルシナリオの問題の解決
モデルを定式化したので、それを使用してシナリオに最適なソリューションを見つけることができます。以下では、付属の CBC ソルバーを使用します。 パルプ。最適な解決策が見つかるまでに 15 ～ 45 秒かかる場合があります。より強力な機能にアクセスできる場合は、 CPLEX ソルバーでは、代わりにコメントアウトされた行を使用すると、はるかに速く解を得ることができます。
これを実行すると、次の出力メッセージが表示されます。
トラックの旅程の抽出と表示
次に、解決されたモデルの決定変数からトラックの旅程を抽出する必要があります。トラックごとに、その停留所と、各停留所で配送する製品を知りたいと考えています。この情報を取得するには、ゼロ以外の決定変数を選別する必要があります。
これにより、次のトラックの旅程が作成されます。
顧客 C1 は 2 台のトラック (T4 と TXNUMX) で訪問されるため、注文が分割されることに注意してください。同時に顧客の要求と利用可能なリソースを考慮すると、これは最適な決定であることがわかります。これは、たとえば、単一の拠点で見つからない一連の商品が注文に含まれている場合にも必要になる場合があります。
トラックルートの可視化
最後のステップとして、 ベロヴィズ トラックのルートを適切に視覚化するには:
まとめ
この問題には多くの変形が可能ですが、この例では、整数計画法を使用してそのような問題をモデル化し、解決する方法を示します。また、Python を使用して次のような強力なコンポーネントを結合する方法も示します。 パルプ および ベロヴィズ 有用な意思決定支援システムを迅速に作成します。配信おめでとうございます！
ソースコードはノートブックで表示できます こちら またはダウンロードされた こちら.
Python での複数のデポからのラスト マイル配信ソース https://towardsdatascience.com/last-mile-delivery-from-multiple-depots-in-python-26c4325407b4?source=rss—-7f60cf5620c9—4 から再公開 https:// datascience.com/feed に向けて
<!–
–>
