論文の概要: A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling
Salesman Problems with Drone
- arxiv url: http://arxiv.org/abs/2303.00614v1
- Date: Wed, 1 Mar 2023 16:11:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-02 14:11:54.255962
- 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.0
- 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 the use of a drone in conjunction with a truck for package
delivery. This study represents a hybrid genetic algorithm for solving TSPD and
FSTSP by combining local search methods and dynamic programming. Similar
algorithms exist in the literature. Our algorithm, however, considers more
sophisticated chromosomes and simpler dynamic programming to enable broader
exploration by the genetic algorithm and efficient exploitation through dynamic
programming and local searches. The key contribution of this paper is the
discovery of how decision-making processes 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 searches to each chromosome,
which is decoded by dynamic programming for fitness evaluation. Our dynamic
programming algorithm merges the two sequences by determining optimal launch
and landing locations for the drone to construct a TSPD solution represented by
the chromosome. We propose novel type-aware order crossover operations and
effective local search methods. A strategy to escape from local optima is
proposed. 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 93 FSTSP instances out of 132.
- Abstract（参考訳）: ドローンによるトラベルセールスマン問題 (TSPD) やFSTSP (Flying Sidekick Traveling Salesman Problem) と呼ばれる新たな輸送問題があり、荷物の配達にドローンを併用する。
本研究では,局所探索法と動的プログラミングを組み合わせることで,TSPDとFSTSPを解くハイブリッド遺伝的アルゴリズムを提案する。
同様のアルゴリズムは文献にも存在する。
しかし,我々のアルゴリズムはより洗練された染色体とより単純な動的プログラムを考慮し,遺伝的アルゴリズムによる広範な探索と動的プログラムと局所探索による効率的な利用を可能にする。
この論文の重要な貢献は、遺伝的アルゴリズム、動的プログラミング、局所探索の層にどのように意思決定プロセスが分割されるべきかの発見である。
特に,我々の遺伝的アルゴリズムは,トラックとドローンのシーケンスを別々に生成し,タイプ認識染色体にエンコードし,各顧客がトラックかドローンのいずれかに割り当てられる。
各染色体に局所検索を施し,動的プログラミングによって解読し,適合性評価を行う。
我々の動的プログラミングアルゴリズムは、ドローンの最適な発射位置と着陸位置を決定し、染色体で表されるTSPDソリューションを構築することによって、2つのシーケンスをマージする。
本稿では,新しい型認識オーダクロスオーバー操作と効率的な局所探索手法を提案する。
局所オプティマから逃れる戦略が提案されている。
我々の新しいアルゴリズムは、ほとんどのベンチマークインスタンスにおいて、品質と時間の両方で既存のアルゴリズムより優れていることを示す。
私たちのアルゴリズムでは、920インスタンスから538 tspdインスタンス、132インスタンスから93 fstspインスタンスで新しい最適ソリューションを見つけました。
関連論文リスト
- 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) - Searching for More Efficient Dynamic Programs [61.79535031840558]
本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。
実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
論文 参考訳（メタデータ） (2021-09-14T20:52:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。