Topic：The Dial-a-Ride Problem with Synchronized Visits
Time: 10:00 AM – 12:00 PM, Tuesday, April 1, 2025
Location: Room A1028, New Main Building
Guest: Dr. Zhaoboshuai, Université Paris-Saclay, France
Host: Prof. Tian Qiong
Abstract:
In drone delivery, a single drone can simultaneously carry several small-sized orders and complete multiple pickup and delivery tasks in one trip, or several drones can jointly pick up and deliver a large-sized order. A central drone delivery platform needs to manage both scenarios. Based on this background, we propose a Dial-a-Ride Problem with Synchronized Visits (DARP-SV), where a central platform must create a routing and scheduling plan using a fleet of drones to pick up and deliver a set of (indivisible) orders from their origins to destinations, with the objective of minimizing costs. These orders may vary in size, potentially exceeding or being below the capacity of a single drone. For this problem, we create a time-space fragment-based formulation by generalizing the fragment-based formulations from Alyasiry et al. (2019) and Rist & Forbes (2021) where a fragment represents a partial path. We also adapt the dynamic discretization discovery (DDD) algorithm from Boland et al. (2017) to fit our problem and fragment-based formulation. DDD is an iterative algorithm for the problem with a large-scale time-space network, where each iteration solves the problem on a partial network and dynamically adjusts the partial network based on the resulting solution until an optimal solution is obtained. The computational results show that the fragment-based formulation outperforms traditional arc-based formulations, and utilizing DDD can expedite the solution process for the fragment-based formulation.
