論文の概要: A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone
- arxiv url: http://arxiv.org/abs/2303.00614v2
- Date: Tue, 30 Apr 2024 01:06:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-01 20:17:07.646458
- Title: A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone
- Title（参考訳）: ドローンによるセールスマン問題に対するタイプアウェアクロモソームを用いたハイブリッド遺伝的アルゴリズム
- Authors: Sasan Mahmoudinazlou, Changhyun Kwon,
- Abstract要約: トラベル・セールスマン問題(TSPD)やフライング・サイドキック・トラベリング・セールスマン問題(FSTSP)と呼ばれる新たな交通問題が存在する。
本研究では,局所探索と動的プログラミングを取り入れたTSPDとFSTSPのハイブリッド遺伝的アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.8287206589886881
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: There are emerging transportation problems known as the Traveling Salesman Problem with Drone (TSPD) and the Flying Sidekick Traveling Salesman Problem (FSTSP) that involve using a drone in conjunction with a truck for package delivery. This study presents a hybrid genetic algorithm for solving TSPD and FSTSP by incorporating local search and dynamic programming. Similar algorithms exist in the literature. Our algorithm, however, considers more sophisticated chromosomes and less computationally complex dynamic programming to enable broader exploration by the genetic algorithm and efficient exploitation through dynamic programming and local search. The key contribution of this paper is the discovery of how decision-making processes for solving TSPD and FSTSP should be divided among the layers of genetic algorithm, dynamic programming, and local search. In particular, our genetic algorithm generates the truck and the drone sequences separately and encodes them in a type-aware chromosome, wherein each customer is assigned to either the truck or the drone. We apply local search to each chromosome, which is decoded by dynamic programming for fitness evaluation. Our new algorithm is shown to outperform existing algorithms on most benchmark instances in both quality and time. Our algorithms found the new best solutions for 538 TSPD instances out of 920 and 74 FSTSP instances out of 132.
- Abstract（参考訳）: ドローンによるトラベルセールスマン問題 (TSPD) やFSTSP (Flying Sidekick Traveling Salesman Problem) と呼ばれる新たな輸送問題があり、荷物の配達にドローンを併用する。
本研究では,局所探索と動的プログラミングを取り入れたTSPDとFSTSPのハイブリッド遺伝的アルゴリズムを提案する。
同様のアルゴリズムが文献に存在している。
しかし,本アルゴリズムは,遺伝的アルゴリズムによるより高度な染色体の探索と,動的プログラムと局所探索による効率的な利用を可能にするため,計算量が少ない動的プログラムを考慮に入れている。
本論文の重要な貢献は、TSPDとFSTSPを解くための意思決定プロセスが、遺伝的アルゴリズム、動的プログラミング、局所探索の層にどのように分割されるべきかを明らかにすることである。
特に、我々の遺伝的アルゴリズムは、トラックとドローンのシーケンスを別々に生成し、それらをタイプ認識染色体にエンコードし、それぞれの顧客がトラックまたはドローンに割り当てられる。
本研究では,各染色体に局所探索を適用し,動的プログラムで復号化して適合度評価を行う。
我々の新しいアルゴリズムは、ほとんどのベンチマークインスタンスにおいて、品質と時間の両方で既存のアルゴリズムより優れていることを示す。
アルゴリズムでは,920インスタンス中538インスタンス,132インスタンス中74インスタンス中74インスタンスに対して,新たなベストソリューションが見つかった。
関連論文リスト
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳（メタデータ） (2025-02-14T15:21:27Z) - An Evolutionary Algorithm For the Vehicle Routing Problem with Drones with Interceptions [0.2455468619225742]
トラックとドローンをラストマイル配送の課題への解決策として利用することは、この論文で探求された新しい、有望な研究方向である。
本稿では,ドローンのインターセプションによる車両ルーティング問題を解決するための進化的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-21T15:26:24Z) - Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
本稿では,ワークステーションの注文処理,アイテムポッドの割り当て,ワークステーションでの注文処理のスケジュールを最適化することで,ウェアハウジングにおけるロボット部品対ピッカー操作を支援する。
そこで我々は, 大規模近傍探索を用いて, サブプロブレム生成に対する学習を最適化する手法を提案する。
Amazon Roboticsと共同で、我々のモデルとアルゴリズムは、最先端のアプローチよりも、実用的な問題に対するより強力なソリューションを生み出していることを示す。
論文 参考訳（メタデータ） (2024-08-29T20:22:22Z) - 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 for the min-max Multiple Traveling Salesman
Problem [0.9790236766474201]
本稿では,Multiple Traveling Salesman Problem (mTSP) を解くためのハイブリッド遺伝的アルゴリズムを提案する。
新たなクロスオーバーオペレーターは、2人の親からの同様のツアーを組み合わせるように設計されており、人口に対して大きな多様性を提供する。
我々のアルゴリズムは、ベンチマークセットに対してテストした場合に、同様のカットオフ時間しきい値で、すべての既存のアルゴリズムを平均で上回ります。
論文 参考訳（メタデータ） (2023-07-14T01:57:10Z) - Hybrid Genetic Algorithm and Mixed Integer Linear Programming for Flying
Sidekick TSP [0.39373541926236766]
本研究では、Flying Sidekick TSP(FSTSP)と呼ばれる旅行セールスマン問題(TSP)の変動を最適化するためのハイブリッド遺伝的アルゴリズム(HGenFS)を提案する。
その結果, 厳密解の定式化が最大10顧客までの問題解決に適していることが確認された。
HGenFSは、特定値と局所探索フェーズを組み込むことで、FSTSPの最適解を数秒で見つけることができることを示した。
論文 参考訳（メタデータ） (2023-04-26T21:19:36Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Selection-Expansion: A Unifying Framework for Motion-Planning and
Diversity Search Algorithms [69.87173070473717]
本稿では,2つの多様性探索アルゴリズム,ノベルティ探索アルゴリズムとゴール探索処理アルゴリズムの特性について検討する。
mpアルゴリズムとの関係は、ポリシーパラメータ空間と結果空間の間のマッピングの滑らかさ、あるいは滑らかさの欠如が検索効率において重要な役割を担っていることを示している。
論文 参考訳（メタデータ） (2021-04-10T13:52:27Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。
エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。
これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
論文 参考訳（メタデータ） (2020-09-15T17:28:42Z) - Combining Geometric and Information-Theoretic Approaches for Multi-Robot
Exploration [16.010307336422148]
提案アルゴリズムの探索時間は,オフラインの最適探索アルゴリズムに対して($p$の関数として)競合的であることを示す。
このアルゴリズムは、単ボットポリゴン探索アルゴリズム、高次計画のための木探索アルゴリズム、低次計画のためのサブモジュラーオリエンテーアアルゴリズムに基づいている。
論文 参考訳（メタデータ） (2020-04-15T02:02:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。