Integrated routing of drones and public transportation vehicles for simultaneous parcel pickup and delivery

The integration of drones with trucks or public transportation (PT) vehicles has become an increasingly popular strategy to extend the operational range of drone-based deliveries. Compared to truck-drone systems, PT-drone integration leverages existing public vehicles (e.g., buses) without the need for additional ground fleets, thereby reducing operational costs and environmental impact. However, existing studies on PT-drone integration have primarily focused on one-way parcel delivery tasks, whereas the simultaneous pickup and delivery (SPD) service remains underexplored. In this study, we develop a mixed integer linear programming (MILP) model that enables the effective synchronization of drone-based SPD service with fixed PT timetables and routes. Specifically, we first construct a time-expanded graph that encodes the spatial distribution of PT stations and the temporal scheduling of their associated trips across different lines. To capture the operational dynamics of drone-based SPD, we then formulate energy consumption as a function of flight time and payload, both of which evolve with routing decisions. Finally, the MILP model is solved to minimize both service time and system cost while ensuring compliance with operational constraints. We derive a set of valid inequalities to tighten the MILP formulation and enhance its overall computational efficiency. For large-scale instances, we also design a tailored Adaptive Large Neighborhood Search (ALNS) algorithm with problem-specific operators. Numerical experiments using real-world data from Nanjing, China, demonstrate the effectiveness of our proposed model in realizing the long-range SPD. The valid inequalities reduce the MILP solver time by 69.15 %, and the ALNS algorithm produces near-optimal solutions within reasonable time.