論文の概要: An Evolutionary Algorithm For the Vehicle Routing Problem with Drones with Interceptions
- arxiv url: http://arxiv.org/abs/2409.14173v1
- Date: Sat, 21 Sep 2024 15:26:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-06 23:48:26.104166
- Title: An Evolutionary Algorithm For the Vehicle Routing Problem with Drones with Interceptions
- Title（参考訳）: 干渉のあるドローンによる車両走行問題に対する進化的アルゴリズム
- Authors: Carlos Pambo, Jacomine Grobler,
- Abstract要約: トラックとドローンをラストマイル配送の課題への解決策として利用することは、この論文で探求された新しい、有望な研究方向である。
本稿では,ドローンのインターセプションによる車両ルーティング問題を解決するための進化的アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.2455468619225742
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The use of trucks and drones as a solution to address last-mile delivery challenges is a new and promising research direction explored in this paper. The variation of the problem where the drone can intercept the truck while in movement or at the customer location is part of an optimisation problem called the vehicle routing problem with drones with interception (VRPDi). This paper proposes an evolutionary algorithm to solve the VRPDi. In this variation of the VRPDi, multiple pairs of trucks and drones need to be scheduled. The pairs leave and return to a depot location together or separately to make deliveries to customer nodes. The drone can intercept the truck after the delivery or meet up with the truck at the following customer location. The algorithm was executed on the travelling salesman problem with drones (TSPD) datasets by Bouman et al. (2015), and the performance of the algorithm was compared by benchmarking the results of the VRPDi against the results of the VRP of the same dataset. This comparison showed improvements in total delivery time between 39% and 60%. Further detailed analysis of the algorithm results examined the total delivery time, distance, node delivery scheduling and the degree of diversity during the algorithm execution. This analysis also considered how the algorithm handled the VRPDi constraints. The results of the algorithm were then benchmarked against algorithms in Dillon et al. (2023) and Ernst (2024). The latter solved the problem with a maximum drone distance constraint added to the VRPDi. The analysis and benchmarking of the algorithm results showed that the algorithm satisfactorily solved 50 and 100-nodes problems in a reasonable amount of time, and the solutions found were better than those found by the algorithms in Dillon et al. (2023) and Ernst (2024) for the same problems.
- Abstract（参考訳）: 最終マイルの配送課題に対処するための解決策としてトラックとドローンを使用することは、この論文で探求された新しい、有望な研究方向である。
ドローンが移動中や顧客の位置でトラックをインターセプトできるという問題の変化は、インターセプション付きドローンによる車両ルーティング問題(VRPDi)と呼ばれる最適化問題の一部である。
本稿では,VRPDiを解くための進化的アルゴリズムを提案する。
VRPDiのこのバリエーションでは、複数のトラックとドローンを予定する必要がある。
ペアは立ち去り、一緒に補給所の場所に戻り、別々に顧客ノードに配送する。
ドローンは配達後にトラックをインターセプトしたり、次の顧客場所でトラックと出会うことができる。
このアルゴリズムは、Boumanらによるドローン(TSPD)データセットによるトラベルセールスマン問題(2015年)で実行され、同じデータセットのVRPの結果に対してVRPDiの結果をベンチマークすることでアルゴリズムのパフォーマンスを比較した。
この比較では、デリバリ時間全体の39%から60%の改善が見られた。
さらに詳細な解析を行い,アルゴリズム実行時の納品時間,距離,ノードの納入スケジュール,多様性の度合いを検討した。
この分析では、アルゴリズムがVRPDiの制約をどのように扱ったかも検討した。
アルゴリズムの結果は、Dillon et al (2023) と Ernst (2024) のアルゴリズムと比較された。
後者はVRPDiに追加された最大ドローン距離制限でこの問題を解決した。
アルゴリズム解析とベンチマークにより,50ノードと100ノードの問題を妥当な時間で解き,同じ問題に対してDillon et al (2023) と Ernst (2024) のアルゴリズムよりも優れた解が得られた。
関連論文リスト
- VRPD-DT: Vehicle Routing Problem with Drones Under Dynamically Changing Traffic Conditions [12.323383132739195]
動的に変化する交通条件(VRPD-DT)下でのドローンによる車両ルーティング問題という新しい問題を提案する。
我々は,機械学習による走行時間予測アルゴリズムを用いて,実際の走行距離と予測走行時間を決定する新しいコストモデルを構築した。
可変近傍降下(VND)アルゴリズムは,交通条件の動的条件下で最適なトラック走行経路を求めるために開発された。
論文 参考訳（メタデータ） (2024-04-13T19:28:24Z) - A self-adaptive genetic algorithm for the flying sidekick travelling
salesman problem [0.0]
本稿では,自己適応型遺伝的アルゴリズムを用いてFSTSP(Flying Sidekick Travelling Salesman Problem)の解法を提案する。
FSTSPでは、ドローンを戦略的に展開し、顧客の位置情報を入手し難い場所に提供しながら、すべての場所を訪問するための総時間を最小化する。
論文 参考訳（メタデータ） (2023-10-23T08:51:02Z) - A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone [0.8287206589886881]
トラベル・セールスマン問題(TSPD)やフライング・サイドキック・トラベリング・セールスマン問題(FSTSP)と呼ばれる新たな交通問題が存在する。
本研究では,局所探索と動的プログラミングを取り入れたTSPDとFSTSPのハイブリッド遺伝的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-01T16:11:09Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Rethinking Drone-Based Search and Rescue with Aerial Person Detection [79.76669658740902]
航空ドローンの映像の視覚検査は、現在土地捜索救助(SAR)活動に不可欠な部分である。
本稿では,この空中人物検出(APD)タスクを自動化するための新しいディープラーニングアルゴリズムを提案する。
本稿では,Aerial Inspection RetinaNet (AIR) アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2021-11-17T21:48:31Z) - Feeling of Presence Maximization: mmWave-Enabled Virtual Reality Meets
Deep Reinforcement Learning [76.46530937296066]
本稿では,無線モバイルユーザに対して,超信頼性でエネルギー効率のよいバーチャルリアリティ(VR)体験を提供するという課題について検討する。
モバイルユーザへの信頼性の高い超高精細ビデオフレーム配信を実現するために,コーディネートマルチポイント(CoMP)伝送技術とミリ波(mmWave)通信を利用する。
論文 参考訳（メタデータ） (2021-06-03T08:35:10Z) - Distributed Multi-agent Meta Learning for Trajectory Design in Wireless
Drone Networks [151.27147513363502]
本稿では,動的無線ネットワーク環境で動作するエネルギー制約型ドローン群に対する軌道設計の問題点について検討する。
値ベース強化学習(VDRL)ソリューションとメタトレイン機構を提案する。
論文 参考訳（メタデータ） (2020-12-06T01:30:12Z) - Multi-Agent Reinforcement Learning in NOMA-aided UAV Networks for
Cellular Offloading [59.32570888309133]
複数の無人航空機(UAV)によるセルローディングのための新しい枠組みの提案
非直交多重アクセス(NOMA)技術は、無線ネットワークのスペクトル効率をさらに向上するために、各UAVに採用されている。
相互深いQ-network (MDQN) アルゴリズムは,UAVの最適3次元軌道と電力配分を共同で決定するために提案される。
論文 参考訳（メタデータ） (2020-10-18T20:22:05Z) - Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet
of Drones Performing Monitoring Missions [4.477547027158141]
事前に定義された地点でノードを複数回訪問する必要があるグラフ上で、一連のドローンの走行経路をスケジュールする方法を示す。
提案した定式化は,交通ネットワークにおける交通流のモニタリングや遠隔地からの探索・救助活動の監視など,いくつかの領域に適用することができる。
詳細な評価では、グリーディアルゴリズムは最適の92.06%でほぼ最適性能を示し、数百台のドローンや位置で設定できる可能性がある。
論文 参考訳（メタデータ） (2020-06-02T09:17:18Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z) - Algorithms for Optimizing Fleet Staging of Air Ambulances [0.0]
本研究は、整数線形計画法における最適カバレッジ問題を構成する。
グロビは開発されたモデルでプログラムされ、パフォーマンスに時間を費やした。
ベースランキングを実装したソリューションが作成され、その後、ローカルおよびタブ検索ベースのアルゴリズムが導入された。
論文 参考訳（メタデータ） (2020-01-10T04:32:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。