論文の概要: Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows

• arxiv url: http://arxiv.org/abs/2303.03475v1
• Date: Mon, 6 Mar 2023 20:07:05 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-08 17:20:48.443666
• Title: Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows
• Title（参考訳）: タイムウインドウを用いたオフラインピックアップ・配信問題に対するローリングホライズンに基づく時間分解
• Authors: Youngseo Kim, Danushka Edirimanna, Michael Wilbur, Philip Pugliese, Aron Laszka, Abhishek Dubey, Samitha Samaranayake
• Abstract要約: オフラインPDPTWのクラスを解くための新しい時間分解方式を提案する。 私たちのフレームワークはよりスケーラブルで、さまざまな難易度の問題インスタンスに対して優れたソリューションを提供することができます。
• 参考スコア（独自算出の注目度）: 5.818566833386833
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. We compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances, the baseline approach is as competitive as our framework. However, in larger problem instances, our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.
• Abstract（参考訳）: 時間窓によるオフラインピックアップと配送の問題(PDPTW)は、輸送コミュニティにおける古典的な組合せ最適化の問題であり、計算的に非常に難しいことが証明されている。 問題の複雑さのため、現実的な問題インスタンスはヒューリスティックスによってのみ解決できる。 様々なヒューリスティックの中で共通の戦略は、問題分解、すなわち、より小さな部分問題の集合への大規模問題の還元であり、空間分解と時間分解は2つの自然なアプローチである。 空間分解は一定の条件下では成功したが、分解境界を越えてサブプロブレム解を縫い合わせることが困難であるため、効果的な時間分解は困難である。 本研究では,時間ウィンドウが狭いPDPTWのクラスを解くための時間分解手法を提案する。 近年,オンラインダイヤル・ア・ライド問題において,転がり地平線最適化の一般的な考え方とともに普及した手法を活用している。 我々の知る限りでは、このようなアプローチを用いてオフラインPDPTWを解く最初の試みである。 フレームワークのパフォーマンスとスケーラビリティを示すために、パラトランジットサービスの最適化をモチベーションの例として使用しています。 Google OR-Toolsを用いたオフラインヒューリスティックアルゴリズムとの比較を行った。 小さな問題例では、ベースラインアプローチはフレームワークと同じくらい競争力があります。 しかし、より大きな問題インスタンスでは、我々のフレームワークはよりスケーラブルで、様々な難易度の問題インスタンスに対して優れたソリューションを提供できる一方、ベースラインアルゴリズムは、同等の計算時間内で実現可能なソリューションを見つけるのに失敗することが多い。

関連論文リスト

• Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem [1.6874375111244329]
  トラベリングセールスパーソン問題(TSP)の解決はいまだに永続的な課題である。 ヒューリスティックな解法は、高品質な解を見つけるための需要を効果的に解決する。 これらの解法の中で、Lin-Kernighan-Helsgaun(LKH)は遺伝的アルゴリズムの性能を補完するものとして際立っている。
  論文  参考訳（メタデータ） (2024-07-04T13:38:19Z)
• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• Paired Autoencoders for Inverse Problems [3.355436702348694]
  前方問題は偏微分方程式の離散化である非線形逆問題の解を考える。 典型的なアルゴリズムの主な計算ボトルネックは、データ不適合性の直接推定である。 逆問題に対する確率自由度推定器として,ペアオートエンコーダフレームワークを用いる。
  論文  参考訳（メタデータ） (2024-05-21T22:00:34Z)
• A Greedy Quantum Route-Generation Algorithm [0.0]
  本稿では,量子コンピュータから得られた全てのサンプルからの情報を用いて,経路を生成するグリーディアルゴリズムを提案する。 有向非巡回グラフ (DAG) としての定式化における量子ビットの関係に気付き, 実現可能な解を適応的に構築するアルゴリズムを設計した。
  論文  参考訳（メタデータ） (2024-05-05T21:20:46Z)
• Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problem [36.88003015541172]
  そこで本稿では,TSP と Time Windows (TSPTW) の正当性を改善するために,ルックアヘッド情報を用いた新しい学習手法を提案する。 多様なデータセットに関する包括的な実験により、MUSLAは既存のベースラインを上回り、一般化可能性を示す。
  論文  参考訳（メタデータ） (2024-03-08T13:49:21Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT [4.873362301533824]
  車両ルーティングはNPハード最適化問題のよく知られたクラスである。 最近の強化学習の取り組みは有望な代替手段である。 本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-14T06:27:09Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。 異種車両ルーティング問題に対するMineReduceの適用について述べる。
  論文  参考訳（メタデータ） (2020-05-15T08:49:50Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。