論文の概要: Optimal Chaining of Vehicle Plans with Time Windows

• arxiv url: http://arxiv.org/abs/2401.02873v3
• Date: Sat, 24 Feb 2024 22:51:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-28 00:08:43.467386
• Title: Optimal Chaining of Vehicle Plans with Time Windows
• Title（参考訳）: タイムウインドウを用いた車両計画の最適チェーン化
• Authors: David Fiedler, Fabio V. Difonzo and Jan Mrkos
• Abstract要約: 本研究は,時間ウィンドウで許容される遅延を考慮した新しい計画連鎖定式化と解法を提案する。 静的ダイヤル・ア・ライド問題を解くための新しい車両ディスパッチ手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For solving problems from the domain of Mobility-on-Demand (MoD), we often need to connect vehicle plans into plans spanning longer time, a process we call plan chaining. As we show in this work, chaining of the plans can be used to reduce the size of MoD providers' fleet (fleet-sizing problem) but also to reduce the total driven distance by providing high-quality vehicle dispatching solutions in MoD systems. Recently, a solution that uses this principle has been proposed to solve the fleet-sizing problem. The method does not consider the time flexibility of the plans. Instead, plans are fixed in time and cannot be delayed. However, time flexibility is an essential property of all vehicle problems with time windows. This work presents a new plan chaining formulation that considers delays as allowed by the time windows and a solution method for solving it. Moreover, we prove that the proposed plan chaining method is optimal, and we analyze its complexity. Finally, we list some practical applications and perform a demonstration for one of them: a new heuristic vehicle dispatching method for solving the static dial-a-ride problem. The demonstration results show that our proposed method provides a better solution than the two heuristic baselines for the majority of instances that cannot be solved optimally. At the same time, our method does not have the largest computational time requirements compared to the baselines. Therefore, we conclude that the proposed optimal chaining method provides not only theoretically sound results but is also practically applicable.
• Abstract（参考訳）: モビリティ・オン・デマンド(MoD)の領域から問題を解決するためには、計画チェインと呼ばれる長い時間にわたる計画に車両計画を接続する必要があります。 本研究で示すように、この計画の連鎖化は、MoDシステムにおける高品質な車両配車ソリューションを提供することにより、MoDプロバイダの車両の規模を縮小する(フライングサイズ問題)だけでなく、総駆動距離の削減にも有効である。 近年,艦隊規模の問題を解決するために,この原理を用いた解法が提案されている。 この方法は計画の時間的柔軟性を考慮しない。 代わりに、計画は時間内に修正され、遅れることはない。 しかしながら、時間の柔軟性は、タイムウインドウのすべての車両問題にとって不可欠な特性である。 本研究は,時間ウィンドウで許容される遅延を考慮した新しい計画連鎖定式化と解法を提案する。 さらに,提案手法が最適であることを証明し,その複雑さを分析した。 最後に, 静的ダイヤル・ア・ライド問題の解法として, 新しいヒューリスティックな車両配車方式を提案する。 その結果,提案手法は最適に解けないほとんどのインスタンスに対して,2つのヒューリスティックなベースラインよりも優れた解を提供することを示した。 同時に,本手法は,ベースラインと比較して計算時間の要求が最大ではない。 したがって,提案手法は理論的に健全な結果を提供するだけでなく,実用的にも適用可能である。

関連論文リスト

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• Solving the Team Orienteering Problem with Transformers [46.93254771681026]
  車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。 本稿では,チームオリエンテーリング問題を高速かつ高精度に解決できる多エージェント経路計画システムを提案する。
  論文  参考訳（メタデータ） (2023-11-30T16:10:35Z)
• Optimization-based Learning for Dynamic Load Planning in Trucking Service Networks [14.972807276002465]
  本稿では,フローと負荷計画の課題を共同で検討するアウトバウンド負荷計画問題(OLPP)について考察する。 本研究の目的は,ネットワーク上の端末で意思決定を行う計画立案者に対して,意思決定支援ツールを開発することである。
  論文  参考訳（メタデータ） (2023-07-08T21:28:20Z)
• Light Unbalanced Optimal Transport [69.18220206873772]
  既存の解法は、原理に基づいているか、複数のニューラルネットワークを含む複雑な最適化目標を重み付けしている。 我々は,この解法がUEOT解の普遍近似を提供し,一般化限界を得ることを示す。
  論文  参考訳（メタデータ） (2023-03-14T15:44:40Z)
• Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows [5.818566833386833]
  オフラインPDPTWのクラスを解くための新しい時間分解方式を提案する。 私たちのフレームワークはよりスケーラブルで、さまざまな難易度の問題インスタンスに対して優れたソリューションを提供することができます。
  論文  参考訳（メタデータ） (2023-03-06T20:07:05Z)
• A Hierarchical Temporal Planning-Based Approach for Dynamic Hoist Scheduling Problems [11.66506213335498]
  ホイストスケジューリングは、自律デバイスの開発で産業応用の電気めっきのボトルネックとなっている。 適応型PDDLの形で新しい時間計画問題としてホイストスケジューリング問題を定式化する。 この問題に対するソリューションメソッドの評価に使用できる実生活ベンチマークインスタンスのコレクションを提供する。
  論文  参考訳（メタデータ） (2022-12-11T05:30:44Z)
• T*$\varepsilon$ -- Bounded-Suboptimal Efficient Motion Planning for Minimum-Time Planar Curvature-Constrained Systems [7.277760003553328]
  本研究では,障害物の存在下での曲率制約系の衝突のない経路を見つけることの問題点を考察する。 有界-準最適解を求めることにより、使用した時間-最適遷移の数を劇的に削減できることを示す。
  論文  参考訳（メタデータ） (2022-04-04T17:38:36Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• Motion Planning by Learning the Solution Manifold in Trajectory Optimization [6.127237810365965]
  本稿では,運動計画問題に対する無限の解集合を生成する最適化手法を提案する。 結果は、実験モデルが運動計画問題のホモトピー解の無限集合を表すことを示している。
  論文  参考訳（メタデータ） (2021-07-13T04:47:47Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。 我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
  論文  参考訳（メタデータ） (2021-05-01T10:18:34Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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