The pickup and delivery problem with synchronized en-route transfers for microtransit planning

Microtransit and other flexible transit fleet services can reduce costs by incorporating transfers. However, transfers are costly to users if they have to get off a vehicle and wait at a stop for another pickup. A mixed integer linear programming model (MILP) is proposed to solve pickup and delivery problems with vehicle-synchronized en-route transfers (PDPSET). The transfer location is determined by the model and can be located at any candidate node in the network rather than a static facility defined in advance. The transfer operation is strictly synchronized between vehicles within a hard time window. A heuristic algorithm is proposed to solve the problem with an acceptable solution in a much shorter computation time than commercial software. Two sets of synthetic numerical experiments are tested: 20 instances based on a 5x5 grid network, and 42 different instances of varying network sizes up to 250x250 grids to test scalability. The results show that adding synchronized en-route transfers in microtransit can further reduce the total cost by 10% on average and maximum savings can reach up to 19.6% in our test instances. The heuristic on average has an optimality gap less than 1.5% while having a fraction of the run time and can scale up to 250x250 grids with run times within 5 minutes. Savings may be achievable by incorporating the en-route transfer strategy into dynamic routing settings.