論文の概要: Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints
- arxiv url: http://arxiv.org/abs/2608.14140v1
- Date: Fri, 14 Aug 2026 09:46:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-17 20:14:29.343872
- Title: Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints
- Title（参考訳）: スマートルート:現実的な制約を伴う車両経路問題の解法のためのアルゴリズムの開発と比較のためのシステム
- Abstract要約: 時間Windows(CVRPTW)を用いた容量化車両ルーティング問題について検討する。
LKH, 2-OPT, 3-OPT, ORToolsフレームワーク, 深層学習モデルJAMPRなどのアルゴリズムと比較した。
以上の結果から,50のDeep Learningと古典的解がSCIPに近くなったが,時間を要することがわかった。
- 参考スコア（独自算出の注目度）: 39.146761527401424
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.
- Abstract（参考訳）: 現実的な制約を伴うルート最適化の問題は、グローバルな都市人口増加に直面している中で極めて重要になっている。
理論的に最適解を提供するアプローチは知っているが、指数複雑性によって問題のサイズが大きくなると、その応用は困難になる。
本稿では,CVRPTW(Capacitated Vehicle Routing Problem with Time Windows)について検討し,LKH,2-OPT,3-OPT,ORToolsフレームワーク,深層学習モデルJAMPRなどのヒューリスティックアルゴリズムと比較する。
以上の結果から,50のディープラーニングと古典的ヒューリスティックな解がSCIPに近くなったが,時間を要することがわかった。
サイズ100の問題に加えて、SCIPの正確な手法は、ニューラルネットワークと古典的ヒューリスティックが同じルートコストで、同時に最初の実現可能なソリューションで50%ほど悪化するのを13倍も遅くする。
実験を行うために、我々はルート最適化問題を解決するスマートルートプラットフォームを開発し、正確な、ヒューリスティック、ディープラーニングモデルを含み、カスタムアルゴリズムとデータセットの便利な統合を容易にする。
関連論文リスト
- NaviFormer: A Deep Reinforcement Learning Transformer-like Model to Holistically Solve the Navigation Problem [53.70554593151033]
NaviFormerは、高レベル経路と低レベル軌道の両方を予測することによって、グローバルナビゲーション問題を解決する深層強化学習モデルである。
結果は,各サブプロブレムの制約や難易度を理解することができるため,NaviFormerの競合精度を示す。
計算速度が優れていることは、リアルタイムのミッションに適していることを証明している。
論文 参考訳（メタデータ） (2026-04-18T11:32:34Z) - Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks [0.47248250311484113]
本稿では,最大重み付き独立集合(MWIS)問題を解くための,新しい,効率的なアルゴリズムを提案する。
MWIS問題のNPハード性を考えると,提案アルゴリズムであるDynLSには3つの重要なイノベーションが組み込まれている。
我々の実験結果はDynLSの優れた性能を示し、1000秒以内の高品質なソリューションを一貫して提供した。
論文 参考訳（メタデータ） (2025-05-07T10:35:53Z) - Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。
本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。
このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
論文 参考訳（メタデータ） (2025-04-08T15:21:01Z) - 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) - TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。
ToP-Formerは、チームのオリエンテーリング問題を効率的に正確に解くために設計されたマルチエージェント経路計画ニューラルネットワークである。
論文 参考訳（メタデータ） (2023-11-30T16:10:35Z) - Enhancing Column Generation by Reinforcement Learning-Based
Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。
CGの性能を高めるために,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-15T00:05:50Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳（メタデータ） (2022-10-31T09:46:26Z) - Solving the capacitated vehicle routing problem with timing windows
using rollouts and MAX-SAT [4.873362301533824]
車両ルーティングはNPハード最適化問題のよく知られたクラスである。
最近の強化学習の取り組みは有望な代替手段である。
本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
論文 参考訳（メタデータ） (2022-06-14T06:27:09Z) - Combining Reinforcement Learning and Optimal Transport for the Traveling
Salesman Problem [18.735056206844202]
我々は,従来の自己回帰的アプローチよりもはるかに高速に,監督や推論なしに学習できるモデルを構築することができることを示す。
また、ディープラーニングモデルに最適なトランスポートアルゴリズムを組み込むことで、エンドツーエンドのトレーニング中に割り当て制約を強制する利点を実証的に評価する。
論文 参考訳（メタデータ） (2022-03-02T07:21:56Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。