論文の概要: Learning-Enhanced Neighborhood Selection for the Vehicle Routing Problem with Time Windows
- arxiv url: http://arxiv.org/abs/2403.08839v1
- Date: Wed, 13 Mar 2024 12:08:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-16 00:41:28.800522
- Title: Learning-Enhanced Neighborhood Selection for the Vehicle Routing Problem with Time Windows
- Title(参考訳): タイムウインドウを用いた車両経路問題に対する学習強化近傍選択
- Authors: Willem Feijen, Guido Schäfer, Koen Dekker, Seppo Pieterse,
- Abstract要約: 機械学習(ML)をLarge Neighborhood Search(LNS)に統合し、LNSの各イテレーションにおいて、ソリューションのどの部分が破壊され、修復されるべきかを決定する。
我々のアプローチは普遍的に適用可能であり、すなわち、破壊アルゴリズムの動作を増幅するために任意のLSSアルゴリズムに適用することができる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Large Neighborhood Search (LNS) is a universal approach that is broadly applicable and has proven to be highly efficient in practice for solving optimization problems. We propose to integrate machine learning (ML) into LNS to assist in deciding which parts of the solution should be destroyed and repaired in each iteration of LNS. We refer to our new approach as Learning-Enhanced Neighborhood Selection (LENS for short). Our approach is universally applicable, i.e., it can be applied to any LNS algorithm to amplify the workings of the destroy algorithm. In this paper, we demonstrate the potential of LENS on the fundamental Vehicle Routing Problem with Time Windows (VRPTW). We implemented an LNS algorithm for VRPTW and collected data on generated novel training instances derived from well-known, extensively utilized benchmark datasets. We trained our LENS approach with this data and compared the experimental results of our approach with two benchmark algorithms: a random neighborhood selection method to show that LENS learns to make informed choices and an oracle neighborhood selection method to demonstrate the potential of our LENS approach. With LENS, we obtain results that significantly improve the quality of the solutions.
- Abstract(参考訳): LNS(Large Neighborhood Search)は、広く適用可能な普遍的な手法であり、最適化問題の解法として非常に効率的であることが証明されている。
機械学習(ML)をLNSに統合し、LNSの各イテレーションでソリューションのどの部分が破壊され、修復されるべきかを判断する。
我々は新しいアプローチをLens(Learning-Enhanced Neighborhood Selection)と呼ぶ。
我々のアプローチは普遍的に適用可能であり、すなわち、破壊アルゴリズムの動作を増幅するために任意のLSSアルゴリズムに適用することができる。
本稿では,車載時間Windows(VRPTW)におけるLENSの可能性を実証する。
我々は、VRPTWのためのLSSアルゴリズムを実装し、よく知られた、広く利用されているベンチマークデータセットから生成された新しいトレーニングインスタンスのデータを収集した。
我々はこのデータを用いてLENSアプローチを訓練し、LENSアプローチの可能性を実証するためにLENSが情報選択を学習したことを示すランダム近傍選択法とオラクル近傍選択法という2つのベンチマークアルゴリズムと比較した。
LENSでは,解の質を著しく向上させる結果が得られる。
関連論文リスト
- PNN: From proximal algorithms to robust unfolded image denoising
networks and Plug-and-Play methods [7.317910352447519]
本稿では,二元FBと二元Chambolle-Pockアルゴリズムの両方に基づいて,ガウス分母タスクのためのPNNを統一的に構築するフレームワークを提案する。
また、これらのアルゴリズムの高速化により、関連するNN層におけるスキップ接続が可能であることを示す。
論文 参考訳(メタデータ) (2023-08-06T15:32:16Z) - Searching Large Neighborhoods for Integer Linear Programs with
Contrastive Learning [39.40838358438744]
線形プログラム(ILP)は、多数の最適化問題のモデリングと解決のための強力なツールである。
アルゴリズムとしてLarge Neighborhood Search (LNS)は、ブランチやバウンドよりも高速に、ILPの高品質なソリューションを見つけることができる。
本稿では,メトリクスによって測定された複数のILPベンチマークに対して,最先端のリアルタイム性能を実現する新しいアプローチCL-LNSを提案する。
論文 参考訳(メタデータ) (2023-02-03T07:15:37Z) - Online Control of Adaptive Large Neighborhood Search using Deep
Reinforcement Learning [7.4746628878102195]
本稿では,バニラを選択し,パラメータを調整し,探索過程における受入基準を制御する,深層強化学習(DRL)アプローチを提案する。
IJCAIコンペティションで用いられる重みと時間窓を用いた時間依存オリエンテーリング問題において,提案手法の評価を行った。
論文 参考訳(メタデータ) (2022-11-01T21:33:46Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳(メタデータ) (2022-10-02T05:03:38Z) - Training Neural Networks using SAT solvers [1.0152838128195465]
本稿では,SATソルバを用いてニューラルネットワークのトレーニングを行うグローバル最適化手法を提案する。
実験では,パリティ学習などのタスクにおいて,ADAMオプティマイザに対するアルゴリズムの有効性を示す。
論文 参考訳(メタデータ) (2022-06-10T01:31:12Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳(メタデータ) (2021-04-09T14:50:59Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳(メタデータ) (2021-01-08T18:55:07Z) - A General Large Neighborhood Search Framework for Solving Integer Linear
Programs [46.62993477453986]
我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。
我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
論文 参考訳(メタデータ) (2020-03-29T23:08:14Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳(メタデータ) (2020-01-22T08:51:05Z) - Channel Assignment in Uplink Wireless Communication using Machine
Learning Approach [54.012791474906514]
本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。
我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。
計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
論文 参考訳(メタデータ) (2020-01-12T15:54:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。