A stochastic optimization model for transit network timetable design to mitigate the randomness of traveling time by adding slack time

• We consider and model a bus network timetabling problem with stochastic travel times.
• The mathematical properties of the proposed model are analyzed.
• A genetic algorithm with local search is designed to solve the problem.
• The obtained bus timetable is cost-saving in different scenarios.
• Adding slack time into timetable reduces the rate of transferring failure.

Transit network timetabling aims at determining the departure time of each trip of all lines in order to facilitate passengers transferring either to or from a bus. In this paper, we consider a bus timetabling problem with stochastic travel times (BTP-STT). Slack time is added into timetable to mitigate the randomness in bus travel times. We then develop a stochastic integer programming model for the BTP-STT to minimize the total waiting time cost for three types of passengers (i.e., transferring passengers, boarding passengers and through passengers). The mathematical properties of the model are characterized. Due to its computational complexity, a genetic algorithm with local search (GALS) is designed to solve our proposed model (OPM). The numerical results based on a small bus network show that the timetable obtained from OPM reduces the total waiting time cost by an average of 9.5%, when it is tested in different scenarios. OPM is relatively effective if the ratio of the number of through passengers to the number of transferring passengers is not larger than a threshold (e.g., 10 in our case). In addition, we test different scale instances randomly generated in a practical setting to further verify the effectiveness of OPM and GALS. We also find that adding slack time into timetable greatly benefits transferring passengers by reducing the rate of transferring failure.