VRPD-DT: Vehicle Routing Problem with Drones Under Dynamically Changing Traffic Conditions

• URL: http://arxiv.org/abs/2404.09065v1
• Date: Sat, 13 Apr 2024 19:28:24 GMT
• Title: VRPD-DT: Vehicle Routing Problem with Drones Under Dynamically Changing Traffic Conditions
• Authors: Navid Imran, Myounggyu Won,
• Abstract summary: 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.
• Score: 12.323383132739195
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The vehicle routing problem with drones (VRP-D) is to determine the optimal routes of trucks and drones such that the total operational cost is minimized in a scenario where the trucks work in tandem with the drones to deliver parcels to customers. While various heuristic algorithms have been developed to address the problem, existing solutions are built based on simplistic cost models, overlooking the temporal dynamics of the costs, which fluctuate depending on the dynamically changing traffic conditions. In this paper, we present a novel problem called the vehicle routing problem with drones under dynamically changing traffic conditions (VRPD-DT) to address the limitation of existing VRP-D solutions. 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 through incorporation of the travel time prediction model. A simulation study was performed to evaluate the performance compared with a state-of-the-art VRP-D heuristic solution. The results demonstrate that the proposed algorithm outperforms the state-of-the-art algorithm in various delivery scenarios.

Related papers

• Eco-Driving Control of Connected and Automated Vehicles using Neural Network based Rollout [0.0]
  Connected and autonomous vehicles have the potential to minimize energy consumption. Existing deterministic and methods created to solve the eco-driving problem generally suffer from high computational and memory requirements. This work proposes a hierarchical multi-horizon optimization framework implemented via a neural network.
  arXiv  Detail & Related papers  (2023-10-16T23:13:51Z)
• Integrating Higher-Order Dynamics and Roadway-Compliance into Constrained ILQR-based Trajectory Planning for Autonomous Vehicles [3.200238632208686]
  Trajectory planning aims to produce a globally optimal route for Autonomous Passenger Vehicles. Existing implementations utilizing the vehicle bicycle kinematic model may not guarantee controllable trajectories. We augment this model by higher-order terms, including the first and second-order derivatives of curvature and longitudinal jerk.
  arXiv  Detail & Related papers  (2023-09-25T22:30:18Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• Motion Planning and Control for Multi Vehicle Autonomous Racing at High Speeds [100.61456258283245]
  This paper presents a multi-layer motion planning and control architecture for autonomous racing. The proposed solution has been applied on a Dallara AV-21 racecar and tested at oval race tracks achieving lateral accelerations up to 25 $m/s2$.
  arXiv  Detail & Related papers  (2022-07-22T15:16:54Z)
• Dynamic Origin-Destination Matrix Estimation in Urban Traffic Networks [0.05735035463793007]
  We model the problem as a bi-level optimization problem. In the inner level, given a tentative travel demand, we solve a dynamic traffic assignment problem to decide the routing of the users between their origins and destinations. In the outer level, we adjust the number of trips and their origins and destinations, aiming at minimizing the discrepancy between the counters generated in the inner level and the given vehicle counts measured by sensors in the traffic network.
  arXiv  Detail & Related papers  (2022-01-31T21:33:46Z)
• Real-world Ride-hailing Vehicle Repositioning using Deep Reinforcement Learning [52.2663102239029]
  We present a new practical framework based on deep reinforcement learning and decision-time planning for real-world vehicle on idle-hailing platforms. Our approach learns ride-based state-value function using a batch training algorithm with deep value. We benchmark our algorithm with baselines in a ride-hailing simulation environment to demonstrate its superiority in improving income efficiency.
  arXiv  Detail & Related papers  (2021-03-08T05:34:05Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  We propose Deep Policy Dynamic Programming (D PDP) to combine the strengths of learned neurals with those of dynamic programming algorithms. D PDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP) and the vehicle routing problem (VRP) and show that the neural policy improves the performance of (restricted) DP algorithms.
  arXiv  Detail & Related papers  (2021-02-23T15:33:57Z)
• End-to-end Interpretable Neural Motion Planner [78.69295676456085]
  We propose a neural motion planner (NMP) for learning to drive autonomously in complex urban scenarios. We design a holistic model that takes as input raw LIDAR data and a HD map and produces interpretable intermediate representations. We demonstrate the effectiveness of our approach in real-world driving data captured in several cities in North America.
  arXiv  Detail & Related papers  (2021-01-17T14:16:12Z)
• An End-to-end Deep Reinforcement Learning Approach for the Long-term Short-term Planning on the Frenet Space [0.0]
  This paper presents a novel end-to-end continuous deep reinforcement learning approach towards autonomous cars' decision-making and motion planning. For the first time, we define both states and action spaces on the Frenet space to make the driving behavior less variant to the road curvatures. The algorithm generates continuoustemporal trajectories on the Frenet frame for the feedback controller to track.
  arXiv  Detail & Related papers  (2020-11-26T02:40:07Z)
• Congestion-aware Evacuation Routing using Augmented Reality Devices [96.68280427555808]
  We present a congestion-aware routing solution for indoor evacuation, which produces real-time individual-customized evacuation routes among multiple destinations. A population density map, obtained on-the-fly by aggregating locations of evacuees from user-end Augmented Reality (AR) devices, is used to model the congestion distribution inside a building.
  arXiv  Detail & Related papers  (2020-04-25T22:54:35Z)
• 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.