論文の概要: Exact and Heuristic Approaches to Drone Delivery Problems
- arxiv url: http://arxiv.org/abs/2108.01996v1
- Date: Thu, 29 Jul 2021 21:31:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-08 11:07:06.430734
- Title: Exact and Heuristic Approaches to Drone Delivery Problems
- Title（参考訳）: ドローン配送問題に対する厳密かつヒューリスティックなアプローチ
- Authors: J\'ulia C. Freitas, Puca Huachi V. Penna, T\'ulio A. M. Toffolo
- Abstract要約: FSTSP(Flying Sidekick Traveling Salesman Problem)は、トラックとドローンによる配送システムである。
それぞれのドローンはトラックに戻り、バッテリーを充電し、別の荷物を拾い、また新しい顧客場所に打ち上げなければならない。
この研究は、新しい混合プログラミング(MIP)の定式化と、この問題に対処するためのアプローチを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Flying Sidekick Traveling Salesman Problem (FSTSP) considers a delivery
system composed by a truck and a drone. The drone launches from the truck with
a single package to deliver to a customer. Each drone must return to the truck
to recharge batteries, pick up another package, and launch again to a new
customer location. This work proposes a novel Mixed Integer Programming (MIP)
formulation and a heuristic approach to address the problem. The proposedMIP
formulation yields better linear relaxation bounds than previously proposed
formulations for all instances, and was capable of optimally solving several
unsolved instances from the literature. A hybrid heuristic based on the General
Variable Neighborhood Search metaheuristic combining Tabu Search concepts is
employed to obtain high-quality solutions for large-size instances. The
efficiency of the algorithm was evaluated on 1415 benchmark instances from the
literature, and over 80% of the best known solutions were improved.
- Abstract（参考訳）: FSTSP(Flying Sidekick Traveling Salesman Problem)は、トラックとドローンによる配送システムである。
ドローンは1つのパッケージでトラックから打ち上げられ、顧客に届けられる。
それぞれのドローンはトラックに戻り、バッテリーを充電し、別の荷物を拾い、また新しい顧客場所に打ち上げなければならない。
本稿では,新しい混合整数型プログラミング(mip)の定式化と,この問題に対するヒューリスティックなアプローチを提案する。
提案するmip定式化は,前述したすべての例の定式化よりも線形緩和境界が向上し,文献から未解決例を最適に解くことができた。
タブサーチの概念を組み合わせた一般変数近傍探索メタヒューリスティックに基づくハイブリッドヒューリスティックを用いて,大規模インスタンスの高品質な解を求める。
アルゴリズムの効率は文献から1415のベンチマークインスタンスで評価され、最もよく知られたソリューションの80%以上が改善された。
関連論文リスト
- Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
本稿では,ワークステーションの注文処理,アイテムポッドの割り当て,ワークステーションでの注文処理のスケジュールを最適化することで,ウェアハウジングにおけるロボット部品対ピッカー操作を支援する。
そこで我々は, 大規模近傍探索を用いて, サブプロブレム生成に対する学習を最適化する手法を提案する。
Amazon Roboticsと共同で、我々のモデルとアルゴリズムは、最先端のアプローチよりも、実用的な問題に対するより強力なソリューションを生み出していることを示す。
論文 参考訳（メタデータ） (2024-08-29T20:22:22Z) - Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks [10.18252143035175]
道路ネットワーク上でのマルチエージェント飛行サイドキック走行セールスマン問題(MA-FSTSP)について紹介する。
このNPハード問題に対して,混合整数線形計画モデルと効率的な3相アルゴリズムを提案する。
当社のアプローチは5分間の時間制限内で300以上の顧客にスケールし、大規模な実世界のロジスティクスアプリケーションの可能性を示している。
論文 参考訳（メタデータ） (2024-08-20T20:44:18Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Solving the Team Orienteering Problem with Transformers [46.93254771681026]
車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。
本稿では,チームオリエンテーリング問題を高速かつ高精度に解決できる多エージェント経路計画システムを提案する。
論文 参考訳（メタデータ） (2023-11-30T16:10:35Z) - 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) - Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
大規模言語モデルの複雑な推論能力を高めるために,textbftextitThought Propagation (TP)を提案する。
TP はまず LLM に対して,入力問題に関連する類似問題の集合を提案し,解決するよう促す。
TPは、類似問題の結果を再利用して、新しいソリューションを直接生成したり、スクラッチから得られた初期ソリューションを修正するための知識集約的な実行プランを導出する。
論文 参考訳（メタデータ） (2023-10-06T01:40:09Z) - A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
CVRP(Capacitated Vehicle Routing Problem)は、輸送や物流など様々な分野で発生するNP最適化問題である。
本稿では,CVRPの車両容量制約を回避できる最短経路を最小化する目的機能を備えた,CVRP用の新しいバイナリエンコーディングを提案する。
本稿では,量子交換演算子Ansatzの変種に基づく符号化の有効性について論じる。
論文 参考訳（メタデータ） (2023-08-17T05:14:43Z) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。
提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。
本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文 参考訳（メタデータ） (2023-04-28T07:09:23Z) - 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) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - The two-echelon routing problem with truck and drones [0.0]
我々は、トラックが最初のエケロンでパーセルとドローンの群を中間補給所へ輸送する、よく知られた2エケロン車両ルーティング問題の新しい変種について研究する。
目的は、古典的な2エケロン車両の経路問題のように、輸送コストの代わりに完成時間を最小化することである。
論文 参考訳（メタデータ） (2020-04-05T18:33:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。