An efficient two-stage matheuristic for scheduling airport electric shuttle buses with flight schedule coordination

Abstract

Airport shuttle services are crucial in addressing spatial challenges, improving accessibility, optimizing the overall travel experience, and promoting sustainable and efficient mobility solutions for passengers traveling to and from airports. However, operating a fleet of electric buses is challenging to provide timely and demand-responsive shuttle service. Therefore, this paper investigates a novel electric shuttle bus scheduling problem considering passenger flight schedule coordination and flexible charging. We first formally describe the problem and provide a mixed-integer linear program (MILP). The decisions to be made include: (1) the timetable of each shuttle bus; (2) the allocation of passengers to buses; (3) the charging time and duration of buses; and (4) whether to accept each group of passengers (request). The objective is to maximize the total profit, including the total revenue minus the bus travel costs. Given the NP-hardness of the problem, we then develop a two-stage heuristic method for solving practical-sized instances. The first stage aims to obtain good initial solutions using four constructive procedures and different rules. The second stage improves the generated initial solutions using a fix-and-optimize procedure matheuristic, which solves a series of the relax MILPs by fixing part of the integer variables. Numerical experiments on a case demonstrate the applicability of the proposed model and solution method. Results on random instances show that the proposed solution methods provide near-optimal solutions in a shorter computation time than the state-of-the-art solver CPLEX. In addition, case study findings show that the developed method can dramatically increase operational profit compared to the sequential heuristic methods.