論文の概要: Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling
Salesman Problem
- arxiv url: http://arxiv.org/abs/2403.05318v1
- Date: Fri, 8 Mar 2024 13:49:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-11 13:22:42.543843
- Title: Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling
Salesman Problem
- Title（参考訳）: 遅刻を避けるために:難解な旅行セールスマン問題を解決する
- Authors: Jingxiao Chen, Ziqin Gong, Minghuan Liu, Jun Wang, Yong Yu, Weinan
Zhang
- Abstract要約: そこで本稿では,TSP と Time Windows (TSPTW) の正当性を改善するために,ルックアヘッド情報を用いた新しい学習手法を提案する。
多様なデータセットに関する包括的な実験により、MUSLAは既存のベースラインを上回り、一般化可能性を示す。
- 参考スコア（独自算出の注目度）: 36.88003015541172
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many real-world problems can be formulated as a constrained Traveling
Salesman Problem (TSP). However, the constraints are always complex and
numerous, making the TSPs challenging to solve. When the number of complicated
constraints grows, it is time-consuming for traditional heuristic algorithms to
avoid illegitimate outcomes. Learning-based methods provide an alternative to
solve TSPs in a soft manner, which also supports GPU acceleration to generate
solutions quickly. Nevertheless, the soft manner inevitably results in
difficulty solving hard-constrained problems with learning algorithms, and the
conflicts between legality and optimality may substantially affect the
optimality of the solution. To overcome this problem and to have an effective
solution against hard constraints, we proposed a novel learning-based method
that uses looking-ahead information as the feature to improve the legality of
TSP with Time Windows (TSPTW) solutions. Besides, we constructed TSPTW datasets
with hard constraints in order to accurately evaluate and benchmark the
statistical performance of various approaches, which can serve the community
for future research. With comprehensive experiments on diverse datasets, MUSLA
outperforms existing baselines and shows generalizability potential.
- Abstract（参考訳）: 多くの現実世界の問題は、制約付きトラベルセールスマン問題(TSP)として定式化することができる。
しかし、制約は常に複雑で多様であり、TSPの解決は困難である。
複雑な制約の数が増えると、不正な結果を避けるために従来のヒューリスティックアルゴリズムに時間がかかる。
学習ベースの手法は、TSPをソフトに解決する代替手段を提供する。
それでも、ソフトなやり方は学習アルゴリズムによる難解な問題の解決を困難にし、合法性と最適性の対立は解の最適性に大きく影響する可能性がある。
この問題を克服し, ハード制約に対する効果的な解決策を得るために, TSP と Time Windows (TSPTW) の正当性を改善するために, ルックアヘッド情報を用いた新しい学習手法を提案する。
さらに,tsptwデータセットを厳密な制約付きで構築し,今後の研究のためにコミュニティに役立つ様々なアプローチの統計的性能を正確に評価・評価した。
多様なデータセットに関する包括的な実験により、MUSLAは既存のベースラインを上回り、一般化可能性を示す。
関連論文リスト
- OTClean: Data Cleaning for Conditional Independence Violations using
Optimal Transport [51.6416022358349]
sysは、条件付き独立性(CI)制約下でのデータ修復に最適な輸送理論を利用するフレームワークである。
我々はSinkhornの行列スケーリングアルゴリズムにインスパイアされた反復アルゴリズムを開発し、高次元および大規模データを効率的に処理する。
論文 参考訳（メタデータ） (2024-03-04T18:23:55Z) - Rolling Horizon based Temporal Decomposition for the Offline Pickup and
Delivery Problem with Time Windows [5.818566833386833]
オフラインPDPTWのクラスを解くための新しい時間分解方式を提案する。
私たちのフレームワークはよりスケーラブルで、さまざまな難易度の問題インスタンスに対して優れたソリューションを提供することができます。
論文 参考訳（メタデータ） (2023-03-06T20:07:05Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳（メタデータ） (2022-11-14T21:54:31Z) - Learning to Solve Soft-Constrained Vehicle Routing Problems with
Lagrangian Relaxation [0.4014524824655105]
現実世界のアプリケーションにおける車両ルーティング問題(VRP)には、様々な制約が伴うことが多い。
ソフト制約付きVRPを解くために,強化学習に基づく手法を提案する。
本稿では,3種類のVRP,TSPTW(Travelling Salesman Problem with Time Windows),CVRP(Capacitated VRP),CVRPTW(Capacitated VRP with Time Windows)に適用する。
論文 参考訳（メタデータ） (2022-07-20T12:51:06Z) - Solving the capacitated vehicle routing problem with timing windows
using rollouts and MAX-SAT [4.873362301533824]
車両ルーティングはNPハード最適化問題のよく知られたクラスである。
最近の強化学習の取り組みは有望な代替手段である。
本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
論文 参考訳（メタデータ） (2022-06-14T06:27:09Z) - Learning Hard Optimization Problems: A Data Generation Perspective [44.4747903763245]
本稿では,トレーニングデータのボラティリティと,それを近似する能力について述べる。
そこで本研究では,教師付きタスクに対処可能な最適化問題に対して,(実際にあるいは近似的に)解を生成(生成)する方法を提案する。
論文 参考訳（メタデータ） (2021-06-04T17:03:44Z) - Constrained Learning with Non-Convex Losses [119.8736858597118]
学習は現代の情報処理の中核技術になっているが、バイアス、安全でない、偏見のあるソリューションにつながるという証拠はたくさんある。
論文 参考訳（メタデータ） (2021-03-08T23:10:33Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Probably Approximately Correct Constrained Learning [135.48447120228658]
我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。
PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。
このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
論文 参考訳（メタデータ） (2020-06-09T19:59:29Z) - Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated
Algorithm Selection [0.0]
トラベリング・サレスパーソン・プロブレム(TSP)は、最もよく知られたNPハード最適化問題の1つである。
我々は、不正確なTSPソルバの任意の動作に対処することで、既存のベンチマーク研究を拡張した。
その結果、解法の性能ランキングは、集中した近似品質に大きく依存していることが判明した。
論文 参考訳（メタデータ） (2020-05-27T11:36:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。