論文の概要: 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インスタンスで新しい最適ソリューションを見つけました。
関連論文リスト
- 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) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-03-28T21:34:16Z) - Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。
この問題をある程度緩和する手法を提案する。
論文 参考訳(メタデータ) (2021-08-11T10:42:11Z) - Waypoint Planning Networks [66.72790309889432]
本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。
我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。
WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
論文 参考訳(メタデータ) (2021-05-01T18:02:01Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳(メタデータ) (2021-04-19T17:22:11Z) - 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) - Resource Allocation in Multi-armed Bandit Exploration: Overcoming
Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。
特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文 参考訳(メタデータ) (2020-10-31T18:19:29Z) - Combining Geometric and Information-Theoretic Approaches for Multi-Robot
Exploration [16.010307336422148]
提案アルゴリズムの探索時間は,オフラインの最適探索アルゴリズムに対して($p$の関数として)競合的であることを示す。
このアルゴリズムは、単ボットポリゴン探索アルゴリズム、高次計画のための木探索アルゴリズム、低次計画のためのサブモジュラーオリエンテーアアルゴリズムに基づいている。
論文 参考訳(メタデータ) (2020-04-15T02:02:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。