Vehicle Routing Problem with Drones Considering Time Windows and Dynamic Demand

Abstract

As a new delivery mode, the collaborative delivery of packages using trucks and drones has been proven to reduce delivery costs and delivery time. To cope with the huge cost challenges brought by strict time constraints and ever-changing customer orders in the actual delivery process, we established a two-stage optimization model based on different demand response strategies with the goal of minimizing delivery costs. To solve this problem, we designed a simulated annealing chimp optimization algorithm with a sine–cosine operator. The performance of this algorithm is improved by designing a variable-dimensional matrix encode to generate an initial solution, incorporating a sine–cosine operator and a simulated annealing mechanism to avoid falling into a local optimum. Numerical experiments verify the effectiveness of the proposed algorithm and strategy. Finally, we analyze the impact of dynamic degree on delivery cost. The proposed model and algorithm extend the theory of the vehicle routing problem with drones and also provide a feasible solution for route planning, taking into account dynamic demands and time windows.

Keywords

• truck–drone
• vehicle routing problem with drones
• package delivery
• time windows
• dynamic demand
• optimization algorithm