Intelligent Large‑Scale Workforce Scheduling at Ctrip: Modeling, Heuristic Algorithms, and System Design

Background: Ctrip’s customer service department handles massive, highly variable call volumes, requiring an intelligent scheduling solution that meets service level targets while improving agent experience.

Application Effect: Traditional manual scheduling could not cope with diverse departmental constraints; the new intelligent system now generates quality rosters within ten minutes, satisfying a wide range of hard and soft constraints.

Problem Analysis: The scheduling task is an enormous integer programming problem with numerous hard and soft constraints, similar to the Nurse Rostering Problem (NRP). Constraints include shift coverage, conflict avoidance, work‑day limits, weekend rules, and employee preferences.

Modeling and Design: The problem is abstracted as a three‑dimensional space (agents, skill types, time slots). Initial naïve models lead to astronomically large search spaces, so the model is refined by grouping time slots into work intervals, dramatically reducing complexity.

Algorithm Flow: Benchmark tests of several heuristics—First Fit, Hill Climbing, Tabu Search, Late Acceptance, Great Deluge, Simulated Annealing—showed comparable results. The production pipeline uses First Fit for a quick initial solution, Tabu Search for rapid improvement, and LAHC/Simulated Annealing for final refinement.

Performance Optimization: Multithreaded evaluation of candidate moves provides a ten‑fold speedup. For especially large cases, distributed parallelism splits the problem across multiple machines, achieving acceptable runtimes while preserving solution quality.

Platform Architecture: A scheduling middle‑platform integrates data cleaning, validation, manual entry, model building, algorithm solving, roster generation, optional manual tuning, and downstream system integration, supporting many business units.

Conclusion and Recruitment: The platform has been adopted by numerous units, revealing further modeling challenges. The team invites candidates to join Ctrip’s hotel R&D group in AI, data analysis, or APS roles.