On solving a share-a-ride problem with forbidden passenger detours

Some of today’s most significant challenges in urban environments concern individual mobility and rapid parcel delivery. With the surge of e-commerce and the ever-increasing volume of goods to be handled, new logistics solutions are in high demand. The share-a-ride problem (SARP) was proposed as one such solution, combining the transportation of people and parcels in taxis. In this paper, we study a variation of SARP for ride-hailing systems that forbids passenger detours. We propose a branch-cut-and-price (BCP) method that incorporates several well-established techniques, including an efficient labeling algorithm for solving the pricing subproblem, two-phase strong branching, rank-1 cuts with limited memory, and n g -paths. High-quality primal bounds used to enhance the BCP performance are obtained in less than one minute by adapting and applying a state-of-the-art matheuristic to our problem to solve instances with up to 90 requests. The proposed BCP solves over 80% of the instances and improves the matheuristic’s results in 12% of the larger datasets. Moreover, we perform an instance space analysis, which concluded that the number of requests, the distribution of time windows in the time horizon, and the average route size were the features that influence instance difficulty the most. Finally, we obtain system service quality insights that quantify how much shorter time windows and longer origin–destination distances for requests make for easier instances to solve, and the trade-offs of providing fewer opportunities for parcel service and more overall deadheading.