Customer satisfaction is crucial for the long term success of any travel service provider. Therefore, identifying situations that can lead to customer dissatisfaction is critical. The strongest evidence of customers dissatisfaction are their complaints. While complaints do not occur very often, they almost always lead to loss of customer goodwill which can cost travel providers millions of dollars in future revenues. In this paper, we describe an approach to proactively identify customers that have the highest propensity to complain as they encounter a travel disruption event. These are invaluable insights that can empower customer service teams with information to deliver a more timely, relevant and impactful service experience. We use three key aspects in this approach: (i) specialized feature engineering for the travel industry; (ii) handling extremely imbalanced data and (iii) adaptation of binary classification, anomaly detection and learning to rank models to our specific task. This research is an important step towards more individualized understanding of customer behavior, and potential service enhancements to further increase customer satisfaction.