On-Line Timetable Rescheduling in a Transit Line.

Public transportation systems in metropolitan areas carry a high density of daily traffic, heterogeneously distributed, and exposed to the negative consequences derived from service disruptions. Breakdowns, accidents, strikes, etc., require on-line operation adjustments to address these incidents and thus reduce their side effects, such as passenger extra-waiting times, complaints, potential operational dangers, etc. The Vehicle Rescheduling Problem consists of defining a new schedule for a set of previously scheduled trips, given that one/several trips cannot be carried out. This paper addresses the rescheduling problem in a transit line that has suffered a fleet size reduction (also denoted as Reduced Fleet Rescheduling Problem). We present different modeling possibilities depending on the assumptions that must be included in the modelization and we show that the problem can be rapidly solved using a reformulation that will be proven to have the integrality property. We test our results in a testbed of random instances outperforming previous results in the literature. We also include a real-world case of the commuter trains of Madrid, Spain to illustrate our solutions. [ABSTRACT FROM AUTHOR]