An exact algorithm for the airport shuttle service vehicle scheduling problem with flight schedule coordination

Abstract

Airport shuttle services are crucial for enhancing air-to-ground connections and improving airline customer satisfaction. However, operating a fleet of vehicles for timely and seamless shuttle services is challenging for airlines. This paper addresses an airport shuttle vehicle scheduling problem, providing cost-saving solutions for airlines. Airlines manage a limited fleet of heterogeneous vehicles that shuttle passengers between the airport and the city center, picking up or delivering passengers whenever and wherever. The decisions to be made include accepting, assigning, and sequencing shuttle service requests, considering passenger clustering, travel time tolerance, maximum waiting time, and flight schedule coordination. The objective is to minimize total operational costs, including vehicle hire costs, vehicle travel costs, and request outsourcing costs. We formulate the problem as a mixed-integer linear program (MILP) enhanced by valid inequalities and a trip number bounding method. We design a logic-based Benders decomposition (LBBD), in which the master problem (MP) generates a trip-chain for each vehicle and the subproblem verifies its timing feasibility. If the subproblem detects infeasibility, feasibility cuts are added to the MP to eliminate invalid trip-chains. Numerical results from a real-world case demonstrate the effectiveness of our model and algorithm. Additionally, results on random instances show that the exact method achieves optimal solutions for instances with up to 90 requests and around 270 passengers.