Abstract: Considering the strict time requirements for air-passengers who have to get to airport punctually and the detour that brings inconvenience to them, the time they require is quantified to their satisfaction to a certain degree so as to develop a mathematical model involving the weights of both trip and detour time of shuttle buses with the single minimum objective. According to the characteristics of the problem to be solved and the model, a set-partition based heuristic algorithm is designed, in which a set of the sequences of efficient trips of shuttle buses are all routed, then a heuristic PNAC (per-node average-cost), algorithm is developed in combination with the scheduling optimization process to choose a group of route sections to visit all relevant passengers. Simulation results verified the effectiveness of the proposed model and algorithm.