Bus and driver scheduling with mealtime windows for a single public bus route

Document Type

Journal Article

Publication Date

2019

Subject Area

mode - bus, ridership - drivers, operations - scheduling, infrastructure - fleet management, planning - methods

Keywords

Bus & driver scheduling, Mealtime windows, Integer linear programming, Valid inequality approach

Abstract

This study deals with the bus & driver scheduling problems with mealtime windows for a single public transport bus route. Firstly, we develop three explicit Integer Linear Programming (ILP) models to formulate: the bus driver scheduling, bus & driver scheduling, and bus & driver scheduling with mealtime windows, respectively. These ILP models enable bus operators to solve their bus & driver scheduling problems by directly invoking an available optimization solver such as IBM ILOG CPLEX. However, our numerical experiments do not show remarkable improvements, as CPLEX takes more than 12, 17, and 35 h respectively to reduce the optimality gap to at most 0.5% for solving the above three models in an over 12-hour bus & driver scheduling problem. To improve the computational efficiency, we develop a valid inequality approach that can generate valid cuts incorporating with the CPLEX. An investigation into the valid inequality approach proves its high computational efficiency. In addition, we develop a self-adaptive search method for determining the upper and lower bounds of driver group and bus fleet sizes. Finally, we test our models and approaches on a real round-trip bus route. The results indicate that compared with the only use of CPLEX to solve the above three models, the valid inequality approach can address large-scale instances in a reasonable CPU time.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part C Home Page:

http://www.sciencedirect.com/science/journal/0968090X

Link to Full Text

Share

COinS