論文の概要: Balanced Order Batching with Task-Oriented Graph Clustering

• arxiv url: http://arxiv.org/abs/2008.09018v1
• Date: Wed, 19 Aug 2020 08:42:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-27 09:10:16.880958
• Title: Balanced Order Batching with Task-Oriented Graph Clustering
• Title（参考訳）: タスク指向グラフクラスタリングによる平衡順序バッチ
• Authors: Lu Duan, Haoyuan Hu, Zili Wu, Guozheng Li, Xinhang Zhang, Yu Gong, Yinghui Xu
• Abstract要約: 本稿では,BTOGCN(Ba balanced Task- Clustering Network)というエンドツーエンドの学習・最適化フレームワークを提案する。 BOBPは、中国最大のロジスティクスプラットフォームであるCainiaoの買収プロセスに端を発する。
• 参考スコア（独自算出の注目度）: 28.05598654297136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Balanced order batching problem (BOBP) arises from the process of warehouse picking in Cainiao, the largest logistics platform in China. Batching orders together in the picking process to form a single picking route, reduces travel distance. The reason for its importance is that order picking is a labor intensive process and, by using good batching methods, substantial savings can be obtained. The BOBP is a NP-hard combinational optimization problem and designing a good problem-specific heuristic under the quasi-real-time system response requirement is non-trivial. In this paper, rather than designing heuristics, we propose an end-to-end learning and optimization framework named Balanced Task-orientated Graph Clustering Network (BTOGCN) to solve the BOBP by reducing it to balanced graph clustering optimization problem. In BTOGCN, a task-oriented estimator network is introduced to guide the type-aware heterogeneous graph clustering networks to find a better clustering result related to the BOBP objective. Through comprehensive experiments on single-graph and multi-graphs, we show: 1) our balanced task-oriented graph clustering network can directly utilize the guidance of target signal and outperforms the two-stage deep embedding and deep clustering method; 2) our method obtains an average 4.57m and 0.13m picking distance ("m" is the abbreviation of the meter (the SI base unit of length)) reduction than the expert-designed algorithm on single and multi-graph set and has a good generalization ability to apply in practical scenario.
• Abstract（参考訳）: バランスド・オーダー・バッチリング問題(BOBP)は、中国最大の物流プラットフォームであるカイニアオで倉庫を拾う過程から生じる。 ピッキングプロセスで注文をまとめて1つのピッキングルートを形成することで、旅行距離を減少させる。 その重要性は、注文のピッキングは労働集約的なプロセスであり、良いバッチ手法を用いることでかなりの節約が得られるためである。 BOBPはNP-ハードな組合せ最適化問題であり、準リアルタイムシステム応答要求の下で優れた問題固有のヒューリスティックを設計するのは非自明である。 本稿では、ヒューリスティックスを設計する代わりに、バランスド・タスク指向グラフクラスタリングネットワーク(BTOGCN)と呼ばれるエンドツーエンドの学習・最適化フレームワークを提案し、バランスド・グラフクラスタリング最適化問題に還元してBOBPを解決する。 BTOGCNでは、BOBPの目的に関するより優れたクラスタリング結果を求めるために、タイプアウェアな異種グラフクラスタリングネットワークを誘導するタスク指向推定器ネットワークが導入された。 シングルグラフとマルチグラフの包括的実験を通じて、以下のことが示される。 1) バランスの取れたタスク指向グラフクラスタリングネットワークは, ターゲット信号の誘導を直接活用し, 2段階の深層埋め込みおよび深層クラスタリング手法よりも優れている。 2) 本手法は, 単グラフおよび多グラフ集合上のエキスパート設計アルゴリズムよりも平均4.57m, 0.13mピッキング距離(mはメートル(長さのsiベース単位)を短縮し, 実用的なシナリオに適用可能な一般化能力を有する。

関連論文リスト

• Large Scale Constrained Clustering With Reinforcement Learning [1.3597551064547502]
  ネットワークが与えられた場合、各ノードではなく、クラスタレベルでリソースを割り当てることによって、リソースの割り当てと使用効率が向上する。 本稿では,この制約付きクラスタリング問題を強化学習を用いて解く手法を提案する。 結果の節では,大規模インスタンスにおいても,アルゴリズムが最適に近い解を見つけることを示す。
  論文  参考訳（メタデータ） (2024-02-15T18:27:18Z)
• Sample-Efficient Clustering and Conquer Procedures for Parallel Large-Scale Ranking and Selection [0.0]
  並列コンピューティング環境では、相関ベースのクラスタリングは$mathcalO(p)$サンプル複雑性低減率を達成することができる。 ニューラルアーキテクチャ検索のような大規模AIアプリケーションでは、スクリーニングなしバージョンの手順が、サンプル効率の点で完全に順序づけられたベンチマークを驚くほど上回っている。
  論文  参考訳（メタデータ） (2024-02-03T15:56:03Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Arch-Graph: Acyclic Architecture Relation Predictor for Task-Transferable Neural Architecture Search [96.31315520244605]
  Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。 Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。 わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
  論文  参考訳（メタデータ） (2022-04-12T16:46:06Z)
• GLAN: A Graph-based Linear Assignment Network [29.788755291070462]
  深層グラフネットワークに基づく学習可能な線形代入問題の解法を提案する。 合成データセットによる実験結果から,本手法は最先端のベースラインよりも優れていることがわかった。 また,提案手法を一般的なマルチオブジェクトトラッキング(MOT)フレームワークに組み込んで,エンド・ツー・エンドでトラッカーをトレーニングする。
  論文  参考訳（メタデータ） (2022-01-05T13:18:02Z)
• Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
  離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。 本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。 最適ではないにもかかわらず、性能は桁違いに向上することを示す。 結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
  論文  参考訳（メタデータ） (2021-06-23T09:46:11Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。