論文の概要: Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics
- arxiv url: http://arxiv.org/abs/2504.10649v1
- Date: Mon, 14 Apr 2025 19:01:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-16 22:07:05.871932
- Title: Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics
- Title（参考訳）: Ride-pool Assignment Algorithms: Modern implementation and Swapping Heuristics
- Authors: Matthew Zalesak, Hins Hu, Samitha Samaranayake,
- Abstract要約: 本稿では,車間ルーティングやリバランシングなどの関連コンポーネントとともに,いくつかの重要な配車プール割り当てアルゴリズムを含む配車プールシミュレータを提案する。
また,新しいアルゴリズムの拡張を容易にするために設計された,高度に最適化されたモジュール化されたC++もオープンソースとして公開しています。
マンハッタンの大規模な実世界のデータセットの実験では、選択された全てのアルゴリズムが互換性を持って実行されているが、新たに提案されたMulti-Round Linear Assignment with Cyclic Exchangeは、計算時間を大幅に短縮した最先端のサービスレートを達成する。
- 参考スコア（独自算出の注目度）: 3.5112462023222504
- License:
- Abstract: On-demand ride-pooling has emerged as a popular urban transportation solution, addressing the efficiency limitations of traditional ride-hailing services by grouping multiple riding requests with spatiotemporal proximity into a single vehicle. Although numerous algorithms have been developed for the Ride-pool Assignment Problem (RAP) -- a core component of ride-pooling systems, there is a lack of open-source implementations, making it difficult to benchmark these algorithms on a common dataset and objective. In this paper, we present the implementation details of a ride-pool simulator that encompasses several key ride-pool assignment algorithms, along with associated components such as vehicle routing and rebalancing. We also open-source a highly optimized and modular C++ codebase, designed to facilitate the extension of new algorithms and features. Additionally, we introduce a family of swapping-based local-search heuristics to enhance existing ride-pool assignment algorithms, achieving a better balance between performance and computational efficiency. Extensive experiments on a large-scale, real-world dataset from Manhattan, NYC reveal that while all selected algorithms perform comparably, the newly proposed Multi-Round Linear Assignment with Cyclic Exchange (LA-MR-CE) algorithm achieves a state-of-the-art service rate with significantly reduced computational time. Furthermore, an in-depth analysis suggests that a performance barrier exists for all myopic ride-pool assignment algorithms due to the system's capacity bottleneck, and incorporating future information could be key to overcoming this limitation.
- Abstract（参考訳）: オンデマンド配車サービスは、従来の配車サービスの効率の限界に対処するため、時空間に近い複数の配車要求を1台の車両にグループ化することで、都市交通ソリューションとして人気を博している。
ライドプール割り当て問題(RAP)には多数のアルゴリズムが開発されているが、オープンソース実装が不足しているため、これらのアルゴリズムを共通のデータセットと目的にベンチマークすることは困難である。
本稿では,車間ルーティングやリバランシングなどの関連コンポーネントとともに,いくつかの重要な配車プール割当てアルゴリズムを含む配車プールシミュレータの実装について述べる。
また、高度に最適化されモジュール化されたC++コードベースをオープンソース化しました。
さらに、既存の配車サービス代入アルゴリズムを強化するために、スワッピングに基づく局所探索ヒューリスティックのファミリーを導入し、性能と計算効率のバランスを良くする。
マンハッタンの大規模な実世界のデータセットに対する大規模な実験により、選択された全てのアルゴリズムが比較可能でありながら、新しく提案されたLA-MR-CEアルゴリズムは、計算時間を著しく短縮した最先端のサービスレートを達成することを明らかにした。
さらに、システムキャパシティのボトルネックにより、すべてのミオピックライドプール割り当てアルゴリズムのパフォーマンス障壁が存在し、将来的な情報を組み込むことが、この制限を克服する鍵となる可能性があることを、詳細な分析で示唆している。
関連論文リスト
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳（メタデータ） (2025-02-14T15:21:27Z) - Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization [0.8786066051474574]
Hierarchical Navigable Small World (HNSW)アルゴリズムは近接探索に広く利用されている。
提案手法は, 局所最適化とクラスタ切断を緩和し, 建設速度を向上し, 推論速度を向上するアルゴリズムである。
様々なベンチマークとデータセットの実験により、我々のアルゴリズムは元のHNSWを精度と速度の両方で上回っていることがわかった。
論文 参考訳（メタデータ） (2025-01-23T10:20:12Z) - MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion
Control in Real Networks [63.24965775030673]
そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。
我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。
我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
論文 参考訳（メタデータ） (2023-02-02T18:27:20Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Fast and computationally efficient generative adversarial network
algorithm for unmanned aerial vehicle-based network coverage optimization [1.2853186701496802]
移動ネットワークにおける動的な交通需要の課題は、無人航空機をベースとした移動セルに対処されている。
将来,無人航空機の膨大な可能性を考えると,カバー範囲最適化のための新しいアルゴリズムを提案する。
提案アルゴリズムは,一意の多層和プーリング損失関数を持つ条件付き生成逆ニューラルネットワークに基づいて実装された。
論文 参考訳（メタデータ） (2022-03-25T12:13:21Z) - Online V2X Scheduling for Raw-Level Cooperative Perception [21.099819062731463]
視界が単独の知性を制限すると、コネクテッドカーの協調的な認識が救助にやってくる。
本稿では,センサ共有スケジューリングのエネルギー最小化問題を定式化して生レベルの協調認識モデルを提案する。
本稿では,対数的性能損失を伴うオンライン学習に基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-12T15:16:45Z) - Real-world Ride-hailing Vehicle Repositioning using Deep Reinforcement
Learning [52.2663102239029]
アイドルヘイリングプラットフォーム上での現実世界の車両の深層強化学習と意思決定時間計画に基づく新しい実用的枠組みを提示する。
本手法は,重み付きバッチ学習アルゴリズムを用いて乗車時の状態値関数を学習する。
配車シミュレーション環境におけるベースラインでアルゴリズムをベンチマークし、収益効率の向上における優位性を実証します。
論文 参考訳（メタデータ） (2021-03-08T05:34:05Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - A Hybrid Multi-Objective Carpool Route Optimization Technique using
Genetic Algorithm and A* Algorithm [0.0]
本研究では,カープール問題に対する最適経路を求めるためのGA-A*ハイブリッドアルゴリズムを提案する。
得られた経路は、ピックアップ/ドロップコストだけでなく、旅行・出先距離を最小化し、サービス提供者の利益を最大化する。
提案アルゴリズムはコルカタのソルトレイク地域に実装されている。
論文 参考訳（メタデータ） (2020-07-11T14:13:20Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。