A dynamic drone routing problem with uncertain demand and energy consumption

This work addresses a drone routing problem with an identical fleet performing same-day deliveries in a dynamic and uncertain environment. We model the problem as a Markov Decision Process to capture the stochastic nature of customer demand and the uncertainty in energy consumption due to varying payloads and weather conditions. To tackle this problem, we propose an approximate dynamic algorithm that integrates routing planning, drone usage, and battery management. Uncertainty in energy consumption is dealt with the chance constraints ensuring that drone trips are completed safely, preventing premature returns to the depot. The proposed approach features a cost function approximation policy that accounts for a restricted number of trips to be assigned to drones. This ensures that the drones are ready at the depot to fulfill new requests that may arise during the day. Extensive computational experiments on 300 instances validate the effectiveness of our method, demonstrating its superiority over a myopic strategy, a policy function approximation approach, and an oracle method, thus highlighting its potential for practical applications.