4つのスケジューリング最適化に関する研究

Oct 09, 2023

車で行く価値のある、バンクーバー郊外の家族向け日帰り旅行 10 選

Oct 26, 2023

イスラエルの食料品店をユニークなものにする 10 の点

May 09, 2023

11 ベスト3

Jul 20, 2023

より良いグリルのための 11 個の Weber グリルアクセサリー、必須

Jan 30, 2024

2023 年のベストランドリーバスケットとバスケット 12 選

お問い合わせを送信してください

送信

Jul 11, 2023

4つのスケジューリング最適化に関する研究

Rapporti scientifici Volume 13,

Scientific Reports volume 13、記事番号: 3999 (2023) この記事を引用

519 アクセス

メトリクスの詳細

本論文では,研究対象として4方向シャトルシステムを取り上げ,4方向シャトルシステムの入出運転最適化および経路最適化スケジューリング問題の最小時間に基づいてスケジューリング最適化の数学的モデルを確立した。改善された遺伝的アルゴリズムはタスク計画を解決するために使用され、改善された A* アルゴリズムはシェルフレベル内のパス最適化を解決するために使用されます。 4方向シャトルシステムの並列運転により発生する衝突を分類し,時間窓法に基づく改良A*アルゴリズムを構築し,動的グラフ理論法による経路最適化を行い,衝突のない安全な経路を探索した。シミュレーション例分析を通じて,本論文で提案した改良A*アルゴリズムが本論文のモデルに対して明らかな最適化効果を有することを検証した。

倉庫物流は自動化システム統合の時代に入り、高層立体棚を主保管設備として、インテリジェント物流システム保管の主流に発展しました。作品本体にもロボット化した棚収納やシャトル＋棚などがあります。棚+シャトル+ホイスト+ピッキングシステム+倉庫管理システムなどのハードウェアとソフトウェアが統合された保管システムは、主要な保管モードの1つとなっています。都市部のラストワンマイルの配達時間と効率に対する需要を改善するために、新しいタイプのシャトルシステム、つまり 4 方向シャトルシステムの使用がますます普及しています。

シャトルシステムのアップグレードとして、4方向シャトルシステムは、棚間の縦方向および横方向のレーン、レーン間のクロスノードなどの特徴を備えています。トロリーは 1 層の棚内で 4 方向に走行できるだけでなく、ホイストと一緒に走行して層変更を完了することもできます。これは、ストレージシステムの動作の安定性、作業効率の向上、および運用生産コストの削減に重要です。しかし、インバウンドおよびアウトバウンドのタスクの拡大と利用可能な 4 方向シャトルの数の増加に伴い、タスクの割り当てと 4 方向シャトルの複数車両の並行運行のスケジュール設定の複雑さが増加しました。固定倉庫シナリオにおける複数の 4 方向シャトルの衝突や衝突のない最適な最短経路を計画することは、4 方向シャトルシステムの研究においては困難な問題です。この論文で調査した 4 方向シャトルシステムは、4 方向シャトルの層変更操作に適合するように、各通路の両側に高層ラックの列と通路の端にホイストを備えた単一深さのラック構成です。。単一深さのラックは、少量および複数種類の小物の保管に適していますが、このシステムではより多くのメイントラックが必要となるため、保管スペースが混雑し、保管スペースの使用率が低下します。しかし、この保管レイアウトでは、小ロット多品種の商品を柔軟なアクセスモードで保管し、複数の4方向シャトルを使用して並行して動作することができるため、アクセス作業の効率が向上します。本稿で検討した4方向シャトルシステムの平面図を図1に示す。

本稿で検討した4方向シャトルシステムの平面レイアウト。

本稿では、設備投資を追加することなく、既存設備間の連携を合理的に活用することで、稼働時間の短縮と倉庫の業務効率の向上を実現する4方向シャトル保管システムのタスクスケジューリングと最適管理について説明します。文献に記載されている自動アクセス装置は、主にスタッカークレーンとシャトル、またはその両方の組み合わせで構成されていますが、4 方向シャトルシステムに関する研究はあまり行われていません。 4 方向シャトルは縦、横、垂直の 3 次元方向に走行して、商品の任意の位置に到達できるため、スケジュールの問題はさらに複雑になります1、2、3、4、5、6。

自動ステレオ倉庫の最も一般的なタイプは、AS/RS、SBS/RS、AVS/RS です。 AS/RS システムは実際の工業生産に導入するのに比較的安価ですが、そのようなシステムは柔軟性が低く、AS/RS は奥行きが 1 つまたは 2 つのラックにしかフィードできません。その結果、倉庫の規模に応じて通路の数が増加し、スペースの利用率が低下します。科学文献では、AVS/RS に関する研究は、互換性のあるシステムと互換性のないシステムに大別できます。前者は、トロリーがホイストで異なる層に上下に移動できるものです。後者はトロリをAVS/RSの特定階層に割り当てて運転するシステムであり、ホイストと一緒に移動することはできません。SBS/RSシステムはシャトルカーを核とした自動保管システムです。このシステムは AVS/RS の新しい技術であり、各層にシャトルカーが必要です。初期投資コストが高いため、主に積載量の少ない倉庫に適しています。学者は主にストレージシステム用の AVS/RS および SBS/RS システムに焦点を当てており、4 方向シャトルのスケジューリングの最適化にはあまり焦点を当てていません 7、8、9、10。リファレンスでは、シャトルスケジューリング理論がさまざまなスケジューリング状況に従って分類され、単一タスク要求の場合の複数のシャトルの選択と、複数のタスク要求の場合の単一のシャトルの選択に焦点が当てられました。ファジー分類アルゴリズムを適用して作業タスクの発生確率を決定し、次に既存の作業タスクと生成する必要がある作業タスクを考慮して、遺伝的アルゴリズムを使用して動的複数車両経路最適化問題を解決し、より合理的にシャトル配送を割り当てました12。。参考文献13では、遺伝的アルゴリズムとランダムストレージ戦略を使用して、AS / RSのタスクを順序付けるための二重ループモードを開発し、タスクの位置と順序を同時に決定するための遺伝的アルゴリズムモデルが提案されました。このモデルは、2 つの貪欲なヒューリスティックアルゴリズムよりも優れていました。タスクのスケジューリング問題は、シャトルとリフトの間で、シャトルとリフトの運動特性に基づいて組み立てラインの並行運転問題に変換されました。スケジューリングタスクキューモデルは、指定された時間枠内で生成されました14。多くの学者は、車両スケジュール問題のモデルを解くための遺伝的アルゴリズムの適用を検討してきましたが、遺伝的演算子と適合関数を使用してシャトルバスのスケジュールモデルを解く改善についてはほとんど考慮していませんでした。

シャトルのスケジュールの最適化は、シャトルシステム研究の焦点であり、難しさです。その中でも、パスの最適化はシステムの効率を向上させるもう 1 つの重要な方法です。パス最適化の中核はアルゴリズム設計です。従来のアルゴリズムには、主に禁止探索アルゴリズムとシミュレーテッドアニーリング手法が含まれます15、16、17、18、19。シミュレーテッドアニーリングアルゴリズムは局所最適法であるため、局所最適解から外れやすく収束が遅く、解の精度に影響を及ぼします20,21,22,23,24。参考文献 25 では、適応変数近傍検索アルゴリズムとラグランジュ緩和アルゴリズムが、時間とエネルギーの生物客観的整数計画法モデルを確立することによって大規模なインスタンスに対処するために開発されました。共有ストレージシステムを研究することにより、特殊なタイプのフォールトトレラントな車両経路設定問題としてのクレーンスケジュール問題が再定式化され、関連する幾何学的経路設定問題の時間計算量に関するいくつかの未解決の問題を解決するために使用できるようになりました 26。参考文献 27 では、統合最適化問題として、無人搬送車、リフト、シャトルが研究されています。混合整数計画法モデルを提案して、入荷プロセス中の関連機器および保管場所へのパレットの割り当てを最適化し、変数近傍検索に基づくアルゴリズムを開発して、モデルを効率的に解決しました。文献 28 では、多シフト S/R 機を備えた多通路型 AS/RS を検討し、遺伝的アルゴリズムを使用してシステムの最適化を実行しました。複数のシャトルの同時動作によって引き起こされる競合デッドロックの問題を解決するために、Li と Roy は、ストレージシステムを重複しないゾーンに分割し、各ゾーンで 1 つの 4 方向シャトルのみがタスクを実行できるようにするゾーン制御方法を使用しました。

学者らはシャトルシステムをかなり成熟して研究してきましたが、シャトルのスケジュール設定により重点を置き、複数の目的の下でシステムの通常のスケジュール操作を支持し、システムのデッドロックや交通制御などがほとんど関与しませんでした。スケジュールの最適化の観点から、研究は主に単一のシャトルシステムに焦点を当ててきました。各エリアのアクセス作業用に 1 台のシャトルを備えた保管ラック。スケジュールモデルは 1 レベルの操作または複数の固定通路に対応する 1 台のエレベーターに限定されます。競合デッドロック問題を解決するために、領域制御方式と予測制御方式では、運用タスクの中間リンクが増加し、シャトル運用の範囲が制限されるため、ストレージシステムの運用効率が低下します。 4 方向シャトルシステムは、負荷需要に応じて動作タスクを動的に調整でき、高い柔軟性を備えていますが、同じレベルで複数のシャトルを並列動作させると経路の競合が発生する可能性があり、システム制御のスケジューリングがより複雑になります。したがって、本論文の研究課題は、4方向シャトルシステムを研究対象とし、複数の4方向のアクセス動作の最適化と経路最適化スケジューリングに基づくスケジューリングの最短時間最適化に基づく数理モデルを確立することである。 4 方向シャトルシステムの 1 つのウェイシャトルと複数のリフト。モデルの特性を組み合わせて、改良された遺伝的アルゴリズムを使用してタスク計画を解決し、改良された A* アルゴリズムを使用して棚レベル内のパスを最適化します。

4方向シャトルカーとホイストの並列運転と動作方向制限のない4方向シャトルカー自動経路探索の革新的なアルゴリズム設計を提案した。

数学的関数は、最短時間の目標最適化に基づいて確立されます。遺伝的アルゴリズムと組み合わせると、各シャトルの動作経路を見つけるローカル経路計画の改良された遺伝的アルゴリズムの使用と Python ソフトウェアシミュレーションを通じて、最適な多点検索特性を簡単に見つけることができます。

A* アルゴリズムのパス検索が改善され、最短パスに基づいて混雑回避を考慮するように強化されました。動的グラフ理論とタイムウィンドウに基づいた改良されたA*アルゴリズムは、複数の四方向シャトル車両の経路競合問題に対して、複数のシャトル車両が同じ層で一緒に動作する場合の衝突ロック問題を解決するために提案されている。同じ層内の四方向シャトル車両の時間のかかる最短経路軌道が得られます。

4 方向シャトル保管システムの理論的サポートを提供するために、4 方向シャトルシステムのスペース利用率、タスクの合理性、経路の最適化を改善できる保管計画、設計レイアウト、タスクスケジューリングの理論的基礎を提供します。

この文書の残りの部分は次のように構成されています。「モデルの構築」セクションでは、提案されたモデルの仮定と、この研究に適用されたモデル設計の定式化を示します。アルゴリズムのフレームワークと改良されたアルゴリズムの具体的な定式化は、「提案されたアルゴリズム」セクションに記載されています。論文で提案したアルゴリズムの具体的な応用例は「応用例の分析」セクションに示されています。「結論」セクションでこの論文を締めくくります。

4 方向シャトルシステムのスケジュール最適化モデルをより適切に研究するために、このホワイトペーパーでは 4 方向シャトルシステムに対して次の仮定を立てます。

棚とコンパートメントは同じ仕様で、各通路の幅も同じで、商品はランダムな保管方法で保管されます。

インバウンドおよびアウトバウンドの操作タスクでは、FCFS 戦略に従って 4 方向シャトルとホイストが連携して動作することが要求されます。

棚の各行には $M$ レベルと $N$ 列があり、長さ、幅、高さは固定されています。

通路の同じセクションを同時に運行できるのは、4 方向シャトル 1 台のみです。

ホイストと 4 方向シャトルは等加速度運動をしています。

4 方向シャトルは一度に 1 つの貨物のみを運ぶことができ、運行プロセスは中断されません。各ホイストは一度に 1 つの 4 方向シャトルまたは単一の貨物のみを積載でき、4 方向シャトルの初期位置が最後のタスクの最終目標貨物位置になります。ホイストの初期位置は、通路ホイスト入口の端にある最後のタスクの最終目標貨物レベルです。

シャトルが商品にアクセスするのにかかる時間、およびホイストに出入りするのにかかる時間は無視され、シャトルの回転時間は一定値と同じになります。

パラメーター

意味

${R}_{count}$

システムの 4 方向シャトルの総数 ($count=\mathrm{1,2},3\dots n$)

${E}_{count}$

システムホイストの総数 ($count=\mathrm{1,2},3\dots m$)

各棚の高さ

${J}_{count}$

操作タスクの総数 ($count=\mathrm{1,2},3\dots k$)

${W}_{T}$

個々の通路の幅

棚の段数

個々の貨物室の長さ

\（{トイレ}\）

個々の貨物室の幅

${V}_{Rm}$

4方向シャトルの最高速度

${a}_{R}$

4方向シャトルの加速

${V}_{Em}$

ホイストの最高最高速度

${a}_{E}$

ホイストの加速度

${T}_{2},{T}_{3}$

time 関数式は ${T}_{1}$ と意味が似ています

${E}_{評価可能}$

システム内で使用可能なホイストの数

${R}_{利用可能}$

システム内で利用可能な 4 方向シャトルの数

${M}_{J}$

インバウンドタスク J のターゲットレベルは $(M=\mathrm{1,2},\dots ,M)$ です。

\（{氏}\）

4 方向シャトルカー R の最後の操作がフロアで完了しました $(M=\mathrm{1,2},\dots ,M)$

${T}_{1Ei}$

ホイスト i が倉庫床入口まで荷降ろしされて稼働するのにかかる時間 $\left(i\subseteq \mathrm{1,2},\dots {E}_{count}\right)$

${T}_{2Ei}$

i ロードしたリフトをターゲットレベルがあるレベルまで実行するのにかかる時間 $\left(i\subseteq \mathrm{1,2},\dots {E}_{count}\right)$

${T}_{1RJ}$

4 方向シャトル j が、トンネルの終端にあるホイスト開口部まで荷降ろしされて走行するのに費やした時間 $\left(j\subseteq \mathrm{1,2},\dots {R}_{count}\right)$;

${T}_{2RJ}$

4 方向シャトル j 荷物をターゲットベイに配送するのにかかる時間 $\left(j\subseteq \mathrm{1,2},\dots {R}_{count}\right)$

${T}_{3Ei}$

4 方向シャトルが配置されているレベルまで降ろしたホイストを実行するのにかかった時間 $\left(i\subseteq \mathrm{1,2},\dots {E}_{count}\right)$;

${T}_{4Ei}$

4方向シャトルを積んだリフトを目標の貨物レベルがある階まで輸送する時間

${T}_{1Ek}$

エレベーター k が倉庫の床入口まで空で走行するのに費やした時間 $\left(k\subseteq \mathrm{1,2},\dots {E}_{count}\right)$

${T}_{2Ek}$

エレベーター k ターゲットレベルが存在するレベルまでロードを実行するのにかかる時間 $\left(k\subseteq \mathrm{1,2},\dots {E}_{count}\right)$

${T}_{1Ei}^{\mathrm{^{\prime}}}$

ホイスト $i$ が空になってから、搬出貨物レベルがある階までの時間 $\left(i\subseteq \mathrm{1,2},\dots {E}_{count}\right)$

${T}_{1Rj}^{\mathrm{^{\prime}}}$

4 方向シャトル $j$ が目的の空の貨物スペース $\left(j\subseteq \mathrm{1,2},\dots {R}_{count}\right)$ に到着するのにかかる時間

${T}_{2Rj}^{\mathrm{^{\prime}}}$

4 方向シャトル $j$ が商品をピックアップしてホイストに配送するのにかかる時間 \(\left(j\subseteq \mathrm{1,2},\dots {R}_{count}\右）\）

${T}_{2Ei}^{\mathrm{^{\prime}}}$

ホイスト $i$ が輸出する商品を輸送するのにかかった時間 $\left(i\subseteq \mathrm{1,2},\dots {E}_{count}\right)$

${T}_{3Ei}^{\mathrm{^{\prime}}}$

他の利用可能なトロリーレベルまでホイスト $i$ が空の状態で費やした時間 $\left(i\subseteq \mathrm{1,2},\dots {E}_{count}\right)$

${T}_{3Rj}^{\mathrm{^{\prime}}}$

4 方向シャトル $j$ が空のホイスト開口部 $\left(j\subseteq \mathrm{1,2},\dots {R}_{count}\right)$ に到達するのにかかる時間

${T}_{1Ei}^{\mathrm{^{\prime}}}$

ホイスト $j$ がターゲットレベルがあるレベルまで 4 方向シャトルを積み込むのにかかる時間 \(\left(i\subseteq \mathrm{1,2},\dots {E}_{count} \右）\）

${T}_{S}^{\mathrm{^{\prime}}}$

最初のアウトバウンド操作の開始時刻

${T}_{E}^{\mathrm{^{\prime}}}$

最後のアウトバウンド操作が完了するまでの時間

${f}_{max}$

母集団の最大適応度値

$f$

集団内で交雑する 2 つの個体のうち大きい方の適応値

${f}_{agv}$

母集団内のすべての個人の平均適応度値

${f}^{\mathrm{^{\prime}}}$

突然変異する集団内の個体の適応度値

$N$

単列貨物室の数

$K$

レーン数

本稿で検討した 4 方向シャトルシステムにおけるシャトル運行の速度と時間の関係を図 2 に示す。これらの仮定に基づいて、4 方向シャトルシステムに必要な通路長、横断通路長、棚高さを求める。シャトルとホイストが最高速度まで加速してから 0 まで減速するのは $S_{Rm} = \left| {\frac{{V_{Rm}^{2} }}{{a_{R} }}} \ right|, \;{ }S_{Cm} = \left| {\frac{{V_{Rm}^{2} }}{{a_{R} }}} \right|{,}\;{ }H_ {Em} = \left| {\frac{{V_{Rm}^{2} }}{{a_{E} }}} \right|$。各コンパートメントの長さ、各コンパートメントの幅、通路の幅、各棚の高さはわかっているため、必要なコンパートメントの最小数とレベルの数は $L_{Rm} = \left| { \frac{{S_{Rm} }}{L}} \right|,\;{ }L_{Cm} = \left| {\frac{{S_{Rm} }}{{2W_{C} + W_{ T} }}} \right|,\;L_{Em} = \frac{{H_{Rm} }}{H}$31.

横方向の時間

目標貨物位置への 4 方向シャトルの初期位置、またはトンネルホイストの終端が同じトンネル内で開く場合。つまり、列 $x$ から列 ${x}^{\mathrm{^{\prime}}}$ または列 $x$ から列 0 までシャトルを実行するのに必要な時間は次のようになります。 :

4 方向シャトルの走行速度と時間の関係。

または

4 方向シャトルの初期位置と目標貨物位置、または 4 方向シャトルと通路端ホイストの位置が同じ通路内、つまり列 $x$ から列までにない場合${x}^{\mathrm{^{\prime}}}$ は、直線移動時間の多くのセグメントごとに、通路 $y$ から通路 ${y}^{\mathrm{^{$ までprime}}}\) は乗り換え通路時間のいくつかのセグメントによって計算されるため、シャトルの運行時間は直線移動時間のセグメント数と乗り換え通路時間のセグメント数の合計になります。各直線セクションの時間は (1) の解と同様で、各セクションの車線変更にかかる時間は次のとおりです。

通路が最初の通路からもう一方の $y$ 通路まで続く場合、4 方向シャトルの走行に必要な時間は次のとおりです。

ホイストの垂直方向の時間

倉庫ピックアップの 1 階までの通路端ホイストの初期位置、つまり $m$ 階から 1 階まで、または 1 階から ${m}^{\ mathrm{^{\prime}}}$ 時間は:

トンネル終端のホイストの初期位置から目標貨物レベルまで、つまり $m$ レベルから ${m}^{\mathrm{^{\prime}}}$ までの時間、は：

インバウンド操作の時間ベースのスケジューリングモデル

ケース 1 入庫する商品の目標荷位置が存在するフロアに空の四方向シャトルがあり、同時にシステムに使用可能なホイストがある場合、四方向シャトルとホイストの動作手順を分析し、動作時間を計算します。目標位置が倉庫層にある場合、ホイストが商品を運ぶのにかかる動作時間は 0 です。

4 方向シャトルの動作手順: 1. シャトルの開始位置は、通路エレベータ口の端までの無負荷動作です。 2. シャトルカーが商品を目的の位置まで送ります。

ホイストの操作手順: 1. ホイストは空の状態で倉庫の床まで移動します。 2. ホイストは商品を目的の貨物フロアまで輸送します。

システムは並列動作しており、4 方向シャトル運転ステップ 1 とホイスト運転ステップ 1、2 が同時に並行して実行されます。

動作時間は式(1)で計算されます。（7）。

対象場所が倉庫の 1 階で、${T}_{1Ei}, {T}_{2Ei}$ が 0 の場合、4 方向シャトル動作ステップ 1 とホイスト動作ステップ 1 2 つは並列操作です。 4 方向シャトルがステップ 1 を完了する前に、まずホイスト動作を待つ必要があります。ホイストがステップ 1 と 2 を完了する前に、まず 4 方向シャトルが動作ステップ (1) を完了するまで待つ必要があります。したがって、最も長い作業時間がかかる部分が完成した部品となります。

ケース2 保管する物品の目的位置があるフロアには無料の4方向シャトルが存在しないが、他のフロアには無料の4方向シャトルがあり、システム内に空きホイストがある場合、4方向シャトルとホイストの動作ステップを分析し、動作時間を計算します。

4 方向シャトルの操作手順: 1. シャトルは開始位置からスタートし、ホイスト入口の通路の端まで空で走行します。 2. シャトルはホイストに従って目的の荷物位置がある層まで荷物を運びます。

ホイストの操作手順: 1. ホイストは、4 方向シャトルが配置されている層まで空で動作します。 2. ホイストはシャトルを目的の貨物が存在する層まで運びます。 3. ホイストは空のまま倉庫の床まで走行します。 4. ホイストは目的の荷物が存在する層まで荷物を運びます。

システムは並列動作しており、4方向シャトル運転ステップ1とホイスト運転ステップ1が並行して動作します。

動作時間は式(1)で計算されます。 (8)。

ケース 3 目的の貨物位置が存在する層には空きの 4 方向シャトルはありませんが、他の層には空きの 4 方向シャトルがあり、4 方向のシャトルを分析するシステム内に利用可能なホイストが 3 つ以上あり、ホイストの動作手順と動作時間の計算。

4 方向シャトルの操作手順: 1. シャトルの開始位置が荷降ろされ、レーンホイスト口の端まで走行します。 2. ホイストを使用して目標貨物レベルまで往復し、目標貨物レベルまで商品を運んだ後の層が配置されます。

ホイストの動作ステップは、ホイスト 1 動作とホイスト 2 動作に分かれています。

ホイスト 1 の操作手順: 1. 層が存在する 4 方向シャトルまでホイスト無負荷運転を行います。 2. ホイストは、層が存在する目標貨物レベルまでシャトルを輸送します。

ホイストの 2 つの操作手順: 1. ホイストは空の状態で倉庫の床まで移動します。 2. 配送シャトルを吊り上げ、目標レベルまで移動します。

システムは並行して動作し、4 方向シャトルの動作ステップ 1 とホイスト 1 の動作ステップ 1 が同時に並行して動作します。ホイスト 1 の動作ステップ 1 と 2 とホイスト 2 の動作ステップ 1 と 2 は、同時に並行して動作を実行します。動作時間は式(1)で計算されます。 (9)。

したがって、最初の出荷の作業の開始から最後の出荷の倉庫作業の完了までの、倉庫作業のバッチが完了するまでの合計時間。

式を参照してください。 (10) ここで、${T}_{S}$ は最初の受信タスクの開始時刻、${T}_{E}$ は最後の受信タスクの終了時刻です。

アウトバウンド操作の時間ベースのスケジューリングモデル

ケース 1 荷物のピックアップフロアに空の四方向シャトルがあり、システム内に空きホイストがある場合、四方向シャトルとホイストの動作ステップを分析し、動作時間を計算します。。

4 方向シャトルの動作手順: 1. シャトルは、商品をピックアップするために目標位置に降ろされた状態で走行を開始します。 2. シャトルは通路のエレベーター口の終点まで商品を運びます。

ホイストの操作手順: 1. ホイストは目標貨物レベルまで空で動作します。 2. ホイストが貨物を倉庫レベルまで輸送します。

並列協調システム運転：4方向シャトル運転ステップ1、2、ホイスト運転ステップ1。

動作時間は式(1)で計算されます。 (11)。

4 方向シャトル動作ステップ 1、2 と巻き上げ動作ステップ 1 が並行動作の場合、四方向シャトルが最初にステップ 1、2 を完了すると、巻き上げ動作を待つ必要があります。ホイストが最初にステップ 1 を完了すると、4 方向シャトルが動作ステップ 1 と 2 を完了するまで待つ必要があります。したがって、最も時間がかかる操作が完了します。

ケース 2 商品が集荷される層には無料の 4 方向シャトルはありませんが、他の層には無料の 4 方向シャトルがあり、4 方向シャトルとホイストの動作を分析するシステムには利用可能なホイストがあります。ステップと動作時間を計算します。

4 方向シャトルの操作手順: 1. シャトルは開始位置からスタートし、空荷のまま通路ホイストの端まで走行します。 2. シャトルは荷を降ろした状態で通路ホイストの終端から目標位置まで走行し、商品をピックアップします。 3. シャトルは商品を通路ホイストの端まで運びます。

ホイストの操作手順: 1. ホイストは、アイドル状態の 4 方向シャトルが配置されているレベルまで空で動作します。 2. ホイストは、目標貨物位置が位置するレベルの通路端ホイスト入口まで 4 方向シャトルを搬送します。 3. ホイストが荷物を倉庫の 1 階まで運びます。

システムの並行および協調動作: 4 方向シャトル動作ステップ 1 およびホイスト動作ステップ 1 (式 12 を参照)。

時間関数 ${T}_{2}^{\mathrm{^{\prime}}}$ の式は、 ${T}_{1}^{\mathrm{^{ \プライム}}}$

したがって、アウトバウンド操作のバッチを完了するための合計時間は、最初の出荷の操作の開始から最後の出荷のアウトバウンド操作の完了までとなります。

確立された複数の4方向シャトルスケジュールの数学的モデルによれば、インバウンドタスクとアウトバウンドタスクは、異なる運行段階でリフトを選択するためのシャトルを選択する問題に分解されます。さらに、改良された遺伝的アルゴリズムを使用して、客観的な最適解が計算されます。クロスオーバーとコンパイル方法の最適化の選択における遺伝的アルゴリズムのタスクの組み合わせのエンコードとデコードの特性に従って、タスクの各グループは、動的道路ネットワークとタイムウィンドウベースの改善された \({A}^{*}\ ) アルゴリズムを使用して、4 方向シャトルの水平方向のパスをナビゲートし、安全で競合のない最適化パスを探します。これで、操作の経路計画全体が完了します。

以前のインバウンドおよびアウトバウンド操作用に構築されたモデルでは、4 方向シャトルがバッチ操作で使用されます。同時出荷操作の最大数は 4 方向シャトルの数によって制限されるためです ${R}_{count} $ システム内のホイスト数 ${E}_{count}$ に応じて、システム内の並列操作タスクの最大数は ${C}_{batch}=\mathrm{ min}({R}_{count},{E}_{count})$。次に、システム内の運用プロセスに応じたスケジューリングリソースの使用は、インバウンド運用ケース 3 と同様に、4 方向シャトルの割り当てとカーゴリフターの割り当てに分解できます。システムのスループットレートを向上させるために、運用タスクは、 2 台のリフターを同時に使用します。1 台はシャトルをターゲット層に配送し、もう 1 台は貨物をターゲット層に送ります。他のジョブのケースでは、ジョブを完了するために 1 つのホイストのみが割り当てられ、この章のモデルではそれらに仮想ホイストを割り当てます。システムジョブ $(\mathrm{1,2},\dots ,N)$ の処理に関するこのスケジューリングモデルによれば、ジョブシーケンスのコーディングとシステムリソースの 3 回の割り当てとして抽象化できます。 (1) 割り当て4方向シャトル。 (2) ホイスト $B$ を割り当てる。 (3) ホイスト $C$ を割り当てます。 (ジョブに 2 台目のホイストが必要ない場合、仮想リフトが割り当てられ、目的関数の計算のこの段階ではジョブ時間は消費されません)。したがって、実二次元行列エンコーディングを実行するためのシステムタスクジョブのシリアル番号、ホイストのシリアル番号、および 4 方向シャトルのシリアル番号に従って、生成される行列の行番号は $P={J}_{count}/{ C}_{batch}$ (非整数の除算、最後の行は 0 で終わります)、列数は $3{C}_{batch}$、つまり ${W}_{{ P}^{*}3{C}_{バッチ}}$。

式を参照してください。 (13)、行列 ${W}_{{P}^{*}3{C}_{batch}}={A}_{{P}^{*}{C}_{batch} }*{B}_{{P}^{*}{C}_{バッチ}}*{C}_{{P}^{*}{C}_{バッチ}}$、行列 $A $ はシステムジョブマトリックスであり、そのメンバーはジョブバッチ番号に対応します。行列 $B$ は、この論文で構築されたモデルで示されているように、ホイスト割り当て行列です。 $B$ 行列と $C$ 行列は同じ行内の 1 つの操作に関するものであり、行列に同じホイスト番号を持つことはできません。また、エレベーターコードは別の行で再利用できます。行列 $B$ は、この操作のシステムで使用されるホイストの数を示すリフトの解です。 $C$ は、利用可能な 4 方向シャトルがない場合に限り、エレベーターの追加の解になります。タスクが配置されているシステム内で、同時に $C$ 行列は、利用可能なリフトが 3 つ以上ある場合、つまりシステムエントリモデルケース 3 の操作に関与します。無効な解が生成されないようにするため、ターゲット演算層と $A$、$B$ 行列の 4 方向シャトルサブタスクが終了する層が一致する場合、$C$ 行列の対応する行は次のようになります。このエンコード制約の目的は、後の演算子が使用するための拡張された解空間を提供することです。たとえば、$({R}_{count}<{E}_{count})$ の場合、システムの最大同時実行数は ${C}_{batch}={R}_{count}\ )、行列 \(A$ の各行の列番号は、対応する 4 方向シャトル車両のエンコーディングを示し、行要素は ${X}_{i}=({a}_{i1 }、{a}_{i2}、\ドット、{a}_{i{C}_{バッチ}};{b}_{i1}、{b}_{i2}、\ドット {b}_ {i{C}_{バッチ}};{c}_{i1,}{c}_{i2},\dots ,{c}_{i{C}_{バッチ}})$。タスクの数が ${a}_{i3}=48$ の場合、$No. 3$ の 4 方向シャトルがこのタスクに使用されます。 ${b}_{i3}=2$ は、ホイスト 2 番がバッチ $i$ の 3 番目の 4 方向シャトル、つまり 4 方向シャトル $No. 3$ と連携して動作することを示します。この操作では、ホイスト $No. 2$ が連携してタスク $No. 48$ の操作を完了します。タスク $No. 48$ の目標在庫が ${J}_{ 48}=(\mathrm{4,5},7)$、シャトル $No.3$ の座標は ${R}_{3}=(\mathrm{2,3},7) です$。これは、ターゲット操作レベルとこの操作で使用される 4 方向シャトルが同じレベルにあることを意味します。 7. ターゲット母集団 ${c}_{i3}=0$ をコーディングまたは生成するとき。前の章でインバウンドの状況を説明するときの 3 つ。 ${c}_{i3}=6$ は、この番号 48 のタスクが 4 方向シャトルカー $No.3$、ホイスト $No.2$、ホイスト \ によって完了されることを意味します。 (No.6\) 協力中この時のシャトルカーの初期位置は階層内にあり、タスクの対象棚位置は同階層ではありません。

上記で作成した 2 次元実数行列のコードでは、各行列は個人を表します。3 つの行列 $A,B,C$ は個人の異なる染色体を表し、異なるコードはさまざまな遺伝子に相当します。個人から母集団を生成するより一般的な方法は乱数生成法であり、無効な個人の生成を避けるためにこの論文でリストされているモデル制約が使用されるため、この論文では制約付きの乱数生成法を使用します。 $({R}_{count}<{E}_{count})$ の場合、行列 $A$ は $(\mathrm{1,2},\dots ,N)$ になります。異なるタスクのシリアル番号のランダムな組み合わせであり、行列 $B$ と $C$ の各行はリフトアンドフォールコードのランダムな組み合わせですが、単一の行を繰り返すことはできません。

この論文では、「目的関数の値が小さいほど適応度が高くなる」という最大化規則を採用します。システムバッチ内のインバウンドおよびアウトバウンド操作によって消費される時間は負ではない値であり、目的関数の解の目標として設定できます。コーディングモデルに見られるように、システムがバッチジョブ $(\mathrm{1,2},\dots ,P)$ バッチを使用していることがわかります。システムリソースのバッチ順次占有が操作の流れになります。バッチ 1 のリソースがジョブを完了すると、リソースを解放して、後続のバッチの同じ列で表されるタスクに割り当てて処理することができます。システムの異なる行にあるタスクは、時間的に重複する可能性があります。たとえば、1. ${a}_{i3}=48$ は、$タスク 48$ がバッチ内の 4 方向シャトル $No.3$ を割り当てたことを示します。 2. ${a}_{i3}=96$ は、$タスク 96$ がバッチ内の 4 方向シャトル $No.4$ を割り当てたことを示します。 3.${a}_{(i+1)4}=52$ は、$タスク 52$ がバッチ $i+1$ で 4 方向シャトル $No.4$ を割り当てたことを示します。。次に、4 方向シャトル $No.4$ が $タスク 96$ を完了し、$タスク 52$ に進みます。シャトル 3 による $タスク 48$ の実行に、バッチ $i$ および $i+1$ の $タスク 96$、$タスク 48$、および $52$ よりもはるかに長い時間がかかる場合）に属するものは時間的に重複します。この論文では、バッチ全体 (バッチ $1$) の開始時刻 ${T}_{1}$ と最後のバッチ (バッチ \) の最後のタスクの終了時刻の差を選択します。 (P\)) を目的関数 ${T}_{sum}={T}_{P}-{T}_{1}$ として表し、次の合計の最大値に分解できます。式 1 に示すように、コーディングモデル $A ,$ の行列の各列で完了するタスク。 (15)。

適応関数の大きさは、解決すべき問題オブジェクトの具体的な意味に大きく関連して決定され、一般に適応度は目的関数を変形することによって得られる。目的関数から適応性を解く方法は、対応する適応性を得るために、目的関数の直接線形変換、指数変換、べき乗指数変換、目的関数値の切り捨てなどに分けることができます。これらのさまざまな変換はすべて影響力を持ち、効率的な集団多様性とアルゴリズムの収束をもたらす可能性があります 32、33、34、35。

ここで、適応関数は、目的関数から単純なパワーインデックス変換を実行することによって取得されるように選択されます (式 16 を参照)。

この論文で構築されたモデルと適応関数は非負であり、選択演算子はルーレット選択方法で使用できます。ルーレットの選択は、基本的にプットバックを伴うランダムなサンプリング方法です。集団の各個人は、その適応性に応じて対応する長さの間隔にマッピングされ、各個人の間隔の長さはその適応値の値に比例します。適応力が高いほど、選抜操作で選ばれる可能性が高くなります。乱数が生成され、その間隔に応じて対応する個体が選択されます。その後、必要な個体数が得られるまでこのプロセスが繰り返されます。

適応度に応じて、各個人の選択確率は式 (1) で見ることができます。 (17) 次のように:

各個人の累積確率は、選択確率 (式 17 を参照) から次のように計算されます。

累積確率はターンテーブル上のセクターのサイズに対応し、セクター領域が大きいほど選択が容易になります。 $P({x}_{i})$ は個人 $i$ の選択確率であり、$fitness({x}_{i})$ は個人 $i $、${N}_{group}$ は母集団内の個人の総数を表します。

任意の 6 人の個人を選択します。各個人の選択確率は次のとおりです。各個人の選択確率と累積確率を表 1 に示します。

累積確率を計算した後、計算した個別累積確率値を長さ１の線分上に左端の始点を０点としてラベリングする。区間 $(\mathrm{0,1})$ では、6 つの数値がランダムに生成され、選択される個人は $1, 2, 4, 4, 5, 6. No.4$ が 2 回選択されます。、選択される個体の確率が大きい場合は、選択される個体の確率が大きい。小さい個体は選択されない可能性もあり、選択された個体が全て同じである可能性もある。ランダムに生成された個別番号を図 3 に示します。

計算された個体の累積確率を線分で表し、計算された個体の累積確率値を長さ１の線分上に左端の始点を０点としてラベリングする。 6 個の番号が (0,1) の間隔でランダムに生成され、図に示すように、選択された個体は 1、2、4、4、5、6 でした。個体番号 4 は 2 回選択されました。

この論文では、個別のコーディングは 3 つの行列で構成されます。たとえば、システム内の 4 方向シャトルの数 ${R}_{count}$ が 3 の場合、操作タスクの数 ${J} _{count}$ は 9 で、システム内のホイストの数 ${E}_{count}$ は 4 です。個別のコーディングは 3 セットの $3*3$ 行列 $ABC, $ は式で見ることができます。 (19)。

母集団個人の $A$ 行列はタスクコード化行列であり、各 $A$ 行列はタスクコードの並べ替えられた組み合わせです。 $BC$ の各行はリフトとしてコード化され、ジョブバッチごとに異なる行がコード化されます。この符号化機能に従って、この論文では 2 つの交点が選択され、その交点は行列 $A$ と行列 $BC$ です。交差演算では、行列は行ごとに 1 次元行列と 2 次元行列に変換されます (式 20 を参照)。

交叉操作では、2 人の異なる親個体による ${P}_{3\times 9}^{1}={A}_{3\times 3}^{p1}{B}_{3\times 3 }^{p1}{C}_{3\times 3}^{p1}$ および ${P}_{3\times 9}^{2}={A}_{3\times 3}^ {p2}{B}_{3\times 3}^{p2}{C}_{3\times 3}^{p2}$、それぞれ、3 セットの行列値が相互に交差して新しい個体を生成します $ {N}_{3\times 9}^{1}={A}_{3\times 3}^{n1}{B}_{3\times 3}^{n1}{C}_{3\ 3}^{n1}$ を掛けます。ここで、2 つの親行列が相互に演算して子行列 $A$ を生成します。つまり、2 つの $A$ 行列の親が交差再編成して子行列 \ を生成します。 (A\)。 $BC$ は親世代で交差し、子世代で $BC$ を生成します。これは、それぞれ $A$ 行列と $BC$ 行列の交点における 2 つの交差点です。クロスオーバーが実際の意味を持ってエンコードされるようにするため、間にクロスオーバー操作は実行されません。 2 つのクロスオーバーは個別に実行され、個体の 1 つのクロスオーバー操作が完了します36。手順は次のとおりです。

ステップ 1: 2 次元行列をエンコードするタスクの場合、上に見られるように、クロスオーバープロセスで ${A}_{3\times 3},$ が 2 次元行列を 1 行 1 列の実数に変換します。行拡張によって行列エンコード ${A}_{1\times 9}^{\mathrm{^{\prime}}}$ を実行すると、クロスオーバーが完了して子が生成され、その逆演算が実行されて次から変換されます。 1 次元行列から 2 次元行列へ。単一行 1 次元行列演算のプロセスでは、単純な交換交叉後の個体内での遺伝子重複の問題を回避するために、サブツアー交換交叉が使用されます。具体的な演算手順を図4と式4に示します。 (21a および b)。

遺伝子交叉操作時の親の遺伝子マッピング。

2 つの子孫を生成します (図 5 および式 22a および b を参照)。

遺伝子交叉操作中に生成された 2 人の子孫の遺伝子地図。

ステップ 2: リフターエンコーディング 2 次元行列 ${BC}_{3\times 6}$ の場合、エンコーディングの実際の意味に従って、その行に重複したエンコーディングがあってはならず、同じエンコーディングが可能です。さまざまな行 (つまり、さまざまなタスクバッチ) で使用できます。交叉操作のために選択された 2 つの個体の異なる親が 2 行でランダムに選択され、サブトレース交換交叉によって 2 つの異なる個体が生成されます (式 23a および b を参照)。

$親 1$ と $親 2$ のそれぞれの任意の行を交叉用に選択し、$親 1$ の最初の行と $親 2$ の 3 番目の行を選択すると、親遺伝子がは次のとおりです (図 6 を参照)。

$親 1$ の最初の行と $親 2$ の 3 番目の行が交叉用に選択され、この時点での親の遺伝子マップが作成されました。

2 つの子孫を生成します (図 7 を参照)。

$親 1$ の最初の行と $親 2$ の 3 番目の行が交叉用に選択され、その時点で 2 つの子の遺伝子マップが生成されます。

2 つの子孫個体を生成します (式 24a および b を参照)。

生成された部分個体に無効な解が多すぎると収束が遅くなる、または収束が困難になるという問題を回避するために、生成された新しい個体の追加の解行列 $C$ も交差プロセスで制約され、無効な解が多すぎるのを回避します。入力モデルのケース 3 を満たさない解は破棄され、満足のいく個体が生成されるまで交叉が継続されます。

ステップ 1 と 2 を実行した後、次のように 2 つの新しい個体が取得されます (式 25a と b を参照)。

子トレーススワップクロスオーバー法は、一方の親でゲノムを選択し、もう一方の親でこれらの選択された遺伝子の位置を見つけるために使用されます。一方、選択されていない遺伝子は変更せずに、2 つの親の染色体遺伝子の位置を親の順序で交換します。遺伝子を選択して2つの子孫を生み出します。この方法により、クロスオーバー後のタスクの重複の問題が回避されます。

この論文では、コーディングモデル内の特定の組み合わせには、タスク番号、リフト、ラダーコーディングなど、特定の意味と対応する制約があります。コンパイル方法には相互変異法を用いる。組み合わせ最適化問題では、遺伝子の各ビットの値は一意であり、「順列コーディング」と呼ばれます。これは、遺伝子のこの特徴が突然変異操作後でも維持されなければならないことを意味します。そうしないと、結果として得られる子孫は無効なソリューションになります。相互変異アルゴリズムは、個人の遺伝子内の 2 つの断片をランダムに識別し、相互変異を実行します。これら 2 つのセグメントには同じ量のコードが含まれている必要があります。これは次のように示されます (式 26 を参照)。

行列の行を任意に選択します。行列の 2 行目が選択されている場合、行列の 1 列目と 3 列目が交換され、行列の 1 列目と 2 列目も交換されます。

交換された遺伝コードは次のとおりです (式 27 を参照)。

確立された時間最小ベースの複数の 4 方向シャトルマルチリフトアクセス操作の最適化と経路最適化の数学的モデルでは、基本的な遺伝的アルゴリズムでは、クロスオーバー操作とバリエーション操作の確率が固定されているため、さまざまな操作タスクでの入力に対して良好な収束を達成することが困難になる可能性があります。したがって、この論文では、そのクロスオーバーオペレーターとバリエーションオペレーターが進化の過程で別々にサンプリングされ、自動適応できるように調整されます。ジョブタスク、4 方向シャトル、およびホイストに関する情報を含む個別のマトリックスエンコーディングが設計されています。遺伝的演算子は、アルゴリズムの演算子の確率と適合関数を改善するために、そのエンコーディングに従って設計されています。本論文で設計した適応遺伝アルゴリズムにおける交叉演算子 ${P}_{c}$ と変動演算子 ${P}_{m}$ の数式は以下のとおりである 37,38,39,40 ,41,42 (式 28a および b を参照)。

この式から、大まかな探索プロセスが集団多様性の維持に役立つように、最初の段階ではより大きな交叉確率と変動確率が選択され、その後、最適な探索プロセスが破壊されないように詳細な探索のためにより小さな値に調整されることがわかります。解決し、収束を加速します。改良されたアルゴリズムの収束テストは、表 2 にリストされているテスト関数を使用してテストされます。

テスト関数の収束曲線を図 1 と 2 に示します。 8、9、10。

Ackley の関数でテストされた改良されたアルゴリズムの収束曲線。

Sphere テスト関数を使用して、改良されたアルゴリズムの関数収束曲線をテストします。

Rosenbrock テスト関数を使用して、改良されたアルゴリズムの関数収束曲線をテストします。

4 方向シャトルでよく発生する競合には、ノード競合、フェーズ競合、キャッチアップ競合、ブロッキング競合があります。システムが構築するモデルでは、同階層の四方向シャトルが同時に動的に連携し、同階層の倉庫の物理的特徴はマトリックスメッシュ構造で構成される通路と棚である。シャトルトラックは、同じレイヤーの 4 方向シャトルをスケジュールするときに自然に図に抽象化でき、各転換点は図の頂点に対応します。旋回前の各区間における加速から停止までの各走行可能距離を円弧の図に抽象化できます。リフト入口から貨物経路までのシャトルの上りタスク、または貨物経路からエレベーター入口までの下りタスクを解くことは、有向非巡回加重グラフの最短経路を解く問題に変換できます。倉庫の特性の包括的なシャトル物理構造に基づいて、本論文では、ユークリッド距離を評価関数計算として使用するヒューリスティック ${A}^{*}$ アルゴリズム 43,44,45,46 を選択します。無効なポイントのドロップを回避し、検索効率を高めます。倉庫の建設が完了し、四方向シャトルの物理的な軌道が固定されているため、システムの起動時に各層の道路ネットワークのグラフを静的に初期化することで、四方向シャトルの経路探索タスクの計算が高速化され、 4 方向シャトルの開始位置から直接到達できる円弧の重みを修正する必要があります。シャトルの衝突の問題は、経典探索の計算の過程で 4 方向シャトルがトラックを占有する時間を使用して、グラフ内のアークウェイトの時間窓補正を実行することによって、賢く回避できます。この論文では、4 方向シャトルのパスはバックエンドシステムによってグローバルにスケジュールされ、4 方向シャトルは無線デバイスを使用してバックエンドと通信し、4 方向シャトルには距離測定レーダー衝突回避装置が装備されています。同じバッチ内のタスクでは、4 方向シャトルのコード番号が経路計算の順序として使用され、コードが小さいほど優先度が高くなります。

実行される現在のタスクでは、4 方向シャトルの初期位置 ((${x}_{i},{y}_{j},{z}_{k}$) を使用します。 (ノード間の 4 方向シャトルの位置 $a,b$ が $w$ を指していると仮定します)、(${x}_{i}^{\mathrm{^{ \prime}}},{y}_{i}^{\mathrm{^{\prime}}},{z}_{k}^{\mathrm{^{\prime}}}$) (仮定ポイント間のターゲット位置 $h,i$ が $q$ のポイントであることを示します。そのウェイトマップは 4 方向シャトルの位置に応じて修正でき、開始位置を追加してポイントに直接指定することもできます。さらに、これら 2 つの頂点が回転せずに直接到達できる円弧が修正されます (図 11 および 12 を参照)。

4 方向シャトルのアクセスパスの重み付け図 (図内の三角形は 4 方向シャトルの位置を表し、四角形はアクセス貨物の位置を表します)。

4 方向シャトルが商品にアクセスするために移動できる経路の重みを使用して、A* アルゴリズムによってこの重みマップ内の一連の円弧と頂点を含む最小経路を見つけることができます。

この時点で、初めて最小パスを見つけるために必要なデータ構造が完成し、${A}^{*}$ アルゴリズムを使用して、一連の円弧と頂点を含む最小パスを見つけることができます。上の加重グラフ。確立された検索重みマップに基づいて、上記の ${A}^{*}$ アルゴリズムに従って最小距離パスの反復検索を実行することができます。

$H(n)$ は、次のように、点からターゲット点までに消費される時間量のユークリッド重み付けとして設計されます (式 28a および b を参照)。

従来の ${A}^{*}$ アルゴリズムでは、システムの並列動作において同じ層に複数の 4 方向シャトルが存在する可能性があり、各単一ユニットの経路計画により同じ層内で衝突が発生する可能性があります。同時にレーン。この論文では、${A}^{*}$ の解に使用されるグラフに時間窓で再度重み付けを行い、シャトル車両の実行タスクの順序に従って制約された経路を解決または計画します。

タイムウィンドウの修正ルールは次のとおりです。 1. タイムウィンドウ、単調増加計算に基づくタイミングルール。 2. 時間窓は最小の円弧として計算され、4 方向シャトルが円弧に入り、円弧を出るまでの期間がその円弧の時間窓です。 3. その円弧が時間 $\left[{T}_{A},{T}_{B}\right]$ 内で 4 方向シャトルが占める軌道である場合、この時間枠内では、その2 つのノード $A,B$ は競合衝突の危険性があり、タイムウィンドウによってシステム $G.$ のグローバルグラフが更新されます $A,B$ が位置するアークと到達可能なアーク$A,B$ を直接使用して、時間枠内で更新されます。図 13 の $\overset{\ lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{d} e$ 弧の点 e で矛盾がある場合、 $ d,e$ の円弧とその頂点に隣接する円弧が増加し、重み ${ T}_{max}$ を増やすには破線のパスによって消費される時間が必要になります。

点 e で $\overset{\ lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{d} e$ の影響を受ける円弧はパスの競合です。

本稿では、実際の倉庫の四方向シャトルシステムを参考に、タスク操作の時間最小化改良遺伝的アルゴリズムと経路探索の時間窓改良A*アルゴリズムに基づくシミュレーション演算例を実装する。計画を作成し、シミュレーションの実験結果を分析して、スケジュールの最適化に関する結論を導き出します。会社 A は大企業で、その倉庫の 1 つは $10*20*8$(10 通路、20 列、8 フロア) の 4 方向シャトル保管システムです。モデルの妥当性を検証するために、入出力操作データのバッチが取得され、4 方向シャトル保管システムのパラメーターが表 3 に示すように設定されます。

4 方向シャトルシステムでは、4 台の 4 方向シャトルと 4 台のホイストが稼働しています。 4 方向シャトルの初期位置は $(\mathrm{4,2},7)、(\mathrm{1,7},5)、(\mathrm{4,6},5)、(\ mathrm{3,2},1)、(\mathrm{6,5},2)$、それぞれシリアル番号 (${R}_{1}$)(${R}_{ 2}$)(${R}_{3}$)(${R}_{4}$)。 4 方向シャトルとホイストの位置は $(\mathrm{2,0},4)、(\mathrm{4,0},1)、(\mathrm{5,0},3)、( \mathrm{6,0},2)$、シリアル番号は ${E}_{1},{E}_{2},{E}_{3},{E}_{4) }$。特定のドキュメントには、2 つのアウトバウンドタスクと 2 つのインバウンドタスクを含む、インバウンドタスクとアウトバウンドタスクのバッチがあり、インバウンドタスクとアウトバウンドタスクの具体的な情報を表 4 に示します。 4 方向のシャトルとホイストのスケジュールを求めます。タスクのバッチを完了するための全体的な動作パス時間を最小限に抑えるソリューション。

プログラムの実行後、反復プロセスと 2 つのアルゴリズムの関連データが取得されます。古典的なアルゴリズムでは、母集団のサイズは 20、反復の最大数は 100、他のパラメーターの交差確率は 0.5、変動確率は 0.004 です。改良された遺伝的アルゴリズムでは、自己適用可能な交叉区間は $[0.5, 0.9]$ であり、変動確率区間は $[0.001, 0.0008]$ です。 2 つの遺伝的アルゴリズムは独立して 15 回実行されます。

表 5 に示すように、改良されたアルゴリズムは解の安定性と収束速度に明らかな利点があり、最適解の平均値を初めて取得することにより、収束効率は従来のアルゴリズムよりも優れています。さらに、分散と歪度によって安定性が向上していることがわかります。

図 14 に示すように、表 5 に入力されたデータによれば、本論文におけるモデル母集団の解空間の最大数は 4 つのアルゴリズムの配置結果の数であるため、両方のアルゴリズムセットは最終的に最適解に収束します。シャトルとエレベーターとそのタスク、および各集団の個別のソリューションは個別です。ただし、グラフは、この計算では、改良されたアルゴリズムが約 20 回最適解に収束することを示しています。ただし、古典的なアルゴリズムは約 35 回最適化されます。ただし、古典的なアルゴリズムは約 35 回で最適化されます。このシミュレーションタスクでは 4 つのジョブのみが使用されており、タスクの数の規模が増加するにつれて、改善されたアルゴリズムの収束効率により明らかな利点が得られます。アルゴリズム演算結果によると、表 6 に示す最適解が得られます。

改良されたアルゴリズムと従来のアルゴリズムの収束傾向は、改良されたアルゴリズムが解の安定性と収束速度において明らかな利点を持っていることを示しています。

上の表では、4 方向のシャトルとホイストのスケジュールシーケンスが次のとおりであることがわかります:$({R}_{1})\to (\mathrm{4,9},7)\to {E}_ {1}, ({R}_{2})\to (\mathrm{5,11,5})\to {E}_{2},({R}_{3})\to (\mathrm {2,7},3)\to {E}_{3} 、 ({R}_{4} )\to (\mathrm{3,6},4)\to {E}_{4}\ )、\(({R}_{1})$ と $({R}_{3})$ の 4 方向シャトルが受信操作を完了します、$({R}_{2}) $ と $\left({R}_{4}\right)$ の 4 方向シャトルがアウトバウンド操作を完了します。オペレーション。上り動作の合計時間は 21.3 秒、合計パスは 23 m です。アウトバウンド操作の合計時間は 24.71 秒です。全長は30mです。

この論文の主な作業は、4 方向シャトルシステムのアクセスおよび退出タスクのスケジューリングと自動経路検索を最適化することです。複数の四方向シャトルと複数のリフトを備えた四方向シャトルシステムについて、四方向シャトルシステムの流れを解析し、最短時間に基づくスケジュール最適化のための数理モデルを構築します。この論文のモデルでは、改良された遺伝的アルゴリズムを使用してタスク計画を解決し、改良された ${A}^{*}$ アルゴリズムを使用して棚層内のパスを最適化し、最適化された数学モデルを解決します。モデルの特徴。各層で並列動作する 4 方向シャトルの競合のない最適な経路が探索され、4 方向シャトルシステムの競合制御は、動的グラフ理論とタイムウィンドウベースの ${A}^{* }$ アルゴリズム。まず、本論文は、四方向シャトルシステムの保管レイアウトと構造的特徴に対する最短時間のインバウンドおよびアウトバウンド操作タスクをスケジュールするための、改良された遺伝的アルゴリズムに基づく最適化モデルを確立する。第二に、本論文は、四方向シャトルとホイストの並列運転と、移動方向制限のない四方向シャトルの自動経路探索のための革新的なアルゴリズム設計を提案する。インバウンドおよびアウトバウンド操作のタスクスケジューリング最適化モデルに従って,改良された遺伝的アルゴリズム解決モデルが提案される。複数の 4 方向シャトルが 1 つのレイヤーで並行して動作する場合、移動経路が重複する可能性があるため、動的な道路ネットワークとタイムウィンドウに基づく改良されたアルゴリズムを使用して、複数の 4 方向シャトルの動作中に障害物を回避します。同じ期間内に重複領域に到達するという競合。

現在の研究中に使用および/または分析されたデータセットは、合理的な要求に応じて責任著者から入手できます。

自動保管・検索システム

シャトルベースの保管と取り出し

早い者勝ち

自動車両保管・取り出しシステム

保管・取り出し

Lee、SG、Souza、RD、Ong、EK レール誘導車両によってサービスされる狭い通路の自動保管および取り出しシステム (AS/RS) のシミュレーションモデリング。計算します。インド 30(3)、241–253。 https://doi.org/10.1016/0166-3615(96)00025-5 (1996)。

記事 Google Scholar

福成 M. & マルボルグ、CJ 自動運転車両の保管および取り出しシステムの性能評価のためのネットワークキューイングアプローチ。ユーロ。Ｊ．Ｏｐｅｒ．解像度 193(1)、152–167。 https://doi.org/10.1016/j.ejor.2007.10.049 (2009)。

記事 MATH Google Scholar

Wauters, T.、Villa, F.、Christiaens, J.、Alvarez-Valdes, R. & Vanden Berghe, G. デュアルシャトル自動保管および取り出しシステムへの分解アプローチ。計算します。工業工学 101、325–337。 https://doi.org/10.1016/j.cie.2016.09.013 (2016)。

記事 Google Scholar

Tappia, E.、Roy, D.、de Koster, R.、Melacini, M. シャトルベースのコンパクトストレージシステムのモデリング、分析、設計に関する洞察。トランスペアレント科学。 51(1)、269–295。 https://doi.org/10.1287/tsc.2016.0699 (2016)。

記事 Google Scholar

Epp, M.、Wiedemann, S. & Furmans, K. 自律車両保管および取り出しシステムの性能評価に対する離散時間キューイングネットワークアプローチ。内部。Ｊ．Ｐｒｏｄ．解像度 55(4)、960–978。 https://doi.org/10.1080/00207543.2016.1208371 (2017)。

記事 Google Scholar

Tian、GD et al. 使用済みリチウムイオン電池のリサイクル: 主な課題と将来の研究動向を特定するための包括的なレビュー。持続する。エネルギー技術評価。 53、102447。https://doi.org/10.1016/j.seta.2022.102447 (2022)。

記事 Google Scholar

Zhao、X.ら。シャトルベースの保管および取り出しシステムの分析。 IEEE アクセス 8、146154 ～ 146165。 https://doi.org/10.1109/ACCESS.2020.3014102 (2020)。

記事 Google Scholar

Eder, M. 複数の深さのストレージを備えたシャトルベースのストレージおよび検索システムのパフォーマンス計算のアプローチ。内部。 J.Adv. メーカーテクノロジー。 107(1-2)、859-873。 https://doi.org/10.1007/s00170-019-04831-7 (2020)。

記事 Google Scholar

Ekren, BY & Akpunar, A. シャトルベースのストレージおよび取得システムのパフォーマンスを見積もるための、オープンキューイングネットワークベースのツール。応用数学。モデル。 89(2)、1678 ～ 1695 年。 https://doi.org/10.1016/j.apm.2020.07.055 (2021)。

記事 MathSciNet MATH Google Scholar

Ekren, BY AVS/RS 倉庫設計のための多目的最適化研究。内部。Ｊ．Ｐｒｏｄ．解像度 59(4)、1107–1126。 https://doi.org/10.1016/j.cor.2017.02.012 (2020)。

記事 Google Scholar

Hu、CH、Egbelu、PJ 無人搬送車システムにおけるアイドル車両のホーム位置を選択するためのフレームワーク。内部。Ｊ．Ｐｒｏｄ．解像度 38(3)、543–562。 https://doi.org/10.1080/002075400189293 (2000)。

記事 MATH Google Scholar

Saez, D.、Cortes, CE、Nunez, A. 遺伝的アルゴリズムとファジークラスタリングに基づく、複数車両の動的集配問題に対するハイブリッド適応予測制御。計算します。オペラ。解像度 35(11)、3412–3438。 https://doi.org/10.1016/j.cor.2007.01.025 (2008)。

記事 MATH Google Scholar

Chung, E. & Lee, HF 自動保管および検索システムの一般化された順序付け問題のための遺伝的アルゴリズム。内部。 J.サーブ。オペラ。情報 3(1)、90-106。 https://doi.org/10.1504/IJSOI.2008.017707 (2008)。

記事 Google Scholar

Wang, YY, Mou, SD & Wu, YH 多層シャトル倉庫システムのタスクスケジューリング。内部。Ｊ．Ｐｒｏｄ．解像度 53(19)、5884–5895。 https://doi.org/10.1080/00207543.2015.1012604 (2015)。

記事 Google Scholar

Li, Y.、Lim, MK、Tseng, ML コールドチェーンロジスティクスのための修正粒子群最適化に基づく環境に優しい車両ルートモデル。工業管理データシステム。 119(3)、473–494。 https://doi.org/10.1108/IMDS-07-2018-0314 (2019)。

記事 Google Scholar

Li, Y. シミュレーテッドアニーリングアルゴリズムに基づく物流物流車両経路の最適化に関する研究。上級マルチメッド。 2022、7363279。https://doi.org/10.1155/2022/7363279 (2022)。

記事 Google Scholar

Alnowibet, KA、Mahdi, S.、El-Alem, M.、Abdelawwad, M. & Mohamed, AW 制約付きグローバル最適化問題を解決するためのガイド付きハイブリッド修正シミュレーテッドアニーリングアルゴリズム。数学 10(8)、1312。https://doi.org/10.3390/math10081312 (2022)。

記事 Google Scholar

Liu, Y.、Zhang, SY & Hu, HY 待ち時間を考慮した複数衛星のダウンリンクスケジュール問題に対するタブリストを使用したシミュレーテッドアニーリングアルゴリズム。 Aerospace 9(5)、235。https://doi.org/10.3390/aerospace9050235 (2022)。

記事 Google Scholar

Kassaymeh, S. et al. バックプロパゲーションニューラルネットワークの最適化と、ハイブリッドサルプスウォームオプティマイザーベースのシミュレーテッドアニーリングアルゴリズムを使用したソフトウェア欠陥推定モデリング。知ってください。ベースのシステム。 244、108511。https://doi.org/10.1016/j.knosys.2022.108511 (2022)。

記事 Google Scholar

Lee, T. & Ueng, J. 負荷分散に関する車両ルートの問題に関する研究。内部。Ｊ．Ｐｈｙｓ．配布します。ロジスト。管理。 29(9–10)、646–657。 https://doi.org/10.1108/09600039910300019 (1999)。

記事 Google Scholar

Su、C. マルチ拠点物流システムの動的車両制御とスケジューリング。統合します。メーカーシステム。 10(1)、56–65。 https://doi.org/10.1108/09576069910247609 (1999)。

記事 Google Scholar

谷口 E.、トンプソン RG、山田 T.、Duin、ITS による RV 車両のルートとスケジュール。 City Logistics 137–174 https://doi.org/10.1108/9780585473840-007 (2001)。

谷口 E.、山田 T.、玉石 M. 移動時間に関するリアルタイム情報を使用した動的な車両ルートとスケジューリングをモデル化します。 21 世紀の交通と交通理論 329–347 https://doi.org/10.1016/B978-008043926-6/50019-1 (2002)。

谷口 E. & 山田 T. 都市物流に向けた時間枠を備えた信頼性の高い車両のルート設定とスケジュール設定。トランスポートのネットワーク信頼性 301–322 https://doi.org/10.1108/9781786359544-018 (2003)。

Yang, P.、Tao, PR、Xu, P. & Gong, YM マルチシャトル自動保管および取り出しシステムにおける二目的操作の最適化により、移動時間とエネルギー消費を削減します。工学最適。 https://doi.org/10.1080/0305215X.2022.2096881 (2022)。

記事 Google Scholar

Polten, L. & Emde, S. 自動保管および取り出しシステムにおけるマルチシャトルクレーンのスケジュール設定。ユーロ。Ｊ．Ｏｐｅｒ．解像度 302(3)、892–908。 https://doi.org/10.1016/j.ejor.2022.01.043 (2022)。

記事 MathSciNet MATH Google Scholar

Zhen、L.、Wu、JW、Li、HL、Tan、ZY、Yuan、YY 自動倉庫内で複数の種類の機器をスケジュールする。アン。オペラ。解像度 https://doi.org/10.1007/s10479-022-04935-6 (2022)。

記事 PubMed PubMed Central Google Scholar

Fandi, W.、Kouloughli, S. & Ghomri, L. 遺伝的アルゴリズムを使用したマルチシャトル AS/RS 寸法の最適化 - 複数通路構成のケース。内部。 J.Adv. メーカーテクノロジー。 120(1–2)、1219–1236。 https://doi.org/10.1007/s00170-022-08787-z (2022)。

記事 Google Scholar

Li、XW、Zhang、CR、Yang、WM & Qi、MY 自動倉庫向けのマルチ AGV の競合のないルーティングと動的ディスパッチング戦略。 iCatse International Conference on Mobile and Wireless Technology (ICMWT)/iTAIWAN ワークショップにて。議事録ペーパー。香港、香港。 6 月 25 ～ 27 日 https://doi.org/10.1007/978-981-13-1059-1_26 (2018)。

Roy, D.、Nigam, S.、de Koster, R.、Adan, I. & Resing, J. モバイルフルフィルメントシステムにおけるロボット保管ゾーン割り当て戦略。トランスペアレント解像度電子ログ。 122、119–142。 https://doi.org/10.1016/j.tre.2018.11.005 (2019)。

記事 Google Scholar

Hulagu, S. & Celikoglu, HB 車両運動ダイナミクスに基づくエネルギー消費と回収に関する電気自動車の位置ルーティングの問題。 IEEEトランス。知性。トランスペアレントシステム。 23(8)、10275–10286。 https://doi.org/10.1109/TITS.2021.3089675 (2022)。

記事 Google Scholar

Huda、RK および Banka、H。適合関数としてファジーラフセットを持つ PSO を使用した効率的な特徴選択方法。ソフトコンピューティング。 26(5)、2501–2521。 https://doi.org/10.1007/S00500-021-06393-X (2021)。

記事 Google Scholar

Hassan, A.、Anter, A. & Kayed, M. 新しいフィットネス関数を使用して最適化された方法でワイヤレスセンサーネットワークの寿命を延ばすための堅牢なクラスタリングアプローチ。持続する。計算します。知らせる。システム。 30、100482。https://doi.org/10.1016/j.suscom.2020.100482 (2021)。

記事 Google Scholar

Brookes, DH、Aghazadeh, A. & Listgarten, J. 適応度関数の希薄性と学習への影響について。手順国立アカド。科学。 https://doi.org/10.1073/PNAS.2109649118 (2022)。

論文 PubMed Google Scholar

Meysam, M.、Seyed, SF、Soodabeh, M.、Leyla, ST、Mirpouya, M. 複数製品、複数期間の在庫ルーティング問題に対する修正された適応遺伝的アルゴリズム。持続する。オペラ。計算します。 3、1～9。 https://doi.org/10.1016/J.SUSOC.2021.08.002 (2022)。

記事 Google Scholar

Xue, Y.、Cai, X.、Neri, F. 分類における大規模な特徴選択のための、間隔ベースの初期化と自己適応クロスオーバー演算子を備えた多目的進化アルゴリズム。応用ソフトコンピューティング。 J. 127、109420。https://doi.org/10.1016/J.ASOC.2022.109420 (2022)。

記事 Google Scholar

Tsai、CY、Liou、JJH、Huang、TM マルチプル GA 手法を使用してバッチピッキングの問題を解決: 移動距離と注文期限を考慮。内部。Ｊ．Ｐｒｏｄ．解像度 46(22)、6533–6555。 https://doi.org/10.1080/00207540701441947 (2008)。

記事 MATH Google Scholar

Chen、HW、Liu、SM、Magomedov、RM & Davidyants、AA 人工ニューラルインテリジェンスネットワークと組み合わせた遺伝的アルゴリズムによる、石油貯留層の流入性能関係曲線の最適化。エネルギー代表 7、3116–3124。 https://doi.org/10.1016/J.EGYR.2021.05.028 (2021)。

記事 Google Scholar

Vishnu、CR、Das、SP、Sridharan、R.、Kumar、PNR、Narahari、NS 信頼性が高く柔軟なサプライチェーンネットワーク設計モデルの開発: 遺伝的アルゴリズムベースのアプローチ。内部。Ｊ．Ｐｒｏｄ．解像度 59(20)、6185–6209。 https://doi.org/10.1080/00207543.2020.1808256 (2021)。

記事 Google Scholar

Saidat, S.、Junoh, AK、Muhamad, WZAW & Yahya, Z. タグチメソッドと遺伝的アルゴリズムによるジョブショップスケジューリングの修正。ニューラルコンピューティング。応用 34(3)、1963 ～ 1980 年。 https://doi.org/10.1007/S00521-021-06504-7 (2021)。

記事 Google Scholar

Duan, QF & Rane, D. インターネット時代の改良された遺伝的アルゴリズムに基づく地方産業活性化の道。計算します。知性。神経科学。 2022、1632224。 https://doi.org/10.1155/2022/1632224 (2022)。

記事 PubMed PubMed Central Google Scholar

Hua、ZM、Liu、ZY、Yang、LJ、Yang、L. リソースに制約のあるプロジェクトのスケジューリング問題を解決するための、タイムウィンドウ分解に基づく遺伝的アルゴリズムの改良。オートム。構造 142、104503。https://doi.org/10.1016/J.AUTCON.2022.104503 (2022)。

記事 Google Scholar

Zhang, Z.、Wu, J.、Dai, J. & He, C. 3D ネットワークレーダー環境におけるステルス無人航空機のための、修正された A-Star アルゴリズムによる最適な経路計画。手順研究所メカ。工学パート G J. Aerosp。工学 236(1)、72–81。 https://doi.org/10.1177/09544100211007381 (2022)。

記事 Google Scholar

Wang、DJ 改良された A* アルゴリズムに基づいた屋内モバイルロボットの経路計画。 J.清華大学ナット。科学。エドン。 52(8)、1085–1089 (2012)。

Google スカラー

Zhao, X.、Wang, Z. & Huang, CK 改良された A* アルゴリズムに基づいたモバイルロボットの経路計画。ロボット 40(6)、903 ～ 910。 https://doi.org/10.13973/j.cnki.robot.170591 (2018)。

記事 Google Scholar

Ma、L.、Zhang、HT、Meng、SJ、Liu、JY 改良された A* アルゴリズムに基づく火山灰領域の経路計画。 J.Adv. トランスペアレント 2022、9938975。https://doi.org/10.1155/2022/9938975 (2022)。

記事 Google Scholar

リファレンスをダウンロードする

ここに、査読者および編集者の皆様に深く感謝いたします。

吉林大学交通学部、長春、130022、中国

Jia Mao、Jinyuan Cheng、Baogui Cao

中国、長春、吉林大学自動車工学院

李翔宇

PubMed Google Scholar でこの著者を検索することもできます

すべての著者は、原稿で報告されている作業に多大な貢献を行っています (技術的な支援、執筆および編集の支援、一般的なサポートなど)。著者全員が最終原稿を読んで承認しました。

宝亀曹への対応。

著者らは競合する利害関係を宣言していません。

シュプリンガーネイチャーは、発行された地図および所属機関における管轄権の主張に関して中立を保ちます。

オープンアクセスこの記事はクリエイティブコモンズ表示 4.0 国際ライセンスに基づいてライセンスされており、元の著者と情報源に適切なクレジットを表示する限り、あらゆる媒体または形式での使用、共有、翻案、配布、複製が許可されます。クリエイティブコモンズライセンスへのリンクを提供し、変更が加えられたかどうかを示します。この記事内の画像またはその他のサードパーティ素材は、素材のクレジットラインに別段の記載がない限り、記事のクリエイティブコモンズライセンスに含まれています。素材が記事のクリエイティブコモンズライセンスに含まれておらず、意図した使用が法的規制で許可されていない場合、または許可されている使用を超えている場合は、著作権所有者から直接許可を得る必要があります。このライセンスのコピーを表示するには、http://creativecommons.org/licenses/by/4.0/ にアクセスしてください。

転載と許可

Mao, J.、Cheng, J.、Li, X. 他 4方向シャトルベースの保管および取り出しシステムのスケジュールの最適化に関する研究。 Sci Rep 13、3999 (2023)。 https://doi.org/10.1038/s41598-023-31050-8

引用をダウンロード

受信日: 2022 年 10 月 28 日

受理日: 2023 年 3 月 6 日

公開日: 2023 年 3 月 10 日

DOI: https://doi.org/10.1038/s41598-023-31050-8

次のリンクを共有すると、誰でもこのコンテンツを読むことができます。

申し訳ございませんが、現在この記事の共有リンクは利用できません。

Springer Nature SharedIt コンテンツ共有イニシアチブによって提供

コメントを送信すると、利用規約とコミュニティガイドラインに従うことに同意したことになります。虐待的なもの、または当社の規約やガイドラインに準拠していないものを見つけた場合は、不適切としてフラグを立ててください。

テキサスのピートメーカーがウィンストンに2,000万ドルの配送センターと倉庫を開設

小売の未来は小規模、クラウドソーシング、ロボットにある

ブログ

4つのスケジューリング最適化に関する研究