司机调度问题

司机调度问题（DSP）是运筹学和理论计算机科学中的一类问题。司机调度问题包括在各种立法和物流标准的约束下，为参与乘客或货物运输的车辆的司机或驾驶员选择一套职责（分配）。

这个非常复杂的问题涉及到与劳工和公司规则有关的若干约束，以及不同的评价标准和目标。能够有效地解决这个问题，对公共交通公司的成本和服务质量有很大影响。一个可行的职责可能需要满足大量的不同规则。

最小和xxx的休息时间最小和xxx的工作时间最小和xxx的总时间xxx的额外工作时间xxx的车辆更换次数特定车辆的最小驾驶时间运营研究已经提供了优化模型和算法，导致这个问题的有效解决。为解决DSP而提出的最常见的模型是集合覆盖和集合分割模型。

在SPP模型中，每个工件（任务）只被一个职责所覆盖。在SCP模型中，有可能有一个以上的职责覆盖一个给定的工件。在这两种模型中，需要覆盖的工件集被排列成行，而先前定义的可用于覆盖特定工件的可行职责集被排列成列。基于这两个模型中的任何一个，DSP的解决方案是选择可行的职责集，以保证有一个（SPP）或多个（SCP）职责覆盖每个工件，同时使最终计划的总成本最小。