A ridesharing routing problem for airport riders with electric vehicles

This paper proposes a ridesharing routing problem for airport riders motivated by a practical application. This problem designs routes for electric vehicles owned by an airport to provide pickup and delivery service for riders both departing from and traveling to the airport. To maintain a high quality of ridesharing service, it is assumed that drivers should ensure that all riders on board from the airport are completely delivered before they pick up new riders to the airport. The departure time from the airport and the return time to the airport of electric vehicles are affected by the flight schedules of riders. Additionally, due to the limited driving range of electric vehicles, the partial recharging at the airport is considered. The proposed ridesharing routing problem is formulated as a trip-based mixed integer linear programming model. An efficient method is proposed to enumerate all non-dominated feasible trips to form a trip-based graph for the model. A branch-and-price algorithm is developed to solve the proposed problem, in which a tailored labeling algorithm with feasibility checking process is designed to solve the pricing subproblem. The numerical experiments indicate that the trip-based model is more efficient compared with the rider-based model, and the proposed branch-and-price algorithm could solve large scale instances efficiently. The effects of acceptable extra time ratio, trip duration, capacity, and battery capacity on both airport and rider sides are discussed by sensitivity analysis.