A Polyhedral Approach to Simplified Crew Scheduling and Vehicle Scheduling Problems
针对带多车场和工时限制的简化乘务与车辆调度问题，提出0-1线性规划模型，加入有效不等式并设计分支切割算法，在随机和实际算例上验证了性能。
Crew and vehicle scheduling are fundamental issues in public transit management. Informally, they can be described as the problem of determining the optimal duties for a set of crews (e.g., bus drivers) or vehicles (e.g., buses) so as to cover a given set of timetabled trips, satisfying a number of constraints laid down by the union contract and company regulations. We consider the simplified but still NP-hard case in which several depots are specified, and limits on both the total time between the start and the end of any duty (spread time) and the total duty operational time (working time) are imposed. We give a 0-1 linear programming formulation based on binary variables associated with trip transitions, which applies to both crew and vehicle scheduling. The model is enhanced by means of new families of valid inequalities, for which exact and heuristic separation procedures are proposed. These techniques are embedded into an exact branch-and-cut algorithm, which also incorporates heuristic procedures. The performance of two implementations of the method (for vehicle scheduling and crew scheduling, respectively) are evaluated through computational testing on both random and real-world test problems from the literature.