論文の概要: A metaheuristic for crew scheduling in a pickup-and-delivery problem
with time windows
- arxiv url: http://arxiv.org/abs/2102.01780v1
- Date: Tue, 2 Feb 2021 22:14:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-04 17:21:56.695162
- Title: A metaheuristic for crew scheduling in a pickup-and-delivery problem
with time windows
- Title（参考訳）: タイムウィンドウを用いたピックアップ・アンド・デリバリー問題における乗組員スケジューリングのメタヒューリスティック
- Authors: Mauro Lucci, Daniel Sever\'in, Paula Zabala
- Abstract要約: 車両ルーティングと乗組員スケジューリングの問題(VRCSP)は、車両の群れのルートを同時に計画し、乗組員をスケジューリングすることである。
我々は、トラックやドライバーを用いて、時間窓によるピックアップ・アンド・デリバリー要求を計画の地平線上で満たさなければならないVRCSPを提案する。
我々は15都市にまたがる100件の要求に対して、12～32台のトラックを1時間足らずで高品質なソリューションを見つけました。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A vehicle routing and crew scheduling problem (VRCSP) consists of
simultaneously planning the routes of a fleet of vehicles and scheduling the
crews, where the vehicle-crew correspondence is not fixed through time. This
allows a greater planning flexibility and a more efficient use of the fleet,
but in counterpart, a high synchronisation is demanded. In this work, we
present a VRCSP where pickup-and-delivery requests with time windows have to be
fulfilled over a given planning horizon by using trucks and drivers. Crews can
be composed of 1 or 2 drivers and any of them can be relieved in a given set of
locations. Moreover, they are allowed to travel among locations with
non-company shuttles, at an additional cost that is minimised. As our problem
considers distinct routes for trucks and drivers, we have an additional
flexibility not contemplated in other previous VRCSP given in the literature
where a crew is handled as an indivisible unit. We tackle this problem with a
two-stage sequential approach: a set of truck routes is computed in the first
stage and a set of driver routes consistent with the truck routes is obtained
in the second one. We design and evaluate the performance of a metaheuristic
based algorithm for the latter stage. Our algorithm is mainly a GRASP with a
perturbation procedure that allows reusing solutions already found in case the
search for new solutions becomes difficult. This procedure together with other
to repair infeasible solutions allow us to find high-quality solutions on
instances of 100 requests spread across 15 cities with a fleet of 12-32 trucks
(depending on the planning horizon) in less than an hour. We also conclude that
the possibility of carrying an additional driver leads to a decrease of the
cost of external shuttles by about 60% on average with respect to individual
crews and, in some cases, to remove this cost completely.
- Abstract（参考訳）: 車両のルーティングおよびクルースケジューリング問題(VRCSP)は、車両の艦隊のルートを計画し、車両とクルーの対応が時間内に固定されていない乗組員をスケジュールすることからなる。
これにより、計画の柔軟性が向上し、艦隊の効率が向上するが、それに対して高い同期が要求される。
本研究では,トラックやドライバーを用いて,時間窓によるピックアップ・アンド・デリバリ要求を計画の地平線上で満たさなければならないVRCSPを提案する。
クルーは1人または2人のドライバーで構成され、それらのどれかは特定の場所のセットで緩和することができます。
さらに、非商用シャトルの場所間での移動も可能で、追加費用は最小限に抑えられる。
我々の問題はトラックとドライバーの異なる経路を考えるため、クルーが不可分なユニットとして扱われる文献にあるように、以前のvrcspでは考えられなかった柔軟性が増している。
2段階連続的なアプローチでこの問題に取り組みます:トラックルートのセットは第1段階で計算され、トラックルートと一致するドライバールートのセットは第2段階で取得されます。
後者の段階におけるメタヒューリスティックベースアルゴリズムの性能を設計・評価する。
提案手法は,新しい解の探索が困難になった場合の解の再使用を可能にする摂動手続きを主目的とする。
この手順は、他の修理不可能ソリューションと一緒に、12-32台のトラック(計画地平線に応じて)を1時間未満で、15都市にまたがる100のリクエストのインスタンスで高品質のソリューションを見つけることができます。
また,追加の運転士を乗せることによって,各乗務員に対して平均約60%の外部シャトルコストが削減され,場合によってはこのコストが完全に削減される可能性が示唆された。
関連論文リスト
- An Online Approach to Solving Public Transit Stationing and Dispatch
Problem [7.948662269574215]
交通機関は限られた数の車両を予備に保管し、破壊時に被害経路を緩和するために派遣する。
本稿では、この問題を解決するために、非ミオピックシーケンシャルな決定手順を用いた原則的アプローチについて述べる。
実験の結果、提案手法は乗客を2%増やし、デッドヘッドマイルを40%削減することがわかった。
論文 参考訳（メタデータ） (2024-03-05T21:48:29Z) - 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) - DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in
Complex Environments [55.204450019073036]
本稿では,倉庫環境における移動ロボットのためのタスク割り当てと分散ナビゲーションアルゴリズムを提案する。
本稿では,共同分散タスク割り当てとナビゲーションの問題について考察し,それを解決するための2段階のアプローチを提案する。
ロボットの衝突のない軌道の計算では,タスク完了時間において最大14%の改善と最大40%の改善が観察される。
論文 参考訳（メタデータ） (2022-09-07T00:35:27Z) - Supervised Permutation Invariant Networks for Solving the CVRP with
Bounded Fleet Size [3.5235974685889397]
車両ルーティング問題などの最適化問題を解くための学習は、大きな計算上の利点をもたらす。
本研究では,アプリオリ固定数の車両を尊重しながら,スクラッチから完全なツアー計画を構築する強力な教師付きディープラーニングフレームワークを提案する。
効率的な後処理方式と組み合わせることで,教師付きアプローチはより高速かつ容易にトレーニングできるだけでなく,競争力のある結果が得られる。
論文 参考訳（メタデータ） (2022-01-05T10:32:18Z) - Integrated Vehicle Routing and Monte Carlo Scheduling Approach for the
Home Service Assignment, Routing, and Scheduling Problem [0.2578242050187029]
ホームサービスマネジメントによるH-SARA問題の定式化と解決を行う。
私たちは、旅行時間、期間、および顧客のキャンセルがサービス管理であると仮定します。
キャンセルの2つのモデルと、ルーティングとスケジューリングへの影響について紹介する。
本研究は, 最適ルーティング, スケジューリング, および経路破壊メタヒューリスティックが両モデルのキャンセルに与える影響を示す一連の数値実験について考察する。
論文 参考訳（メタデータ） (2021-06-30T16:12:14Z) - An SMT Based Compositional Model to Solve a Conflict-Free Electric
Vehicle Routing Problem [2.64699517152535]
CF-EVRP(Electric Conflict-Free Vehicle Routing Problem)は、車両の運転範囲の制限、顧客への配送時間帯の制限、道路セグメントが許容できる車両数に対する制限といった制約を含む。
我々は、問題をより小さく、より単純なサブプロブレムに分解し、準最適で実現可能なソリューションを提供する構成モデルを開発する。
論文 参考訳（メタデータ） (2021-06-10T20:37:46Z) - Flatland Competition 2020: MAPF and MARL for Efficient Train
Coordination on a Grid World [49.80905654161763]
車両再スケジュール問題(vrsp)の解法開発を目的としたフラットランドコンペティション
VRSPは、交通ネットワークにおける旅行のスケジュールと、故障が発生した場合の車両の再スケジュールに関するものである。
現代の鉄道網の複雑化は、交通の動的リアルタイムスケジューリングを事実上不可能にします。
論文 参考訳（メタデータ） (2021-03-30T17:13:29Z) - A Maximum Independent Set Method for Scheduling Earth Observing
Satellite Constellations [41.013477422930755]
本稿では,衛星スケジューリング問題の解法として,実現不可能なグラフ表現を生成する手法を提案する。
光衛星のスカイサット星座と、最大24個の衛星のシミュレートされた星座の、要求された最大10,000の撮像位置のシナリオでテストされている。
論文 参考訳（メタデータ） (2020-08-15T19:32:21Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z) - Modeling and solving the multimodal car- and ride-sharing problem [0.0]
マルチモーダルカー・ライドシェアリング問題(MMCRP)を紹介する。
車両のプールは一連の乗車要求をカバーするために使用され、発見されていない要求は他の交通手段に割り当てられる。
カラム生成に基づく2層分解アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-15T09:43:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。