Ground-vehicle and unmanned-aerial-vehicle routing problems from two-echelon scheme perspective: A review
Hongqi Li, Jun Chen, Feilong Wang, Ming Bai
Abstract
More and more studies have aimed to optimize the ground vehicle (GV) and unmanned aerial vehicle (UAV) system in which GVs function as mobile satellites and UAVs are dispatched from GVs for last-mile deliveries. From the two-echelon scheme perspective, GV routes originating at the depot are on one echelon, and UAV routes originating at satellites are on the other echelon. A change in a GV route may affect some UAV routes, which indicates the satellite synchronization. In the past decade, the optimization of vehicle routes in two-echelon networks has attracted increasing attention in the operations research community. We classify routing problems of two-echelon networks based on the modeling mechanism connecting the two echelons. Different formulations for describing connection mechanisms of the two-echelon scheme, especially constraints on capacitated satellites, satellite synchronization, vehicle coupling/decoupling at satellites, etc., are briefly introduced. There are several modeling challenges of optimizing delivery routes for a fleet of GV–UAV combinations that include new connection mechanisms between the two echelons. Some important variants, especially those involving mobile satellite synchronization, and GV–UAV flexibly coupling/decoupling, require new mathematical formulations and algorithms catering to more general and practical situations.