Fugu-MT 論文翻訳(概要): Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows

論文の概要: Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows

arxiv url: http://arxiv.org/abs/2011.06331v5
Date: Tue, 8 Jun 2021 08:24:45 GMT
ステータス: 処理完了
システム内更新日: 2022-09-26 06:51:25.049590
Title: Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows
Title（参考訳）: 同時ピックアップ配信と時間Windowsによる車両ルーティングのメメカティック検索
Authors: Shengcai Liu, Ke Tang and Xin Yao
Abstract要約: 本稿では,この問題を解決するために,局所探索を効率的に行うメメティックアルゴリズム(MATE)を提案する。 MATEは最先端のアルゴリズムをすべて上回り、特に12インスタンス(合計65インスタンス)でよく知られた新しいソリューションを見つける。
参考スコア（独自算出の注目度）: 31.512563458410963
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows (VRPSPDTW) has attracted much research interest in the last decade, due to its wide application in modern logistics. Since VRPSPDTW is NP-hard and exact methods are only applicable to small-scale instances, heuristics and meta-heuristics are commonly adopted. In this paper we propose a novel Memetic Algorithm with efficient local search and extended neighborhood, dubbed MATE, to solve this problem. Compared to existing algorithms, the advantages of MATE lie in two aspects. First, it is capable of more effectively exploring the search space, due to its novel initialization procedure, crossover and large-step-size operators. Second, it is also more efficient in local exploitation, due to its sophisticated constant-time-complexity move evaluation mechanism. Experimental results on public benchmarks show that MATE outperforms all the state-of-the-art algorithms, and notably, finds new best-known solutions on 12 instances (65 instances in total). Moreover, a comprehensive ablation study is also conducted to show the effectiveness of the novel components integrated in MATE. Finally, a new benchmark of large-scale instances, derived from a real-world application of the JD logistics, is introduced, which can serve as a new and more challenging test set for future research.
Abstract（参考訳）: 同時ピックアップ・デリバリ・アンド・タイム・ウインドウ(VRPSPDTW)による車両ルーティング問題は、現代の物流に広く応用されているため、過去10年間に多くの研究関心を集めている。 VRPSPDTWはNPハードであり、正確な手法は小規模のインスタンスにのみ適用できるため、ヒューリスティックスやメタヒューリスティックスが一般的である。本稿では,この問題を解決するために,効率的な局所探索と拡張近傍であるmateを用いたmemeticアルゴリズムを提案する。既存のアルゴリズムと比較して、MATEの利点は2つの側面にある。まず,新たな初期化手順,クロスオーバー,大規模演算子により,探索空間をより効果的に探索することができる。第二に、局所的な搾取においても、その高度な定数時間複雑度移動評価機構により効率的である。公開ベンチマークの実験結果によると、MATEは最先端のアルゴリズムをすべて上回り、特に12インスタンス(合計65インスタンス)で新しい最もよく知られたソリューションを見つける。さらに,MATEに組み込まれた新規成分の有効性を示すため,包括的アブレーション試験も行った。最後に、JDロジスティクスの現実的な応用から派生した、大規模インスタンスの新しいベンチマークが紹介され、将来の研究の新たな、より困難なテストセットとして機能する。

関連論文リスト

BEACON: A Bayesian Optimization Strategy for Novelty Search in Expensive Black-Box Systems [1.204357447396532]
ノベルティ・サーチ (NS) は、シミュレーションや実験を通じて様々なシステムの振る舞いを自動的に発見する探索アルゴリズムのクラスである。このような高価なブラックボックスシステムに特化して設計されたサンプル効率のNSに対するベイズ最適化法を提案する。提案手法は,限られたサンプル予算の下で,より大規模な多様な挙動の集合を見出すことにより,既存のNSアルゴリズムよりも大幅に優れていることを示す。
論文参考訳（メタデータ） (2024-06-05T20:23:52Z)
New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
本研究では境界解の概念を用いた線形プログラミング(ILP)の新たな特徴付けを提案する。そこで我々は,局所探索アルゴリズムのLocal-ILPを開発した。 MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。
論文参考訳（メタデータ） (2023-04-29T07:22:07Z)
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文参考訳（メタデータ） (2022-03-28T21:34:16Z)
AutoSpace: Neural Architecture Search with Less Human Interference [84.42680793945007]
現在のニューラルネットワークアーキテクチャ検索(NAS)アルゴリズムは、ネットワーク構築のための検索空間を設計するための専門知識と努力を必要とします。探索空間を最適なものに進化させる新しい微分可能な進化フレームワークであるAutoSpaceを提案する。学習した検索空間では、最近のNASアルゴリズムの性能は、以前手作業で設計した空間に比べて大幅に改善できる。
論文参考訳（メタデータ） (2021-03-22T13:28:56Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-07T08:00:02Z)
Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood [6.85316573653194]
キャパシタン化車両ルーティング問題(CVRP)に特化したHGS(Hybrid Genetic Search)の実装について紹介する。この最先端のアルゴリズムは、Vidal et al. (2012)と同じ一般的な手法を用いており、また過去10年間に学んだ方法論的改善や教訓も含んでいる。
論文参考訳（メタデータ） (2020-11-23T21:37:49Z)
A global-local neighborhood search algorithm and tabu search for flexible job shop scheduling problem [3.946442574906068]
この研究はGLNSA(Global-local neighborhood search algorithm)と呼ばれる新しいメタヒューリスティックアルゴリズムを提案する。提案アルゴリズムは,Nopt1地区の簡易版を実装したタブ検索と補完する。実験の結果,提案アルゴリズムの性能は,最近発表された他のアルゴリズムと比較すると良好であった。
論文参考訳（メタデータ） (2020-10-23T23:08:51Z)
Finding Action Tubes with a Sparse-to-Dense Framework [62.60742627484788]
本稿では,ビデオストリームからのアクションチューブ提案を1つのフォワードパスでスパース・トゥ・デンス方式で生成するフレームワークを提案する。 UCF101-24, JHMDB-21, UCFSportsベンチマークデータセット上で, 本モデルの有効性を評価する。
論文参考訳（メタデータ） (2020-08-30T15:38:44Z)
Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文参考訳（メタデータ） (2020-05-09T02:48:23Z)
Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining [69.00394670035747]
ハイブリッドメタヒューリスティックスは、オペレーション研究のトレンドとなっている。成功例は、Greedy Randomized Adaptive Search Procedures (GRASP)とデータマイニング技術を組み合わせたものだ。
論文参考訳（メタデータ） (2019-08-28T13:12:30Z)

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

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