Exact and Heuristic Approaches to Drone Delivery Problems

• URL: http://arxiv.org/abs/2108.01996v1
• Date: Thu, 29 Jul 2021 21:31:50 GMT
• Title: Exact and Heuristic Approaches to Drone Delivery Problems
• Authors: J\'ulia C. Freitas, Puca Huachi V. Penna, T\'ulio A. M. Toffolo
• Abstract summary: The Flying Sidekick Traveling Salesman Problem (FSTSP) considers a delivery system composed by a truck and a drone. Each drone must return to the truck to recharge batteries, pick another package, and launch again to a new customer location. This work proposes a novel Mixed Programming (MIP) formulation and a approach to address the problem.
• Score: 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.

Related papers

• Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
  This paper supports robotic parts-to-picker operations in warehousing by optimizing order-workstation assignments, item-pod assignments and the schedule of order fulfillment at workstations. We solve it via large-scale neighborhood search, with a novel learn-then-optimize approach to subproblem generation. In collaboration with Amazon Robotics, we show that our model and algorithm generate much stronger solutions for practical problems than state-of-the-art approaches.
  arXiv  Detail & Related papers  (2024-08-29T20:22:22Z)
• Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks [10.18252143035175]
  We introduce the multi-agent flying sidekick traveling salesman problem (MA-FSTSP) on road networks. We propose a mixed-integer linear programming model and an efficient three-phase algorithm for this NP-hard problem. Our approach scales to more than 300 customers within a 5-minute time limit, showcasing its potential for large-scale, real-world logistics applications.
  arXiv  Detail & Related papers  (2024-08-20T20:44:18Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Solving the Team Orienteering Problem with Transformers [46.93254771681026]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. This paper presents a multi-agent route planning system capable of solving the Team Orienteering Problem in a very fast and accurate manner.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• A self-adaptive genetic algorithm for the flying sidekick travelling salesman problem [0.0]
  This paper presents a novel approach to solving the Flying Sidekick Travelling Salesman Problem (FSTSP) using a self-adaptive genetic algorithm. In FSTSP, optimisation is to minimise the total time to visit all locations while strategically deploying a drone to serve hard-to-reach customer locations.
  arXiv  Detail & Related papers  (2023-10-23T08:51:02Z)
• Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
  We propose textbftextitThought Propagation (TP) to enhance the complex reasoning ability of Large Language Models. TP first prompts LLMs to propose and solve a set of analogous problems that are related to the input one. TP reuses the results of analogous problems to directly yield a new solution or derive a knowledge-intensive plan for execution to amend the initial solution obtained from scratch.
  arXiv  Detail & Related papers  (2023-10-06T01:40:09Z)
• A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
  The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. We present a new binary encoding for the CVRP, with an objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. We discuss the effectiveness of the proposed encoding under the framework of the variant of the Quantum Alternating Operator Ansatz.
  arXiv  Detail & Related papers  (2023-08-17T05:14:43Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts. We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances. We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
  arXiv  Detail & Related papers  (2023-04-28T07:09:23Z)
• Hybrid Genetic Algorithm and Mixed Integer Linear Programming for Flying Sidekick TSP [0.39373541926236766]
  This work presents a hybrid Genetic Algorithm (HGenFS) for optimizing a variation of the Traveling Salesman Problem (TSP) called Flying Sidekick TSP (FSTSP) The results obtained confirmed that the adopted formulation for the exact solution is suitable for solving problems up to ten customers. The HGenFS proved to be capable of finding optimal solutions for the FSTSP in a few seconds by incorporating specifics and a local search phase.
  arXiv  Detail & Related papers  (2023-04-26T21:19:36Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• The two-echelon routing problem with truck and drones [0.0]
  We study novel variants of the well-known two-echelon vehicle routing problem in which a truck works on the first echelon to transport parcels and a fleet of drones to intermediate depots. The objective is to minimize the completion time instead of the transportation cost as in classical 2-echelon vehicle routing problems.
  arXiv  Detail & Related papers  (2020-04-05T18:33:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.