論文の概要: Learned upper bounds for the Time-Dependent Travelling Salesman Problem
- arxiv url: http://arxiv.org/abs/2107.13641v1
- Date: Wed, 28 Jul 2021 20:54:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-30 13:12:31.409789
- Title: Learned upper bounds for the Time-Dependent Travelling Salesman Problem
- Title（参考訳）: 時間依存型トラベルセールスマン問題の学習上限
- Authors: Tommaso Adamo and Gianpaolo Ghiani and Pierpaolo Greco and Emanuela
Guerriero
- Abstract要約: 時間依存トラベリングセールスマン問題(Time-Dependent Travelling Salesman Problem)は、グラフの頂点をカバーする少なくとも全期間のハミルトンツアーを見つけることである。
古典的(かつより単純な)時間非依存な非対称トラベリングセールスマン問題の解法に基づく上限化手法を考案する。
このアプローチの有効性は、2つのヨーロッパの都市の実走行時間関数に関する計算キャンペーンを通じて評価されている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Given a graph whose arc traversal times vary over time, the Time-Dependent
Travelling Salesman Problem consists in finding a Hamiltonian tour of least
total duration covering the vertices of the graph. The main goal of this work
is to define tight upper bounds for this problem by reusing the information
gained when solving instances with similar features. This is customary in
distribution management, where vehicle routes have to be generated over and
over again with similar input data. To this aim, we devise an upper bounding
technique based on the solution of a classical (and simpler) time-independent
Asymmetric Travelling Salesman Problem, where the constant arc costs are
suitably defined by the combined use of a Linear Program and a mix of
unsupervised and supervised Machine Learning techniques. The effectiveness of
this approach has been assessed through a computational campaign on the real
travel time functions of two European cities: Paris and London. The overall
average gap between our heuristic and the best-known solutions is about
0.001\%. For 31 instances, new best solutions have been obtained.
- Abstract（参考訳）: アークトラバーサル時間が時間とともに変化するグラフが与えられると、時間依存のトラベルセールスマン問題は、グラフの頂点をカバーする最小の持続時間のハミルトニアンツアーを見つけることからなる。
この研究の主な目標は、同様の機能でインスタンスを解決する際に得られる情報を再利用することで、この問題の厳密な上限を定義することである。
これは配車管理において慣例であり、同様の入力データで車両の経路を何度も生成する必要がある。
本研究では,古典的(かつより単純な)時間非依存の非対称トラベリングセールスマン問題の解法に基づいて,線形プログラムと教師なしおよび教師なしの機械学習技術の組み合わせにより,一定弧コストを適切に定義する上限化手法を提案する。
このアプローチの有効性は、パリとロンドンという2つのヨーロッパの都市の実走行時間関数に関する計算キャンペーンを通じて評価されている。
ヒューリスティックと最もよく知られた解の間の全体平均ギャップは約 0.001\% である。
31のケースで、新しい最良のソリューションが得られました。
関連論文リスト
- Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
乱れのないデータから歪んだ表現を学習することは、機械学習における根本的な課題である。
本稿では,2次最適輸送に基づく非交叉表現学習手法を提案する。
提案手法の有効性を4つの標準ベンチマークで示す。
論文 参考訳（メタデータ） (2024-07-10T16:51:32Z) - Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making [66.27188304203217]
時間的距離は、計画、制御、強化学習のための多くのアルゴリズムの中心にある。
このような時間的距離を設定内で定義しようとする以前の試みは、重要な制限によって妨げられている。
比較学習によって学習された後継特徴が,三角形の不等式を満たす時間的距離を形成することを示す。
論文 参考訳（メタデータ） (2024-06-24T19:36:45Z) - Damped Online Newton Step for Portfolio Selection [96.0297968061824]
古典的なオンラインポートフォリオ選択の問題を再考し、各ラウンドで学習者がポートフォリオの集合上の分布を選択し、その富を割り当てる。
この問題に対する対数的後悔を達成する既存のアルゴリズムは、ラウンドの総数とスケールする時間と空間の複雑さがある。
対数的後悔を伴う最初の実用的オンラインポートフォリオ選択アルゴリズムを提示し、その時間と空間の複雑さは水平線上で対数的にのみ依存する。
論文 参考訳（メタデータ） (2022-02-15T17:01:55Z) - Machine-learning-based arc selection for constrained shortest path
problems in column generation [5.08128537391027]
本研究では,機械学習に基づく新しい価格アルゴリズムを提案する。
目的は、ネットワークのサイズを小さくし、PPを加速することであり、線形緩和溶液の一部となる確率の高い弧のみを保持することである。
この方法は、公共交通機関における車両と乗員のスケジューリング問題と、時間窓による車両のルーティング問題という2つの特定の問題に適用されている。
論文 参考訳（メタデータ） (2022-01-07T16:49:12Z) - Spatio-Temporal Joint Graph Convolutional Networks for Traffic
Forecasting [75.10017445699532]
近年、時間グラフモデリング問題として交通予測の定式化に焦点が移っている。
本稿では,道路網における交通予測の精度向上のための新しい手法を提案する。
論文 参考訳（メタデータ） (2021-11-25T08:45:14Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。
既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。
そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文 参考訳（メタデータ） (2021-03-30T08:58:45Z) - Time-Series Imputation with Wasserstein Interpolation for Optimal
Look-Ahead-Bias and Variance Tradeoff [66.59869239999459]
ファイナンスでは、ポートフォリオ最適化モデルをトレーニングする前に、損失の計算を適用することができる。
インキュベーションのために全データセットを使用するルックアヘッドバイアスと、トレーニングデータのみを使用することによるインキュベーションの大きなばらつきとの間には、本質的にトレードオフがある。
提案手法は,提案法における差分とルックアヘッドバイアスのトレードオフを最適に制御するベイズ後部コンセンサス分布である。
論文 参考訳（メタデータ） (2021-02-25T09:05:35Z) - A Reinforcement Learning Approach to the Orienteering Problem with Time
Windows [0.0]
Orienteering Problem with Time Windows (OPTW) は、異なる訪問場所から収集した総得点を最大化する最適化問題である。
本研究では,強化学習を用いて学習したポインタネットワークモデルを用いて,OPTW問題の解法を提案する。
論文 参考訳（メタデータ） (2020-11-07T00:38:06Z) - Quantum computing approach to railway dispatching and conflict
management optimization on single-track railway lines [0.4724825031148411]
単線鉄道における遅延と競合管理という,実用的な鉄道派遣問題について考察する。
本稿では,量子アニール技術と互換性のある2次非拘束二元最適化(QUBO)モデルを提案する。
概念実証として、D-Wave量子アニールを用いてポーランドの鉄道網から選択した実生活問題を解く。
論文 参考訳（メタデータ） (2020-10-16T08:17:57Z) - Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet
of Drones Performing Monitoring Missions [4.477547027158141]
事前に定義された地点でノードを複数回訪問する必要があるグラフ上で、一連のドローンの走行経路をスケジュールする方法を示す。
提案した定式化は,交通ネットワークにおける交通流のモニタリングや遠隔地からの探索・救助活動の監視など,いくつかの領域に適用することができる。
詳細な評価では、グリーディアルゴリズムは最適の92.06%でほぼ最適性能を示し、数百台のドローンや位置で設定できる可能性がある。
論文 参考訳（メタデータ） (2020-06-02T09:17:18Z) - Street-level Travel-time Estimation via Aggregated Uber Data [2.838842554577539]
都市部における道路セグメントに沿った時間的パターンの推定は,交通技術者や都市計画者にとって重要な課題である。
本研究では,大都市圏の街路レベルの走行時間を推定するために,粗粒度および集約された走行時間データを活用する手法を提案する。
論文 参考訳（メタデータ） (2020-01-13T21:14:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。