The airport shuttle bus scheduling problem

This paper introduces the airport shuttle bus scheduling problem (ASBSP) as a new practical scheduling variant. In this problem, a number of identical vehicles that have a specific number of available seats provides transfer service between the airport and the city centre. After making a transfer in one direction, the vehicle can either make a new transfer in the opposite direction depending on the availability and the schedule of the passengers or make an empty return to make a new transfer in the same direction. The vehicles can wait in either location until their next transfer. The passengers have certain time windows for the transfer in relation to their flight times and operational rules to satisfy customer satisfaction. This is a profit-seeking service where transfer requests can also be rejected. The ASBSP aims to prepare a daily schedule for the available vehicles and to assign passengers to these vehicles with the objective of maximising the total profit. This paper presents two alternative mixed integer programming formulations and proposes two valid inequalities to get better bounds. Furthermore, it develops a hybrid metaheuristic that integrates multi-start, simulated annealing and large neighbourhood search for its solution. Extensive computational experiments on real-life benchmark instances have been made to test the performances of the formulations and the hybrid metaheuristic. Furthermore, the impacts of several problem parameters including the number of vehicles, vehicle capacity, transfer fee, transportation time and allowable passenger waiting times on the problem complexity and results have been investigated.