Ridesharing Problem with Flexible Pickup and Delivery Locations for App-Based Transportation Service: Mathematical Modeling and Decomposition Methods

App-based transportation service system, such as Uber and Didi, has brought a new transportation mode to users, who are able to make reservations using mobile apps conveniently. However, one of the fundamental challenges in app-based transportation system is the inefficiency and unreliability of the vehicle routing plans caused by complex topology of urban road network and unpredictable traffic conditions. A common way to tackle this problem is repositioning pickup or delivery locations via the coordination between drivers and passengers. This paper studies an on-demand ridesharing problem that determines the optimal ride-share matching strategy and vehicle routing plan with respect to flexible pickup and delivery locations. By introducing the concept of space-time windows, the problem is formulated as the pickup and delivery problem with space-time windows (PDPSW) in space-time network. To solve the model efficiently and accurately, we particularly develop a customized solution approach based on Lagrangian relaxation. Numerical examples are conducted to demonstrate the performance of the proposed framework and draw some managerial insights into the optimal system operation. The results indicate that adopting the serving strategy of flexible pickup and delivery locations will evidently reduce the system cost and improve the service quality in app-based transportation service systems.