Comparison Training for a Rescheduling Problem in Neural Networks

Didier Keymeulen, Martine de GerlacheNeurIPS 1993

Introduction

Airline scheduling is a massive optimization puzzle, but rescheduling in the face of unexpected disruptions is often significantly harder. When a pilot calls in sick or a flight is delayed, the "Crew Pool Rescheduler" (CPR) team must find a replacement immediately. Standard operations research tools often fail in these scenarios due to two primary constraints:

  1. Speed: Generating a completely new schedule can take days, whereas rescheduling needs to happen in minutes.
  2. Stability: A mathematical "optimum" might completely change every pilot's schedule to achieve maximum efficiency, which is a nightmare for staff morale and operational continuity.

Human experts (the CPR team) usually pick the "best" substitute based on implicit rules regarding "stability" (minimizing disruption) and "equity" (fair work distribution). This paper explores applying a "comparison training" neural network architecture—originally designed for games like Backgammon—to automate this complex "best choice problem" by learning directly from the experts' historical decisions.

Methodology: The Dual Neural Network

To capture the implicit knowledge of human schedulers, the authors utilize a Dual Neural Network architecture, a structure similar to what is widely known today as a Siamese Network.

Dual Neural Network Architecture

Instead of training a network to output an absolute score (e.g., "This pilot is a 0.8/1.0 match"), the system uses a comparison paradigm. The network learns to compare two profiles and decide which one is better suited for the replacement task.

The architecture consists of two identical multi-layer networks that share the same weights. During training, two pilot profiles—the "Best" one chosen by an expert and a "Less Good" alternative—are fed into the two branches. The output node calculates the difference between the two branches. If the "Best" profile is on the left, the target output is 0; if they are swapped, the target is 1.

To speed up training, the authors implemented a convergence acceleration technique. By manually increasing a weight factor ($V$) between the sub-networks and the final output, they created an asymmetric impact on the gradient. This forces the network to focus more heavily on pairs it hasn't yet learned to classify correctly.

Data and Features

The study utilized real-world data from Sabena, the national Belgian Airline at the time. The researchers identified 15 relevant parameters to "codify" a pilot's profile. These features included previous and future occupations, human relationship factors, and the specific context of the perturbed schedule.

Training data was gathered by observing the CPR team at work over a 15-day period. From these observations, the authors extracted training and test sets consisting of perturbed schedules and the actual solutions chosen by the human experts.

Key Insights: Scoring vs. Comparing

A core argument of the paper is that a "scoring function" is unnecessary and difficult to define for this problem. Human experts don't naturally assign numerical scores to pilots; they simply evaluate candidates and pick the best one. Therefore, a "comparing function" is a much more natural fit for modeling human decision-making.

Geometrical Interpretation of Scoring vs. Comparing

The paper provides a compelling geometrical interpretation of this difference. As illustrated above, a scoring function (left) tries to find a hyperplane tangent to "circles" of exact scores, which is a highly constrained and difficult optimization landscape. In contrast, a comparing function (right) only needs to ensure that the "best" vector's end-point is closer to the hyperplane than any other candidate's vector. This relaxed constraint makes the learning process significantly more robust.

Furthermore, the model explicitly prioritizes "schedule stability"—the principle that a small change shouldn't ripple through the entire system. This is a critical operational constraint that is often ignored by purely mathematical optimization models but is naturally captured by learning from expert comparisons.

Results and Limitations

The network successfully learned the expert preferences for all training schedules, with the error function dropping significantly as training progressed. The introduction of the increasing weight factor $V$ proved highly effective, resulting in a much sharper convergence curve compared to a standard dual network. After training, the network demonstrated the ability to generalize, successfully retrieving the "best" profile for new, unseen perturbed schedules that were similar to the training set.

However, the authors noted several limitations. The network fails to converge if the training data contains contradictory expert decisions (e.g., an expert picks Pilot A in one scenario but Pilot B in an identical one). Resolving these ambiguities would likely require adding more "context parameters" to the input features. Additionally, while the model showed generalization capacity, the specific "degree of similarity" required for the network to perform well on new schedules remains an open question. Finally, the dataset was limited to just 15 days of observation; scaling this approach to a production-ready system would require a significantly larger and more diverse dataset.

Summary updated

BibTeX
@inproceedings{keymeulen1993comparison,
  author = {Didier Keymeulen and Martine de Gerlache},
  title = {{Comparison Training for a Rescheduling Problem in Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1993},
}
Figure