論文の概要: Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem
- arxiv url: http://arxiv.org/abs/2404.11458v1
- Date: Wed, 17 Apr 2024 15:05:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-18 13:35:28.177538
- Title: Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem
- Title（参考訳）: Learn to Tour: ピックアップ・アンド・デリバリー・トラベリング・セールスマン問題におけるソリューション・フィージビリティ・マッピングのためのオペレータ設計
- Authors: Bowen Fang, Xu Chen, Xuan Di,
- Abstract要約: 本稿では,旅行セールスマン問題(TSP)の学習方法を提案する。
1対1のピックアップ・アンド・デリバリノードのシーケンスで一番短いツアーを見つける。
PDTSPでは、各ピックアップノードを対応する配信ノードの前に訪問しなければならないという優先的な制約を満たさなければならない。
- 参考スコア（独自算出の注目度）: 12.34897099691387
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper aims to develop a learning method for a special class of traveling salesman problems (TSP), namely, the pickup-and-delivery TSP (PDTSP), which finds the shortest tour along a sequence of one-to-one pickup-and-delivery nodes. One-to-one here means that the transported people or goods are associated with designated pairs of pickup and delivery nodes, in contrast to that indistinguishable goods can be delivered to any nodes. In PDTSP, precedence constraints need to be satisfied that each pickup node must be visited before its corresponding delivery node. Classic operations research (OR) algorithms for PDTSP are difficult to scale to large-sized problems. Recently, reinforcement learning (RL) has been applied to TSPs. The basic idea is to explore and evaluate visiting sequences in a solution space. However, this approach could be less computationally efficient, as it has to potentially evaluate many infeasible solutions of which precedence constraints are violated. To restrict solution search within a feasible space, we utilize operators that always map one feasible solution to another, without spending time exploring the infeasible solution space. Such operators are evaluated and selected as policies to solve PDTSPs in an RL framework. We make a comparison of our method and baselines, including classic OR algorithms and existing learning methods. Results show that our approach can find tours shorter than baselines.
- Abstract（参考訳）: 本稿では,旅行セールスマン問題 (TSP) の学習方法,すなわち,1対1のピックアップ・アンド・デリバリノードの順序に沿って最短のツアーを見出すことのできるピックアップ・アンド・デリバリTSP (PDTSP) を開発することを目的とする。
ここで1対1とは、輸送された人や商品が指定されたピックアップと配送ノードに関連付けられていることを意味する。
PDTSPでは、各ピックアップノードを対応する配信ノードの前に訪問しなければならないという優先的な制約を満たさなければならない。
PDTSPの古典的操作研究(OR)アルゴリズムは大規模問題へのスケールが難しい。
近年, 強化学習 (RL) がTSPに適用されている。
基本的な考え方は、ソリューション空間における訪問シーケンスを探索し、評価することである。
しかし、この手法は計算効率が低い可能性があり、先行制約に違反する多くの実現不可能な解を評価する必要がある。
実現可能空間内の解探索を制限するために、実現不可能な解空間を探索するのに時間を費やすことなく、ある実現可能解を常に別の実現可能空間にマップする演算子を利用する。
このような演算子は、RLフレームワークでPDTSPを解くポリシーとして評価され、選択される。
従来のORアルゴリズムや既存の学習方法など,提案手法とベースラインを比較した。
その結果,本手法はベースラインよりも短いツアーを見つけることができることがわかった。
関連論文リスト
- TSPDiffuser: Diffusion Models as Learned Samplers for Traveling Salesperson Path Planning Problems [7.566713416204861]
旅行セールスパーソンパス計画問題(TSPPP)のための新しいデータ駆動パスプランナを提案する。
障害物マップ内の目的地の集合を考慮に入れれば、最も短い衝突のない経路を効率的に見つけることが目的である。
我々は,TSPPP インスタンスの集合とその各ソリューション上で拡散モデルを訓練し,未知の問題インスタンスに対する可塑性経路を生成する。
論文 参考訳（メタデータ） (2024-06-05T02:15:55Z) - Exact algorithms and heuristics for capacitated covering salesman problems [0.0]
本稿では,CCSP(Capacitated Covering Salesman Problem)を紹介する。
目的は、車両が横断する距離を最小化しながら、車両群を補給することである。
ILP(Integer Linear Programming)とBRKGA(Biased Random-Key Genetic Routing)のメタヒューリスティックに基づくCCSPの最適化手法を提案する。
論文 参考訳（メタデータ） (2024-03-03T07:50:29Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。
孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
論文 参考訳（メタデータ） (2023-09-29T19:55:56Z) - Communication-Efficient Decentralized Federated Learning via One-Bit
Compressive Sensing [52.402550431781805]
分散連合学習(DFL)は、様々なアプリケーションにまたがる実用性によって人気を博している。
集中型バージョンと比較して、DFLの多数のノード間で共有モデルをトレーニングするのはより難しい。
我々は,iADM (iexact alternating direction method) の枠組みに基づく新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-08-31T12:22:40Z) - Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem [67.32731657297377]
トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。
近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。
本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
論文 参考訳（メタデータ） (2023-04-19T03:48:32Z) - H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman
Problem [11.310986634385742]
本稿では,大規模トラベリングセールスマン問題(TSP)に対処する階層的強化学習(H-TSP)に基づくエンドツーエンド学習フレームワークを提案する。
我々は,H-TSPがSOTA検索に匹敵する結果が得られることを示し,時間消費を2桁まで削減する(3.32s vs. 395.85s)。
ソリューションの品質に関してはまだSOTAの結果にギャップがあるが、H-TSPは実用的なアプリケーション、特にオンコールルーティングや乗車などの時間に敏感なアプリケーションに有用であると考えている。
論文 参考訳（メタデータ） (2023-04-19T03:10:30Z) - Keypoint-Guided Optimal Transport [85.396726225935]
最適マッチングを探索するリレーション保存(KPG-RL)によるキーポイント誘導モデルを提案する。
提案した KPG-RL モデルはシンクホーンのアルゴリズムで解くことができ、異なる空間で分布がサポートされている場合でも適用可能である。
二重KPG-RLからの学習された輸送計画に基づき、ターゲット領域にソースデータを転送する新しい多様体バリ中心射影を提案する。
論文 参考訳（メタデータ） (2023-03-23T08:35:56Z) - Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning [59.14935871979047]
本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。
これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
論文 参考訳（メタデータ） (2022-07-04T14:31:47Z) - Learning to Optimise General TSP Instances [2.6782615615913348]
トラベリングセールスマン問題(TSP)は古典的な最適化問題である。
ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。
本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
論文 参考訳（メタデータ） (2020-10-23T07:37:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。