A Ride-Sharing Problem with Meeting Points and Return Restrictions
研究了封闭企业社区内通勤和商务出行的拼车问题，提出整数线性规划模型，包含返回限制、会合点和换乘选项，并用启发式算法求解，发现拼车可减少最多31.3%里程和28.7%车辆数。
Ride sharing has been widely acknowledged as an effective solution for reducing travel costs, congestion, and pollution. This paper considers the ride-sharing problem of the scheduled commuter and business traffic within a closed community of companies that agree to share the calendars of their employees. We propose a formulation in the form of a general integer linear program (ILP) for the aforementioned ride-sharing problem, which incorporates return restrictions to satisfy the business needs, as well as meeting points and the option for riders to transfer between drivers. All the instances with 40 and 60 participants and most of the instances with 80 participants can be solved to optimality within a time limit of two hours. Using instances of up to 100 participants, the ILP can be solved with a gap of no more than 1.8% within the time limit. Because of the high computational complexity, we develop a constructive heuristic that is based on the savings concept. This heuristic is also able to combine ride sharing with the use of an external mobility service provider. Our numerical study shows that ride sharing can be an effective way of reducing the number of trips and vehicle miles. Particularly, ride sharing creates more benefits when the participation is high and when the origins and the destinations of the trips are more spatially concentrated. The results show that ride sharing can create up to 31.3% mileage savings and up to 28.7% reduction in the number of cars needed to fulfill employees’ travel schedules. We also illustrate our model using a real-life ride-sharing problem of a Dutch consultancy and research firm. The online appendix is available at https://doi.org/10.1287/trsc.2018.0832 .