Time-Dependent Vehicle Routing Problem with Drones Under Vehicle Restricted Zones and No-Fly Zones - Shuo Wei; Houming Fan; Xiaoxue Ren; Xiaolong Diao (Applied Sciences)
This paper addresses the time-dependent vehicle routing problem with drones in vehicle-restricted zones and no-fly zones (TDVRPD-VRZ-NFZ). The optimization model considers the impacts of vehicle-restricted zones, no-fly zones, and time-dependent road networks on delivery paths. The objective is to minimize the total cost, including vehicle dispatch costs, energy consumption costs for vehicles and drones, and time-window penalty costs. The model is verified for correctness using Gurobi. In response to the problem’s characteristics, a hybrid genetic algorithm and variable neighborhood search with a learning mechanism (HGAVNS-LM) is proposed to solve the problem. The algorithm starts by generating the initial population using a combination of logistic mapping and reverse learning. It then improves the genetic operators and variable neighborhood search operators to optimize the initial population. To improve the algorithm’s performance, an individual elite archive is used for knowledge learning, and a self-learning mechanism is established to dynamically adjust the algorithm’s key parameters. The solution obtained by HGAVNS-LM shows a deviation of −0.2% to −0.3% compared to Gurobi, but it saves 99.68% in solving time. Compared to the genetic neighborhood search algorithm and the hybrid genetic algorithm, the improvement rates are 5.1% and 13.0%, respectively. Through the analysis of multiple sets of test cases, it is concluded that time-varying road networks, vehicle-restricted zones and no-fly zones, and different detour rules all affect delivery costs and delivery plans. The research results provide a more scientific theoretical basis for logistics companies to customize delivery solutions.