論文の概要: Modeling and solving the multimodal car- and ride-sharing problem
- arxiv url: http://arxiv.org/abs/2001.05490v2
- Date: Wed, 28 Sep 2022 12:58:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 06:32:34.013814
- Title: Modeling and solving the multimodal car- and ride-sharing problem
- Title（参考訳）: マルチモーダルカー・ライドシェアリング問題のモデル化と解決
- Authors: Miriam Enzi, Sophie N. Parragh, David Pisinger and Matthias
Prandtstetter
- Abstract要約: マルチモーダルカー・ライドシェアリング問題(MMCRP)を紹介する。
車両のプールは一連の乗車要求をカバーするために使用され、発見されていない要求は他の交通手段に割り当てられる。
カラム生成に基づく2層分解アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the multimodal car- and ride-sharing problem (MMCRP), in which a
pool of cars is used to cover a set of ride requests while uncovered requests
are assigned to other modes of transport (MOT). A car's route consists of one
or more trips. Each trip must have a specific but non-predetermined driver,
start in a depot and finish in a (possibly different) depot. Ride-sharing
between users is allowed, even when two rides do not have the same origin
and/or destination. A user has always the option of using other modes of
transport according to an individual list of preferences.
The problem can be formulated as a vehicle scheduling problem. In order to
solve the problem, an auxiliary graph is constructed in which each trip
starting and ending in a depot, and covering possible ride-shares, is modeled
as an arc in a time-space graph. We propose a two-layer decomposition algorithm
based on column generation, where the master problem ensures that each request
can only be covered at most once, and the pricing problem generates new
promising routes by solving a kind of shortest-path problem in a time-space
network. Computational experiments based on realistic instances are reported.
The benchmark instances are based on demographic, spatial, and economic data of
Vienna, Austria. We solve large instances with the column generation based
approach to near optimality in reasonable time, and we further investigate
various exact and heuristic pricing schemes.
- Abstract（参考訳）: マルチモーダルカー・ライドシェアリング問題 (MMCRP) では、車両プールが一連の乗車要求をカバーし、未発見の要求を他の交通手段 (MOT) に割り当てる。
車両の経路は1つまたは複数のトリップで構成される。
各トリップには、特定のが非決定的なドライバーがいて、デポから始まり、(おそらくは異なる)デポで終わる必要がある。
利用者間のライドシェアリングは、2つの乗車が同じ起源や目的地を持っていない場合でも許可される。
ユーザは、好みの個々のリストに従って、他の転送モードを使用するオプションを常に持っている。
この問題は車両スケジューリング問題として定式化することができる。
この問題を解決するために,各走行開始と終了をデポで表し,乗り合いをカバーした補助グラフを時間空間グラフの弧としてモデル化する。
本稿では,列生成に基づく2層分解アルゴリズムを提案し,各要求が最大1回しかカバーできないことを保証するとともに,時間空間ネットワークにおける最短経路問題の解法により,新たな経路を生成する。
実例に基づく計算実験が報告されている。
ベンチマークの例はオーストリアのウィーンの人口統計、空間データ、経済データに基づいている。
我々は,列生成に基づく手法を用いて,合理的な時間における近似最適性を求める大規模インスタンスを解決し,さらに様々な厳密かつヒューリスティックな価格体系について検討した。
関連論文リスト
- Contextual Stochastic Vehicle Routing with Time Windows [47.91283991228738]
本研究は,車両経路問題に時間窓 (VRPTW) と走行時間を用いて検討する。
観測された特徴に照らし合わせて,輸送コストと到着遅れの罰則を最小化する,文脈的VRPTWを導入する。
本稿では,歴史データを用いた新しいデータ駆動規範モデルを提案する。
論文 参考訳（メタデータ） (2024-02-10T14:56:36Z) - Solving the Team Orienteering Problem with Transformers [46.93254771681026]
車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。
本稿では,チームオリエンテーリング問題を高速かつ高精度に解決できる多エージェント経路計画システムを提案する。
論文 参考訳（メタデータ） (2023-11-30T16:10:35Z) - Fair collaborative vehicle routing: A deep multi-agent reinforcement
learning approach [49.00137468773683]
協力的な車両ルーティングは、キャリアがそれぞれの輸送要求を共有し、互いに代表して輸送要求を実行することで協力するときに発生する。
従来のゲーム理論解の概念は、特性関数がエージェントの数とともに指数関数的にスケールするので、計算に費用がかかる。
我々は,この問題を,深層マルチエージェント強化学習を用いて解決した連立交渉ゲームとしてモデル化することを提案する。
論文 参考訳（メタデータ） (2023-10-26T15:42:29Z) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。
提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。
本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文 参考訳（メタデータ） (2023-04-28T07:09:23Z) - Multi-Start Team Orienteering Problem for UAS Mission Re-Planning with
Data-Efficient Deep Reinforcement Learning [9.877261093287304]
我々は、当初車両が補給所から離れた場所にあり、燃料の量が異なるミッション再計画問題について検討する。
そこで我々は,各部分ツアーに対する自己注意と,部分ツアーと残りのノード間のエンコーダ・デコーダの注意を組み込んだポリシーネットワークを構築した。
本稿では,複数の非重複サンプルのロールアウトに基づく局所的なミニバッチベースラインに,グリーディロールアウトベースラインを置き換えたREINFORCEアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-02T15:15:56Z) - Machine-learning-based arc selection for constrained shortest path
problems in column generation [5.08128537391027]
本研究では,機械学習に基づく新しい価格アルゴリズムを提案する。
目的は、ネットワークのサイズを小さくし、PPを加速することであり、線形緩和溶液の一部となる確率の高い弧のみを保持することである。
この方法は、公共交通機関における車両と乗員のスケジューリング問題と、時間窓による車両のルーティング問題という2つの特定の問題に適用されている。
論文 参考訳（メタデータ） (2022-01-07T16:49:12Z) - A Case Study of Vehicle Route Optimization [2.2101681534594237]
本研究では,主に関連する実世界の制約と要件を取り入れる。
時間ウィンドウと停止時間のための2段階戦略とタイムラインアルゴリズムを提案する。
4つの最先端アルゴリズムに対する8つの異なる問題インスタンスの評価は、我々のアプローチが与えられた制約を妥当な時間で処理することを示している。
論文 参考訳（メタデータ） (2021-11-17T13:10:55Z) - The bi-objective multimodal car-sharing problem [0.0]
BiO-MMCPの目的は、旅行のための輸送の最適モードを決定することである。
ユーザ満足度は共有モビリティシステムにおいて重要な側面であるため、ユーザの好みを第2の目的として考える。
我々は2つの双方向フレームワークに埋め込まれた分岐とカットのアルゴリズムを開発した。
論文 参考訳（メタデータ） (2020-10-18T13:48:17Z) - Multi-Agent Routing Value Iteration Network [88.38796921838203]
疎結合グラフの学習値に基づいてマルチエージェントルーティングを行うことができるグラフニューラルネットワークに基づくモデルを提案する。
最大25ノードのグラフ上で2つのエージェントでトレーニングしたモデルでは,より多くのエージェントやノードを持つ状況に容易に一般化できることが示されている。
論文 参考訳（メタデータ） (2020-07-09T22:16:45Z) - Modeling and solving a vehicle-sharing problem considering multiple
alternative modes of transport [0.0]
1つ以上の補給所と定員の定員を持つ企業における自動車シェアリングについて検討する。
車両は、デポからデポへの利用者のフルトリップに使用する必要がある。
我々は,他の交通手段と比較して省エネを最大化するために,利用者旅行に車両を割り当てることを目指している。
論文 参考訳（メタデータ） (2020-03-17T11:12: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。