論文の概要: Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problems
- arxiv url: http://arxiv.org/abs/2508.14071v1
- Date: Tue, 12 Aug 2025 05:28:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-21 16:52:41.15326
- Title: Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problems
- Title（参考訳）: エッジセレクタモデルによる車両経路問題の解法
- Authors: Bachtiar Herdianto, Romain Billot, Flavien Lucas, Marc Sevaux, Daniele Vigo,
- Abstract要約: 本研究は、車両ルーティング問題(VRP)を解決するために設計されたハイブリッド機械学習とメタヒューリスティックメカニズムを提案する。
本手法の主目的はエッジソリューションセレクタモデルであり, 局所探索において, 解のエッジを分類し, 禁止動作を識別する。
提案手法はスケーラビリティと一般化性の両方を示し,異なるベースラインメタヒューリスティックスにおける性能改善を実現している。
- 参考スコア（独自算出の注目度）: 1.9573380763700716
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This research proposes a hybrid Machine Learning and metaheuristic mechanism that is designed to solve Vehicle Routing Problems (VRPs). The main of our method is an edge solution selector model, which classifies solution edges to identify prohibited moves during the local search, hence guiding the search process within metaheuristic baselines. Two learning-based mechanisms are used to develop the edge selector: a simple tabular binary classifier and a Graph Neural Network (GNN). The tabular classifier employs Gradient Boosting Trees and Feedforward Neural Network as the baseline algorithms. Adjustments to the decision threshold are also applied to handle the class imbalance in the problem instance. An alternative mechanism employs the GNN to utilize graph structure for direct solution edge prediction, with the objective of guiding local search by predicting prohibited moves. These hybrid mechanisms are then applied in state-fo-the-art metaheuristic baselines. Our method demonstrates both scalability and generalizability, achieving performance improvements across different baseline metaheuristics, various problem sizes and variants, including the Capacitated Vehicle Routing Problem (CVRP) and CVRP with Time Windows (CVRPTW). Experimental evaluations on benchmark datasets up to 30,000 customer nodes, supported by pair-wise statistical analysis, verify the observed improvements.
- Abstract（参考訳）: 本研究は、車両ルーティング問題(VRP)を解決するために設計されたハイブリッド機械学習とメタヒューリスティックメカニズムを提案する。
本手法の主目的はエッジソリューションセレクタモデルであり,解のエッジを分類し,局所探索中に禁止された動作を特定することにより,メタヒューリスティックなベースライン内での探索プロセスを導出する。
エッジセレクタの開発には,2つの学習機構が使用されている。単純な表2値分類器とグラフニューラルネットワーク(GNN)である。
表型分類器は、ベースラインアルゴリズムとしてGradient Boosting TreesとFeedforward Neural Networkを採用している。
問題インスタンスのクラス不均衡を処理するために、決定しきい値の調整も適用される。
グラフ構造を利用して直接解法エッジの予測を行い、禁止された動きを予測して局所探索を誘導する。
これらのハイブリッド機構は、最先端のメタヒューリスティックベースラインに適用される。
提案手法は,キャパシタレートカールーティング問題 (CVRP) やCVRP with Time Windows (CVRPTW) など,様々なベースラインメタヒューリスティクス,様々な問題サイズ,バリエーションにまたがる性能向上を実現する。
ペアワイズ統計分析によってサポートされた最大30,000の顧客ノードのベンチマークデータセットに対する実験的評価により、観測された改善が検証された。
関連論文リスト
- Hybrid Node-Destroyer Model with Large Neighborhood Search for Solving the Capacitated Vehicle Routing Problem [1.9573380763700716]
本稿ではメタヒューリスティックアルゴリズムの性能向上を目的とした反復学習ハイブリッド最適化手法を提案する。
提案手法は, 演算複雑性を低減し, 最適化プロセスに関わる探索空間を縮小する。
論文 参考訳（メタデータ） (2025-08-12T05:56:13Z) - Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning [53.527506374566485]
本稿では,多エージェント強化学習クラスタフレームワーク,すなわちAR-DBSCANを用いた新しいAdaptive and Robust DBSCANを提案する。
我々は、AR-DBSCANが、NMIおよびARIメトリクスの最大144.1%と175.3%のクラスタリング精度を向上するだけでなく、支配的なパラメータを確実に見つけることができることを示した。
論文 参考訳（メタデータ） (2025-05-07T11:37:23Z) - GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
車両のルーティング問題を解決するためにEdges Fusionフレームワークを用いた適応型グラフ注意サンプリングを提案する。
提案手法は,既存の手法を2.08%-6.23%上回り,より強力な一般化能力を示す。
論文 参考訳（メタデータ） (2024-05-21T03:33:07Z) - Spatial-temporal-demand clustering for solving large-scale vehicle
routing problems with time windows [0.0]
本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。
その類似度基準は、顧客の空間的、時間的、需要データを含む。
本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
論文 参考訳（メタデータ） (2024-01-20T06:06:01Z) - A hybrid deep-learning-metaheuristic framework for bi-level network
design problems [2.741266294612776]
本研究では,道路ネットワーク設計問題(NDP)のための双方向アーキテクチャを用いたハイブリッドディープラーニング・メタヒューリスティックフレームワークを提案する。
我々は、ユーザ均衡(UE)トラフィック割り当て問題の解を近似するために、グラフニューラルネットワーク(GNN)を訓練する。
遺伝的アルゴリズム(GA)の適合度関数評価の計算にトレーニングモデルを用いて,NDPの解を近似する。
論文 参考訳（メタデータ） (2023-03-10T16:23:56Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳（メタデータ） (2022-11-01T18:33:20Z) - Neural Improvement Heuristics for Graph Combinatorial Optimization
Problems [49.85111302670361]
本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。
提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
論文 参考訳（メタデータ） (2022-06-01T10:35:29Z) - Semi-supervised Domain Adaptive Structure Learning [72.01544419893628]
半教師付きドメイン適応 (SSDA) は,1) アノテーションの低いデータに過度に適合する手法と,2) ドメイン間の分散シフトの両方を克服しなければならない課題である。
SSLとDAの協調を正規化するための適応型構造学習手法を提案する。
論文 参考訳（メタデータ） (2021-12-12T06:11:16Z) - Enhanced Exploration in Neural Feature Selection for Deep Click-Through
Rate Prediction Models via Ensemble of Gating Layers [7.381829794276824]
神経機能選択(NFS)の目標は、最も説明力のある比較的小さな機能のサブセットを選択することである。
ゲーティングアプローチは、情報の少ない特徴をドロップするために、識別可能なバイナリゲートのセットを挿入する。
勾配に基づく解の探索能力を向上させるために,単純だが効果的なアンサンブル学習手法を提案する。
論文 参考訳（メタデータ） (2021-12-07T04:37:05Z) - Reconfigurable Intelligent Surface Assisted Mobile Edge Computing with
Heterogeneous Learning Tasks [53.1636151439562]
モバイルエッジコンピューティング(MEC)は、AIアプリケーションに自然なプラットフォームを提供します。
再構成可能なインテリジェントサーフェス(RIS)の助けを借りて、MECで機械学習タスクを実行するインフラストラクチャを提示します。
具体的には,モバイルユーザの送信パワー,基地局のビームフォーミングベクトル,risの位相シフト行列を共同で最適化することにより,参加ユーザの学習誤差を最小化する。
論文 参考訳（メタデータ） (2020-12-25T07:08:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。