Revenue-Maximizing Share-a-Ride Problem with Consideration of Recipients’ Roaming Locations

Impact Factor:8.4

DOI number:10.1016/j.trc.2026.106019

Teaching and Research Group:TURBO - 交通与城市运行实验室

Journal:Transportation Research Part C: Emerging Technologies

Abstract:This paper investigates a share-a-ride problem with parcels’ roaming delivery locations (SARP-PRDL), where a single vehicle fleet simultaneously serves passenger and parcel requests, and parcels can be delivered to one of multiple candidate destinations depending on recipients’ daily activities. Both static and dynamic request scheduling are studied within a unified modeling and solution framework. The static problem is formulated as a mixed-integer nonlinear program (MINLP) to maximize the platform’s total revenue and subsequently linearized into a mixed-integer linear program (MILP). To solve it efficiently, we design a matheuristic based on a branch-and-price (B&P) framework, incorporating a local search-inspired heuristic to enhance column generation in the pricing subproblem. For dynamic requests, we extend the approach by introducing a reoptimization strategy that supplements the existing greedy insertion algorithm, enabling continuous route improvement during operations. Extensive computational experiments demonstrate the effectiveness of the proposed methodology relative to off-the-shelf solvers and heuristic algorithms. Results indicate that considering roaming delivery locations of parcels in share-a-ride problem could improves both request fulfillment and revenue. For dynamic scheduling, the proposed reoptimization strategy achieves better revenue than the greedy insertion approach, particularly when the number of idle vehicles after static scheduling is limited; however, this advantage diminishes as idle vehicle availability increases.

Indexed by:Journal articles

Document Code:106019

Volume:194

Translation or Not:no

Date of Publication:2026-09-18

Included Journals:SCI

Links to published journals:https://www.sciencedirect.com/science/article/pii/S0968090X2600505X?dgcid=coauthor