An Exact Method for a First-Mile Ridesharing Problem.

This article focuses on the first-mile ridesharing problem (FMRSP), a vehicle routing problem that generalizes the vehicle routing problem with time windows (VRPTW) by incorporating customer deadlines requiring each vehicle route to arrive at a destination before the earliest deadline among served customers. Motivated by airport pickup and delivery services in China, the study develops an exact solution method based on a branch-price-and-cut (BPC) algorithm featuring an innovative bidirectional labeling algorithm that efficiently handles deadline constraints. Extensive computational experiments on benchmark instances and real-world data from a major Chinese transportation company demonstrate that the proposed algorithm can optimally solve instances with up to 100 customers from the literature and up to 290 customers in practice. The study also analyzes the effectiveness of the bidirectional labeling and variable fixing techniques, showing significant computational improvements over forward-only labeling approaches.