The two-echelon routing problem with truck and drones

• URL: http://arxiv.org/abs/2004.02275v1
• Date: Sun, 5 Apr 2020 18:33:16 GMT
• Title: The two-echelon routing problem with truck and drones
• Authors: Minh Ho\`ang H\`a and Lam Vu and Duy Manh Vu
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, 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 while in the second echelon, the drones are used to deliver parcels from intermediate depots to customers. The objective is to minimize the completion time instead of the transportation cost as in classical 2-echelon vehicle routing problems. Depending on the context, a drone can be launched from the truck at an intermediate depot once (single trip drone) or several times (multiple trip drone). Mixed Integer Linear Programming (MILP) models are first proposed to formulate mathematically the problems and solve to optimality small-size instances. To handle larger instances, a metaheuristic based on the idea of Greedy Randomized Adaptive Search Procedure (GRASP) is introduced. Experimental results obtained on instances of different contexts are reported and analyzed.

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)
• VRPD-DT: Vehicle Routing Problem with Drones Under Dynamically Changing Traffic Conditions [12.323383132739195]
  We present a novel problem called the vehicle routing problem with drones under dynamically changing traffic conditions (VRPD-DT) We design a novel cost model that factors in the actual travel distance and projected travel time, computed using a machine learning-driven travel time prediction algorithm. A variable neighborhood descent (VND) algorithm is developed to find the optimal truck-drone routes under the dynamics of traffic conditions.
  arXiv  Detail & Related papers  (2024-04-13T19:28:24Z)
• 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)
• Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach [49.00137468773683]
  Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2023-10-26T15:42:29Z)
• POA: Passable Obstacles Aware Path-planning Algorithm for Navigation of a Two-wheeled Robot in Highly Cluttered Environments [53.41594627336511]
  Passable Obstacles Aware (POA) planner is a novel navigation method for two-wheeled robots in a cluttered environment. Our algorithm allows two-wheeled robots to find a path through passable obstacles.
  arXiv  Detail & Related papers  (2023-07-16T19:44:27Z)
• Decentralized Vehicle Coordination: The Berkeley DeepDrive Drone Dataset [103.35624417260541]
  Decentralized vehicle coordination is useful in understructured road environments. We collect the Berkeley DeepDrive Drone dataset to study implicit "social etiquette" observed by nearby drivers. The dataset is of primary interest for studying decentralized multiagent planning employed by human drivers and for computer vision in remote sensing settings.
  arXiv  Detail & Related papers  (2022-09-19T05:06:57Z)
• Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks [31.52357826598224]
  We address the problem of routing a team of drones and trucks over large-scale urban road networks. Drones can use trucks as temporary modes of transit en route to their own destinations. But it comes at the potentially prohibitive computational cost of deciding which trucks and drones should coordinate.
  arXiv  Detail & Related papers  (2021-10-17T12:00:30Z)
• Exact and Heuristic Approaches to Drone Delivery Problems [0.0]
  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.
  arXiv  Detail & Related papers  (2021-07-29T21:31:50Z)
• Dogfight: Detecting Drones from Drones Videos [58.158988162743825]
  This paper attempts to address the problem of drones detection from other flying drones variations. The erratic movement of the source and target drones, small size, arbitrary shape, large intensity, and occlusion make this problem quite challenging. To handle this, instead of using region-proposal based methods, we propose to use a two-stage segmentation-based approach.
  arXiv  Detail & Related papers  (2021-03-31T17:43:31Z)
• Three Dimensional Route Planning for Multiple Unmanned Aerial Vehicles using Salp Swarm Algorithm [0.0]
  Route planning is a series of translation and rotational steps from a given start location to the destination goal location. The proposed approach improves the average cost and overall time by 1.25% and 6.035% respectively.
  arXiv  Detail & Related papers  (2019-11-24T12:36:18Z)

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.